Cross-Validation

Repeatedly fit on one part of the data and score on another. Each observation receives a prediction from a model that did not use that observation for training.

$k$ -Fold Cross-Validation¶

Partition the indices into disjoint nonempty folds $I_1,\ldots,I_k$ , with $n_j=|I_j|$ and $\sum_jn_j=n$ . Let $\kappa(i)$ identify observation $i$ ’s fold.

For each fold $j$ , remove $I_j$ and fit $\widehat f^{(-j)}=A(T\setminus T_j)$ .
Predict the held-out observations in $I_j$ .
Average all held-out losses.

L_j=\frac1{n_j}\sum_{i\in I_j}L(Y_i,\widehat f^{(-j)}(X_i)),

(1)

\boxed{\widehat{\operatorname{Err}}_{\mathrm{CV}} =\sum_{j=1}^k\frac{n_j}{n}L_j =\frac1n\sum_{i=1}^nL(Y_i,\widehat f^{(-\kappa(i))}(X_i)).}

(2)

If all folds are equally sized, this is $k^{-1}\sum_j L_j$ . If they differ in size, weight fold means by their observation counts to obtain average loss per observation.

Round	Fold 1	Fold 2	Fold 3
1	Hold out	Train	Train
2	Train	Hold out	Train
3	Train	Train	Hold out

Every observation is scored once and used for training in $k-1$ rounds. The fitted models differ between rounds.

What Does CV Estimate?¶

For a fixed algorithm and equal folds under iid sampling, each training subset contains $m=n(1-1/k)$ observations, independent of its held-out fold. Therefore

E[\widehat{\operatorname{Err}}_{\mathrm{CV}}]=\operatorname{Err}_m.

(3)

This is average generalization error for a procedure trained on $m$ observations. It is not an exact measurement of the conditional error of the final fit on all $n$ observations. For unequal folds, the expectation is a weighted average of risks at sizes $n-n_j$ .

The folds’ losses are dependent because the training subsets overlap. Their sample standard deviation divided by $\sqrt{k}$ is not generally a justified standard error for the CV score.

Choice	Training size per fit	Main tradeoff
Smaller $k$	Further below $n$	More training-size mismatch; larger held-out folds.
Larger $k$	Closer to $n$	Less training-size mismatch; more fits and strongly overlapping training sets.
$k=n$	$n-1$	Leave-one-out; one scored observation per fit.

The familiar “low bias, high variance” description of leave-one-out is a useful heuristic, not a universal ordering of CV variances. Training-size bias depends on the learning curve, and variance depends on the data and procedure.

Worked Two-Fold Example¶

Use the illustrative observations

$i$	1	2	3	4	5	6
$x_i$	0	1	2	3	4	5
$y_i$	1	2	2	4	4	5
Fold	1	2	1	2	1	2

For a simple intercept-only algorithm, predict the mean of the training responses.

Calculate the Held-Out Losses

To score fold 1, fit on responses $2,4,5$ . The fitted prediction is $11/3$ :

L_1=\frac{(1-11/3)^2+(2-11/3)^2+(4-11/3)^2}{3}=\frac{10}{3}.

(4)

To score fold 2, fit on responses $1,2,4$ . The fitted prediction is $7/3$ :

L_2=\frac{(2-7/3)^2+(4-7/3)^2+(5-7/3)^2}{3}=\frac{10}{3}.

(5)

Thus $\widehat{\operatorname{Err}}_{\mathrm{CV}}=10/3\approx3.3333$ . Fitting the intercept-only rule to all six observations instead gives $\bar y=3$ and training MSE 2. The smaller training score benefits from fitting and scoring the same responses.

Selecting a Tuning Parameter¶

Select

Use validation folds to compare model choices. Refit the winner on all development data.

Assess

Use untouched test data or outer CV to evaluate the complete selection procedure. The winning validation score is not an independent assessment.

For candidates $\lambda\in\Lambda$ , use the same fold assignments and compute

\widehat\lambda=\arg\min_{\lambda\in\Lambda} \frac1n\sum_iL(Y_i,\widehat f_{\lambda}^{(-\kappa(i))}(X_i)).

(6)

Then refit $A_{\widehat\lambda}$ on all available development data. Candidate choices might be neighbour count, polynomial degree, or a regularization parameter.

The minimum CV score was used to select the winner, so it is generally optimistic as an assessment of the complete selection procedure. A final independent test set or nested CV separates selection from assessment.

Nested CV¶

For each outer fold, run all tuning using inner folds of the outer training set. Refit the selected procedure on that outer training set and score the untouched outer fold. Aggregate the outer held-out losses to assess the tuning procedure. After assessment, tune again using the full development data and fit the final rule.

Keep the Whole Procedure Inside the Split¶

Step	Correct location
Imputation and scaling	Learn values on the current training fold, then apply to its held-out fold.
Feature screening or dimension reduction	Fit within the training fold, including supervised selection.
Hyperparameter search	Use validation/inner folds, leaving the assessment set untouched.
Grouped or repeated observations	Keep each dependent group together when evaluating generalization to new groups.
Future prediction from ordered data	Respect time order; train on the past and evaluate later observations.

These are practical extensions of the iid setup. A random split cannot create independence when the observations are dependent.

kkk-Fold Cross-Validation¶

What Does CV Estimate?¶

Worked Two-Fold Example¶

Selecting a Tuning Parameter¶

Nested CV¶

Keep the Whole Procedure Inside the Split¶

$k$ -Fold Cross-Validation¶