Validation and cross-validation

Ten emails sit in a folder, and four of them are spam. You hide two emails, fit a rule on the other eight, and score the rule on the two you hid. If the hidden pair happens to be ordinary mail, a rule that never says spam scores two out of two. If the hidden pair happens to be the two spam messages, the same rule scores zero out of two.

One rule, two estimates, and the difference comes entirely from which rows were hidden. The section question is how to reserve data without wasting it, and the answer has two parts: reserve a set, then rotate the reservation so that every row takes its turn as the hidden set. That rotation is cross-validation, and it is also the chapter's question in miniature, because an honest score can only come from rows that the fitting never touched. !The ten rows of the worked example under five-fold rotation. Each row of the grid is one fit: the shaded pair is held out and scored, the unshaded rows are used for fitting, and the column at the right gives that fold's error. Every data row is shaded exactly once, so the five scores use each row once for scoring and four times for fitting. Their average is the cross-validated error; a single split that held out one fold is the lucky estimate the section opens with. The figure is schematic: the fold assignment and the errors are the section's worked table. Status: schematic.

The plainest method is the validation set approach, which holds back some rows and uses them only for scoring. Split the rows into a training set, the rows the model may fit, and a validation set, fit the model on the first part, and score it on the second [S:50:209]. The validation error then estimates the test error on rows the model has never met [S:50:209]. The method has two costs. The estimate moves whenever the split moves, and the model is fitted on fewer rows than you actually own, which tends to make the estimate pessimistic, meaning it reports a worse error than the full-data model will have [S:50:211]. !Thirty shuffles of the same 24 messages, scored by cross-validation at five fold counts (data/c15.s02.L1.json, seed 20261108). At two folds a single split reports anything from 12.5% to 41.7% and averages 18.6%. At 24 folds every shuffle reports 16.7%, the 4/24 error of the model fitted on all the rows, marked by the dashed line. The spread collapses as the folds rotate, and the price is written above the columns: 2 fits at the left, 24 at the right. Dots stack upward where shuffles report the same score. The data are synthetic: the 24 messages and their labels were written for the lab. Status: synthetic.

Cross-validation attacks both costs by rotating the hidden part. Divide the rows into folds of roughly equal size, fit on all folds but one, score the held-out fold, and repeat until every fold has been held out once [S:50:214]. The reported number is the average of the fold scores weighted by fold size, so a fold with more rows counts more and every row counts once. When the folds are equal, this is the plain average of the scores [S:50:214]. Every row contributes to exactly one score, and the procedure with a single row per fold is called leave-one-out cross-validation [S:50:212].

The number of folds is a dial with three consequences. Few folds give each model a small share of the rows, so the score is pessimistic for the model you will finally fit. Many folds reduce that bias — the systematic gap between the fold estimate and the error of the model fitted on all rows — because each training set then holds almost everything [S:50:212]. The cost is computation and correlation: neighbouring folds share almost all their rows, so their scores move together, and the average of correlated scores is noisier than the number of folds suggests [S:50:217]. Leave-one-out sits at the extreme, with the least bias, the most correlated scores, and as many fits as there are rows [S:50:213].

Cross-validation answers two different questions, and the distinction matters when you report a number. Sometimes you want the value itself, as a forecast of how the chosen procedure will behave on new rows [S:50:216]. At other times you want only the location of the best setting, where a setting is a choice such as how much flexibility to allow. Plot the score against the setting and you get a curve; its lowest point locates the best setting, and its height there estimates that setting's error, which interests you less in the second use [S:50:216]. The first use is a forecast, and the second is a decision, so a report should say which one it is making.

Worked example. Take ten rows and five folds of two rows each, with the fold assignment and the errors below.

The five held-out folds produce 1, 0, 1, 0 and 1 errors, in that order, which gives the arithmetic below. The column headed error? records whether the model got the row wrong, so yes marks an error.

$$\text{CV error}=\frac{1}{5}\left(\frac{1}{2}+\frac{0}{2}+\frac{1}{2}+\frac{0}{2}+\frac{1}{2}\right)=\frac{3}{10}.$$

The cross-validated error is 3/10, while a single split that held out the second fold would have reported 0/2, which is exactly the kind of lucky estimate that started this section. The average is less exciting and more trustworthy than the single split, because each of the ten rows was scored exactly once and used for fitting in the other four rounds.

Think of five examiners who each mark a different fifth of the same pile of scripts, with the rest of the pile available as worked examples. The comparison breaks because the five examiners are not independent: they see almost the same worked examples, so their marks are correlated and agree more closely than five unrelated examiners would. That agreement is why the average is not five independent measurements. Positive correlation makes the variance of the average larger, not smaller, so the fold average carries less information than five independent marks [S:50:217]. It is still steadier than a single split, because every row is scored once and the fold models share most of their training rows.

Cross-validation estimates a procedure, not the single model you will finally ship, because it fits several models and scores each one [S:21:274]. The folds share most of their rows, so the average is not a clean independent sample, and its own error bar — a range saying how far the reported number would move if the rows were drawn again — needs care. When rows arrive in order, random folds let the model see the future, a problem the next section takes up [S:21:276].

The method also costs one fit per fold, which is real money when a single fit takes hours. The recipe therefore matters as much as the number. The fold count, the splitting rule and the metric, meaning the measure you score with, each change the result, and the reported figure should always be read together with that variability [S:50:215].

The formal statement. Fix a learning procedure, meaning a rule that takes rows and returns a fitted predictor. Divide the $n$ rows into folds. For each fold, fit the procedure on the other folds and score the fitted predictor on the held-out fold. The cross-validated risk is

$$\widehat{\mathrm{CV}}=\frac{1}{n}\sum _j{n}_j{\hat{R}}_j,$$

where ${\hat{R}}_j$ is the average loss on fold $j$ and $n_j$ is the number of rows in it. The line weights each fold by its size, so every row counts once and unequal folds still produce a per-row average.

The derivation. Two facts follow from the definition. First, the folds partition the rows, so the weights sum to $n$ and the estimate is an average over rows rather than over folds. Second, the estimate belongs to a procedure fitted on all but one fold, so each training set holds a fraction of the rows and not all of them [S:50:216]. That difference produces the pessimism L1 reports: each training set holds fewer rows than the full dataset, so when the learning curve still slopes at that size, the number is pessimistic for the model you finally fit [S:50:216].

The edge case. The tempting error bar is the standard deviation of the fold scores divided by the square root of the number of folds, and a textbook states that formula for a set of experiments [S:27:290]. It assumes independent scores, and the fold scores are not independent, because the training sets overlap and the fitted models move together. For leave-one-out the overlap is almost total, and the average of highly correlated scores has higher variance than the average of independent ones [S:50:217]. With $K$ equal folds, a common score variance ${\sigma }^2$ and correlation $\rho$ between fold scores, the variance of their average is ${\sigma }^2[1+(K-1)\rho ]/K$, which rises with $\rho$. The formula therefore reports an interval that is too narrow, which is the opposite of the caution L1 asked for.

What L1 hid. L1 said cross-validation estimates a procedure. The formal statement adds which procedure: one fitted on a fraction of the rows. L1 also hid the selection step. When you pick the fold count, the model and the inputs by reading the same cross-validated scores, the winning score is optimistic, and an honest estimate needs an outer loop that never sees the inner choice [S:27:290]. L1 was safe because it reported one procedure fixed in advance.

Where the analogy breaks. The five-examiners analogy suggests five independent measurements whose average is more precise than one. The formal object is one measurement repeated on overlapping training sets, so the scores are positively correlated and their average carries less information than five independent marks. The analogy is safe for the arithmetic of averaging and unsafe for the error bar.

Original sources. Hastie, Tibshirani and Friedman name the key references for cross-validation as Stone (1974), Stone (1977) and Allen (1974) [S:64:276]. They also record that Stone (1977) showed AIC and leave-one-out cross-validation are asymptotically equivalent [S:64:276]. The treatment L1 follows is the resampling chapter of ISL [S:50:209]. The corpus does not contain the three papers, so the text cites them through this pointer and does not quote them.

An open question. Cross-validation gives a point estimate with no agreed interval. The field has not settled how to attach a confidence interval to a cross-validated error, because the fold scores are dependent and the procedure is often chosen on the same data. One textbook gives the standard error of the fold average as the fold standard deviation divided by the square root of the number of folds [S:27:290]. ISL shows that the dependence raises the variance of that average, so the formula understates it [S:50:217]. Evidence that would settle a given case: a nominal 95% interval whose coverage is measured over repeated studies at a fixed number of rows, fold count and procedure, with the selection step included.

A frontier result. Nested cross-validation is the current answer to the selection problem. The inner loop chooses the setting and the outer loop estimates the error of the choosing procedure, so the reported number pays for the search [S:27:290]. It depends on this section's idea twice, because both loops are averages over held-out folds. The cost is a second layer of fits, so the method trades computation for a number that includes the search.

What to read next. Read ISL §5.1 for the validation set, leave-one-out and fold cross-validation, and §5.1.4 for the bias–variance trade-off in the choice of fold count [S:50:209] [S:50:216]. Then read the nested cross-validation section of Mathematics for Machine Learning [S:27:290] and the bibliographic notes in ESL for the original papers [S:64:276].