k-fold cross-validation

k-fold cross-validation cuts the data into \(k\) roughly equal folds and runs \(k\) rounds. In each round one fold is held out for testing and the model trains on the other \(k-1\); the \(k\) scores are averaged. Every row is used for training \(k-1\) times and for testing exactly once.

With 1,000 samples and \(k = 5\), each round trains on 800 and tests on 200. Five and ten are the usual choices: enough folds that the split stops dominating the answer, few enough that fitting the model \(k\) times is affordable, and each training set still large enough to resemble the full one.

One step before that: shuffle, unless the row order carries meaning. Data sorted by class, by date or by collection batch produces folds that are not exchangeable, and a fold containing one class is not a test set.

The failure that does not announce itself

The rotation only means something if each round’s model has never seen its test fold — including indirectly. Any step fitted on the whole dataset before the folds are drawn has seen everything: scaling that uses the global mean, imputation from the global median, feature selection ranked against all the labels, an encoder built from every category present.

import numpy as np
from sklearn.feature_selection import SelectKBest, f_classif
from sklearn.linear_model import LogisticRegression
from sklearn.model_selection import cross_val_score, KFold
from sklearn.pipeline import make_pipeline

rng = np.random.default_rng(4)
n, p = 120, 3000
x = rng.normal(size=(n, p))
y = rng.integers(0, 2, size=n)
"""Pure noise: the labels are independent of every feature, so the honest score is 0.5."""

selected = SelectKBest(f_classif, k=20).fit(x, y).transform(x)
leaky = cross_val_score(LogisticRegression(max_iter=1000), selected, y,
                        cv=KFold(5, shuffle=True, random_state=0)).mean()
honest = cross_val_score(make_pipeline(SelectKBest(f_classif, k=20), LogisticRegression(max_iter=1000)),
                         x, y, cv=KFold(5, shuffle=True, random_state=0)).mean()
print(f"selection before the split (leaks) {leaky:.4f}")
print(f"selection inside the pipeline      {honest:.4f}")
print(f"the truth                          0.5000")
# selection before the split (leaks) 0.9000
# selection inside the pipeline      0.5333
# the truth                          0.5000

The labels here are drawn independently of every one of the 3,000 features, so the expected accuracy of any model on independent test labels is 0.5. A single run scatters around that value. Selecting the twenty features that correlate best with the labels and then cross-validating gives 0.9000. Doing the selection inside the pipeline, so that each fold selects using only its own training rows, gives 0.5333, within chance variation of 0.5.

The first number is not a bug in the cross-validation; the folds were rotated correctly. The selection step had already looked at the test labels, so the twenty features it kept were the ones that happened to correlate with those particular labels, and every fold inherited that. With 3,000 candidates and 120 rows, some will correlate strongly by chance.

The defense is mechanical: put every fitted step in a Pipeline and pass the pipeline to the cross-validator. Then each fold fits its own scaler, its own imputer and its own selection.

Rows that belong together

The same problem appears without any preprocessing when rows are not independent. Ten readings from one patient, several sessions from one user, repeated photographs of one object — if some land in training and others in testing, the model can recognize the individual rather than the pattern, and the fold boundary has not separated anything.

Group-aware splitters keep every row from a group on one side. Where the classes are also imbalanced, both constraints are needed at once.

Choosing k

Five or ten folds are practical common choices. Leave-one-out uses the largest training sets but requires n fits. Its held-out errors need not be almost perfectly correlated merely because the training sets overlap: a constant predictor evaluated on independent labels is a simple counterexample. Choose the scheme with its computation and estimation properties in mind.

Repeating the whole procedure with different shuffles and averaging is usually a better use of extra compute than raising \(k\), because the split seed moves the answer more than the fold count does — measured under cross-validation. For classification, use the stratified variant as the default.

References

• scikit-learn User Guide, Cross-validation: evaluating estimator performance
• Yoshua Bengio and Yves Grandvalet, “No Unbiased Estimator of the Variance of K-Fold Cross-Validation”, Journal of Machine Learning Research, 5, 2004, 1089–1105