How a machine learning problem is set up

By the end of this page you can take any vague request — "predict whether this patient is ill" — and write it down as $\X$, $\Y$, $\D$, $\ell$, $\H$, and an $\argmin$, which is the only form a computer can actually solve.

Why we stopped writing rules

For decades "AI" mostly meant rule-based AI: an expert and a programmer writing out the conditions for each conclusion explicitly — IF pressure > 90 AND valve_state = open THEN raise alarm — thousands of rules in a hand-maintained if/else forest. The notes' example, AT&T diagnosing telephone-line faults from logs, is a domain where that is the right tool, and the three reasons why are exactly the reasons it collapses elsewhere: the input is already symbolic (named events, not raw physics), the experts can say their rules out loud, and the rule count is finite and stable.

The pixel-space argument

Now change one thing: the input is a photograph and the question is "is there a cat in this picture?" The notes put it in one line — how do you describe a picture in pixel space? — and that line is why machine learning exists.

A modest $1000 \times 1000$ colour photo is $1000 \times 1000 \times 3 = 3{,}000{,}000$ numbers, each in $\{0,\dots,255\}$. There is no field called has_cat; there is pixel[417][233].red = 118, and your rule has to be written in those terms. Try it — "if pixel $(417,233)$ is brownish and…" — and it falls apart immediately:

• Translation, scale, pose, illumination. Move the cat 40 pixels left and every coordinate in your rule is wrong; a cat close up, far away, curled up or seen from behind share almost no pixel-level structure; the same cat at sunset has completely different RGB values.
• Occlusion and clutter. Half the cat is behind a chair, and there is a cat-shaped cushion.
• The combinatorics are absurd. There are $256^{3{,}000{,}000}$ possible images to hand-partition into "cat" and "not cat" with conditions on individual coordinates.

The setup: inputs, outputs, and the function in between

The formal skeleton. Everything in Part II hangs on it.

Every symbol, in words:

• $\X$ — everything you might be shown. For images $\X = \{0,\dots,255\}^{3{,}000{,}000}$; for house prices $\X = \R^3$ (size, bedrooms, age); for five yes/no questions $\X = \{0,1\}^5$.
• $\Y$ — every answer you might give. $\Y = \{\text{cat}, \text{not cat}\}$, or $\R$ for a price, or $\{0,1\}$ for ill / healthy.
• $h$ — the function itself, under three interchangeable names: the hypothesis (the statistics word), the model (the engineering word) and the prediction function (what it does). Same object.

Note what $h$ is not: a lookup table of answers you already have. $h$ must be defined on all of $\X$, including inputs nobody has ever seen — the requirement that makes the problem hard, and whose name is generalization.

Training data

A dataset is a table: one row per sample, one column per feature, plus a label column. One we will reuse — five houses, $d = 3$ features, $N = 5$:

In the notation: $N = 5$, $d = 3$, $\X = \R^3$, $\Y = \R$. The third row is $\big(x^{(3)}, y^{(3)}\big)$ with $x^{(3)} = (900, 2, 40)$, $y^{(3)} = 150$, and $x^{(3)}_3 = 40$ — sample 3, feature 3, the age.

Training versus inference

Keeping these apart is the discipline of the whole subject: training consumes labels, inference does not have them. Anything that touches $y^{(\text{new})}$ at inference time is cheating, and most embarrassing ML bugs are a version of that cheating (leakage).

Two kinds of task: classification and regression

The notes split ML tasks in two, entirely by looking at $\Y$ — not at $\X$, not at the algorithm.

Both adjectives do real work. Finite vs continuous decides whether "close" is a coherent idea: between two house prices there is another house price, between "cat" and "dog" there is nothing. Unordered vs ordered decides whether being wrong can be wrong by an amount: predicting 420 when the truth is 410 is a small error, while predicting "dog" for a cat is not 10% wrong, just wrong.

A genuinely ambiguous case

Predict the star rating (1–5) a user will give a restaurant.

$\Y = \{1,2,3,4,5\}$ is finite (classification) but also ordered — predicting 4 when the truth is 5 is a better mistake than predicting 1 (regression). The notes' definitions genuinely disagree here; this is a third category, ordinal regression beyond syllabus, not covered. Decide by asking what the loss function should be, since that is what the choice actually controls:

• If mistaking 5 stars for 1 star should hurt 16× more than mistaking 5 for 4, you want $(\hat{y}-y)^2$. Treat it as regression, predict a real number, and round at the end if you must output an integer.
• If your product only cares "did we get the exact star count right", you want $\1\{\hat y \neq y\}$. Treat it as 5-way classification.

Loss functions: writing down what "wrong" costs

Q2 was: how do we measure performance? The answer is a loss function.

Read the type signature literally: $\Y \times \Y$ is "a pair of labels" and $\to \R$ is "out comes one real number" — not a vector, not a verdict. Everything messy about "is this model any good?" has to be crushed into a scalar, because optimisation algorithms can only minimise scalars.

Classification loss: zero-one

For classification the only question is "right or wrong?", so:

where $\1\{\cdot\}$ is the indicator function:

So the loss is $1$ when prediction and truth differ and $0$ when they match. The indicator is just a way of writing "if" inside an algebraic expression so it can be summed — it returns in majority vote and entropy.

Asymmetric classification loss

Zero-one loss says every mistake costs the same; in medicine that is plainly false. With $y = 1$ meaning ill and $y = 0$ meaning healthy, the two failure modes are a false positive (prediction ill, truth healthy: $\hat y = 1$, $y = 0$ — an unnecessary biopsy) and a false negative (prediction healthy, truth ill: $\hat y = 0$, $y = 1$ — the patient goes home and the tumour keeps growing). These are not equally bad, so they do not get equal loss. The notes' table, reproduced exactly — convention: rows are the truth $y$, columns the guess $\hat y$, i.e. $\ell(y, \hat y)$:

The four cells: $\ell(0,0) = 0$ and $\ell(1,1) = 0$ — correct answers are free; $\ell(y=0, \hat y=1) = 2$ — healthy called ill, a false positive; $\ell(y=1, \hat y=0) = 10$ — ill called healthy, a false negative. The diagonal is zero and the off-diagonal is asymmetric: a false negative is five times worse than a false positive.

Quantitatively: under this loss you should predict "ill" whenever the expected cost of saying healthy exceeds the expected cost of saying ill. If $p$ is the probability the patient is ill, saying healthy costs $10p$ and saying ill costs $2(1-p)$. Predict ill when $10p \gt 2(1-p)$, i.e. $12p \gt 2$, i.e. $p \gt 1/6 \approx 0.167$. Under plain zero-one loss the same computation gives the threshold $p \gt 1/2$. The asymmetric loss has moved the operating threshold from 50% down to 17% — the model refers anyone with better than a one-in-six chance of illness.

Regression loss: squared error

For regression the magnitude of the miss matters, so the standard choice is the squared error:

The quantity $r = \hat y - y$ is the residual: how far off you were and in which direction. Squaring discards the direction (10 over is as bad as 10 under) and keeps the magnitude. Why square rather than take $|\hat y - y|$, which also discards the sign? Four reasons, three of them good:

1. Differentiability. $\frac{d}{d\hat y}(\hat y - y)^2 = 2(\hat y - y)$ — defined everywhere and proportional to the error: big miss, big push. The absolute value has a kink at $0$ where the derivative jumps from $-1$ to $+1$ and is undefined exactly at the optimum, and every method in Chapter 9 follows derivatives.
2. It penalises large errors disproportionately. Doubling the error quadruples the loss: being off by 10 costs 100, while ten errors of 1 cost 10 in total. So it prefers "wrong by a little, everywhere" to "right everywhere but catastrophic once".
3. It connects to the mean. This is the mathematically deep reason. Suppose you must predict a single constant $c$ for all of $y^{(1)},\dots,y^{(N)}$. Minimising $\sum_i (c - y^{(i)})^2$: differentiate and set to zero, $$ \frac{d}{dc}\sum_{i=1}^N (c - y^{(i)})^2 = 2\sum_{i=1}^N (c - y^{(i)}) = 0 \;\Longrightarrow\; Nc = \sum_i y^{(i)} \;\Longrightarrow\; c = \frac{1}{N}\sum_i y^{(i)} = \bar y. $$ The minimiser of squared error is the mean. (Minimising absolute error instead gives the median.) Every closed-form result in linear regression — including the normal equation — exists because squared error is a quadratic whose derivative is linear, so setting it to zero gives a linear system you can solve exactly. Choose any other loss and you generally lose the closed form.
4. The honest fourth reason: it is what everyone else does, which makes results comparable.

Generalization, test error, and the i.i.d. assumption

You have a loss, so you can score $h$ on any labelled point. But which points? Not the training points — you already know their labels, so predicting them earns nothing. The notes are explicit: you care about performance on a new, previously unseen datapoint $x^{(\text{new})}$ ("test data"), and applying $h$ to it is inference. Given its true label $y^{(\text{new})}$, unknown to you, you want

to be small. This quantity is called the generalization error or test error. Generalization = performance on unseen data.

The difficulty: if $x^{(\text{new})}$ could be anything, generalization would be hopeless — nothing in a dataset of cats and dogs tells you what to do with a recording of a cello. We need an assumption tying the future to the past:

The acronym spelled out, one letter at a time:

• independent — knowing one sample tells you nothing about the next: sampling with replacement from an urn, not dealing a hand of cards.
• identically — every sample comes from the same $P$; the urn is not refilled with different marbles halfway through.
• distributed — such a $P$ exists, over pairs $(x,y)$ jointly, not over $x$ alone: it describes which inputs show up and what labels they carry, including label noise (two identical-looking patients can have different outcomes).

When i.i.d. fails: distribution shift

Hospitals that deployed sepsis-prediction models trained on pre-COVID records found them degrading sharply and silently once COVID changed demographics, admission criteria and vital-sign patterns: the models were trained on $P_{\text{before}}$ and applied to $P_{\text{after}}$, and nothing in a model can notice that the world moved. This is distribution shift, a failure of the identically distributed half. What breaks precisely: your held-out number estimates $\E_{P_{\text{before}}}[\ell]$ while you now care about $\E_{P_{\text{after}}}[\ell]$ — an accurate answer to a question you stopped asking.

The independence half fails just as often and more sneakily: consecutive video frames, consecutive days of stock prices, several X-rays of one patient. The samples come from the right distribution but are correlated, so your effective sample size is far below $N$ — 10,000 frames from one 6-minute clip carry a few dozen samples' worth of information — and your risk estimate is dramatically overconfident.

Risk: the thing we actually want to minimise

Given i.i.d., we can stop talking about one hypothetical new point and talk about the average over all possible new points. That average is the risk.

Read the expectation carefully:

• What is random? The datapoint $(x,y)$ — not $h$, which is a fixed function being evaluated. $R(h)$ is one number per candidate $h$: a score for a function.
• Over what? The unknown joint $P$ on $\X \times \Y$, covering both which inputs arise and which labels they carry. Discretely, $R(h) = \sum_{x,y} P(x,y)\,\ell(h(x),y)$ — the loss weighted by how often each situation occurs, so inputs that never occur contribute nothing however badly $h$ handles them.
• Why can't we compute it? $P$ is unknown, not merely hard: "it is very difficult to know the true joint probability distribution." If you knew $P$ you would not need machine learning — you would output $\argmin_{\hat y} \E[\ell(\hat y, y) \mid x]$ for every $x$, optimal by construction.

Empirical risk: the thing we can actually compute

We cannot average over $P$, but we have $N$ samples drawn from it — so we average over those.

(That is the pre-reading's truth-first ordering; the lecture notes write $\frac1N\sum_i \ell\big(h(x^{(i)}), y^{(i)}\big)$ — identical for symmetric losses, but see the argument-order warning above.)

Empirical risk minimization

Everything needed to answer Q1. We want to minimise $R(h)$ and cannot evaluate it; we can evaluate $\hat R(h)$; so, in the notes' words, minimize the average loss on the training data.

Three pieces of this deserve individual attention.

What $\argmin$ means

$\min_h \hat R(h)$ is the smallest achievable value — a number. $\argmin_h \hat R(h)$ is the argument achieving it — a function, which is what ERM returns. With ties the $\argmin$ is a set and you pick one by a stated tie-breaking rule (common in decision trees).

What $\H$ is, and why you must restrict it

$\H$ is the menu you may order from:

• $\H = \{$ all lines $h(x) = wx + b \}$ — linear regression.
• $\H = \{$ all decision trees of depth $\leq 3$ on these $d$ attributes $\}$ — decision trees.
• $\H = \{$ all functions $\X \to \Y \}$ — the unrestricted class.

That last one shows why the restriction is not a technicality. If $\H$ contains every function, ERM has an exact, useless solution: the lookup table returning $y^{(i)}$ on each training $x^{(i)}$ and garbage elsewhere achieves $\hat R = 0$. $\H$ is what forces the model to compress, and compression is what produces generalization. Too rich gives overfitting, too poor and no member of $\H$ is any good (underfitting) — the trade-off that is the spine of Part II.

From $\argmin_{h \in \H}$ to $\argmin_{\theta}$

Searching over a set of functions sounds impossible — a CPU does not loop over functions. The trick, as the pre-reading puts it: fix the structure of the hypothesis function, then search over parameter values. Fix $h(x; w, b) = wx + b$ and a member of $\H$ is determined by two numbers; collect them into $\theta = (w,b)$ and the search becomes

This is the most important change of viewpoint in the course: a search over an abstract space of functions becomes a search over $\R^2$, a surface you can picture, differentiate and walk downhill on. Parameterisation turns learning into optimisation. Read $\argmin_\theta$ as "$\argmin_{h\in\H}$ where $\H$ is pinned to one shape and only the dials are free."

Holy cow, so much notation

A direct quote from the pre-reading, and the correct reaction. Every symbol on this page, in one table — come back to it.

Unsupervised learning

Everything so far was supervised: every input came with a label, and the supervision is the labels. Labels are expensive — a radiologist's hour per medical image — while unlabelled data is nearly free. So what can you do with only $x^{(1)},\dots,x^{(N)} \in \X$ and no $y$?

• Clustering — group similar $x^{(i)}$'s together. No label says what the groups mean; the algorithm finds that the points fall into $k$ blobs, and a human names them afterwards.
• Dimensionality reduction — convert $x^{(i)} \in \R^d$ with $d = 10{,}000$ into $\tilde x^{(i)} \in \R^{\tilde d}$ with $\tilde d \ll d$ (say 10). You cannot keep everything, so you keep the property the notes single out: $$ x^{(i)} \approx x^{(j)} \;\Longrightarrow\; \tilde x^{(i)} \approx \tilde x^{(j)} $$ Neighbourhood structure survives; everything else is negotiable. Two practical reasons: human interpretability (you cannot plot $\R^{10{,}000}$, you can plot $\R^2$ — and seeing the data is how you notice half of it came from one broken sensor) and faster processing, since every downstream algorithm scales with $d$.
• Learning representations good enough to generate new samples — new images, new text. Generation is a stringent test: a convincing new face means the model captured something real about how faces are structured.

Self-supervised learning: the payoff

Take text from the internet: trillions of words, no labels, nobody annotated any of it. Now hide a word and let it be the label. From "the cat sat on the mat": $x = $ "the cat sat on the", $y = $ "mat". The label was already in the data — you just looked away from it and then checked yourself — so no annotator was involved and it scales to the whole internet.

After that it is ordinary supervised learning, and everything on this page applies verbatim. $\X$ = all finite token sequences. $\Y$ = the vocabulary, a finite unordered set of maybe 50,000 tokens, so this is 50,000-way classification with a classification loss (in practice a smooth surrogate for zero-one; see logistic regression). $\H$ = very large neural networks parameterised by $\theta$, and training is $\argmin_\theta \hat R(\theta)$ by stochastic gradient descent. What you get is a next-word predictor; feed each prediction back in as input and it writes. In the notes' words, this forms the basis of LLMs.

The same trick works outside text: hide a patch of an image, predict the next video frame, predict one language's sentence from the other's. Whenever you can remove part of a datapoint and ask the model to restore it, free unlabelled data becomes a supervised problem with the full machinery of this chapter available.

Recap and what comes next

The whole chapter in eight lines:

1. Rules work when experts can state them. When they cannot — pixels, speech, language — learn from examples instead.
2. Formalise: inputs $\X$, labels $\Y$, find $h : \X \to \Y$ from data $\D = \{(x^{(i)},y^{(i)})\}_{i=1}^N$.
3. Training produces $h$; inference applies it. Keep them apart.
4. $\Y$ finite and unordered ⇒ classification; $\Y$ continuous and ordered ⇒ regression.
5. A loss $\ell : \Y\times\Y\to\R$ scores one prediction. Zero-one for classification, squared error for regression, asymmetric tables when the mistakes differ in cost. Check the argument order.
6. Averaging the loss over the unknown data distribution gives the risk $R(h)$ — what you want, and cannot compute.
7. Averaging it over your sample gives the empirical risk $\hat R(h)$ — a Monte-Carlo estimate of $R(h)$, unbiased for a fixed $h$, optimistically biased for an $h$ you selected using it.
8. ERM: $h^* = \argmin_{h\in\H} \hat R(h)$, which becomes $\argmin_\theta$ once the structure of $h$ is fixed. Choosing $\H$ and computing the $\argmin$ are the next four chapters.

Next: decision trees — the first concrete $\H$, chosen because you can read the resulting model out loud. Then entropy and mutual information for choosing splits well, and then linear regression, where for the first time the $\argmin$ has an exact closed-form solution.