The wall between train and test

Take the rule that keeps one neighbour, store the 300 ones and 300 sevens, and then apply it to those same 600 stored images rather than to the held-back ones: how many mistakes does it make? Write your number down before you read any further.

None — not a few, but none at all, and nothing about the digits themselves produced that result: every stored example sits at distance zero from itself and the nearest neighbour of a row is that row. The rule therefore returns the row's own label, so the answer is right because it is the label, and dividing zero by 600 yields zero. !The wall and two ways across it. Left: labelled rows are cut into a training set the rule may store and a test set it may not read. Middle: scored on its stored rows, the one-neighbour rule returns each row's own label, because every stored row sits at distance zero from itself. Right: a split by row can put the same writer on both sides, so the sets look separate while test rows are near-copies of stored ones. Status: schematic.

A reading that comes out the same whatever you point it at is a property of the instrument: score the rule on the examples it stored and you are measuring the storage, not the rule. That zero survives if you replace the digits with bottles, change the number of features, or shuffle the labels the night before; nothing in the arithmetic of distance can break it, and only a contradiction inside the stored set can. !The reported error as test rows cross the wall. Each crossing copies one held-out row into the stored pile, and the copy answers its own test row at distance zero. As the copied share grows, the reported error falls to zero, and the error on rows that never crossed stays near 10 per cent while the uncopied rows are still numerous. The fall measures the copies, not an improvement in the rule. Status: synthetic.

The repair is a second set: cut the labelled data into a training set, which the rule may store, and a test set, which it may not read while being built. The number you report is the error rate on the test set [S:27:268], and "not read" is the whole condition, because a test row copied into the training set stops being a test row.

Worked example. Six rows with one feature and a label: (1, 0), (2, 0), (3, 1), (4, 1), (5, 0), (6, 1); store the first four and test on the last two. A query at 5 is nearest to the stored row at 4, whose label is 1, so the answer is wrong. A query at 6 is nearest to 4 as well, but its own label is 1, so that answer is right and the test error is one of two.

Score the same rule on the four stored examples and every row is nearest to itself, so the training error is zero of four; now copy the row (5, 0) into the training set. The test example at 5 then has an exact copy, so it is answered correctly, and the row at 6 was already correct, so the reported error falls from one of two to zero of two. The rule did not improve: the test set stopped being a test set.

A test set can be dishonest even when its size appears right: one route is duplication, where a test example that also sits in the training set is a free correct answer for this rule. The other route is grouping, and the standard digit collection, the MNIST digits, was split by writer, with the characters of 250 writers on each side, because a random split would put the same hand on both sides [S:162:10]. Whenever examples arrive in groups, the cut has to fall between the groups rather than inside them.

The protocol is a single sentence: do not go back to training after you have looked at the test set [S:27:268]. Read the number, dislike it, change the rule, and read it again, and the test set has become a second selection set. It is now the portion of the data you examine while choosing among candidate rules, before you report a final number, and nothing warns you that this has happened, because the number still prints like a measurement.

The wall costs data, and the cost is real: every row you hold back is a row the predictor cannot store, and a test set of one item reports zero or one and nothing between. The wall also fails quietly in the other direction, because rows that are near-duplicates, or that come from the same writer, sensor or week, can sit on both sides while the sizes look perfect. No arithmetic on the examples reveals where the groups are; you have to know where the data came from.

The formal statement. A split divides the labelled rows into two disjoint parts, a training set and a test set. A learner is a procedure that maps a training set to a predictor, so the fitted rule is a function of the training rows alone. The test risk is the average loss of that predictor on the test rows. The condition that makes the number a test number is not that the row indices are disjoint. It is that no test row entered the procedure.

The proof. For the one-nearest-neighbour rule, the training error is zero whenever no two stored rows share an input and carry different labels. Distance satisfies $\rho (x_i,x_i)=0$, and the distance to any other stored row is positive once its input differs, so row $i$ is its own nearest neighbour and the rule returns $y_i$. The italicised clause is the only hypothesis, and the proof fails without it: a duplicate at distance zero can outrank the row itself under the tie rule, and then at least one of the two rows must be misclassified.

The edge case. The test estimate is unbiased for the population the test rows come from, and for no other. Take a split that places writers on one side and different writers on the other. The number then estimates performance on new writers, which is the number you want, but it is not an estimate of performance on the writers you trained on. MNIST was split this way, with the characters of 250 writers on each side, because a random split would put the same hand in both sets [S:162:10]. The row count is identical either way. The quantity being estimated is not.

The protocol, formally. Suppose a class holds several candidates and you report the smallest test error among them. Each candidate's test error is unbiased on its own. The smallest of several unbiased estimates is not, and it is biased downward:

Read it as: the average of the best of several noisy readings sits below the best average, so the winner looks better than it is. Nothing in the arithmetic announces the change, which is why the remedy is procedural. Fix the rule before you read the number, or hold back rows that no selection step has touched.

What the core left out. The size of the test set fixes the resolution of the answer. A test set of $n$ rows gives a standard error of $\sqrt{R(1-R)/n}$ on the error rate, and no arithmetic recovers precision that $n$ rows do not contain. The core's remark about a test set of one item is this fact at its extreme.

Original sources. What may be the first train-test split is Bledsoe's: he divided Highleyman's characters by writer, using 40 writers for training and 10 for testing [S:59:163]. The MNIST construction repeated the idea at scale, placing the first 250 writers in training and the remaining 250 in test [S:162:10]. The protocol, that you do not return to training after reading the test set, is stated in section 8.2.3 of [S:27:268].

An open question. Whether a test set can be reused without losing its meaning is unsettled in practice. [S:27:268] goes further than most textbooks: even knowing the performance on the test set leaks information, and the page cites Blum and Hardt for the claim. The open question is what a report should contain when the analyst has looked at the number several times. A number read once and a number read after many attempts are different measurements, and only the first is described by the formula in 2.4. Evidence that would settle a protocol: a stated validity guarantee that survives an adaptive sequence of queries, checked on a simulated sequence in which the analyst reacts to each number.

A frontier method. Conformal prediction replaces the point estimate with a set that contains the true label at a chosen rate, for a fresh row drawn from the same distribution as the calibration rows [S:48:20]. Under a known covariate shift, weighted conformal prediction keeps the guarantee by upweighting calibration rows that are more likely under the test distribution [S:48:20]. The wall remains in place: the calibration rows are rows that no fitting step read.

What to read next. Read sections 8.2.3 and 8.2.4 of [S:27:268] for the split and for cross-validation, [S:59:163] for the historical experiment, and [S:162:10] for the writer-level split. Then read [S:48:20] for what a guarantee looks like when the test rows are not exchangeable with the calibration rows. The last reading is the one that shows how much of the wall is about arithmetic and how much is about exchangeability.