Intermediate30 min

Cross-Validation

k-fold, stratified, leave-one-out and nested CV, with the bias–variance trade-off in choosing k.

Assumes you know

Train, Validation and Test Splits

Cross-Validation

Intuition first

A single validation split gives you one number, and that number depends on which rows happened to land in it. With a few hundred validation examples, the luck of the draw can shift accuracy by several points — enough to pick the wrong model.

Cross-validation removes the luck by rotating the role of the validation set. Split the data into $k$ parts. Train on $k-1$ of them, validate on the one left out, and repeat until every part has served as validation exactly once. Average the $k$ scores.

You get two things out of it. A more stable estimate, because it averages over $k$ different splits. And a sense of how unstable your model is, because the spread of the $k$ scores tells you how much the answer depends on the sample.

The price is $k$ times the compute.

k-fold cross-validation

5-fold cross-validation. Each row is one fit; the shaded block is the fold held out for validation. Every example is validated exactly once and trained on four times.

\text{CV}_k = \frac{1}{k}\sum_{j=1}^{k} \hat{R}^{(j)}

where $\hat{R}^{(j)}$ is the error on fold $j$ from the model trained without it.

Notation used in this lesson
Symbol	Meaning	Read aloud
k	Number of folds	k
n	Number of examples	n
R̂⁽ʲ⁾	Error measured on fold j	R hat superscript j
CVₖ	Cross-validated error, averaged over folds	C V k
SE	Standard error across folds, a measure of stability	standard error

Choosing k

The choice is itself a bias–variance trade-off, on the estimate rather than the model.

k	Training set per fit	Bias of estimate	Variance of estimate	Cost
2	50% of data	High (pessimistic)	Low	2 fits
5	80%	Moderate	Moderate	5 fits
10	90%	Low	Moderate	10 fits
n (LOOCV)	$n - 1$	Nearly none	Often high	$n$ fits

Small $k$ is pessimistic. Each model trains on much less than the full dataset, so it performs worse than the model you will eventually ship on 100% of the data. The estimate is biased upward in error.

Large $k$ reduces that bias but the $k$ estimates become highly correlated — the training sets overlap almost completely — so averaging them removes less variance than the count suggests.

Leave-one-out cross-validation

Setting $k = n$ leaves out one example at a time.

\text{LOOCV} = \frac{1}{n}\sum_{i=1}^{n} L\big(y_i,\; \hat{f}^{(-i)}(x_i)\big)

Nearly unbiased, since each fit uses $n-1$ examples. Two problems in practice.

First, cost: $n$ model fits. Second, and less obvious, the variance of the estimate is often higher than 10-fold, because the $n$ fitted models are nearly identical — they differ by one example — so their errors are strongly correlated and averaging them cancels little noise.

Why LOOCV can have high varianceAdvanced

Consider averaging $n$ random variables each with variance $v$ and pairwise correlation $\rho$ :

\Var\left(\frac{1}{n}\sum_{i=1}^n Z_i\right) = \frac{v}{n} + \frac{n-1}{n}\rho v

As $n \to \infty$ the first term vanishes but the second tends to $\rho v$ . So the variance of the average is floored by the correlation, no matter how many terms you average.

For LOOCV the fitted models overlap in $n-2$ of their $n-1$ training points, so $\rho$ is very close to 1 and almost no variance reduction occurs. For 10-fold the training sets overlap in about 8/9 of their rows — still correlated, but less so.

There is a genuine exception worth knowing: for linear models fitted by least squares, LOOCV has a closed form that costs a single fit,

\text{LOOCV} = \frac{1}{n}\sum_{i=1}^n \left(\frac{y_i - \hat{y}_i}{1 - h_{ii}}\right)^2

where $h_{ii}$ is the $i$ -th diagonal entry of the hat matrix $H = X(X^{\mathsf{T}}X)^{-1}X^{\mathsf{T}}$ . When it is this cheap, the cost objection disappears — which is why LOOCV is standard for ridge regression and almost nowhere else.

Variants you will need

Stratified k-fold — preserves class proportions in each fold. Always use this for classification; it strictly reduces the variance of the estimate at no cost.

Grouped k-fold — keeps all rows sharing a key (patient, user, document) in the same fold. Required whenever rows are not independent.

Time series split — trains on the past, validates on the immediately following period, and never lets a fold see data from after its validation window.

Time series cross-validation. The training window only ever extends backwards from the validation block, so no fit sees its own future.

Report the spread, not just the mean

The standard error across folds tells you whether a difference between two models is real:

\text{SE} = \frac{s}{\sqrt{k}}, \qquad s = \sqrt{\frac{1}{k-1}\sum_{j=1}^k \big(\hat{R}^{(j)} - \text{CV}_k\big)^2}

Solved problem 1 · Is model B actually better?

Two models are compared with 5-fold cross-validation. Accuracies per fold:

Model A: 0.812, 0.795, 0.834, 0.801, 0.818
Model B: 0.826, 0.781, 0.858, 0.793, 0.847

Which should you choose?

Step 1 — mean for Model A

0.812 + 0.795 + 0.834 + 0.801 + 0.818 = 4.060

\overline{A} = \frac{4.060}{5} = 0.8120

Step 2 — mean for Model B

0.826 + 0.781 + 0.858 + 0.793 + 0.847 = 4.105

\overline{B} = \frac{4.105}{5} = 0.8210

B is ahead by $0.0090$ .

Step 3 — spread for Model A

Deviations from $0.8120$ :

0.0000,\; -0.0170,\; 0.0220,\; -0.0110,\; 0.0060

\text{squares}: 0,\; 2.890\times10^{-4},\; 4.840\times10^{-4},\; 1.210\times10^{-4},\; 0.360\times10^{-4}

\text{sum} = 9.300\times10^{-4}

s_A = \sqrt{\frac{9.300\times10^{-4}}{4}} = \sqrt{2.325\times10^{-4}} \approx 0.01525

Step 4 — spread for Model B

Deviations from $0.8210$ :

0.0050,\; -0.0400,\; 0.0370,\; -0.0280,\; 0.0260

\text{squares}: 0.25,\; 16.00,\; 13.69,\; 7.84,\; 6.76 \;\; (\times 10^{-4})

\text{sum} = 44.54 \times 10^{-4}

s_B = \sqrt{\frac{44.54\times10^{-4}}{4}} = \sqrt{11.135\times10^{-4}} \approx 0.03337

Step 5 — standard errors

\text{SE}_A = \frac{0.01525}{\sqrt{5}} \approx 0.00682, \qquad \text{SE}_B = \frac{0.03337}{\sqrt{5}} \approx 0.01492

Step 6 — compare the difference to its uncertainty

The difference is $0.0090$ . A rough standard error for the difference:

\sqrt{\text{SE}_A^2 + \text{SE}_B^2} = \sqrt{0.00682^2 + 0.01492^2} = \sqrt{4.65\times10^{-5} + 2.226\times10^{-4}} \approx 0.0164

The observed gap of $0.0090$ is only $0.55$ standard errors — well inside noise.

Answer

The 0.9-point advantage is not statistically meaningful: it is about half a standard error of the difference. Model B is also more than twice as variable across folds ( $s_B = 0.033$ versus $s_A = 0.015$ ), meaning its performance depends heavily on which data it sees.

Choose Model A — equal performance within noise, and substantially more stable. When two models tie, prefer the one with lower variance, and after that the simpler one.

Nested cross-validation

If you use cross-validation to select hyperparameters, the resulting CV score is optimistically biased for the same reason a reused validation set is — selection has contaminated it.

Nested CV fixes this with two loops: an inner loop that selects hyperparameters, and an outer loop that evaluates the whole selection procedure on data the inner loop never saw.

python

import numpy as np
from sklearn.model_selection import GridSearchCV, StratifiedKFold, cross_val_score
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC
from sklearn.datasets import make_classification

X, y = make_classification(n_samples=600, n_features=15, random_state=0)

pipe = Pipeline([("scale", StandardScaler()), ("svc", SVC())])
grid = {"svc__C": [0.1, 1, 10, 100], "svc__gamma": ["scale", 0.01, 0.1]}

inner = StratifiedKFold(n_splits=5, shuffle=True, random_state=1)
outer = StratifiedKFold(n_splits=5, shuffle=True, random_state=2)

# Inner loop picks C and gamma; outer loop scores the whole procedure.
search = GridSearchCV(pipe, grid, cv=inner, scoring="accuracy")
scores = cross_val_score(search, X, y, cv=outer, scoring="accuracy")

print(f"nested CV accuracy: {scores.mean():.4f} ± {scores.std(ddof=1)/np.sqrt(len(scores)):.4f}")
print(f"per fold: {np.round(scores, 4)}")

The cost is $k_{\text{outer}} \times k_{\text{inner}} \times |\text{grid}|$ fits — here $5 \times 5 \times 12 = 300$ . Expensive, and the correct thing to do when reporting a number that has to be trusted.

Exercise 1

You have 80 labelled examples — expensive medical annotations. Would you use a single 80/20 split, 10-fold CV, or LOOCV? Justify.

Show solution

Not a single split. A 20% validation set is 16 examples; accuracy on 16 examples has a standard error of roughly

\sqrt{\frac{0.8 \times 0.2}{16}} = \sqrt{0.01} = 0.10

Ten percentage points of noise makes model comparison meaningless, and you cannot afford to sacrifice 16 of 80 examples from training.

10-fold CV is the right default. Each fit trains on 72 examples, every example is used for validation exactly once, and you get a spread across folds to judge stability. Cost is trivial at this scale.

LOOCV is defensible — 80 fits is nothing — and gives slightly less bias. But the fold estimates are near-perfectly correlated, so the variance of the estimate is typically no better than 10-fold, and each fold score is 0 or 1 which makes the spread uninformative. The exception is a linear model with the closed-form shortcut, where LOOCV is free.

Also worth doing at this sample size: repeated stratified 10-fold (say 5 repeats with different seeds), averaging the 50 fold scores, to reduce dependence on one particular partition.

Exercise 2

Explain why cross-validation scores are not an unbiased estimate of the model you finally deploy, even when done correctly.

Show solution

Two separate reasons.

Training set size. Each CV fit trains on $(k-1)/k$ of the data, while the deployed model is refitted on 100%. Since error generally decreases with more data, the CV estimate is pessimistic for the deployed model. With $k = 5$ each fit sees 80% of the data, so the gap can be material on small datasets and is negligible on large ones.

Selection. If any choice — hyperparameters, feature set, algorithm — was made by comparing CV scores, the winning score is optimistically biased, because it is a maximum over noisy estimates. This pushes in the opposite direction to the first effect.

The two biases partially cancel, which is convenient and also means you cannot rely on either dominating. If you need a trustworthy number, use nested CV for the estimate and plain CV for the selection, and report the nested figure.

Next: Hyperparameter Search, which is what the inner loop above was doing, done deliberately.