What learning will mean

A colleague hands you a method and reports 97 per cent on 600 digits. The figure is the complement of the 3 per cent error that section 2.3 measured on six hundred digits, and it answers nothing until you ask the four questions that form the standard skeleton of the subject [S:27:265]. Which predictors was the method willing to consider, what did one mistake cost, how was the number measured on data the method had not seen, and how did the method search among its candidates?

Worked example. Take a case small enough to check by hand: six rows that each hold one feature and a label, namely (1, 0), (2, 0), (3, 1), (4, 1), (5, 0) and (6, 1). Store the first four and test on the last two; method A is one neighbour, which stores those four rows and answers a query with the label of the closest one. Its class is the lookup rules, one for each possible stored set and distance. Method B is a threshold: it answers 1 when the feature is above a cut and 0 otherwise, tries every cut between consecutive feature values, and keeps the cut with the fewest training errors. !The four questions every method answers. A class names the candidates, a loss prices one answer, a search is whatever the procedure does to pick a candidate from the class, and a test set estimates the error on rows no step touched. Method A answers with lookup rules, zero-one loss, storage, and a test set read once. Method B answers with thresholds, the same loss, a scan over cuts, and the same test set. Status: schematic.

Both methods get all four training rows right, and on the two held-out rows both make one error, because each answers 1 for both queries, which is wrong at 5 and right at 6. The reported number is one of two for both methods, measured on the same two rows with the same zero-one loss, so what differs is the class and the search. Method A's class is the lookup rules and its search is storage, while method B's class is the thresholds and its search is a scan over cuts, so the number alone cannot tell you which method you are holding. !Two methods on the six rows of section 2.4. Method A stores the first four rows and answers a query with its nearest stored row; method B cuts the feature axis and answers 1 above the cut. Both fit all four stored rows, both answer 1 at x = 5 and x = 6, and both score one error of two on the held-out pair. The class and the search differ; the reported number does not. Status: re-simulated.

The four questions name those differences: the set of candidates is the hypothesis class, and the cost of one answer is the loss, already met. The jump from a measured number to unseen data is generalisation, and the search is whatever the procedure does to pick one candidate from the class. Every procedure that turns labelled examples into a predictor answers those four, whether or not the paper states them.

For a fixed class and a fixed loss, the standard search keeps the candidate with the smallest average loss on the stored rows. That is empirical risk minimisation:

The formula says: of all the candidates in the class, keep the one whose average cost on the stored rows is smallest. The symbol H names the class, h names one candidate from it, and the hat on the left marks the candidate the procedure returns. Here n is the number of stored rows.

The nearest-neighbour rule answers the four questions in an unusual way: to the first, it names no predefined class and searches none, because it answers any query by looking up the nearest stored row [S:79:258]. To the second it answers with the zero-one loss, to the third with a test set read once, and to the fourth with nothing, because fitting is storage [S:47:32]. Fitting is whatever a method does with the stored rows before it answers a query, and for this rule it is storage, because the rule keeps the rows and computes nothing from them. That last answer is why this rule came first in the book.

Return to the colleague's 97 per cent and note what the four questions ask: 97 per cent of which 600 rows, and were they stored or held back? Which loss turned the errors into that percentage, and which class was searched by which search? A report that answers all four is a measurement you can check, and a report that answers none is a headline.

The framework organises methods, and it does not supply a guarantee: every answer still rests on an assumption about data you have not seen, and the assumption is never absent, only relocated [S:47:31]. The nearest-neighbour rule rejects a predefined class and still assumes that nearby inputs carry agreeing labels, which is a claim the data cannot check. A test number is an estimate from a finite set that a different split would change, and Barber's advice is to run a simple method first, so that later numbers have a baseline to beat [S:51:337]. The four questions tell you what that baseline assumes.

The formal statement. A learning problem is fixed by five objects: an input space $X$, a label set $Y$, a distribution over pairs from $X\times Y$, a loss $\ell$, and a class of candidate predictors $H$. A learner is a map from finite samples to members of $H$. Empirical risk minimisation returns the candidate with the smallest average loss on the rows, with ties in that choice broken by a stated rule. The four questions of the core name the class, the loss, the gap between the true risk $R$ and the average $\hat{R}$, and the learner.

The theorem. Suppose the class is finite, the $n$ rows are independent draws from the distribution, and the loss takes values between zero and one. Then, with probability at least $1-\alpha$, every candidate $h$ in the class obeys the next inequality.

The inequality says: the gap between the average on your rows and the average on the world shrinks like $1/\sqrt{n}$ and grows like the logarithm of the number of candidates.

The proof. Hoeffding's inequality bounds the gap for one fixed candidate by a quantity that decays exponentially in the number of rows times the square of the gap. A union bound over the candidates multiplies that quantity by the size of the class. Setting the product equal to $\alpha$ and solving for the gap gives the statement. Three steps, one inequality, one union bound, one logarithm, and no hidden constant.

The edge case. The one-nearest-neighbour rule has no finite class. Its candidates are the lookup rules generated by every possible stored set and distance, so the size of the class is infinite, the logarithm is infinite, and the bound says nothing at all [S:79:258]. That is not a defect of the bound. It is the formal content of the core's remark that the rule never searches a predefined class. A guarantee for this rule has to come from somewhere else, and in 2.5 it comes from a Lipschitz condition on the labels. Two rules can give the same four answers and still need different theorems.

What the core left out. No search does not mean no assumption. The assumption moves into the metric and into the claim that nearby inputs carry agreeing labels, which is an inductive bias rather than a fact about the table [S:47:31]. The fourth question's answer for this rule is storage, and storage is a choice: it decides that the class is the set of predictors that look up a stored row. Answering the fourth question with a noun hides that the class is still being chosen.

Original sources. The four questions are section 8.2 of Mathematics for Machine Learning, where they head the four subsections on the class, the loss, generalisation and the search [S:27:265]. The observation that nearest neighbour needs no predefined class is in chapter 19 of Shalev-Shwartz and Ben-David [S:79:258]. The claim that a nearby-label assumption is itself an inductive bias is in Daumé's chapter on geometry [S:47:31].

An open question. Whether the four questions are complete is open. Each of them is answered relative to a distribution, and the distribution is not one of the questions [S:27:266]. Recent work also shows that the complexity axis can behave unlike the classical picture: as model size grows, test error can rise and then fall again, and in some regimes more training data hurts [S:311:1]. Evidence that would settle whether an ingredient is missing: a task where all four answers are fixed and held constant, yet performance changes systematically with the number of rows in a way that no term in the framework predicts. The double-descent experiments are a candidate, and they are not yet a derivation.

A frontier result. Double descent and the effective-model-complexity conjecture are the current attempt to place this behaviour on one curve [S:311:1]. The conjecture is not a theorem, which is what makes it a frontier rather than a chapter, and the paper states it as a conjecture. If it holds, the fourth question acquires a second part: not only how the learner searches, but how much of the search it is allowed to finish.

What to read next. Read section 8.2 of [S:27:265] for the framework. Read chapter 5 of [S:79:61] for the no-free-lunch theorem that explains why a class is unavoidable. Read chapter 19 of [S:79:258] for the nearest-neighbour analysis that the framework does not cover, and then read [S:311:1] for the phenomenon the four questions leave out.