A question a classifier cannot answer for itself
A classifier can fit its training cases perfectly and still fail on new cases. To assess a learning procedure, we must specify how cases arise, what information is available when each decision is made, and which cases are reserved for evaluation. A score without that protocol can measure memory of answers instead of prediction.
This unit constructs a deliberately tiny synthetic binary problem. Its complete data and program are shown, so every reported result is reproducible. The experiment demonstrates a protocol; eight test observations cannot establish performance on a real population. The split is a partition of a single illustrative sequence. For the later probability theorem only, we additionally assume that the observations at all positions are independent draws from the same distribution; one observed table cannot verify that assumption.
Data, transformations, and candidate rules
Each case has features and a binary label . The training set contains two copies of each of , , and , where the last coordinate is the label. Hence each feature has training mean and population standard deviation , using the denominator eight. We fit the transformation on training features only:
The same fitted map is applied unchanged to validation and test features. Never recompute its mean from their features. Even a label-free transformation can transmit evaluation-set information into a fitted pipeline. For a feature constant in training, a real implementation must define a zero-scale policy; neither feature is constant here.
We construct exactly two candidates from training data. The threshold rule is . The small tree first branches at , then at ; its four leaf labels are training-majority labels. All four leaves have two identical training labels, so no tie rule is needed. The resulting function is . The split locations and candidate family were fixed before examining validation. These two fitting recipes are intentionally simple; we do not claim that a generic tree induction algorithm necessarily makes these splits.
The validation cases are , , , . Choose the candidate with fewer validation errors; if tied, choose the threshold rule. Having selected it, freeze the entire pipeline before opening the test labels. The eight test cases, in order, are , , , , , , , . The last four include two labels inconsistent with XOR. Identical feature vectors may have different labels: that is permitted by a noisy joint distribution and prevents a deterministic feature-only classifier from being correct on every listed case.
Concept lensStructural
The split follows the information flow
Training fits the transformation and the tree leaves. Validation chooses between the two fitted pipelines. The test set describes the frozen selected pipeline. Looking at the test result and then changing the model makes that set part of model selection; a fresh independent test set is needed for an unbiased final evaluation of the revised procedure.
Read the confusion matrices
Definition 29.1.1
(Confusion matrix and scores)
Take label 1 as positive. A true positive (TP) predicts 1 for an actual 1, a false positive (FP) predicts 1 for an actual 0, a false negative (FN) predicts 0 for an actual 1, and a true negative (TN) predicts 0 for an actual 0. Rows below are actual labels 0, 1 and columns are predicted labels 0, 1. Thus each matrix is .
Accuracy is defined whenever there is at least one case. Precision, recall and the false-positive rate (FPR) have denominators over predicted positives, actual positives and actual negatives respectively, and are undefined when their denominator is zero unless a convention is stated.
The validation errors are and , so the selected rule is the tree. Its test accuracy is , its positive-class precision is , and its recall is . Here the denominators happen to agree; they need not in general. If there are no predicted positives, precision is undefined without an explicitly chosen convention. The threshold's test matrix is included to make all arithmetic inspectable, not to authorize a second selection on the test set. In a real workflow its test score should normally remain unopened until the selection policy is frozen; here both are displayed only as part of a fully specified teaching calculation.
Worked example 29.1.2
(A false negative and a false positive)
For test case the tree predicts 0 and the true label is 1, giving one FN. For it predicts 1 and the true label is 0, giving one FP. Both disagreements are real errors on the specified labels. Calling a label noisy does not permit removing it after seeing the prediction.
Worked example 29.1.3
(A classifier that never predicts positive)
Suppose a rule predicts on all ten cases, and two of the cases are actually . Then , , , . Accuracy is . Recall is and the false-positive rate is . Precision has denominator , so it is undefined without a stated convention. The high accuracy and zero false-positive rate conceal that the rule finds none of the positive cases.
Common mistake
(Reading high accuracy as good performance)
Accuracy hides which type of error occurred. Suppose of cases are positive and a rule predicts every time. Its accuracy is , yet its recall is : it detects none of the cases that matter.
The following standard-library program reproduces the matrices. The training mean and scale, tree leaves, validation selection, and only then test scoring are visible. The table is fixed, not a simulated experimental result.
from math import sqrt
train = [(0,0,0), (0,1,1), (1,0,1), (1,1,0)] * 2
valid = [(0,0,0), (0,1,1), (1,0,1), (1,1,0)]
test = [(0,0,0), (0,1,1), (1,0,1), (1,1,0),
(0,0,1), (0,1,1), (1,0,0), (1,1,0)]
mean = [sum(r[j] for r in train) / len(train) for j in (0, 1)]
scale = [sqrt(sum((r[j] - mean[j])**2 for r in train) / len(train))
for j in (0, 1)]
assert all(s > 0 for s in scale)
def branch(row):
return tuple(int((row[j] - mean[j]) / scale[j] >= 0) for j in (0, 1))
leaves = {}
for a in (0, 1):
for b in (0, 1):
labels = [r[2] for r in train if branch(r) == (a, b)]
assert labels and 2 * sum(labels) != len(labels)
leaves[a, b] = int(2 * sum(labels) > len(labels))
def threshold(r): return branch(r)[0]
def tree(r): return leaves[branch(r)]
def matrix(data, rule):
m = [[0, 0], [0, 0]]
for r in data:
m[r[2]][rule(r)] += 1
return m
def errors(m): return m[0][1] + m[1][0]
models = [("threshold", threshold), ("tree", tree)]
vm = [(name, rule, matrix(valid, rule)) for name, rule in models]
chosen = min(vm, key=lambda item: errors(item[2])) # first wins ties
print("validation", [(name, m) for name, _, m in vm])
print("selected", chosen[0])
print("test", [(name, matrix(test, rule)) for name, rule in models])
Why validation can guide selection
Definition 29.1.4
(Risk and validation error)
Let the training data be fixed for the following argument. Assume the validation cases , , are iid from a distribution P and independent of the training data. Given the training data, let be a finite, nonempty set of fitted classifiers and let their entire fitting and feature transformation be fixed independently of validation. Write
The fresh pair in R is distributed according to P and independent of the data that produced h, including validation if h was selected using validation. The logarithm below is natural. The probability statements below are conditional on the training data. If the conditional hypotheses hold for almost every training set, the same bound also holds unconditionally by averaging over training sets.
Theorem 29.1.5
(A finite-family validation bound)
For , with probability at least over the validation sample, every one of the K candidates simultaneously satisfies
Consequently the inequality also holds for a candidate selected by any validation-dependent rule. This is a probabilistic guarantee about the sampling procedure, not a promise that the observed validation error equals the true risk.
Proof
(Hoeffding for each candidate, then the union bound)
Conditional on training, each candidate is fixed and its validation error indicators are iid Bernoulli variables with mean . Hoeffding's inequality gives . By the union bound, the probability that at least one of K inequalities fails is at most . Setting this equal to yields the displayed radius. On the complementary event all candidates satisfy the bound at once, so whichever one validation selects satisfies it too. No independence between the candidates' errors is required. The independence needed is between the fixed candidates and the iid validation sample.
Proof X-ray
What the union bound does, and does not, buy
The event covers the entire family fixed after training and before validation. It accounts for choosing among those K candidates. It does not automatically cover new candidates invented after inspecting validation labels, repeated uncounted searches, non-iid sampling, or data-dependent preprocessing fitted on the validation sample.
For this example , and , the radius is . The selected tree has validation error zero, so the upper bound on its true error is about on the stated high-probability event. It is extremely loose: zero observed errors on four cases is not proof of zero population error. The deterministic sample itself does not establish iid sampling, and this numerical statement applies only under the stated distributional assumptions.
Worked example 29.1.6
(How many validation cases give radius 0.05?)
Keep and and ask for radius at most . The condition is equivalent to , so is the smallest integer that works: at the radius is about , and at it is about . Halving the radius requires four times as many cases, because enters through . Doubling the number of candidates from to replaces by , a far smaller cost than doubling .
Leakage is a broken experiment, not merely a coding style
Definition 29.1.7
(Evaluation leakage)
Leakage is any influence of a data set on the pipeline that the protocol reserves that set to assess. Training data may influence fitting; validation data may influence only the choice within a candidate family fixed beforehand; test data may influence nothing about the frozen pipeline. A score computed after leakage no longer estimates how that pipeline treats unseen cases.
Counterexample mode
Memorizing an evaluation answer
Suppose each evaluation case has a unique identifier that will never recur, and a developer reads its label before writing a lookup rule that returns the saved label for each identifier. The measured error on those same cases is zero by construction: for instance, storing the eight test labels under identifiers gives error . On a new identifier , the lookup contains no answer and a fallback may perform badly. The candidates now depend on the evaluation labels, so the fixed-family proof cannot be invoked for that family. Perfect reported accuracy measures access to answers, not a demonstrated ability to generalize.
Leakage can be less obvious: selecting features using all labels, fitting a scaler using held-out cases, splitting records from the same person across sets when predicting on new people, or repeatedly changing the model after reading test outcomes. Split at the unit that will be new at deployment, such as a person or future time period. Group and time splits can be necessary but need their own analysis; they do not automatically satisfy the iid theorem. Fit every learned preprocessing step within training folds in cross-validation. Validation itself is used for selection, so under the fixed-family iid assumptions the winning error is downward biased in expectation as an estimate of the selected model's risk, though it need not underestimate risk in every realization; a separate untouched test estimates that frozen model on the test sampling population, not necessarily on a shifted deployment population.
Common mistake
(Choosing the model by its test score)
If the test set picks among candidates, it becomes part of model selection. Suppose rules guess each of the test labels by independent fair coin flips, so each has true error . One rule gets at least of the correct with probability , so the chance that at least one of the does is . The best test score would suggest skill that does not exist.
Exercises
Exercise 29.1.8
(For a different test set the selected rule produces , , , . Calculate accuracy, precision, recall and false-positive rate. Explain their denominators.)
Foundation
Solution(3)
- 1
Count the cases and the accuracy
Key step
There are cases, so accuracy is .
- 2
Divide by the right group
Precision is , with denominator the predicted positives. Recall is , with denominator the actual positives.
- 3
Error rate among negatives
The false-positive rate is , with denominator the actual negatives. Accuracy alone conceals which type of error occurred.
Quick check
(A third candidate has validation error . Does adding it after viewing the validation labels preserve the theorem with ? What if all three candidates and their training-only fitting recipes had been fixed before validation?)
Solution · Answer
Not in general. The third candidate may encode the validation answers, and merely counting it as one of three does not restore independence. If all three fitted candidates were fixed from training independently of iid validation, the theorem applies with , including to whichever one validation selects. A prior finite family must include every candidate actually considered, not only those eventually reported.
Quick check
(Suppose the threshold rule has validation error and the tree has validation error . Using the theorem with , give an upper bound for the selected rule's risk. Why might it be unhelpful?)
Solution · Answer
The threshold is selected, and its validation error is . The radius remains approximately , so the bound is on the event. A risk is at most one anyway; this upper bound gives little useful assurance. It is a statement about the procedure over repeated iid validation samples, not a probability assigned to a fixed unknown risk after seeing this sample.
Quick check
(A hospital has 100 patients, each with five images. A random image split puts some images of the same patient in both training and test. Explain a mechanism for optimistic evaluation and propose a split. Does your proposal by itself guarantee iid patients?)
Solution · Answer
Patient-specific texture or acquisition signatures can appear in both sets, letting a model recognize patients rather than generalize to new ones. Assign all images of each patient to one set and keep test patients untouched. This tests new patients from the sampled setting more directly. Correlated patients, selection bias or time drift may remain; a grouped split alone does not prove iid sampling or external validity.