Diagnosing Cross-Validation Bias for Unstable Learners

Why Instability Can Complicate Cross-Validation

Cross-validation evaluates fitted procedures on observations held out from their training sets. For a stable procedure, removing part of the data may have little effect on its predictions. For an unstable procedure, a small change in the training set can change a selected threshold, pruning level, or entire fitted model. The resulting cross-validation score can then describe a meaningfully different training situation from the one of interest: the procedure trained on all $n$ observations.

A useful diagnosis separates two questions. First, does cross-validation target the risk of the procedure trained on a fold-sized sample, rather than the risk at the full sample size? Second, does the particular split reveal marked sensitivity to which observations enter each training set? The first question has a precise answer under independent sampling. The second calls for examining fitted procedures and fold-level errors, not just reporting their average.

Training-Size Risk and the Cross-Validation Target

Definition: Let $Z_1,\ldots,Z_n$ be independent observations with common distribution $F$, and let $A_m$ be a learning procedure that maps a training sample of size $m$ to a predictor. For a loss function $L$, define its training-size-$m$ risk by $$ R_m=E\!\left[L\{A_m(Z_1,\ldots,Z_m),Z_{m+1}\}\right], $$ where $Z_{m+1}$ is an independent test observation. The risk $R_n$ is the expected risk of the procedure trained on all $n$ observations.

The procedure $A_m$ includes every data-dependent step used to produce the predictor. For example, if a pruning rule selects a tree size from the training data, the complete procedure includes that selection. The definition averages over both the random training sample and the independent test observation.

Suppose $n$ is divisible by $K$, and use a fixed partition into $K$ folds of size $v=n/K$. Write $I_k$ for the indices in fold $k$, and let $A_{-k}$ denote the predictor obtained by applying the procedure to the observations outside that fold. The cross-validation score is

\widehat R_{\mathrm{CV}}=\frac{1}{K}\sum_{k=1}^K \frac{1}{v}\sum_{i\in I_k}L(A_{-k},Z_i).

Theorem: If the observations are independent and identically distributed and the fold assignment is fixed independently of their values, then $$ E[\widehat R_{\mathrm{CV}}]=R_{n-v}. $$ Thus the expected score targets risk at the fold training size $n-v$, not necessarily risk $R_n$.

Proof. Fix a fold $k$ and an index $i\in I_k$. The predictor $A_{-k}$ is constructed from the $n-v$ observations outside the fold. By independence, these observations have the same joint distribution as $n-v$ independent draws from $F$, and they are independent of $Z_i$, which also has distribution $F$. Therefore

E[L(A_{-k},Z_i)]=R_{n-v}.

There are $Kv=n$ validation terms, and the weights in the score sum to one. Taking expectations term by term gives

E[\widehat R_{\mathrm{CV}}] =\frac{1}{Kv}\sum_{k=1}^K\sum_{i\in I_k}E[L(A_{-k},Z_i)] =\frac{1}{Kv}(Kv)R_{n-v} =R_{n-v}.

This is an expectation identity; it does not say that a particular observed score equals $R_{n-v}$, nor that $R_{n-v}$ must be larger or smaller than $R_n$. The training-size difference is one precise source of possible bias relative to the full-sample target:

E[\widehat R_{\mathrm{CV}}]-R_n=R_{n-v}-R_n.

Worked Example: A Training-Size Bias From a Triggered Threshold

Let $Y$ be Bernoulli with $P(Y=1)=p=0.2$, and suppose there is no informative covariate. Consider the procedure that predicts 1 for every future case if at least one training response is 1; otherwise, it predicts 0. Use zero-one loss.

For a training sample of size $m$, the probability of predicting 1 is $1-(1-p)^m$. If the procedure predicts 1, its test error probability is $1-p$; if it predicts 0, its error probability is $p$. Therefore

\begin{aligned} R_m &=(1-p)\{1-(1-p)^m\}+p(1-p)^m\\ &=(1-p)+(2p-1)(1-p)^m\\ &=0.8-0.6(0.8)^m. \end{aligned}

For $n=6$ and $K=3$, each fold trains on $m=4$ observations. Hence

E[\widehat R_{\mathrm{CV}}]=R_4=0.8-0.6(0.8)^4=0.55424.

The full-sample procedure has expected risk

$$ R_6=0.8-0.6(0.8)^6=0.6427136, $$

so the expected cross-validation score is lower than the full-sample risk by $0.6427136-0.55424=0.0884736$. Here, the direction follows from the explicit risk calculation: as the training sample grows, the chance of triggering the always-1 prediction increases, which is harmful when $p=0.2$. This direction is not universal; it depends on how the procedure and the data distribution interact.

Training-Set Perturbations as a Diagnostic

A direct way to investigate instability is to perturb the training set and check whether the fitted procedure changes materially. Perturbations can include deleting one observation, adding one observation, or replacing one observation with another plausible draw. For pruning, record whether the selected tree size changes and how its predictions change. For threshold selection, record the chosen threshold and which observations change predicted class.

Prediction changes matter because a model can have different internal form but identical predictions on relevant cases. Conversely, a small-looking change in a threshold can switch many classifications when observations cluster near that threshold. Where possible, evaluate both fits on the same independent probe observations; this holds the evaluation cases fixed so differences can be attributed to the changed training data.

Diagnostic principle: Large changes in fitted predictions or probe-set loss after a small training-set perturbation are evidence of sensitivity. They do not, by themselves, establish the direction or magnitude of cross-validation bias. Bias relative to $R_n$ concerns the difference $R_{n-v}-R_n$, which requires comparing risks at those training sizes.

One formal way to organize this comparison is to couple training samples of successive sizes by taking prefixes of a single independent sequence. If the loss is bounded and the expected risk change from adding one observation is small at every intermediate size, then the total training-size gap is bounded by the sum of those changes.

Theorem: Suppose the loss is bounded and $R_j$ is defined as above for each $j=m,\ldots,n$. If, for each $j=m,\ldots,n-1$, $$ \delta_j=E\left[\left|L\{A_{j+1}(Z_1,\ldots,Z_{j+1}),Z_{j+2}\} -L\{A_j(Z_1,\ldots,Z_j),Z_{j+2}\}\right|\right], $$ then $$ |R_n-R_m|\leq\sum_{j=m}^{n-1}\delta_j. $$

Proof. The test observation $Z_{j+2}$ is independent of both training samples in the definition of $\delta_j$. Consequently, the expectations of the two loss terms are $R_{j+1}$ and $R_j$. The inequality $|E[W]|\leq E[|W|]$, applied to their difference, gives

|R_{j+1}-R_j|\leq\delta_j.

Using the triangle inequality along the sequence of training sizes,

|R_n-R_m| =\left|\sum_{j=m}^{n-1}(R_{j+1}-R_j)\right| \leq\sum_{j=m}^{n-1}|R_{j+1}-R_j| \leq\sum_{j=m}^{n-1}\delta_j.

This bound explains the diagnostic role of perturbations: consistently small changes along the relevant training-size range limit the risk gap. A few observed perturbations cannot prove the population quantities $\delta_j$ are small, however; they are empirical evidence, not a certificate.

Worked Example: One Observation Flips the Fitted Rule

Use the triggered-threshold procedure from the preceding example with $p=0.2$. Consider a training sample of three zeros. The fitted rule predicts 0, so its population test error is $0.2$. Add one observation with response 1. The refitted rule predicts 1, and its population test error is $0.8$. The risk change for this particular perturbation is

$$ 0.8-0.2=0.6. $$

The large change is not caused by a gradual movement in a fitted coefficient: the rule switches discontinuously when the positive observation enters the sample. For a pruning procedure, the analogous warning sign would be a single case changing the selected subtree and changing predictions on a substantial set of probe cases. Such a finding motivates closer investigation of fold assignments and training-size effects; it does not alone determine the expected bias.

Reading Fold-Level Error Patterns

The average cross-validation score can hide a distinctive pattern: one fold may have a very different error rate, or folds may select different pruning levels or thresholds. Inspect the fold-specific score together with the training-set composition, selected model, and errors on that fold. If an unusual observation is in a validation fold, ask whether its presence in another fold’s training set changes the fitted procedure. This connects the error pattern to a concrete perturbation mechanism.

Fold scores are not independent replications: their training sets overlap. Nor is their spread a direct estimate of bias. A high fold error can reflect an unusually difficult validation subset, a training-set perturbation, or both. The observed pattern is most informative when the model changes in a way that explains the errors.

Worked Example: A Fold Pattern With One Positive Case

Take six observed responses $1,0,0,0,0,0$, use the triggered-threshold procedure, and form three folds of size two: fold A contains the positive case and one zero; folds B and C each contain two zeros. Each training set has four observations.

Fold A. Its training set consists of four zeros, so the fitted rule predicts 0. On the two validation cases, it makes one error (the positive case), giving fold error $1/2=0.5$.

Fold B. Its training set includes the one positive response, so the fitted rule predicts 1. Both validation responses are zero; the fold error is $2/2=1$.

Fold C. Its training set also includes the positive response, so it predicts 1 and makes two errors on its two zero responses. Its fold error is again $1$.

The overall score is therefore

\widehat R_{\mathrm{CV}}=\frac{0.5+1+1}{3}=\frac{5}{6}\approx0.8333.

The full-sample fit predicts 1, whose population risk under the specified distribution is $0.8$. This one observed partition has a high score, and the folds exhibit a clear fit change: training sets without the positive case predict 0, while the others predict 1. But $5/6$ is one realized score, not the expectation $R_4=0.55424$ calculated in the earlier example. This example shows why fold patterns can reveal sensitivity while a single split cannot establish the expected bias.

Common Mistakes and Practical Interpretation

Calling every difference from full-sample risk “instability bias.” The exact expectation identity identifies a training-size target. Instability can make the training-size gap important, but its direction must be assessed for the procedure and distribution in question.
Inferring bias from unequal fold scores alone. Fold variation is a clue, not a bias estimate. Examine the fitted rules, validation cases, and which training perturbation could explain the difference.
Treating a model change as automatically consequential. A change in pruning level or threshold matters for prediction risk only insofar as it changes relevant predictions or losses.
Assuming a small perturbation check proves stability. A finite set of observed perturbations may miss rare influential observations or other regions of the training-sample distribution.
Confusing the score for a selected procedure with the score for a fixed procedure. If the same validation results are used both to choose among procedures and to report performance, selection can add another source of optimism. The fixed-procedure expectation identity above does not remove that issue.

A useful report therefore pairs the cross-validation average with fold-specific errors and a record of the fitted choices in each fold. For an unstable learner, also investigate whether plausible training-set perturbations change predictions on common probe cases. These checks diagnose mechanisms; they do not replace a clearly defined target risk or justify a universal correction.

Check Your Understanding

Answer each question by distinguishing the mathematical target from the diagnostic evidence.

With $n=60$ observations and six equal folds, what training-size risk does the expected cross-validation score target?
Why does the expectation identity not determine whether cross-validation overestimates or underestimates $R_n$?
A single observation changes a pruning procedure’s selected tree size but not its predictions on the probe cases. What does this show, and what does it not show?
Two folds have very different error rates. Name two pieces of information to inspect before interpreting this as evidence of instability.
For the triggered-threshold rule with $p=0.2$, explain why increasing the training size raises risk rather than lowers it.