Nested Cross-Validation for Classifier Selection

Why Selection Needs Its Own Validation Layer

A classification procedure often does more than fit one prespecified rule. It may choose a feature subset, compare linear and quadratic discriminant rules, tune a covariance regularization parameter, or select among several combinations of these choices. Each choice uses data. If the same observations are used both to select the procedure and to report its error, the reported error can be too small: among several candidates, the winner may partly be the one that happened to fit those observations best.

Nested cross-validation separates these tasks. Inner folds select the procedure using only the current training portion. Outer folds assess the selected procedure on observations that played no role in that selection or fit. The resulting estimate concerns the entire selection-and-fitting process, not merely a classifier treated as if it had been fixed in advance.

Definition: Let $D_m$ denote a training sample of size $m$. A learning procedure $A$ maps $D_m$ to a fitted classifier $g_{D_m}$, including any feature selection, tuning, and refitting specified by the procedure. Its misclassification risk is $R(g_{D_m})=P\{g_{D_m}(X)\ne Y\mid D_m\}$, where $(X,Y)$ is a new observation from the target population, independent of $D_m$. Nested cross-validation uses inner validation to carry out choices within $A$, then outer validation to estimate the risk of the resulting procedure.

This definition makes an important distinction: the object being assessed is not just, for example, “LDA with five features.” It may instead be “the rule that uses inner cross-validation to choose a feature subset and shrinkage level, then refits LDA using those choices.” If the procedure includes a data-dependent step, that step belongs inside the procedure being assessed.

The Nested Design

Suppose $D_n=\{(X_i,Y_i):i=1,\ldots,n\}$ is divided into $K$ disjoint outer folds $I_1,\ldots,I_K$. For outer fold $k$, the outer training set is $D_{-k}=D_n\setminus I_k$, and $I_k$ is held aside for assessment. The inner cross-validation is run using only $D_{-k}$. It selects a candidate configuration, such as a feature-selection method and a covariance regularization value. The chosen pipeline is then refitted on all of $D_{-k}$, and its predictions are evaluated on $I_k$.

Set aside an outer fold.
Do not use its observations or labels for feature selection, tuning, preprocessing decisions, or fitting.

Select using inner folds.
Compare candidate procedures by cross-validation within the outer training set, according to a prespecified selection criterion.

Refit the selected procedure.
Apply the selected pipeline to all of the outer training set, including any preprocessing and feature selection that must be estimated from data.

Assess once on the outer fold.
Record its predictions and errors on the untouched outer observations.

Aggregate outer predictions.
Combine the outer-fold errors to estimate the error of the selection-and-fitting procedure.

For zero-one loss, let $\hat g_{-k}$ be the classifier selected and refitted using $D_{-k}$. If the outer folds have sizes $n_k=|I_k|$, the pooled estimate is

\widehat R_{\mathrm{nested}} = \frac{1}{n}\sum_{k=1}^K\sum_{i\in I_k} \mathbf{1}\{\hat g_{-k}(X_i)\ne Y_i\}.

Pooling gives each assessed observation equal weight. Equivalently, it is the fold-size-weighted average of the fold error rates. When folds have equal size, it also equals their unweighted average. The candidate set and selection criterion should be specified in advance; choosing them after examining outer-fold results turns the outer assessment into another selection set.

Worked Example: Selecting Features and Covariance Regularization

Suppose the candidate pipelines are LDA using either feature set A or feature set B, each with either no covariance shrinkage or a fixed positive shrinkage value. Three outer folds are used. Within each outer training set, four-fold inner cross-validation produces the following total numbers of errors across its inner validation observations. Each outer training set contains eight observations, so each candidate has eight inner validation predictions.

Outer fold	A, no shrinkage	A, shrinkage	B, no shrinkage	B, shrinkage	Inner-selected pipeline	Errors on outer fold
1	3	2	4	3	A, shrinkage	1 of 4
2	2	3	1	2	B, no shrinkage	2 of 4
3	3	2	3	4	A, shrinkage	0 of 4

For outer fold 1, the smallest inner error count is 2, so the selected pipeline is feature set A with shrinkage. For fold 2, the minimum is 1, so the selected pipeline is feature set B without shrinkage. For fold 3, the minimum is 2, so A with shrinkage is selected. In each case the selected pipeline is then refitted on that outer training set before its outer-fold errors are counted.

There are $4+4+4=12$ outer predictions and $1+2+0=3$ errors. Thus

\widehat R_{\mathrm{nested}}=\frac{3}{12}=0.25.

The selected pipeline varies across outer folds. That is not a flaw: this variation is part of the behavior of the selection procedure being assessed. The number 0.25 is not the inner error of one final pipeline, nor does this example establish that the procedure’s future error is exactly 0.25.

What the Outer Error Estimates

Theorem: Suppose the observations are independent and identically distributed from a population $P$, and the outer-fold assignment is fixed in advance or randomized independently of the observations. For each outer fold $I_k$, assume the complete selection-and-fitting procedure $\hat g_{-k}$ uses only $D_{-k}$. Conditional on $D_{-k}$ and the fold assignment, the expected outer-fold error rate is $R(\hat g_{-k})$: $$ E\left[ \left. \frac{1}{n_k}\sum_{i\in I_k} \mathbf{1}\{\hat g_{-k}(X_i)\ne Y_i\} \right|D_{-k}, I_1,\ldots,I_K \right] =R(\hat g_{-k}). $$

Proof. Conditional on $D_{-k}$ and the fold assignment, $\hat g_{-k}$ is fixed. The observations in $I_k$ are independent of $D_{-k}$, and each has the population distribution $P$. Therefore, for every $i\in I_k$,

E\left[ \left. \mathbf{1}\{\hat g_{-k}(X_i)\ne Y_i\} \right|D_{-k}, I_1,\ldots,I_K \right] = P\{\hat g_{-k}(X)\ne Y\mid D_{-k}\} = R(\hat g_{-k}).

Taking the conditional expectation of the average and using linearity of expectation gives $n_k^{-1}\sum_{i\in I_k}R(\hat g_{-k})=R(\hat g_{-k})$, as claimed. No independence among the errors from different outer folds is needed for this expectation identity. $\square$

The theorem is conditional on the training data: an outer fold estimates the risk of the particular procedure fitted on its complement. Averaging across folds therefore targets the average risk of procedures trained on outer-training samples of size $n-n_k$, with the stated selection process repeated within each. It does not make the estimate an exact assessment of the final procedure refitted on all $n$ observations. Training-set size, fold construction, and selection instability can all matter when relating the nested estimate to that final fit.

Worked Example: Interpreting the Training-Size Target

Suppose $n=120$ observations are split into five equal outer folds. Each outer fit uses $120-24=96$ observations. Within each set of 96, the procedure selects features and a regularization value by inner cross-validation, then refits the chosen pipeline on those 96 observations.

The outer estimate describes the average performance of this selection-and-fitting process when trained on 96 observations, under the fold design and target population used. A final model selected and fitted using all 120 observations has a different training-set size and may select a different pipeline. The outer estimate is useful evidence about that final model’s generalization, but the theorem does not equate the two risks.

If the procedure is unstable—for example, small changes in training data often change the selected feature set—the gap between behavior at training size 96 and behavior at size 120 may be material. The numerical fact that the final fit uses 24 more observations does not by itself determine the direction or magnitude of any change in risk.

Why the Inner and Outer Layers Must Stay Separate

Result: If candidate procedures have the same true risk $r$, and their validation-error estimates are unbiased for $r$, then selecting the candidate with the smallest validation error has expected minimum validation error no greater than $r$. The inequality is strict if the candidate estimates differ with positive probability. This statement concerns the selected validation score, not necessarily the future risk of the selected candidate.

Proof. Write the validation-error estimates as $\hat r_1,\ldots,\hat r_J$, with $E[\hat r_j]=r$ for each $j$. Pointwise,

\min_{1\le j\le J}\hat r_j \le \frac{1}{J}\sum_{j=1}^J\hat r_j.

Taking expectations gives $E[\min_j\hat r_j]\le J^{-1}\sum_j E[\hat r_j]=r$. If the estimates are not all equal with positive probability, the pointwise inequality is strict on an event of positive probability, so the expectation inequality is strict. This explains why the winning inner score is not an independent assessment of the winner. $\square$

Worked Example: A Validation Set Used for Selection Is Not a Test Set

Let the label $Y$ be Bernoulli with $P(Y=1)=P(Y=0)=1/2$. Consider two fixed candidate classifiers: $g_0$ always predicts 0, and $g_1$ always predicts 1. Each has true misclassification risk $1/2$, since each is wrong for exactly one of the two equally likely labels.

Now suppose one validation observation is used both to choose between these candidates and to report error. If its label is 0, the validation errors are 0 for $g_0$ and 1 for $g_1$; the selected candidate has reported error 0. If its label is 1, the errors are 1 for $g_0$ and 0 for $g_1$; again, the selected candidate has reported error 0. Thus the reported selected validation error is always 0.

The selected constant classifier still has error probability $1/2$ on an independent future observation: the future label is equally likely to be either value and is independent of the validation label used for selection. Consequently, reusing the assessment observation produces reported error 0 even though the selected classifier’s future risk is $1/2$. In a nested design, that observation must not participate in inner selection; it belongs only to the outer assessment.

Class Balance, Preprocessing, and the Target Population

The risk being estimated depends on the population and loss of interest. Under ordinary zero-one loss, a population with class probabilities $\pi_c=P(Y=c)$ has risk

R(g)=\sum_c \pi_c\,P\{g(X)\ne Y\mid Y=c\}.

Stratifying folds by class can help ensure that every training and assessment fold contains observations from each class. But if the observed class proportions are deliberately fixed by the sampling or fold design, a raw pooled error need not estimate risk under a different target prevalence. The class-conditional error rates and the target class probabilities must be combined to match the intended population.

Worked Example: Reweighting Class-Conditional Error

Suppose a population has class 0 prevalence 0.8 and class 1 prevalence 0.2. A nested assessment gives class-conditional error rates of 0.10 for class 0 and 0.40 for class 1. The corresponding population zero-one risk is

$$ R=0.8(0.10)+0.2(0.40)=0.08+0.08=0.16. $$

A balanced error summary instead gives $(0.10+0.40)/2=0.25$. That number weights the two classes equally; it is not the ordinary population misclassification risk for prevalence 0.8 and 0.2. It may be an appropriate target if equal class weighting is intentional, but the weighting rule must be stated.

The same separation principle applies to the whole pipeline. Any operation that learns from data—such as estimating means and scales, screening features, selecting a subset, or estimating covariance matrices—must be carried out using only the relevant training portion. If feature screening is performed once on all observations before outer folds are made, the outer validation labels have already influenced the candidate features. The outer predictions are then not an assessment of a procedure that would have had access only to its training data.

Common Mistakes and Practical Interpretation

Reporting the best inner score as the error estimate. It was used to choose a winner, so it is subject to selection optimism. Use outer-fold predictions for assessment.
Doing feature selection before the outer split. Even if the classifier fit is repeated in each fold, a feature set chosen using all labels leaks information from outer assessment observations.
Leaving scaling or covariance estimation outside the folds. Data-dependent preprocessing and covariance regularization belong within each training portion, just like classifier fitting.
Calling the estimate the exact risk of the final full-data model. Outer fits use fewer observations than the final fit and may select different configurations.
Confusing class-balanced error with population error. The two coincide only under the relevant matching class weights; state the target weighting.

Nested cross-validation is most useful when model selection is part of the scientific or operational procedure and an independent test sample is unavailable or too small to reserve. It provides an assessment that respects the selection process, provided the outer folds remain untouched until evaluation. It does not eliminate uncertainty, guarantee that the final full-data model has the estimated risk, or repair a mismatch between the validation population and the intended deployment population.

Key takeaway: Put every data-driven choice inside the inner training process, refit the selected pipeline on each outer training set, and assess it only on that outer fold. Interpret the pooled outer error as an estimate for the complete selection procedure at the outer training size and under the assessment design.

Check Your Understanding

Answer each question by tracing which observations may influence selection, fitting, and assessment.

Why is the minimum inner cross-validation error not an independent estimate of the selected classifier’s risk?
In five-fold outer cross-validation with 200 observations, how many observations are used to fit each outer classifier before any inner folds are considered?
A researcher selects features using all 200 labels, then performs outer cross-validation. Which part of the design has leaked information, and why does this matter?
State the conditional expectation identity for the outer-fold error and explain the independence condition that makes it valid.
If class-conditional error rates are 0.05 and 0.35, why can the population risk differ from their unweighted average?