Why every model's error splits into three parts, why cross-validation is the right tool for choosing between them, and which of the metrics everyone reports are actively misleading.
Fix an input \(\vx_0\). The training set \(S\) is random, so the fitted model \(\hat f_S\) is random, so its prediction \(\hat f_S(\vx_0)\) is a random variable. The target \(y_0\) is random too. Ask: what is the expected squared error, averaging over both?
Two caveats that are usually left out.
A single train/validation split wastes data and gives a noisy estimate. \(k\)-fold cross-validation reuses every point in both roles.
Partition the data into \(k\) folds. For each fold \(j\): train on the other \(k-1\) folds, evaluate on fold \(j\). Average the \(k\) scores.
\[ \text{CV}_k = \frac1k\sum_{j=1}^{k} \hat R_{\text{fold }j}\big(\hat f^{(-j)}\big). \]Every point is used for validation exactly once and for training \(k-1\) times.
Be precise about what this estimates. \(\text{CV}_k\) is an approximately unbiased estimate of the risk of a model trained on \(n(k-1)/k\) points — not of the model you will finally ship, which is trained on all \(n\). Since more data helps, CV is slightly pessimistic. With \(k=5\) you are estimating the performance of a model trained on 80% of your data.
Nested cross-validation. If you use CV to choose a hyperparameter and then report that same CV score as your performance estimate, you have made the Lecture 01 mistake: the score is a minimum over many candidates and is optimistically biased.
The fix is two loops. An outer loop splits into train/test; an inner CV on the outer training portion selects the hyperparameter; the selected model is evaluated once on the outer test fold. The outer scores are unbiased. It costs \(k_{\text{outer}}\times k_{\text{inner}}\times|\text{grid}|\) fits, which is why people skip it — and why published CV numbers are systematically optimistic.
For classification, the confusion matrix is the raw material. Everything else is a summary of it, and every summary throws something away.
\[\begin{array}{ll} \text{accuracy} = \dfrac{TP+TN}{n} & \text{useless under imbalance (Lecture 05)}\\[8pt] \text{precision} = \dfrac{TP}{TP+FP} & \text{of those flagged, how many were right}\\[8pt] \text{recall} = \dfrac{TP}{TP+FN} & \text{of the real positives, how many were caught}\\[8pt] F_1 = \dfrac{2\,PR}{P+R} & \text{harmonic mean; hides which of the two is bad}\\[8pt] \text{ROC-AUC} & P(\text{score of a random positive} > \text{random negative})\\[8pt] \text{PR-AUC} & \text{the same idea, but sensitive to the base rate}\\[8pt] \text{log loss} = -\tfrac1n\sum\log \hat p_{y_i} & \text{proper: rewards calibration and resolution}\\[8pt] \text{Brier} = \tfrac1n\sum(\hat p_i-y_i)^2 & \text{also proper; less harsh on confident errors} \end{array}\]
Why ROC-AUC misleads on imbalanced problems. The false positive rate is \(FP/(FP+TN)\), and with 99.5% negatives the denominator is enormous. Ten thousand false positives against a million negatives moves the FPR by 0.01 — invisible on an ROC curve — while destroying precision if there are only 5000 true positives to find.
PR curves use \(FP/(TP+FP)\) instead, whose denominator is the number of things you actually flagged. That is the quantity a human reviewer experiences. For rare-positive problems, report precision–recall, and report precision at the \(k\) your operational capacity allows.
For each symptom, say whether the problem is bias, variance, or noise, and what you would try.
1. Variance. A 40× gap means the model fits the training set far better than it generalises. Try: more data; more regularisation; a smaller hypothesis class; early stopping; ensembling. Check for leakage first, since a gap this large sometimes means the training set contains something the validation set does not.
2. Bias. Both errors are high and close together, and both sit well above the noise floor — the model is consistently missing the same structure, and its instability is not the issue. More data will not help at all: the curves have already converged. Try: more capacity, better features, a different model family, interaction terms. This is the case where people waste weeks collecting data that cannot possibly help.
3. Neither — this is as good as it gets. Validation error is essentially at the noise floor and the gap is negligible. Any further "improvement" would be fitting noise. Stop, and if you need better performance, the only route is more informative features (which lowers the noise floor by explaining more of \(y\)), not a better model.
4. Variance in the estimate, not necessarily in the model. A validation set small enough that the score swings by 3× is not measuring anything. Fix the measurement before drawing any conclusion: use \(k\)-fold CV, repeat over several partitions, and report the standard error. Only once the estimate is stable can you ask whether the model has a variance problem.
Prove that the cross term in the bias–variance decomposition vanishes, being explicit about which expectation each quantity is taken over.
Then explain why an ensemble of \(M\) independently-trained high-variance models has roughly \(1/M\) of the variance and the same bias — and why that makes bagging (Lecture 11) work.
The cross term. All expectations are over the training set \(S\) at a fixed test point \(\vx_0\). Write \(a = f^\star(\vx_0)-\bar f(\vx_0)\) and \(b_S = \bar f(\vx_0)-\hat f_S(\vx_0)\).
\(a\) is a constant: \(f^\star(\vx_0)\) is a property of the world and \(\bar f(\vx_0) = \E_S[\hat f_S(\vx_0)]\) is an expectation, already averaged over. Neither depends on \(S\). So
\[\E_S[2ab_S] = 2a\,\E_S[b_S] = 2a\big(\bar f(\vx_0) - \E_S[\hat f_S(\vx_0)]\big) = 2a\cdot 0 = 0. \qquad\blacksquare\]The vanishing is not an approximation; it is forced by choosing to expand around the mean. Expanding around anything else would leave a cross term.
Ensembling. Let \(\hat f^{(1)},\dots,\hat f^{(M)}\) be fitted on independent training sets and define \(\hat F = \frac1M\sum_m \hat f^{(m)}\).
Bias is unchanged:
\[\E_S[\hat F(\vx_0)] = \frac1M\sum_{m}\E[\hat f^{(m)}(\vx_0)] = \bar f(\vx_0),\]by linearity of expectation — the same \(\bar f\), so the same bias. Averaging cannot fix bias.
Variance falls: with independence, variances add and the \(1/M^2\) survives (Phase A Lecture 13):
\[\Var(\hat F) = \frac{1}{M^2}\sum_m \Var(\hat f^{(m)}) = \frac{\Var(\hat f)}{M}.\]Why this makes bagging work. It says: take a model with low bias and high variance — a deep unpruned decision tree is the canonical example — and average many of them. The bias stays low, the variance is divided, and the total error falls. You get the flexibility of a high-capacity model without its instability. That is the entire justification for random forests.
The catch, and why random forests do more than bagging. Independence is the load-bearing assumption, and in practice the \(M\) models are trained on bootstrap resamples of the same dataset, so they are correlated. With pairwise correlation \(\rho\),
\[\Var(\hat F) = \rho\,\Var(\hat f) + \frac{1-\rho}{M}\Var(\hat f) \;\xrightarrow[M\to\infty]{}\; \rho\,\Var(\hat f).\]The variance reduction saturates at \(\rho\Var(\hat f)\), no matter how many trees you add. This is why random forests randomise the feature subset at each split as well as bootstrapping the rows: the extra randomness is there purely to reduce \(\rho\), and it is worth the small increase in individual-tree bias. Lecture 11 makes this concrete.
You must compare two models on a test set of 500 examples. Model A gets 87.2% accuracy, model B gets 89.0%.
1. Accuracy is a mean of Bernoulli indicators, so
\(\text{se}=\sqrt{p(1-p)/n}\) (Lecture 04, exercise 3).
Model A: \(\sqrt{0.872\times0.128/500}=0.0150\). Model B: \(\sqrt{0.890\times0.110/500}=0.0140\).
Treating them as independent, the difference has \(\text{se}=\sqrt{0.0150^2+0.0140^2}=0.0205\), so the
95% interval for the difference is \(0.018\pm0.040 = [-0.022,\,0.058]\). It comfortably contains zero.
Not distinguishable.
2. The two models are evaluated on the same 500 examples, so their errors are strongly positively correlated — both get the easy cases right and the genuinely ambiguous cases wrong. The independence assumption above throws that away and is badly conservative.
A paired analysis looks only at the disagreements. Build the 2×2 table of (A correct, B correct): let \(b\) be the count where A is right and B is wrong, and \(c\) where B is right and A is wrong. The cells where they agree carry no information about which is better. McNemar's test uses \(\chi^2 = \frac{(|b-c|-1)^2}{b+c}\), or exactly, a binomial test of \(b\) against \(\text{Bin}(b+c,\,0.5)\).
If the models disagree on only 40 examples, split 29 to 11 in B's favour, the exact binomial \(p\)-value is about \(0.006\) — clearly significant, where the unpaired analysis said nothing. Same data, vastly more power, purely from not discarding the pairing. (For continuous metrics the analogue is a paired \(t\)-test or a bootstrap over paired differences.)
3. For an unpaired comparison, detecting \(\delta=0.018\) at 80% power and 5% significance needs roughly
\[n \gtrsim \frac{2(z_{0.975}+z_{0.8})^2\,p(1-p)}{\delta^2} = \frac{2(1.96+0.84)^2(0.88)(0.12)}{0.018^2} \approx 5100 \text{ per model.}\]Paired, the requirement depends on the disagreement rate rather than the accuracy, and is typically 5–20× smaller — often a few hundred examples.
The general lesson: small test sets cannot resolve small differences, and most reported improvements of a point or two on a 500-example benchmark are not measurements. Either enlarge the test set, or pair the comparison, or report the interval and say honestly that the difference is within noise.
Coding. Investigate the double-descent phenomenon, which complicates the classical bias–variance picture.
lstsq) when \(d>n\).import numpy as np
rng = np.random.default_rng(0)
n, sigma = 40, 0.3
truth = lambda x: np.sin(2*x) + 0.3*x
xtr = np.sort(rng.uniform(-3, 3, n)); ytr = truth(xtr) + sigma*rng.normal(size=n)
xte = rng.uniform(-3, 3, 4000); yte = truth(xte) + sigma*rng.normal(size=4000)
def feats(x, d, seed=0):
r = np.random.default_rng(seed)
W = r.normal(0, 1.0, d); b = r.uniform(0, 2*np.pi, d)
return np.cos(np.outer(x, W) + b) * np.sqrt(2.0/d)
print(f"{'d':>5} {'train':>10} {'test':>12} {'||w||':>12}")
for d in (2, 5, 10, 20, 35, 39, 40, 41, 45, 60, 100, 200, 400):
Ztr, Zte = feats(xtr, d), feats(xte, d)
w, *_ = np.linalg.lstsq(Ztr, ytr, rcond=None) # min-norm when d > n
tr = np.mean((Ztr@w - ytr)**2); te = np.mean((Zte@w - yte)**2)
print(f"{d:5d} {tr:10.5f} {min(te,1e6):12.4f} {np.linalg.norm(w):12.3f}")
print("\\nwith ridge alpha = 1e-2:")
for d in (20, 39, 40, 41, 60, 200, 400):
Ztr, Zte = feats(xtr, d), feats(xte, d)
w = np.linalg.solve(Ztr.T@Ztr + 1e-2*np.eye(d), Ztr.T@ytr)
print(f"{d:5d} test {np.mean((Zte@w - yte)**2):10.4f} ||w|| {np.linalg.norm(w):8.3f}")2. Three regimes. Below \(d\approx20\), classical behaviour: test error falls as bias drops. Approaching \(d=n=40\) test error explodes, often by two or three orders of magnitude, and \(\|\vw\|\) explodes with it. This is the interpolation threshold: the model has exactly enough freedom to fit all \(n\) points and no freedom to spare, so the unique interpolating solution is forced through every noisy point with enormous coefficients — \(\mZ\) is square and typically horribly ill-conditioned (Phase A Lecture 11).
Then, past \(d=n\), test error falls again, often below the first minimum, and keeps
improving to \(d=400\). That is the second descent. The reason: with \(d>n\) there are infinitely many
interpolating solutions, and lstsq returns the minimum-norm one. Having more features
gives the minimum-norm solution more room to be smooth, so \(\|\vw\|\) actually decreases as \(d\)
grows past \(n\).
3. Ridge removes the spike almost entirely. Test error becomes essentially monotone decreasing in \(d\), flattening out. The peak was never really about capacity — it was about the ill-conditioning of a square \(\mZ\), and \(\alpha\mI\) puts a floor under the small eigenvalues (Lecture 06). This is the most practically important part of the exercise: double descent is a phenomenon of unregularised minimum-norm interpolation, and a properly tuned regulariser makes it disappear.
4. Is the decomposition wrong? No. It is an identity, proved above with no assumptions beyond the existence of the moments, and it holds at every \(d\).
What is wrong is the folk theory attached to it: "variance increases monotonically with the number of parameters". That was always a heuristic about a particular family of models, never a theorem. In the overparameterised regime, variance is controlled by the implicit bias of the estimator — here, the minimum-norm preference — and not by the parameter count. Adding parameters can reduce variance by giving that implicit preference more scope.
This matters because it is the honest resolution of "how can a network with a billion parameters generalise". Not "the bias–variance tradeoff is wrong", but "parameter count is a bad proxy for the complexity term, and the right notion of capacity depends on what the training procedure implicitly prefers". Phase C takes this up properly, and it is worth flagging that the theory here is still active research rather than settled.
Next: Part IV. We leave supervised learning. Lecture 08 derives PCA three different ways and shows all three give the same answer — the top eigenvectors of the covariance matrix.