Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

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

1. Two risks, one gap

A classifier is a function h:X→{−1,+1}h:\mathcal{X}\to\{-1,+1\} chosen from a class H\mathcal{H}. Fix a loss, say the 0–1 loss ℓ(h(x),y)=1{h(x)≠y}\ell(h(x), y) = \mathbb{1}\{h(x)\neq y\}. There are two numbers attached to hh, and they are different objects:

true risk L(h)=E(x,y)∼P[ℓ(h(x),y)],empirical risk L^n(h)=1n∑i=1nℓ(h(xi),yi).\text{true risk } L(h) = \mathbb{E}_{(x,y)\sim P}\big[\ell(h(x),y)\big], \qquad \text{empirical risk } \hat L_n(h) = \frac1n\sum_{i=1}^{n}\ell(h(x_i),y_i).

The first is a property of hh alone, but it depends on the unknown distribution PP; the second can be computed from the sample S={(xi,yi)}i=1nS=\{(x_i,y_i)\}_{i=1}^n but is a random variable. Empirical risk minimisation (ERM) returns

h^=arg⁡min⁡h∈HL^n(h),\hat h = \arg\min_{h\in\mathcal{H}} \hat L_n(h),

and the only question that matters is how far L(h^)L(\hat h) can be from L^n(h^)\hat L_n(\hat h) — the generalisation gap. Everything in this page is a bound on that gap.

Two immediate observations set the agenda.

2. Uniform convergence, finitely many hypotheses

Suppose H\mathcal{H} is finite, ∣H∣=M|\mathcal{H}| = M, and the loss is bounded in [0,1][0,1]. For a fixed hh, Hoeffding’s inequality gives

P(∣L^n(h)−L(h)∣≥ε)≤2e−2nε2.\mathbb{P}\big(|\hat L_n(h) - L(h)| \ge \varepsilon\big) \le 2e^{-2n\varepsilon^{2}} .

A union bound over the MM hypotheses, followed by choosing ε\varepsilon so that the right side is at most δ\delta, yields: with probability at least 1−δ1-\delta, simultaneously for all h∈Hh\in\mathcal{H},

∣L^n(h)−L(h)∣  ≤  log⁡M+log⁡(2/δ)2n.\big|\hat L_n(h) - L(h)\big| \;\le\; \sqrt{\frac{\log M + \log(2/\delta)}{2n}} .

This is the whole idea of statistical learning theory, and it already answers the practical questions:

3. Infinitely many hypotheses: the VC idea

A linear classifier on Rd\mathbb{R}^d has infinitely many parameter vectors, so M=∞M=\infty and the union bound dies. What replaces MM is the number of distinguishable behaviours on nn points. A hypothesis class shatters a set of nn points if it can realise all 2n2^n labellings of them; the VC dimension is the largest nn for which some set of nn points is shattered.

Class on R\mathbb{R} or R2\mathbb{R}^2VC dimensionWhy
constant classifiers0one behaviour only
thresholds 1{x≥t}\mathbb{1}\{x \ge t\}1two points: one labelling impossible
intervals [a,b][a,b]2two points shattered; with three, the middle alone cannot be isolated
half-spaces (lines) in R2\mathbb{R}^23any three non-collinear points; four points of a convex quadrilateral defeat it
half-spaces in Rd\mathbb{R}^dd+1d+1the classical count

The theorem we will not prove says the gap is controlled by VV, the VC dimension, in place of log⁡M\log M:

L(h^)  ≤  L^n(h^)+O ⁣(Vlog⁡n+log⁡(1/δ)n)with high probability,L(\hat h) \;\le\; \hat L_n(\hat h) + O\!\left(\sqrt{\frac{V\log n + \log(1/\delta)}{n}}\right) \qquad\text{with high probability,}

and, conversely, no algorithm can learn a class of infinite VC dimension in this distribution-free sense. So VV is a capacity: it must be finite, but it may grow with the data, and the price is one more log⁡n\log n. 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.

  1. 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 L(h^)L(\hat h), so it must not influence any choice.

  2. kk-fold cross-validation. Split into kk folds, train on k−1k-1, validate on the held-out fold, average. It uses the data more efficiently and gives a variance estimate; it is kk times more expensive.

  3. 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.

  4. 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 kk in kNN, against KK 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,

E[(y−f^(x))2]=noise+(bias)2+variance,\mathbb{E}\big[(y - \hat f(x))^2\big] = \text{noise} + \big(\text{bias}\big)^2 + \text{variance},

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:

Exercises

  1. For a fixed classifier and a known data distribution, compute the true risk and the empirical risk on samples of size 10,100,100010,100,1000. Plot both and describe the gap.

  2. 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?

  3. Prove that the VC dimension of intervals on the line is 2: exhibit two shattered points and show that no three can be shattered.

  4. Why is KK-fold cross-validation preferable to a single train/test split when choosing a model? Give a case in which it is still optimistic.

  5. Use the union bound of section 2 with M=210M=2^{10} and δ=0.05\delta=0.05 to find the sample size needed for a gap of 0.02; compare with the same computation for M=10M=10. Which of the two grows faster in MM, the gap or the sample size?

  6. Give a labelling of four points in general position in R2\mathbb{R}^2 that no line can realise, and one of five points that is realisable, to see why the VC dimension of half-spaces is d+1d+1 and not more.

  7. 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