The K-Fold Cross-Validation Algorithm

Why Cross-Validation Reuses the Data Carefully

A single train-test split evaluates a prediction procedure on one held-out portion of the data. Its result can depend on which observations landed in that portion. K-fold cross-validation repeats the holdout idea in a structured way: divide the observations into \(K\) groups, fit the procedure \(K\) times, and use each group once as the held-out data. Combining the resulting held-out predictions gives one estimate of predictive performance.

The key is that an observation's cross-validation prediction must come from a fit that did not use that observation. The method does not simply measure how closely a model fits the same data used to estimate it. Instead, it assembles predictions made on held-out observations, then scores those predictions using a chosen loss.

Definition: Let a data set contain \(n\) observations, indexed \(1,\ldots,n\). A \(K\)-fold partition is a collection of nonempty, nonoverlapping sets of observation indices \(F_1,\ldots,F_K\) whose union is \(\{1,\ldots,n\}\). For fold \(k\), the training indices are the complement \(T_k=\{1,\ldots,n\}\setminus F_k\). Fit the specified prediction procedure using observations in \(T_k\), and use that fit to predict the outcomes for observations in \(F_k\). Each observation is held out exactly once.

Usually, folds are made approximately equal in size, but equal sizes are not required for the algorithm. The full set of observations is partitioned first; then the procedure is fitted separately \(K\) times. In every fit, all folds other than the current held-out fold are available for training. A reproducible random seed, when random assignment is used, helps make the partition repeatable.

The Algorithm and Its Score

For observation \(i\), write \(y_i\) for its observed outcome. If \(i\in F_k\), denote its prediction from the fit trained on \(T_k\) by \(\hat{y}_i^{(-k)}\). The superscript indicates that fold \(k\) was left out of that fit. The collection of these predictions is often called the set of out-of-fold predictions: every observation has one, and none is produced by a fit trained on that observation.

The steps below describe the algorithm for a regression prediction task. The fitting procedure can be a regression model or another specified method that produces predictions. Choose a loss that matches the evaluation question. For squared-error loss, the pooled cross-validated mean squared error (MSE) is the average squared difference between observed outcomes and their out-of-fold predictions.

\text{CV MSE}=\frac{1}{n}\sum_{k=1}^{K}\sum_{i\in F_k}\left(y_i-\hat{y}_i^{(-k)}\right)^2

The corresponding root mean squared error (RMSE) is the square root of the MSE. If outcomes are measured in a particular unit, MSE is in squared outcome units and RMSE is in the original outcome units. For fold \(k\), let \(n_k\) be its number of observations and let \(\text{MSE}_k\) be the average squared error within that fold. The pooled score can also be written as a size-weighted average of fold scores:

\text{CV MSE}=\sum_{k=1}^{K}\frac{n_k}{n}\text{MSE}_k

This weighting matters when the fold sizes differ. Taking a simple average of fold MSEs gives each fold equal weight, even if one fold contains fewer observations. The pooled definition instead gives each held-out observation equal weight.

Partition the observations.
Choose \(K\) nonempty folds that together contain every observation exactly once.

Fit once per fold.
For each \(k\), fit the specified prediction procedure using the observations in \(T_k\), excluding all observations in \(F_k\).

Predict the held-out fold.
Use the fit from Step 2 to predict every outcome in \(F_k\), and record those out-of-fold predictions.

Combine and score.
After all \(K\) fits, calculate the chosen loss from the out-of-fold predictions. For MSE, pool the squared errors over all \(n\) observations and divide by \(n\).

Worked Examples

Worked Example: Pooling Squared Errors Across Three Folds

Suppose a hypothetical data set has six observations and is divided into three folds: \(F_1=\{1,2\}\), \(F_2=\{3,4\}\), and \(F_3=\{5,6\}\). A specified regression procedure is fitted three times, each time leaving out one fold. The following table gives the resulting out-of-fold predictions. Outcomes and predictions are in hypothetical outcome units.

Observation	Fold held out	Observed outcome \(y_i\)	Out-of-fold prediction	Squared error
1	1	3	1	\((3-1)^2=4\)
2	1	5	4	\((5-4)^2=1\)
3	2	4	5	\((4-5)^2=1\)
4	2	7	4	\((7-4)^2=9\)
5	3	6	4	\((6-4)^2=4\)
6	3	8	8	\((8-8)^2=0\)

Each prediction was produced by a fit that excluded the observation being predicted. The sum of the six squared errors is \(4+1+1+9+4+0=19\) outcome-units squared. Therefore,

\text{CV MSE}=\frac{19}{6}=3.167\text{ outcome-units squared}

Taking the square root gives \(\text{CV RMSE}=\sqrt{19/6}\approx 1.780\) outcome units. In this hypothetical evaluation, the pooled squared prediction error averages 3.167 squared outcome units per held-out observation; the RMSE expresses the typical error scale in the original outcome units. It does not imply that every prediction is within 1.780 units of its outcome.

Worked Example: Weighting Unequal Fold Sizes

A hypothetical data set of eight observations is partitioned into folds of sizes 3, 3, and 2. Suppose the squared errors from the three held-out fits are as follows: fold 1 has errors \(1,4,0\); fold 2 has errors \(9,1,4\); and fold 3 has errors \(16,0\). Calculate the pooled cross-validated MSE.

The fold-specific MSEs are

\text{MSE}_1=\frac{1+4+0}{3}=\frac{5}{3},\qquad \text{MSE}_2=\frac{9+1+4}{3}=\frac{14}{3},\qquad \text{MSE}_3=\frac{16+0}{2}=8.

Weighting each fold by its share of the eight observations gives

\text{CV MSE}=\frac{3}{8}\left(\frac{5}{3}\right)+\frac{3}{8}\left(\frac{14}{3}\right)+\frac{2}{8}(8) =\frac{5+14+16}{8}=\frac{35}{8}=4.375.

The same result follows by adding all eight squared errors and dividing by eight: \(35/8=4.375\) squared outcome units. By contrast, the unweighted average of the three fold MSEs would be \(\left(5/3+14/3+8\right)/3=43/9\approx4.778\), which gives the two-observation fold the same influence as either three-observation fold. That is not the pooled, observation-weighted MSE.

Worked Example: Using Mean Absolute Error Instead

The fold procedure does not depend on squared-error loss. Suppose eight hypothetical observations have been divided into four folds of two observations each. Their absolute errors, computed from the held-out predictions, are respectively \(1,2\) in fold 1; \(0,3\) in fold 2; \(2,1\) in fold 3; and \(4,0\) in fold 4. The pooled mean absolute error (MAE) is the average absolute error over all eight held-out predictions:

\text{CV MAE}=\frac{1+2+0+3+2+1+4+0}{8} =\frac{13}{8}=1.625\text{ outcome units}.

For a fold-based calculation, the four fold MAEs are \(3/2\), \(3/2\), \(3/2\), and \(4/2=2\). Since all four folds have the same size, their unweighted average is \((1.5+1.5+1.5+2)/4=1.625\), agreeing with the pooled MAE. If fold sizes differed, the fold MAEs would need to be weighted by fold size to reproduce the pooled result.

MAE penalizes an error according to its absolute size, whereas MSE squares the error and therefore gives larger errors more weight. The scoring rule should be selected to reflect the prediction task; this example illustrates the calculation, not a rule that one loss is always preferable.

Why the Estimate Is Useful, and What It Represents

Each observation contributes a held-out prediction, so the final score summarizes performance across the complete set of observations rather than only one test fold. The model is refitted for every fold because leaving out a different group changes the training data. This is the defining computational feature of K-fold cross-validation; it is not one model fit followed by \(K\) evaluations of that same fit.

The score estimates how the specified fitting procedure performs on observations not used for the corresponding fit, under conditions similar to the evaluation data. Its relevance depends on the data and task. Observations should be suitable representatives of the population or prediction setting of interest, and the partitioning must respect the way observations were collected. For example, if observations are dependent in a way that makes a random partition inappropriate, the resulting score may not represent the intended prediction task. Cross-validation itself does not repair an unsuitable data design.

The cross-validation fits use fewer observations than the full data set: each fit uses \(n-n_k\) observations. Consequently, the score directly evaluates the procedure trained on those fold-specific training sets, not the performance of a final fit trained on all \(n\) observations. The estimate is informative for assessing predictive performance, but it is not a promise that a future set of predictions will have exactly that error.

For a regression prediction task, the ordinary regression assumptions used for inference are not automatically required just to calculate a cross-validation score. The calculation requires observed outcomes, a procedure that can be fitted on each training set, predictions for the held-out observations, and a defined loss. However, whether the resulting estimate answers the intended scientific or practical question depends on the suitability of the observations, partition, and prediction procedure.

Common Mistakes

Scoring predictions from a fit that used the held-out outcomes. Those are not held-out predictions. For fold \(k\), every observation in \(F_k\) must be excluded from the fit that predicts it.
Fitting only once. K-fold cross-validation requires \(K\) fits, one for each training set \(T_k\). Each fit has a different held-out fold.
Averaging fold scores equally when fold sizes differ. The pooled MSE weights each fold by \(n_k/n\); an unweighted average can give observations unequal influence.
Confusing MSE and RMSE units. MSE is measured in squared outcome units. RMSE is measured in outcome units because it is the square root of MSE.
Interpreting the score as guaranteed future error. It is an estimate based on held-out predictions under the data and partition used, not a guarantee for every future sample or prediction.

Key takeaway: Partition the observations into \(K\) folds, fit on the complement of each fold, predict that fold, and combine all held-out losses. For MSE, pool squared errors across observations or equivalently take the fold-size-weighted average of fold MSEs.

Check Your Understanding

Answer these questions by tracing the held-out observations and the scoring calculation.

In a five-fold run, how many times is the specified prediction procedure fitted, and how many times is each observation held out?
Why must the fit used to predict an observation exclude that observation?
Three folds have sizes 4, 4, and 2, with fold MSEs 2, 3, and 5. Write the size-weighted expression for the pooled CV MSE.
If the CV MSE is 9 squared outcome units, what is the CV RMSE, and what are its units?
Does K-fold cross-validation directly measure the performance of a fit trained on all \(n\) observations? Explain briefly.