Cross-Validation

• Explain why a single validation split can give a noisy, unreliable estimate of a model's true performance, especially with limited data.
• Describe the k-fold cross-validation procedure precisely, including how the final performance estimate is computed.
• Trace a concrete 5-fold cross-validation run by hand on a small dataset.
• Explain leave-one-out cross-validation as the extreme case of k-fold, and the tradeoff it makes between bias and computational cost.

training-test-and-validation-splits, earlier in this discipline, introduced holding out a single validation set to compare candidate models or hyperparameters (like the regularization strength λ from the previous concept). That single split has a real weakness: with a limited amount of data, which particular examples happen to land in the validation set can meaningfully affect which model looks best — an unlucky split might make a genuinely good model look mediocre, or vice versa. Cross-validation fixes this by using every example for validation exactly once, across several different splits, and averaging the results into a single, more reliable estimate.

This is also a direct, statistical instance of a technique already covered in this curriculum: foundations/probability-statistics's sampling-and-sampling-distributions established that any single sample-based estimate carries sampling variability — cross-validation is exactly the practice of averaging over multiple samples to reduce that variability, applied specifically to model evaluation.

The k-fold procedure

K-fold cross-validation partitions the training data into k equally sized, disjoint folds. For each of the k folds in turn, the model is trained on the other k−1 folds and evaluated on the held-out fold; this produces k separate performance scores, one per fold. The final cross-validation estimate is the average of these k scores. Crucially, every example is used for validation exactly once (in whichever fold it belongs to) and for training k−1 times (in every fold except its own) — so the final average uses every data point's information, rather than relying on a single fixed split.

Choosing k

Common choices are k = 5 or k = 10. Smaller k (like k=5) trains fewer models, is computationally cheaper, but each fold's training set is a smaller fraction of the full data, giving a slightly pessimistic bias to the error estimate. Larger k uses more of the data for training in each fold (less bias), at the cost of training more models overall (more compute), and with some increase in variance between folds since the training sets across folds increasingly overlap.

Leave-one-out cross-validation, the extreme case

Leave-one-out cross-validation (LOOCV) is k-fold with k = N, the total number of examples: each fold holds out exactly one example, training on all the rest. This gives the least-biased possible estimate of out-of-sample performance (each training run uses almost the entire dataset), but requires training N separate models — computationally prohibitive for large datasets, and (for reasons beyond this discipline's scope) can actually have higher variance across runs than moderate k, despite its lower bias, because the N training sets it produces are nearly identical to each other and thus highly correlated.

Example 1: A concrete 5-fold cross-validation run

Suppose 100 examples are split into 5 folds of 20 examples each, and a model's accuracy is measured on each held-out fold:

text
Fold 1 held out: train on folds 2-5 (80 examples), test on fold 1 → 82% accuracy
Fold 2 held out: train on folds 1,3-5 (80 examples), test on fold 2 → 79% accuracy
Fold 3 held out: train on folds 1-2,4-5 (80 examples), test on fold 3 → 85% accuracy
Fold 4 held out: train on folds 1-3,5 (80 examples), test on fold 4 → 81% accuracy
Fold 5 held out: train on folds 1-4 (80 examples), test on fold 5 → 83% accuracy

Cross-validation estimate = (82+79+85+81+83) / 5 = 410/5 = 82.0%

Notice the individual fold accuracies range from 79% to 85% — a single validation split could have reported any one of these numbers depending on luck; the averaged 82.0% is a more stable, trustworthy estimate of the model's true generalization performance.

Example 2: Using cross-validation to choose a hyperparameter

Applying 5-fold cross-validation to compare three ridge regression penalty strengths (from the previous concept) on the same data:

text
λ = 0.1:  cross-validation accuracy = 79.5%
λ = 1.0:  cross-validation accuracy = 83.2%  ← best average across all 5 folds
λ = 10:   cross-validation accuracy = 76.8%

λ = 1.0 is chosen because it has the best average performance across folds — a far more reliable basis for choosing a hyperparameter than a single train/validation split, which is exactly the scenario Example 1 showed to be noisy.

• "Cross-validation eliminates the need for a separate test set." It does not — cross-validation is still a form of model/hyperparameter selection performed using only the training data (split internally into folds); the final, held-out test set from training-test-and-validation-splits, touched exactly once, is still required to report an honest final performance number uncontaminated by the selection process.
• "Higher k is always better since it's less biased." Higher k means more computation (training k separate models) and, in the extreme case of leave-one-out, can increase variance across runs due to the high correlation between nearly-identical training sets — k=5 or k=10 are standard defaults precisely because they balance bias, variance, and compute cost reasonably well.
• "The cross-validation score for the winning hyperparameter is an unbiased estimate of that model's true test performance." It is not, for the same many-hypotheses reason flagged since the feasibility-of-learning concept: many hyperparameter values were compared, and the one that happened to score best is now selected — its cross-validation score carries a small optimistic bias from that selection, which is exactly why the untouched test set still matters for the final reported number.

K-fold cross-validation trains and validates a model on k different splits of the same data, averaging the resulting scores into a single, more reliable estimate than any one train/validation split alone — directly applying the same reduce-variability-by-averaging-over-samples logic already established in foundations/probability-statistics. Leave-one-out cross-validation is the extreme case with k equal to the sample size, trading lower bias for higher computational cost and, counterintuitively, sometimes higher variance. Cross-validation improves model and hyperparameter selection, but does not replace the untouched final test set from earlier in this discipline.