In traditional programming, a human writes explicit rules. The computer applies those rules to data and produces output:

$$\text{Data}+\text{Rules}⟶\text{Computer}⟶\text{Output}$$

If the rules are imprecise, the output is wrong. The sandwich example illustrates this: the rule "put the pieces together" did not specify that peanut butter and jelly must face inward. The result was a messy sandwich.

In machine learning, the roles are reversed. The human provides data and the desired output. The computer's job is to learn the rules:

$$\text{Data}+\text{Desired Output}⟶\text{Computer}⟶\text{Program (learned rules)}$$

This is sometimes called reverse engineering. Instead of writing the program, you give the computer examples of correct behavior and let it discover the program.

Two random variables $X$ and $Y$ are independent if knowing the value of $X$ tells you nothing about the value of $Y$. Formally:

$$P(X=x\mid Y=y)=P(X=x)\text{for all }x,y$$

Equivalently, the joint probability factorizes:

$$P(X=x,Y=y)=P(X=x)\cdot P(Y=y)$$

What this means in plain language: the outcome of one data point has no effect on the outcome of any other data point. They carry no information about each other.

A set of random variables $\{X_1,X_2,\dots ,X_n\}$ is identically distributed if each $X_i$ is drawn from the same underlying probability distribution. That is, for any value $x$:

$$P(X_1\le x)=P(X_2\le x)=\cdots =P(X_n\le x)=F(x)$$

where $F(x)$ is the cumulative distribution function (CDF). All data points share the same mean $\mu$, the same variance ${\sigma }^2$, and the same distributional shape (e.g., all are Gaussian).

The IID assumption underpins nearly every foundational ML algorithm covered in this course. When we write a training set as $\{(x_1,y_1),(x_2,y_2),\dots ,(x_n,y_n)\}$, the IID assumption says:

1. Independence: The pair $(x_i,y_i)$ is independent of $(x_j,y_j)$ for all $i\ne j$.
2. Identical distribution: Every $(x_i,y_i)$ is drawn from the same joint distribution $P(X,Y)$.

This assumption lets us write the likelihood of the entire dataset as a product:

$$P(\text{data}\mid \text{model})=\prod _{i=1}^{n}P(x_i,y_i\mid \text{model})$$

Without independence, this factorization fails. Without identical distribution, a single model cannot capture all data points. This course focuses on IID data because the core algorithms — linear regression, logistic regression, Naïve Bayes, SVM, decision trees — all rely on this assumption.

Mitchell's definition (1997): A computer program is said to learn from experience $E$ with respect to some class of tasks $T$ and performance measure $P$, if its performance at tasks in $T$, as measured by $P$, improves with experience $E$.

The three components:

• Task $T$: What exactly is the job? Classify emails? Predict a price? Recognize handwriting?
• Performance $P$: How will success be measured? Almost always a number — accuracy, mean squared error, average distance before failure.
• Experience $E$: What data can the system learn from? Labeled examples? Unlabeled sensor readings? Games played against itself?

An entity is a single real-world object (e.g., one specific student). An entity set is the collection of all entities under study (e.g., all students in the batch).

Features (synonyms: attributes, predictors, characteristics, dimensions, independent variables) are the properties used to describe each entity. Formally, each entity is represented as a vector:

$${\mathbf{x}}^{(i)}={\left[\begin{array}{c}{x}_1^{(i)}{x}_2^{(i)}\cdots x_d^{(i)}\end{array}\right]}^{\top }\in {\mathbb{R}}^d$$

where:

• $i$ indexes the entity (row number in the dataset)
• $d$ is the number of features (the dimensionality)
• $x_j^{(i)}$ is the value of the $j$-th feature for the $i$-th entity

High-dimensional data is a dataset where $d$ (the number of features) is large — typically $d\ge 100$. Describing a person with 100 characteristics is practically impossible for a human, but a computer handles it routinely. The challenge is that as $d$ grows:

1. The curse of dimensionality: data points become sparse in the feature space. The volume of the space grows exponentially with $d$, meaning exponentially more data is needed to maintain the same density of coverage.
2. Computational cost: many algorithms scale as $O(d^2)$ or worse.
3. Interpretability: a model with 100 features is hard for a human to understand.

Machine learning algorithms are categorized by the level of supervision — the nature and timing of the feedback provided during training:

$$\begin{array}{rl}\text{Supervised}& :\text{Every example has a label. Feedback is direct and immediate.}\\ \text{Unsupervised}& :\text{No labels at all. The algorithm must find hidden structure.}\\ \text{Semi-supervised}& :\text{A few labels + many unlabeled examples.}\\ \text{Reinforcement}& :\text{Delayed reward/penalty. The agent learns through interaction.}\end{array}$$

In supervised learning, the training data consists of input-output pairs:

$$\mathcal{D}=\{({\mathbf{x}}^{(1)},y^{(1)}),({\mathbf{x}}^{(2)},y^{(2)}),\dots ,({\mathbf{x}}^{(n)},y^{(n)})\}$$

where ${\mathbf{x}}^{(i)}$ is the feature vector and $y^{(i)}$ is the label (the correct answer, provided by a human). The algorithm learns a function $f$ such that:

$$f({\mathbf{x}}^{(i)})\approx y^{(i)}\text{for all }i$$

The key word is labeled — every training example has been annotated with the ground truth.

Classification is supervised learning where the target label $y$ is a category (discrete, finite set of classes). Formally:

$$y^{(i)}\in \{C_1,C_2,\dots ,C_K\}$$

where $K$ is the number of classes. The model learns a decision rule $f:{\mathbb{R}}^d\to \{C_1,\dots ,C_K\}$.

Examples: spam/ham (K=2), iris species (K=3), digit recognition (K=10), benign/malignant tumor (K=2).

Regression is supervised learning where the target label $y$ is a continuous, real-valued number. Formally:

$$y^{(i)}\in \mathbb{R}$$

The model learns a function $f:{\mathbb{R}}^d\to \mathbb{R}$ that predicts a quantity — not a category.

Examples: predicting house price, used car price, stock price, temperature tomorrow, patient's blood pressure.

In unsupervised learning, the training data has no labels:

$$\mathcal{D}=\{{\mathbf{x}}^{(1)},{\mathbf{x}}^{(2)},\dots ,{\mathbf{x}}^{(n)}\}$$

The algorithm receives only the input vectors. Its job: find hidden structure — groups, patterns, associations — without being told what to look for.

Association analysis finds strong co-occurrence patterns among items in transaction data — without any pre-labeled output. A classic rule:

$$\text{bread}⟶\text{beer}(\text{support: }60\%,\text{ confidence: }90\%)$$

Support: 60% of all transactions contain both bread and beer. Confidence: 90% of transactions that contain bread also contain beer.

Semi-supervised learning combines a small labeled dataset ${\mathcal{D}}_L$ with a large unlabeled dataset ${\mathcal{D}}_U$:

$$\mathcal{D}={\mathcal{D}}_L\cup {\mathcal{D}}_U,|{\mathcal{D}}_L|\ll |{\mathcal{D}}_U|$$

The algorithm uses the structure in ${\mathcal{D}}_U$ to improve learning from the sparse labels in ${\mathcal{D}}_L$.

Reinforcement learning (RL) is fundamentally different from supervised and unsupervised learning. There are no labels — only a delayed reward signal from the environment.

Formal components:

• Agent: The learner / decision-maker.
• Environment: The world the agent operates in.
• State $s_t$: The situation at time $t$.
• Action $a_t$: What the agent does at time $t$.
• Reward $r_t$: Scalar feedback from the environment after taking action $a_t$ in state $s_t$.
• Policy $\pi$: A mapping from states to actions — $\pi (s)=a$. This is what the agent learns.

The agent's goal: maximize the cumulative reward over time:

$$G_t=r_t+\gamma r_{t+1}+{\gamma }^2{r}_{t+2}+\cdots =\sum _{k=0}^{\infty }{\gamma }^k{r}_{t+k}$$

where $\gamma \in [0,1]$ is the discount factor — rewards now are worth more than rewards later.

Case 1 — Human expertise does not exist. The problem is in an environment with no human expert. The system must learn rules on its own by interacting with the environment. Mars rover navigation: No programmer can write code for every rock, slope, or sandy patch a rover might encounter on Mars. The rover uses onboard cameras and laser range-finders to build a terrain model and learn what is safe to traverse. PTE breakdown: $T$ = identify safe terrain, $E$ = camera + laser data, $P$ = distance traveled before getting stuck. Large Hadron Collider (LHC): Petabytes of particle collision data. No human can look at raw sensor readings and identify a Higgs boson event. An ML model hunts for tiny statistical anomalies — deviations of a few parts per billion — that signal interesting physics.

Case 2 — Humans can perform the task but cannot explain how. These are tasks we find remarkably easy but cannot articulate as rules. Voice recognition: You instantly recognize your friend's voice, even when they say the same word as a stranger. But you cannot explain what "warmth" in a voice means in programmable terms. "The voice has a kind of resonant quality" is not a rule a computer can execute. ML bypasses this: feed it audio samples labeled with speaker identity, and it learns the acoustic signature without needing a human-readable rule. Face description: You describe a person as having "kind of pointy nose, curly hair, about 5 feet tall." "Kind of pointy" is not a computable feature. ML learns directly from labeled images — no verbal description needed.

Case 3 — Models must be customized to individuals. No single static rule works for everyone. The correct behavior differs per user or changes constantly. Personalized medicine: A standard drug dose works for ~70% of people, is toxic for ~10%, and has no effect on ~20%. An ML model trained on an individual's genomic data, blood markers, and lifestyle can predict their personal disease risk. It can also recommend an optimal dosage. No one-size-fits-all formula exists — the model must learn from the individual's own data.

Dimensionality reduction is the process of reducing the number of features $d$ while preserving as much information (variance) as possible. You never simply delete features — you consolidate their information into fewer dimensions. Principal Component Analysis (PCA) does this by finding new axes (principal components) that are linear combinations of the original features. They are ranked by how much variance they capture:

$${\mathbf{z}}^{(i)}={\mathbf{W}}^{\top }{\mathbf{x}}^{(i)}$$

where $\mathbf{W}\in {\mathbb{R}}^{d\times k}$ ($k<d$) is a matrix whose columns are the top $k$ eigenvectors of the data covariance matrix. The transformed vector ${\mathbf{z}}^{(i)}\in {\mathbb{R}}^k$ lives in a lower-dimensional space but retains the bulk of the original data's variance.