Learning Foundations: Classification and Generalization
Not in this course: SVM (other course), Bayesian methods and HMM (other courses). The kernel trick is not an SVM topic and has its own page: The Kernel Method.
Goals¶
Classification problem: train/test split
kNN revisited as a nonparametric baseline
Occam’s razor and why simple models can generalize
Uniform convergence and the VC idea (intuition, not full theory)
1. Two risks, one gap¶
A classifier is a function chosen from a class . Fix a loss, say the 0–1 loss . There are two numbers attached to , and they are different objects:
The first is a property of alone, but it depends on the unknown distribution ; the second can be computed from the sample but is a random variable. Empirical risk minimisation (ERM) returns
and the only question that matters is how far can be from — the generalisation gap. Everything in this page is a bound on that gap.
Two immediate observations set the agenda.
ERM over all functions is useless. If is the set of all functions , the predictor that memorises the sample has and no guarantee on : on a new point it can be wrong with probability one. The restriction to a smaller class is what makes learning possible, and the size of that class will appear explicitly in the bounds.
The gap must be uniform. We do not need for the we happen to output; we need it for every simultaneously, because the output itself depends on the sample. That “for every” is what costs the extra factors below.
2. Uniform convergence, finitely many hypotheses¶
Suppose is finite, , and the loss is bounded in . For a fixed , Hoeffding’s inequality gives
A union bound over the hypotheses, followed by choosing so that the right side is at most , yields: with probability at least , simultaneously for all ,
This is the whole idea of statistical learning theory, and it already answers the practical questions:
More data helps like . With hypotheses and samples the gap is about , that is six percentage points; halves it.
More hypotheses hurt like . Growing the class from 103 to 106 hypotheses costs a factor in the gap, not a factor 1000. This is why rich classes are usable at all, and why the relevant complexity is logarithmic in the number of models.
The bound is loose on purpose. It holds for adversarial and for the worst ; on any real problem the true gap is much smaller. Its value is the shape of the trade-off, not the constant.
3. Infinitely many hypotheses: the VC idea¶
A linear classifier on has infinitely many parameter vectors, so and the union bound dies. What replaces is the number of distinguishable behaviours on points. A hypothesis class shatters a set of points if it can realise all labellings of them; the VC dimension is the largest for which some set of points is shattered.
| Class on or | VC dimension | Why |
|---|---|---|
| constant classifiers | 0 | one behaviour only |
| thresholds | 1 | two points: one labelling impossible |
| intervals | 2 | two points shattered; with three, the middle alone cannot be isolated |
| half-spaces (lines) in | 3 | any three non-collinear points; four points of a convex quadrilateral defeat it |
| half-spaces in | the classical count |
The theorem we will not prove says the gap is controlled by , the VC dimension, in place of :
and, conversely, no algorithm can learn a class of infinite VC dimension in this distribution-free sense. So is a capacity: it must be finite, but it may grow with the data, and the price is one more . The constants in the theorem are useless in practice (they are far too pessimistic for a few thousand samples), which is why the rest of the course measures the gap with data splits rather than with the bound.
4. Measuring the gap: splits and cross-validation¶
The theory says the gap exists; practice needs a number for it.
Train / validation / test. Fit on the training part, choose hyperparameters (number of neighbours, number of components, kernel width) on the validation part, and report the test error once. The test set is a proxy for , so it must not influence any choice.
-fold cross-validation. Split into folds, train on , validate on the held-out fold, average. It uses the data more efficiently and gives a variance estimate; it is times more expensive.
Leakage. Standardising, selecting features, or tuning on the full data before splitting makes the estimate optimistic. The rule is mechanical: anything fitted — means, variances, PCA directions, selected features — is fitted inside each fold.
What cross-validation cannot see. It estimates the error of the procedure on data from the same distribution. Distribution shift, duplicated rows across folds, and time-ordered data break it silently; for the last one the split must respect time.
The run of numbers we produce in the labs — validation accuracy against in kNN, against in k-means, against the number of components in PCA — is this section being used, not a separate topic.
5. Occam, bias, variance¶
The bounds above are worst case; the reason simple models often win in practice is the bias–variance decomposition of the squared error,
where the bias grows and the variance shrinks as the class gets richer. The best model sits where the two cross, which is a different question from “which class has smaller VC dimension” — a small class can be badly biased. The Bias–Variance Tradeoff page does this decomposition with numbers; here we only note that the two stories (capacity bounds and bias–variance) describe the same U-shaped curve from two directions.
A practical checklist that follows from the page, useful for the assignments:
Report both training and validation error; a small training error alone says nothing.
Say which quantity was used to make each choice; anything tuned on the test set invalidates it.
Compare against a baseline (the majority class, or 1-NN) before claiming a method works.
When adding parameters, say what the class gained in capacity and what it cost in variance.
Exercises¶
For a fixed classifier and a known data distribution, compute the true risk and the empirical risk on samples of size . Plot both and describe the gap.
Show that empirical risk minimisation over all functions has zero empirical risk and no guarantee of generalisation. Where exactly does a restriction on the hypothesis class enter the argument?
Prove that the VC dimension of intervals on the line is 2: exhibit two shattered points and show that no three can be shattered.
Why is -fold cross-validation preferable to a single train/test split when choosing a model? Give a case in which it is still optimistic.
Use the union bound of section 2 with and to find the sample size needed for a gap of 0.02; compare with the same computation for . Which of the two grows faster in , the gap or the sample size?
Give a labelling of four points in general position in that no line can realise, and one of five points that is realisable, to see why the VC dimension of half-spaces is and not more.
A colleague standardises the features and runs PCA on all data before the cross-validation split, then reports a very low error. Explain precisely which estimate is biased and how to repair the pipeline.
Sources¶
Blum, Hopcroft, Kannan, Foundations of Data Science, Ch. 12 (selected).
Hastie, Tibshirani, Friedman, The Elements of Statistical Learning, 2nd ed., §7.1–7.3 (model assessment and the bias–variance decomposition) and §7.9 (VC dimension).
Shalev-Shwartz, Ben-David, Understanding Machine Learning, Ch. 2–6 (ERM, uniform convergence, VC dimension).