A table of examples

Six rows, two numbers in each row, and one recorded answer at the end of it.

!The chapter's six-row table drawn as a plane. Ink runs along the horizontal axis and middle-third ink along the vertical. The six stored rows carry their recorded digits as marks; the query at (9, 5) carries none. A dataset is the same object as the table, with rows as points, features as axes, and the missing label as a hole at a known place. Status: schematic.

A seventh row holds the two numbers 9 and 5, and its last cell is blank. !Two straight cuts fit all six labelled rows: y = x - 7 and y = x - 3, with label 1 above each line and label 0 below. The query at (9, 5) falls in the band between the two lines, so the first cut answers 1 and the second answers 0. Every label is matched and the answer is still not determined. Status: schematic.

The table describes six handwritten digits by two counts: the column headed ink counts the dark cells in the whole image, and the column headed middle-third ink counts the dark cells in the middle third of the columns. The last column records the digit that a person saw, and the seventh row is the question this chapter keeps asking. It carries measurements and no recorded answer, which is what a query looks like before a prediction exists.

Can a machine learn a rule nobody told it? It can learn one from a table, and the table must carry three things before any prediction is possible. Every row, including the question row, needs the same measurements in the same order; every stored row needs a recorded answer; and the answers need to vary with the measurements, or there is nothing to learn.

Row 3 is an example: one image held as two numbers, whose 0 is the label, the answer a person recorded beside it. The six labelled rows together are the dataset, and each column is a feature. A row that carries a label is a stored row, one the rule may keep; the seventh row is not stored, because it has no label to keep. Write x for a row's list of feature values, d for how many values it holds (two here), and n for the number of stored rows (six here).

The first requirement sounds like administrative bookkeeping and is not, because an image in a real collection arrives as a grid of darkness values. David Barber's digit experiment uses images of 28 by 28 cells, so each one becomes a list of 784 numbers [S:51:339]. The bracketed code is a source tag: S for source, then the source number and the page number, and every number taken from a source carries one.

The table then has 784 columns, and every row must fill all of them in the same order. A row that records the word dark where a number belongs breaks the comparison for every query, not only for itself.

The second requirement separates evidence from questions, and it is the reason labels cost more than inputs. The seventh row has no label, which is exactly what makes it a query, while a stored row with no label is a second query that cannot support a prediction. Somebody had to look at each stored example and write the answer down, and that labour is what the table records.

The third requirement turns a record into a problem. If all six labels were 0, the table would allow one answer and no measurement would matter, so a constant column of answers is still a table but not yet a prediction problem; nothing in it rewards examining the features.

Worked example. Check the table above against the three requirements, beginning with its shape. It has 2 feature columns and 6 stored rows, so there are 12 feature cells and 6 labels, and all 12 cells hold numbers. To score a rule is to run it on a set of rows and record the answers it gives. The query row holds 2 numbers and no label, so it can be placed in the table and cannot be scored.

Now deliberately spoil one cell, replacing the 11 in row 1 with the word light. Eleven of the twelve feature cells still hold numbers, and five of the six in the ink column do, but row 1 can no longer be compared with any query. Delete the label in row 6 instead, and row 6 becomes a second query: the stored rows fall from 6 to 5, and nothing else about the table changes.

Numbers alone do not determine the rule, which is the quiet problem underneath the three requirements. Suppose two predictors agree with all six labels: one answers 0 for the query at 9 and 5, and the other answers 1. Both satisfy the table completely, because the table constrains a predictor at six places and is silent at the seventh, which is the place you care about. Something beyond the table has to choose between them, and the next section supplies one such thing.

The table is a sample, and nothing in it says the next example comes from the same source. A collection of digits written by one group of people can behave differently from a collection written by another [S:162:10], and the columns may keep their names while their meaning shifts. No row in the table reports that shift, which is the unavoidable cost of learning from examples: the table is all you have, and it is never the entire world.

The formal statement. A table is a finite indexed family of pairs. Write $D=((x_1,y_1),\dots ,(x_n,y_n))$, where $n$ is the number of stored rows, each input $x_i$ is a list of $d$ numbers in a fixed order, $d$ is the number of features, and each label $y_i$ belongs to a set $Y$. A predictor is a function $h$ that returns a member of $Y$ for every input, and $h$ fits $D$ when $h(x_i)=y_i$ for every stored row. The three conditions of the core become three hypotheses:

(H1) one $d$ and one coordinate order, shared by every row including the query;

(H2) a label for each $i\le n$;

(H3) the labels are not constant across the sample.

The proof. Take a query $x^{\ast }$ that is not one of the stored inputs, and a predictor $h$ that fits $D$. Pick any label $c$ in $Y$ and define $h^{\prime }$ by $h^{\prime }(x)=h(x)$ for every input other than $x^{\ast }$, and $h^{\prime }(x^{\ast })=c$. The two predictors agree on all $n$ stored rows, so both fit $D$, and they disagree at the query. Since $c$ was arbitrary, the table is consistent with as many answers at $x^{\ast }$ as $Y$ has members. The construction uses (H2) and the fact that $x^{\ast }$ is new; no step is omitted.

This is the exact content of the core's remark that the table is silent at the seventh row. It is silent there because the seventh row is new, not because tables are silent.

The edge case. Let the query coincide with a stored input, so $x^{\ast }=x_i$. The construction fails, because $h^{\prime }$ would have to disagree with $h$ at a point where both are pinned to $y_i$. The table therefore does determine an answer at every stored row. That looks harmless here and becomes the whole problem in 2.4, where scoring the rule on its own rows returns a perfect score for exactly this reason.

What the core left out. Condition (H3) describes six labels, while the assumption a predictor needs concerns the distribution that produced them. The formal version: the pairs are independent draws from a joint distribution over $X\times Y$, and the label is not independent of the input [S:27:266]. A sample can show variation and still come from a distribution whose labels ignore the features, and a constant sample can come from a distribution that does not. You cannot check that distinction from the table alone, which is why the core stated the condition about the answer column and not about the world.

(H1) hides a second assumption: that each of the $d$ numbers carries the same meaning in every row. Two collections can share the column names and disagree about what a column measures [S:59:162].

Original sources. The formulation of supervised learning as pairs drawn from a joint distribution, with the independent-and-identically-distributed assumption stated outright, is in section 8.2 of Mathematics for Machine Learning [S:27:266]. The 784-column table is the MNIST construction, with images normalised into 28 by 28 fields and split by writer [S:162:10]. The historical version of the same move is Highleyman's corpus of 1800 characters, gathered from 50 writers and remembered as the first machine-learning benchmark [S:59:162].

An open question. The field has not settled how to guarantee that the table you hold is a sample from the population where the predictor will run. The i.i.d. assumption is precisely that, an assumption [S:27:266]. When the test distribution differs from the training distribution, the guarantee does not transfer, and the vocabulary for the difference names the failure without removing it [S:62:769]. A detector that fires late is a different failure from one that never fires, and a table cannot tell you which one you have. Evidence that would settle a given case: labelled rows drawn from the deployment distribution, or a shift detector whose false-negative rate you have measured on shifts the detector was not built for.

A frontier method. Weighted conformal prediction produces prediction sets with a coverage guarantee under a known covariate shift, by reweighting calibration rows with a likelihood ratio between the test and calibration input distributions [S:48:20]. It depends on the table idea twice. The calibration rows are a table, and the guarantee is a statement about a row no step of the method saw. The price is a model of how the inputs shift, and that price is stated rather than assumed.

What to read next. Read section 8.2 of [S:27:265] for the four ingredients that 2.6 states, chapter 19 of [S:62:769] for the taxonomy of shift, and [S:162:10] for how one real table was assembled. Then read [S:59:162] for the benchmark history, which shows how much of a dataset is a decision rather than a measurement.