Model Selection · Machine Learning

01 · Motivation

Why does this matter?

Chapter 02 taught you how to fit a model to a dataset. The question that decides whether your work is worth anything is the next one: does it also work on data it has never seen? A degree-9 polynomial can pass through all ten of your training points and be useless on the eleventh.

Choosing among candidate models, complexities, and regularisation strengths so the chosen one generalises is the whole job of this chapter. Three uncomfortable realities motivate the machinery that follows.

Training error lies

The number you minimise during training is the model’s score on data it has already memorised — an optimistically biased estimate of fresh-data behaviour. The bigger the model, the bigger the lie.

No model wins everywhere

The No Free Lunch theorem says: averaged over all conceivable problems, every learner has the same accuracy. The “best” model is a property of the problem, not the algorithm.

The trade-off is irreducible

Test error splits into bias (wrong on average), variance (jittery sample to sample), and noise (inherent randomness). The first two fight; the third never goes away.

why

The model-selection problem in one sentence

Among many models you could fit — different complexities, feature subsets, regularisation strengths — pick the one whose expected error on unseen data is lowest. Since you don’t have unseen data while choosing, you need honest estimates of that quantity. That is what cross-validation, AIC/BIC, and held-out sets are for.

The No Free Lunch theorem

Before obsessing over the perfect model, a sobering result: we are not shopping for a universal winner.

No Free Lunch (informal)

\frac{1}{|F|}\sum_{f \in F} \text{Acc}_G(L \mid f) \;=\; \frac{1}{2} \quad\text{for every learner } L.

Averaged uniformly over all target functions $f$ , every learner is equally (un)accurate. If $L_1$ beats $L_2$ on some problems, there must be others where $L_2$ beats $L_1$ .

The proof is a one-line counting argument: for every target $f$ where the learner beats chance on the unseen points by margin $\delta$ , there is a mirror target $f'$ that agrees with $f$ on the training data and disagrees on every unseen point — so the learner is beaten by the same $\delta$ . The pair cancels.

read

What NFL really tells you (and what it doesn't)

NFL does not say all algorithms are equally good on the problems you actually care about. Real problems are smooth, low-dimensional, structured — far from random. NFL just kills the dream of a one-algorithm-fits-all winner, and justifies a healthy habit: try several models, compare them honestly, let the data decide.

02 · Intuition

The idea in plain language

Forget formulas for a moment. The whole chapter rests on one image: throwing darts at a bullseye.

The true answer for a test input is the centre of the target. Every time you draw a fresh training set and refit, you throw one dart — the model’s prediction. Over many resamples you accumulate a constellation, and two things describe it:

How far the average dart lands from the centre — the systematic miss. That is bias. A simple model (a line fitting a curve) has high bias: more data won’t help it reach the truth on average.
How spread out the darts are around their own average — the jitter. That is variance. A flexible model (degree-15 on 10 points) has high variance: each new training set flings it somewhere new.

key

The decomposition in one breath

Expected test error $=$ bias² $+$ variance $+$ noise. Three non-negative terms. Noise is fixed by the problem — you can’t fight it. Bias and variance are yours to control: simpler models lower variance but raise bias; more flexible models do the reverse. Picking a model is finding the bottom of their sum.

The U-curve of generalisation

Put model complexity (polynomial degree, number of features, tree depth) on the horizontal axis and error on the vertical. Bias² falls as complexity grows; variance rises; their sum plus noise is a U. On the left the model underfits (bias dominates); on the right it overfits (variance dominates); the sweet spot is in the middle.

!

Training error is not on this graph

Training error falls monotonically as complexity grows — degree-9 through 10 points hits exactly zero. That number is useless for picking a model. The U-curve is the test error: the thing you care about, and the thing you must estimate without peeking at the test set.

The curse of dimensionality

As you add features, the input space’s volume grows exponentially. To densely cover even a fraction of a $D$ -dimensional cube you need on the order of $N^D$ points — real datasets never come close. The geometry turns hostile:

Sparsity

Even with millions of samples, a 100-D space is mostly empty. Every test point sits in a region the training set never visited.

Distance concentration

In high dimensions, all pairs of points end up roughly equidistant. “Nearest neighbour” stops meaning anything.

Variance explosion

More features ⇒ more parameters ⇒ more sample-noise fitted ⇒ higher variance. Adding a useless feature can strictly worsen generalisation unless you regularise.

×

'If a model doesn't work, add more features'

The intuitive move is often exactly wrong. The curse says: drop features, project to a lower dimension, or regularise. More features only help when they carry signal and the sample size scales with them — otherwise you are just buying variance.

The curse is why every technique below exists. Feature selection, regularisation, and dimensionality reduction all say the same thing: trade a little representational power for a lot of statistical stability. And a fourth family — ensembles — bends the curve down instead of sliding along it.

03 · Formalism

Definitions and equations

f: the true (unknown) function generating targets.
t: the observed target $t = f(\mathbf{x}) + \varepsilon$ , with $\mathbb{E}[\varepsilon] = 0$ , $\mathrm{Var}[\varepsilon] = \sigma^2$ .
D: a training set of $N$ i.i.d. samples from $p(\mathbf{x}, t)$ .
yD: the model fitted on $\mathcal{D}$ , evaluated at $\mathbf{x}$ : $y_{\mathcal{D}}(\mathbf{x})$ .
ȳ: the average model $\bar y(\mathbf{x}) = \mathbb{E}_{\mathcal{D}}[y_{\mathcal{D}}(\mathbf{x})]$ — what you’d predict averaging over infinitely many training sets.

The bias–variance decomposition

Compute the expected squared error at a single test point and watch three terms emerge.

Derivation Deriving bias–variance at one point

1 · Split the target

With $t = f(\mathbf{x}) + \varepsilon$ ,

\mathbb{E}\bigl[(t - y_{\mathcal{D}}(\mathbf{x}))^2\bigr] = \mathbb{E}\bigl[(f(\mathbf{x}) + \varepsilon - y_{\mathcal{D}}(\mathbf{x}))^2\bigr].

2 · Expand around the mean model

Add and subtract $\bar y(\mathbf{x})$ inside the bracket:

= \mathbb{E}\bigl[\bigl((f - \bar y) + (\bar y - y_{\mathcal{D}}) + \varepsilon\bigr)^2\bigr].

3 · Cross terms vanish

$\varepsilon$ is mean-zero and independent of $\mathcal{D}$ , and $\mathbb{E}_{\mathcal{D}}[\bar y - y_{\mathcal{D}}] = 0$ by definition of $\bar y$ . So all three cross terms have zero expectation, leaving

\mathbb{E}\bigl[(t - y_{\mathcal{D}}(\mathbf{x}))^2\bigr] = \underbrace{(f(\mathbf{x}) - \bar y(\mathbf{x}))^2}_{\text{bias}^2} + \underbrace{\mathbb{E}_{\mathcal{D}}\bigl[(\bar y(\mathbf{x}) - y_{\mathcal{D}}(\mathbf{x}))^2\bigr]}_{\text{variance}} + \underbrace{\sigma^2}_{\text{noise}}.

tip

How to talk about each term in an oral

Bias — the gap between the truth and the model’s expected prediction. Driven by a hypothesis class that is too small/rigid. Falls as the model gets richer.
Variance — the average squared distance between a single fit and the expected fit. Driven by sensitivity to the sample. Falls with more data, a smaller class, or regularisation.
Noise — $\sigma^2$ , the irreducible floor. No model drives it below zero.

Integrated over the input distribution $p(\mathbf{x})$ you get the same three terms weighted by where the data lives — recognise both the pointwise and integral forms.

Estimating prediction error honestly

The decomposition is theoretical — you can’t compute it without knowing $f$ . What you can do is estimate total error from data. Training error $L_\text{train} = \frac1N\sum_n (t_n - y(\mathbf{x}_n))^2$ is optimistically biased and always falls with complexity — useless alone. The true error $L_\text{true} = \int (f(\mathbf{x}) - y(\mathbf{x}))^2 p(\mathbf{x})\,d\mathbf{x}$ is what you want; the rest of this section replaces that integral with something computable.

Training set

Fits each candidate’s parameters $\mathbf{w}$ by minimising the training loss.

Validation set

Picks among candidates — $\lambda$ , polynomial degree, feature subset. Tunes hyperparameters.

Test set

Locked in a vault. Touched once, at the very end, for a final unbiased number. Peek and it stops being unbiased — no exceptions.

×

The cardinal sin of ML

Using the test set in any way during model selection — peeking, tuning, “one quick check” — taints it. The number it then produces is optimistically biased. The honest fix is brutal: set that test set aside as compromised and find a fresh one.

Cross-validation fixes the wastefulness of a single split. Partition the training pool into $k$ equal folds; for each fold $i$ , fit on the other $k-1$ and score on fold $i$ ; average:

k-fold CV

L_{k\text{-fold}} = \frac{1}{k}\sum_{i=1}^{k} \frac{1}{|D_i|}\sum_{(\mathbf{x}_n, t_n)\in D_i} \bigl(t_n - y_{\mathcal{D}\setminus D_i}(\mathbf{x}_n)\bigr)^2.

Every example validates exactly once and trains in $k-1$ folds. Slightly pessimistic (each fit sees $N(k-1)/k$ samples) but far lower variance than one split. Defaults: $k=10$ ; $k=5$ when fits are costly; $k=N$ (leave-one-out) for tiny data — almost unbiased but slow and high-variance.

Analytical alternatives: $C_p$ , AIC, BIC, adjusted $R^2$

CV refits $k$ times. For huge data or slow models, analytical penalties add a complexity term to the training error and pick the smallest penalised score (largest, for adjusted $R^2$ ):

Criterion	Formula	Notes
Mallows’ $C_p$	$\tfrac1N(\text{RSS} + 2d\,\tilde\sigma^2)$	penalty $\propto$ #params $d$ , calibrated by noise. Small is good.
AIC	$-2\ln L + 2d$	KL distance to the truth (up to constants); $=C_p$ under Gaussian noise.
BIC	$\tfrac1N(\text{RSS} + \ln(N)\,d\,\tilde\sigma^2)$	penalty grows with $\ln N$ — punishes complexity harder, prefers smaller models.
Adjusted $R^2$	$1 - \tfrac{\text{RSS}/(N-d-1)}{\text{TSS}/(N-1)}$	can decrease when a useless feature is added. Large is good.

vs

AIC vs BIC — when to use which

AIC is consistent for prediction — asymptotically picks the lowest-prediction-error model even if the truth isn’t in your candidate set. BIC is consistent for identification — if the true model is in the set, BIC finds it with probability $\to 1$ as $N \to \infty$ . Rule of thumb: predict → AIC, infer → BIC. On borderline cases BIC prefers the simpler model.

Three capacity-control families

Feature selection

Discard features. Filter — rank each feature offline (correlation, mutual information, F-test), keep the top $k$ ; fast but blind to interactions. Wrapper — search subsets by refitting the learner (forward stepwise, backward elimination); honours the real loss, costly. Embedded — selection happens inside the fit (lasso’s $\ell_1$ zeros weights; trees skip unused features).

Regularisation

Keep all features, shrink their weights. Ridge ( $\ell_2$ ) shrinks smoothly, closed-form, keeps all features. Lasso ( $\ell_1$ ) drives some weights to exactly zero (embedded selection), no closed form. The strength $\lambda$ is itself a hyperparameter — tune it on a log grid with CV, then refit.

Dimensionality reduction

Build new features that summarise the space. PCA projects onto the directions of maximum variance. Unlike feature selection it mixes features rather than dropping them.

×

The 'select best by training RSS' trap

Within a fixed size $k$ , comparing subsets by training RSS is fine — same complexity, same bias. But comparing across sizes by training RSS always picks the biggest model. Across sizes you must use CV, $C_p$ , AIC, BIC, or held-out error.

Optional depth PCA in five steps, and four ways it can mislead you

Centre: $\tilde{\mathbf{x}}_n = \mathbf{x}_n - \bar{\mathbf{x}}$ — non-negotiable; PCA finds directions through the centroid.
Covariance: $\mathbf{S} = \tfrac{1}{N-1}\sum_n \tilde{\mathbf{x}}_n\tilde{\mathbf{x}}_n^\top \in \mathbb{R}^{D\times D}$ .
Diagonalise: $\mathbf{S}\mathbf{e}_k = \lambda_k\mathbf{e}_k$ . The eigenvector with the largest eigenvalue is PC1 — the direction of maximum variance; the next-largest orthogonal one is PC2, and so on.
Project: $\mathbf{X}' = \mathbf{X}\mathbf{E}_k$ with $\mathbf{E}_k = (\mathbf{e}_1,\dots,\mathbf{e}_k)$ ; component $k$ captures a fraction $\lambda_k/\sum_i\lambda_i$ of the variance. Pick $k$ at the elbow of the cumulative-variance plot (e.g. 90–95%).
Reconstruct (optional): $\hat{\mathbf{X}} = \mathbf{X}'\mathbf{E}_k^\top + \bar{\mathbf{x}}$ . Lossy by $\sum_{j>k}\lambda_j$ — which is how PCA denoises: throwing away small-eigenvalue directions throws away noise.

Four failure modes: (i) variance ≠ predictive signal — a low-variance but relevant feature gets discarded (consider LDA, or CV the choice of $k$ ); (ii) multiple clusters — the principal axis runs between clusters, hiding the most informative dimension; (iii) nonlinear manifolds — linear projection collapses a Swiss roll wrongly (use kernel PCA, ISOMAP, autoencoders); (iv) cost — diagonalising $\mathbf{S}$ is $O(D^3)$ ; use truncated SVD on $\mathbf{X}$ directly above $D\sim 10^4$ .

Ensembles: bending the trade-off

Every technique so far slides the dial between bias and variance. Ensembles combine many models so the combined error beats any component’s.

Bagging — variance through averaging. If $X_1,\dots,X_B$ are i.i.d. with variance $v$ , then $\mathrm{Var}(\tfrac1B\sum_b X_b) = v/B$ — averaging cuts variance by $B$ without changing the mean. Refits of the same model on the same data are perfectly correlated, not independent, so bagging manufactures approximate independence by bootstrap resampling: draw $B$ samples (with replacement, size $N$ ), fit one model each, and average (or majority-vote):

Bagged predictor

y_{\text{bag}}(\mathbf{x}) = \frac{1}{B}\sum_{b=1}^{B} y^{(b)}(\mathbf{x}), \qquad y^{(b)} \text{ fitted on bootstrap sample } b.

Bias ≈ that of one base model; variance much lower. Shines for unstable base learners — deep trees, neural nets — where small data perturbations cause wildly different fits.

Boosting — sequential bias reduction. Train learners sequentially, each focusing on what its predecessors got wrong; combine by weighted vote. The classic is AdaBoost:

Algorithm AdaBoost, round by round

1 · Initialise

$w_1(n) = 1/N$ for every example. Repeat steps 2–5 for $r = 1,\dots,T$ .

2 · Fit and score

Normalise $p_r(n) = w_r(n)/\sum_j w_r(j)$ , train weak learner $y_r$ on the weighted data, compute the weighted error $\varepsilon_r = \sum_n p_r(n)\,\mathbb{1}[y_r(\mathbf{x}_n)\neq t_n]$ . If $\varepsilon_r \geq 0.5$ , stop — no longer better than chance.

3 · Confidence

\beta_r = \frac{\varepsilon_r}{1-\varepsilon_r}\in(0,1), \qquad \alpha_r = \tfrac12\ln\!\frac{1-\varepsilon_r}{\varepsilon_r} = -\tfrac12\ln\beta_r.

Smaller $\beta_r$ (larger $\alpha_r$ ) means a more reliable learner. Both notations appear in exams.

4 · Re-weight

$w_{r+1}(n) = w_r(n)\,\beta_r^{\,1-\mathbb{1}[y_r(\mathbf{x}_n)\neq t_n]}$ — correctly classified examples are multiplied by $\beta_r < 1$ (down-weighted); misclassified ones keep their weight (relatively up-weighted).

5 · Renormalise and repeat

Rescale the weights to sum to one, then continue with round $r+1$ .

AdaBoost final hypothesis

y_{\text{boost}}(\mathbf{x}) = \mathrm{sign}\!\left(\sum_{r=1}^{T}\alpha_r\,y_r(\mathbf{x})\right) = \arg\max_t \sum_{r=1}^{T}\log\tfrac{1}{\beta_r}\,\mathbb{1}[y_r(\mathbf{x}) = t].

Signed form for binary $\{-1,+1\}$ ; arg-max form (slide notation) for multi-class. Schapire’s theorem: training error decays as $\prod_r 2\sqrt{\varepsilon_r(1-\varepsilon_r)}$ — exponentially in $T$ when each learner has a bounded edge.

	Bagging	Boosting
Targets	variance	bias (and some variance)
Training	parallel	sequential
Best base learner	high-variance, low-bias (deep trees)	weak, high-bias (stumps)
Sample weighting	equal, bootstrap	up-weight errors
Combination	average / majority vote	weighted vote ( $\alpha_r$ )
Noise sensitivity	robust	fragile — can overfit noisy labels

04 · Worked example

Bias, variance, and k-fold CV by hand

Part A · Bias and variance of two learners

The truth is $f(x) = x$ , evaluated at the test point $x = 1$ , with noise variance $\sigma^2 = 0.04$ . Training sets have $N = 4$ points at $x \in \{-1, 0, 1, 2\}$ . Compare Learner A (predicts the mean of the training targets, ignoring $x$ ) and Learner B (OLS line).

Worked example Bias² and variance at x = 1

1 · Learner A — expected prediction

The training mean is $\bar t = \tfrac14\sum_n(x_n + \varepsilon_n) = \tfrac14(-1+0+1+2) + \bar\varepsilon = 0.5 + \bar\varepsilon$ , so $\bar y^A(1) = \mathbb{E}[\bar t] = 0.5$ .

2 · Learner A — bias², variance, total

Bias² $= (f(1) - \bar y^A(1))^2 = (1 - 0.5)^2 = 0.25$ (large — too simple). Variance comes only from $\bar\varepsilon$ : $\mathrm{Var}[\bar\varepsilon] = \sigma^2/4 = 0.01$ . Total $= 0.25 + 0.01 + 0.04 = 0.30$ , dominated by bias.

3 · Learner B — expected prediction

OLS recovers the truth in expectation: $\hat w_1 = 1 + \text{noise}$ , $\hat w_0 = 0 + \text{noise}$ , so $\bar y^B(1) = 0 + 1 = 1 = f(1)$ .

4 · Learner B — bias², variance, total

Bias² $= (1-1)^2 = 0$ . Propagating noise through the OLS variance formula, $\mathrm{Var}[y^B(1)] = (1,1)(\boldsymbol\Phi^\top\boldsymbol\Phi)^{-1}(1,1)^\top\sigma^2 = 0.45\cdot 0.04 = 0.018$ . Total $= 0 + 0.018 + 0.04 = 0.058$ , dominated by noise.

Learner	Bias²	Variance	Noise	Total
A (constant)	0.250	0.010	0.040	0.300
B (linear, OLS)	0.000	0.018	0.040	0.058

Learner A has lower variance but loses by a factor of five on bias. A degree-10 “Learner C” would show the mirror: zero bias, comically large variance. Model selection keeps both small.

Part B · 4-fold CV on 12 points

Twelve points, four candidate degrees, $k = 4$ (3 examples per fold). For each candidate: split into folds $D_1\dots D_4$ , fit on the other nine, score on the held-out three, average the four MSEs, and pick the smallest $L_\text{CV}$ .

Model	Fold 1	Fold 2	Fold 3	Fold 4	$L_\text{CV}$
Degree 1	0.180	0.155	0.171	0.166	0.168
Degree 2	0.062	0.058	0.071	0.067	0.0645
Degree 3	0.041	0.038	0.052	0.047	0.0445
Degree 4	0.044	0.043	0.061	0.058	0.0515

A clean U: degree 1 underfits, degree 3 is the sweet spot, degree 4 begins to overfit. Pick degree 3, then refit on all 12 points for the final model — and only then touch the test set, once.

×

Don't average the chosen parameter values

CV gives you a chosen hyperparameter (degree 3), not a final model — the four fold-fits have different coefficients. Refit the chosen-degree model on the entire training pool. Averaging the fold coefficients throws away $N/k$ of your data and is simply wrong.

05 · Visual explanation

The pictures that make it click

The validation protocol

The discipline drawn out: the test set sits in its vault until the very end, and the loop inside the validation phase is where all the CV work happens.

k-fold CV in motion

For $k = 5$ : each row is one iteration, the amber tile is that iteration’s validation fold, grey tiles are training. Every fold is amber exactly once.

PCA geometry

The cloud is elongated along an axis that has nothing to do with the original coordinates. PCA finds that axis (PC1), the orthogonal one (PC2), and lets you project onto PC1 — discarding PC2 with minimal loss because the data barely varies there. (Provided “what matters” is variance — the caveat from §3.) Both components are drawn from the centroid $\bar{\mathbf{x}}$ , which is why PCA is run on centred data.

06 · Hands-on

Try it yourself

Four labs, each making one idea click by letting you push it around. Push the controls, watch the numbers, then read the takeaway.

Hands-on 1

The bias–variance dartboard

Each Resample draws a fresh training set, refits the chosen model, and plots its prediction at the test point x = 0.6 as one dart. The gold centre line is the truth. Build the constellation, then read how bias (cloud offset) and variance (cloud spread) trade off.

noise σ0.15

0 fits

Bias²

—

Variance

—

Noise σ²

—

Total error

—

Try thisStart on Constant and resample ~20 times — bias is huge, variance tiny. Switch to Linear: the cloud slides toward the centre. Switch to Degree 9: the darts spray everywhere — bias near zero, variance explodes.

TakeawayBias is "where is the cloud centred?"; variance is "how spread is the cloud?". Total error is their sum plus the irreducible noise σ². The winning model keeps both small — the optimum almost never lives at the extremes.

Hands-on 2

Find the bottom of the U-curve

Polynomial regression on a noisy sine. Slide the degree and watch the fit (left), the train and test error across all degrees (right), and the regime verdict. Add training points to see how more data shifts the sweet spot.

degree3

train N20

balanced

Train MSE

0.046

Test MSE

0.043

Best degree (test)

3

Best test MSE

0.043

Try thisWith N = 20, push the degree up one step at a time: train MSE falls monotonically while test MSE dips, then climbs. Now raise N to 60 — the U widens and the best degree drifts higher. More data buys you a bigger model.

TakeawayTraining error is the lie; test error is the truth. They are different functions of complexity, and the minimum of the test curve — not zero training error — is what model selection chases.

Hands-on 3

Walk through k-fold cross-validation

Choose k and step through the folds. Each step turns one fold amber (held out for scoring), refits the polynomial on the grey folds, and records its validation MSE. After all k steps, the averaged CV score is your estimate of test error.

folds k5

poly degree3

step 0 / 5

Current fold MSE

—

Running average

—

Train size

24

Val size

—

Try thisSet k = 5, degree 3, and step through all five folds — per-fold MSEs vary by 20–30%, the natural fold noise, and the average steadies after a few folds. Bump degree to 10 and reset: the per-fold scores turn large and erratic — overfitting, revealed fold by fold.

TakeawayCV gives a distribution of fold scores, not one number; the average is your test-error estimate and the spread is its uncertainty. Every point validates exactly once.

Hands-on 4

Single tree vs bagging vs boosting

Three predictors on the same noisy task: a single shallow stump, a bag of B stumps on bootstrap samples, and a boosted sequence of B rounds. Grow B and watch bagging smooth the noise while boosting builds detail.

ensemble B20

noise σ0.15

Single stump

0.136

Bagging (B)

0.128

Boosting (B)

0.062

Rounds B

20

Try thisAt B = 1 all three are the same crude step. Crank B to 60: bagging smooths into a piecewise-constant blur (variance down, bias flat) while boosting builds a detailed staircase that tracks the truth (bias down). Now raise noise to 0.4 — boosting starts overfitting, bagging shrugs.

TakeawayBagging is the variance killer — it averages independent fits to cancel noise. Boosting is the bias killer — it composes weak learners into something more flexible. They attack the trade-off from opposite sides.

07 · Exam intel

What the exam actually tests

Model selection is short on novel formulas and long on conceptual fluency. Five question shapes recur.

Q1

Derive the bias–variance decomposition

Start from $\mathbb{E}[(t - y_{\mathcal{D}}(\mathbf{x}))^2]$ , add and subtract $\bar y(\mathbf{x})$ , expand the square, and argue all cross-terms vanish ( $\varepsilon$ mean-zero and independent; $\bar y - y_{\mathcal{D}}$ mean-zero by definition). End with $\text{Error} = (f-\bar y)^2 + \mathbb{E}_{\mathcal{D}}[(\bar y - y_{\mathcal{D}})^2] + \sigma^2$ . Bonus: name the irreducible term (noise) and the two you control.

Q2

Compare the validation strategies

Method	Bias of estimate	Variance	Cost
Hold-out	moderate (small train)	high (one split)	1 fit
$k$ -fold ( $k=10$ )	small	low	$k$ fits
Leave-one-out	almost zero	high	$N$ fits

“Use LOO because it’s unbiased” loses marks unless you also flag its high variance and $N$ -fit cost.

Q3

State No Free Lunch and its consequence

Averaged over all targets, every learner has accuracy $\tfrac12$ . One-sentence proof: for any $f$ beaten by the learner by $\delta$ , a mirror $f'$ (agreeing on train, disagreeing on test) beats it by $\delta$ ; the pair cancels. Consequence: no universal best model — selection is a matching problem between inductive bias and problem structure.

Q4

Bagging vs boosting — when does each help?

Bagging reduces variance — use with high-variance/low-bias bases (deep trees, nets); useless on already-stable biased learners; robust to noisy labels. Boosting reduces bias — use with weak, high-bias bases (stumps); sensitive to label noise (errors gain weight); sequential, so not parallelisable. Random forests = bagging trees with feature subsampling; gradient boosting = boosting generalised to any differentiable loss.

tip

Memorise five identities and you have the chapter

Bias–variance: $\text{Error} = \text{Bias}^2 + \text{Variance} + \sigma^2$ .
$k$ -fold CV: $L_\text{CV} = \tfrac1k\sum_{i=1}^k L(D_i;\,\mathcal{D}\setminus D_i)$ .
AIC $= -2\ln L + 2d$ ; BIC $= -2\ln L + d\ln N$ (penalises harder).
PCA: eigenvectors of $\mathbf{S} = \tfrac1{N-1}\sum (\mathbf{x}_n-\bar{\mathbf{x}})(\mathbf{x}_n-\bar{\mathbf{x}})^\top$ ; variance of component $k$ is $\lambda_k/\sum_i\lambda_i$ .
AdaBoost confidence: $\alpha_r = \tfrac12\ln\!\frac{1-\varepsilon_r}{\varepsilon_r}$ .

08 · Common mistakes

Where students get this wrong

×

Tuning on the test set

The most common (and career-ending) ML mistake. “I’ll just try a few $\lambda$ and keep the best test accuracy” turns the test set into a validation set; the final number is optimistic by an unknown amount. Physically separate the test set from the tuning loop — once tuned on, it is burned.

×

Random k-fold on time-series data

Random folds assume exchangeable samples. Time series aren’t — tomorrow depends on today. Random permutation lets the model “see the future” during training and wildly over-estimates generalisation. Use forward-chaining CV: fold $i$ trains on $1..t_i$ and validates on $t_i+1..t_{i+1}$ . Same caveat for spatially autocorrelated data.

×

Reporting plain R² as a selection metric

Plain $R^2$ increases monotonically as you add features — by construction a training-set quantity. Use adjusted $R^2$ , $C_p$ , AIC, BIC, or out-of-sample error. Forgetting “adjusted” is the classic slip when comparing nested linear models.

×

'PCA is a feature-selection method'

It isn’t. PCA replaces features with linear combinations of all of them — each component is a weighted sum across every input. You don’t drop features, you mix them. Lasso, forward stepwise, and best-subset are what return an actual subset.

×

Doing PCA (or scaling) before the split

Principal components — and feature means/standard deviations — must be learned on the training data only, then applied to the test set. Fitting them on the whole dataset lets test samples influence the very axes they’re projected onto: a subtle but real leak.

×

'Adding more features can only help'

False. More features enlarge the hypothesis space — lower bias, higher variance — and if they carry no signal you’ve bought variance for nothing. Adding random noise columns reliably degrades an unregularised model. That is the curse of dimensionality in one sentence.

×

Confusing bagging with boosting

Both vote, and that’s where the similarity ends. Bagging fits in parallel, models independent, targets variance, tolerates noise. Boosting fits in sequence, each model depends on the previous one’s errors, targets bias, is fragile to noise. Mixing them up is the fastest way to lose marks here.

×

Assuming AIC and BIC always agree

They are almost never equal and often disagree on borderline models — and consistently, BIC prefers the simpler model because its $\ln N$ penalty grows with sample size. If asked to compute both, expect disagreement and explain which you’d trust (predict → AIC, infer → BIC).

09 · Self-check

Can you answer these?

Four questions in the style the chapter likes to be tested. Click an option for instant feedback.

You fit a degree-9 polynomial on 10 points and get training MSE = 0. What do you also know?

Your bias² is 0.10, variance is 0.30, and noise variance is 0.05. Which intervention is most promising?

You used 10-fold CV to pick λ for ridge. Once λ* is chosen, what is the correct next step?

Your base learner is a decision stump (depth-1 tree): high bias, very low variance. Which ensemble helps most?

10 · Recap

One-screen summary

Chapter 04 — load-bearing ideas

No Free Lunch. Averaged over all problems, every learner ties. Model selection matches the model’s inductive bias to the problem’s structure — not a search for a universal winner.
Bias–variance decomposition. $\text{Error} = \text{Bias}^2 + \text{Variance} + \sigma^2$ ; three non-negative terms, the first two trading off with complexity, the third the irreducible floor.
The U-curve. Training error falls monotonically; test error dips then climbs. Selection finds the bottom of the U — and you must estimate it without peeking at the test set.
Train / validation / test. Train fits parameters, validation tunes hyperparameters, test reports once. $k$ -fold CV replaces a single split with $k$ rotating ones, averaging out split noise.
Analytical criteria. $C_p$ , AIC ( $-2\ln L + 2d$ ), BIC ( $-2\ln L + d\ln N$ ), adjusted $R^2$ . BIC penalises harder; AIC for prediction, BIC for identification.
Curse of dimensionality. Volume explodes in $D$ ; sparsity, distance concentration, and variance explosion degrade performance unless $N$ scales. Signal-free features make it worse.
Three capacity knobs. Feature selection (filter / wrapper / embedded), regularisation (ridge / lasso), dimensionality reduction (PCA) — all slide along the U-curve.
Bagging = variance killer. Bootstrap, fit independent models, average; best with high-variance bases. Variance scales like $1/B$ for independent fits.
Boosting = bias killer. Sequential weak learners on re-weighted data. AdaBoost: $\beta_r = \varepsilon_r/(1-\varepsilon_r)$ , update $w_{r+1}(n) = w_r(n)\,\beta_r^{1-\mathbb{1}[\text{wrong}]}$ , vote $\arg\max_t\sum_r\log(1/\beta_r)\mathbb{1}[y_r(\mathbf{x})=t]$ . Best with high-bias bases; fragile to label noise.

→

Looking ahead → Chapter 05

We’ve measured generalisation empirically. Next we ask whether it can be guaranteed in theory — PAC learning, hypothesis-space complexity, and the VC dimension that bounds how much data a model class needs.