Comparing Classifiers Across Cross-Validation Splits

Why Compare Classifiers Pairwise?

When two classification procedures are evaluated on the same cross-validation splits, their errors should be compared within each split. A split on which the test cases are unusually difficult may raise both classifiers' errors. Subtracting their errors on that shared test fold removes some of this common variation and targets the difference between the procedures rather than the difficulty of the fold.

Pairing does not, however, make results from different folds or repetitions independent. Cross-validation training sets overlap, and repeated cross-validation reuses the same observations. This tutorial develops paired split-level differences and explains a commonly used correction for the resulting uncertainty. The correction is useful as a warning against overly small standard errors, but it is not an exact solution to the dependence problem.

Paired Differences on Shared Test Folds

Suppose \(J\) cross-validation evaluations use the same training and test split for classifiers A and B. On split \(j\), let \(\hat e_{Aj}\) and \(\hat e_{Bj}\) be their respective proportions of misclassified test observations. Define the paired difference as A's error minus B's error.

The test observations must be shared for this pairing to be meaningful. For example, if A and B are assessed on different folds, the difference combines classifier performance with differences in test-set difficulty. A paired comparison holds that source of variation in common. When fold sizes are equal, averaging the \(d_j\)'s also gives the difference between the two classifiers' average fold errors. With unequal fold sizes, an observation-weighted overall error difference and an unweighted average of fold differences need not be the same quantity.

Pairing Helps Within a Split, Not Across Splits

The benefit of pairing within a split can be stated directly in terms of variance. For any two error-rate random variables \(U\) and \(V\) with finite variances,

If A's and B's errors tend to rise together on difficult test folds, their covariance is positive. Subtracting their errors can then be less variable than treating the two error rates as unrelated quantities. Pairing is therefore important even before considering the dependence between folds.

The usual standard error \(s_d/\sqrt{J}\) treats the \(J\) differences as independent observations. That assumption is generally implausible for cross-validation. In \(K\)-fold cross-validation, the training sets for two different folds overlap substantially. In repeated \(K\)-fold cross-validation, each observation appears in test folds repeatedly, while the fitted classifiers are based on highly overlapping training samples. Consequently, split-level differences can be correlated even though they are paired correctly within each split.

The effect of positive dependence can be derived in a simple model. This derivation does not assert that cross-validation differences have exactly this correlation structure; it shows why the independent-split calculation can be too optimistic.

Derivation. By definition, \(\bar D=J^{-1}\sum_j D_j\). Expanding the variance as a sum of variances and covariances gives

There are \(J(J-1)/2\) distinct pairs, which accounts for the second term in the expansion. When \(\rho=0\), the result reduces to \(\sigma^2/J\). When \(\rho>0\), the variance exceeds that independent-split value. In particular, collecting more highly correlated splits does not provide as much new information as the same number of independent evaluations would.

A Corrected Standard Error

A widely used approximate adjustment is the Nadeau–Bengio corrected resampled standard error. For \(J\) paired split differences, let \(n_{\text{train}}\) and \(n_{\text{test}}\) denote the training and test sizes for a split. The corrected variance estimate is

For equal-sized \(K\)-fold splits, \(n_{\text{test}}/n_{\text{train}}=1/(K-1)\). In repeated \(K\)-fold cross-validation with \(R\) repetitions, \(J=RK\). Thus the correction factor is \(1/(RK)+1/(K-1)\), rather than just \(1/(RK)\). This formula uses the observed variability of the paired differences and adds a term intended to reflect dependence from the overlapping training samples.

The corrected standard error is an approximate uncertainty measure, not an exact variance formula under arbitrary cross-validation dependence. A commonly used corrected resampled \(t\) procedure divides \(\bar d\) by this standard error and compares the result with a \(t\) reference distribution using \(J-1\) degrees of freedom. That reference distribution does not make the split differences independent; the procedure is an approximation, and its calibration can be unreliable when the number of independent data units is small or the dependence structure is complicated.

What the Correction Does—and Does Not—Establish

A cross-validation comparison concerns the procedures as trained on subsets of the available data. It does not directly measure the difference between two particular final classifiers fitted on the entire data set, nor does it automatically give an exact confidence interval for their population risks. The training-set size matters: a procedure trained on a fraction of the data may behave differently from the same procedure refitted on all observations.

The corrected standard error also cannot repair a poorly designed comparison. If model selection or tuning uses information from the test folds, the resulting evaluation can be optimistic; use nested cross-validation when selection must be included in the assessment. The comparison should otherwise hold the splits and evaluation metric in common, and should state whether algorithmic randomness is fixed or included in the procedure being evaluated.

A frequent mistake is to count all \(RK\) fold results as independent replications and report \(s_d/\sqrt{RK}\) as though each fold came from a new data set. The arithmetic is correct only under the independence assumption. Cross-validation folds share training observations, and repeated folds reuse test observations, so the assumption generally lacks justification. The corrected formula is a practical adjustment, not a proof that the resulting test has exact size or that more repetitions eliminate uncertainty.