Cross-validation

The idea

A single train/test split gives you one noisy measurement of generalization error — which points landed in the test fold changes the number, badly so on small data. Cross-validation buys a better estimate by recycling the data: split into $k$ folds, train $k$ models each with a different fold held out, average the $k$ held-out scores.

$\widehat{\text{Err}}_{CV} = \frac{1}{k}\sum_{j=1}^{k} \text{Err}_j$

Averaging reduces the variance of the estimate; every observation gets validated exactly once. Two forces set $k$:

• Bias: each model sees only $\frac{k-1}{k}$ of the data, so CV error is slightly pessimistic. Bigger $k$ ⇒ less bias.
• Variance and cost: as $k \to n$ (leave-one-out), the $n$ training sets are nearly identical, the fold errors become highly correlated, and averaging correlated errors does not shrink variance much — while costing $n$ fits. $k = 5$ or $10$ is the standard sweet spot.

Variants that matter:

• Stratified k-fold preserves class ratios per fold — mandatory with imbalance, or some folds may have almost no positives.
• Group k-fold keeps all rows of one entity (user, patient, session) in the same fold; otherwise the model memorizes entities, not patterns.
• Time-series split (expanding or rolling window): train only on the past, validate on the future. Random folds on temporal data are leakage by construction.
• Nested CV wraps hyperparameter search in an inner CV and scores the tuned procedure on outer folds it never saw. Quote the outer score; the best inner score is selection-biased upward.

The classic trap: preprocessing fit on the full dataset before splitting. Scalers, imputers, target encoders, feature selection, SMOTE — all of it must be fit inside each training fold (use a pipeline), or validation folds contaminate training and every score inflates.

Worked example

A 5-fold CV run returns accuracies:

$0.81, \quad 0.79, \quad 0.84, \quad 0.80, \quad 0.83$

Mean: $\bar{a} = 4.07 / 5 = 0.814$. Sample standard deviation: deviations $(-0.004, -0.024, +0.026, -0.014, +0.016)$, squared sum $0.00172$, so $s = \sqrt{0.00172/4} \approx 0.021$. Report 0.814 ± 0.021, not "0.84" (the best fold) and not "81.4%" with false precision.

Why the spread matters: suppose a competing model scores folds $0.83, 0.84, 0.81, 0.85, 0.82$ — mean $0.83$. The gap between models ($0.016$) is smaller than the fold-to-fold noise ($\approx 0.02$), so this comparison is not yet decisive; compare per-fold differences (both models on the same folds) or use repeated CV before declaring a winner. A hiring-loop favorite: "model A got 81.4, model B got 83.0 — which do you ship?" The right answer starts with "what is the variance?"

Cheat sheet

Procedure: $k$ folds → train on $k-1$, validate on 1, rotate; report mean ± std of fold scores.

• $k$ up ⇒ bias down, compute up, and (near $k = n$) estimate variance can rise because folds are correlated.
• LOOCV special case: for linear smoothers (OLS, ridge) it has a closed form — no refitting needed.
• Preprocessing (scaling, imputation, encoding, feature selection, resampling) goes INSIDE the fold via a pipeline. SMOTE-before-split is the canonical inflated-score bug.
• The best CV score after a search is optimistic; only outer/nested or test-set scores are quotable.
• After selecting the model/hyperparameters, refit on ALL training data for deployment — CV models are throwaways.
• CV estimates the error of the procedure, not of one fitted model — that is the subtlety behind most CV interview traps.