Cross-Validation and Resampling

The Bias-Variance Tradeoff ended with a diagnostic table that compares training error against test error. That comparison assumes you have a test error. Usually you do not: every observation you own has already been spent on fitting. Resampling methods solve this by repeatedly refitting the model to subsets of the data, and using the held-out parts to estimate performance on data the model has not seen.

A. Why training error is not an estimate of test error

Training error is measured on the same observations used to choose the parameters, so the fitting process has already adapted to whatever noise those points carry. It is therefore biased downward as an estimate of performance on new data, and the bias grows with model flexibility.

That is not a small correction you can ignore. It is precisely the quantity that made the degree-15 polynomial look best in the previous articles while being the worst model of the three. A selection procedure driven by training error will reliably choose the most flexible candidate available.

B. The validation set approach

The simplest fix: split the observations at random into a training set and a validation set, fit on the first, and measure error on the second. Since the validation observations played no part in fitting, the resulting error is an honest estimate.

It has two well-known drawbacks:

1. The estimate is highly variable. It depends on which observations happened to land in the validation set. A different split gives a noticeably different number.
2. It wastes data. Only a subset is used for fitting, and statistical methods generally perform worse on fewer observations, so the validation error tends to overestimate the error of the model you would fit on the full dataset.

C. Leave-one-out cross-validation

LOOCV addresses both. With $n$ observations, hold out a single observation $(x_i, y_i)$, fit on the remaining $n-1$, and predict the one left out. Repeat for every $i$, then average:

$$\mathrm{CV}_{(n)} = \frac{1}{n}\sum_{i=1}^{n} \mathrm{MSE}_i , \qquad \mathrm{MSE}_i = (y_i - \hat y_i)^2 .$$

Each fit uses $n-1$ observations, so there is far less upward bias than a half-sized training set, and because it averages over every possible single-point holdout there is no randomness in the split at all - run it twice and get the same answer.

D. LOOCV worked out completely

The dataset is small enough to do every fold explicitly. Five observations, one predictor:

Fitting a simple linear regression to all five gives $\hat y = 2.2 + 0.6x$ - the fit derived step by step in Linear Regression from First Principles. LOOCV refits it five times, each time omitting one row:

$$\mathrm{CV}_{(5)} = \frac{4.0000 + 0.7347 + 1.5625 + 0.7347 + 0.2500}{5} = \frac{7.2819}{5} = 1.4564 .$$

Compare that with the training MSE of the full fit, which is $\mathrm{RSS}/n = 2.4/5 = 0.48$. The honest estimate, $1.4564$, is three times larger. That gap is exactly the optimism this article opened with.

Notice also fold 1: dropping $(1,2)$ - the point furthest below the line - lets the remaining four pull the fit up, and the prediction misses by 2.0 for a squared error of 4.0, more than half the total. With only five observations, one influential point dominates. This is a genuine property of the estimate, not a defect in the method.

Running it reproduces the table row for row and prints LOOCV MSE: 1.4564, confirming the hand computation.

E. k-fold cross-validation

LOOCV requires $n$ model fits, which is expensive when $n$ is large or fitting is slow. k-fold cross-validation splits the observations into $k$ groups of roughly equal size, holds out each group in turn, and averages:

$$\mathrm{CV}_{(k)} = \frac{1}{k}\sum_{j=1}^{k} \mathrm{MSE}_j .$$

LOOCV is the special case $k = n$. Using $k = 5$ or $k = 10$ needs only 5 or 10 fits instead of $n$.

F. Why k=5 or k=10, and not k=n

The obvious reading is that smaller $k$ is a pure computational compromise. It is not - there is a bias-variance tradeoff in the estimate itself.

Bias favours large $k$. Each LOOCV fit uses $n-1$ observations, almost the full dataset, so it barely overestimates the error. Five-fold fits use only 80% of the data, so they overestimate somewhat more.

Variance favours moderate $k$. In LOOCV the $n$ fitted models are trained on almost identical data - any two differ in just two observations - so their errors are highly positively correlated. Averaging strongly correlated quantities reduces variance far less than averaging weakly correlated ones. With $k = 5$ or $10$ the training sets overlap less, the errors are less correlated, and the average is more stable.

Following James et al., $k = 5$ and $k = 10$ have been shown empirically to give test-error estimates that suffer from neither excessive bias nor very high variance. That is the reason for the convention, and it is an empirical finding rather than a theorem.

G. Two ways to get this wrong

Selecting features before cross-validating. If you screen predictors using the whole dataset and then cross-validate the model built from the survivors, the held-out folds already influenced which features were chosen. The estimate will be optimistic, sometimes dramatically. Every data-dependent choice must happen inside the loop.

Cross-validating dependent observations with a random split. The method assumes held-out observations are independent of the training ones. With time series, repeated measurements on the same subject, or grouped data, a random split leaks information across the boundary. Use a split that respects the structure - forward-chaining for time, grouped folds for clusters.

For classification, everything above carries over with the error measure changed from squared error to the misclassification rate; the logic of the folds is identical.

Key takeaways

• Training error is biased downward as an estimate of test error, and worsens with flexibility, so it cannot be used to select models.
• A validation split is honest but high-variance and wastes data.
• LOOCV averages $n$ single-point holdouts: no split randomness, little bias. On our five-point dataset it gave $1.4564$ against a training MSE of $0.48$.
• k-fold with $k = 5$ or $10$ is the standard compromise - cheaper than LOOCV and empirically better because less correlated fits average more effectively.
• Every data-dependent decision must sit inside the resampling loop, and the fold structure must respect dependence in the data.

What's next

We have used a linear fit as a running example three times now without deriving it. That is the gap to close: Linear Regression from First Principles builds the least-squares estimator from scratch and shows where $\hat y = 2.2 + 0.6x$ came from.