Comparing Two Classifiers with Paired Tests on the Same Rows

Two models evaluated on the same data differ by a fraction of a point. The difference may be real, or it may be the same kind of noise that would appear if the split were redrawn. Deciding between the two requires a test, and the test has to account for the fact that the two measurements are paired on the same rows and that the fold scores are not independent.

The pairing, and why an unpaired test is wrong

If both models are scored on the same test rows, the scores are correlated: rows that are hard for one model tend to be hard for the other, and the row-level errors overlap. A paired test works on the differences, which removes the row-level variance that both models share and leaves only the disagreement between them. The reduction in variance is the whole point, and it can be large: for two models with similar error rates, the variance of the difference can be an order of magnitude smaller than the variance of either error rate.

An unpaired comparison treats the two error rates as independent estimates and computes a standard error from both variances, which overstates the uncertainty of the difference and makes real differences look insignificant. The direction of the error is conservative, so the failure mode is missed detections rather than false alarms, but it is still a failure: a test that cannot detect a real difference is not doing its job.

On a single test set with $n$ rows, the natural paired statistic is McNemar’s test. It tabulates the rows where the models disagree: $b$ rows where the first is wrong and the second right, $c$ rows where the reverse. Under the null hypothesis of equal error rates, $b$ and $c$ are draws from a binomial with $p = 0.5$ conditional on $b+c$. The test statistic is $(|b-c|-1)^2/(b+c)$ with the continuity correction, compared against a chi-squared distribution with one degree of freedom. Rows where both models agree, whether both right or both wrong, carry no information about the difference and drop out of the computation.

from math import comb

def mcnemar_exact(b, c):
    """Two-sided exact p-value for the discordant counts."""
    n = b + c
    if n == 0:
        return 1.0
    k = min(b, c)
    tail = sum(comb(n, i) for i in range(k + 1)) / 2 ** n
    return min(1.0, 2 * tail)

The exact form is preferable when $b+c$ is small, which it often is: two good models on a moderate test set may disagree on a few dozen rows, and the chi-squared approximation is poor at that count. The exact binomial computation is cheap and has no approximation error.

Why the resampled t-test over cross-validation folds is invalid

The tempting procedure with $k$-fold results is a paired t-test over the $k$ fold differences. It is the most commonly applied test and it is wrong, for two reasons that Dietterich’s analysis makes precise.

The first is that the $k$ fold differences are not independent. Each pair of folds shares $k-2$ of the $k$ training blocks, so the training sets are highly overlapping, and the models fitted on them are correlated. The t-test assumes independent samples from a normal distribution; here the samples are dependent, and the dependence inflates the effective variance relative to what the test assumes, so the test rejects too often.

The second is that the differences are not identically distributed. Each fold’s difference has a different variance, because each fold’s test block has different composition and the models’ behaviour varies with it. Averaging over folds with equal weights when the variances differ is not the maximum-likelihood estimator, and the t-statistic built from it has a distribution that depends on the unknown variance pattern.

The consequence is a test with a nominal 5 percent level that rejects far more often than 5 percent of the time under the null. Dietterich’s simulation results put the actual rate well above nominal for the resampled t-test, and the corrected procedures exist because of it.

The corrected alternatives and their assumptions

Dietterich proposed a corrected resampled t-test that divides the standard error by a factor reflecting the overlap: the variance estimate is inflated by $(1/k + n_{\text{test}}/n_{\text{train}})$, where $n_{\text{test}}$ and $n_{\text{train}}$ are the fold sizes. The correction accounts for the correlation between training sets, and it makes the test conservative rather than anti-conservative, which is the safer direction.

The 5x2cv paired t-test runs five repetitions of a two-fold split, each with a different random partition, and computes a t-statistic from the ten differences. The two-fold structure means each training set is disjoint from its test set, and the repetitions give independent partitions, so the dependence problem is much reduced. The cost is ten fits per model and the requirement that the split be genuinely random, which rules it out for grouped or ordered data.

The combined 5x2cv F-test uses the same partitions but a variance-ratio statistic, which is less sensitive to unequal error variances between the two models. Both procedures are described and compared in the same paper, and both are preferable to the naive fold t-test on i.i.d. data.

For grouped or time-ordered data, none of these apply directly, because the partitions are not exchangeable. The correct approach is a permutation test over the grouping units: permute the assignment of groups to folds, recompute the difference, and compare the observed difference to the resulting distribution. That test assumes exchangeability of groups under the null, which is the right assumption when groups are the sampling unit, and it costs a few hundred refits.

The interval is the useful output

A p-value answers whether the difference is distinguishable from zero, and the interval answers how large the difference plausibly is. The second is what a decision needs. For a paired comparison on a single test set, the interval follows from the discordant counts: the difference in error rates is $(c-b)/n$, and its standard error depends on the same counts, since only the discordant rows contribute.

Reporting the interval alongside the counts makes the test’s power visible. A wide interval around a small difference says that the data cannot separate the models, which is a different statement from saying they are equivalent. A narrow interval around a small difference says the models differ by a small amount, and the decision then rests on whether that amount is worth the cost of switching.

The discordant counts are also worth reporting raw, because they show how much of the test set the comparison actually used. Two models that agree on every row produce no evidence either way, and a test that reports only a p-value of 1.0 has hidden the fact that the evaluation had no resolution to offer.

What the test does not decide

A significant difference is not an important one. On a large test set, a difference of a tenth of a point can be significant, and the confidence interval around it can exclude zero while the interval’s width is smaller than the uncertainty in the labels themselves. Annotation noise puts a floor on the meaningfulness of any difference: if two annotators agree on a task only 90 percent of the time, a difference of a fraction of a point between models is below the resolution of the target.

Multiple comparisons compound the problem. Comparing ten models pairwise produces 45 tests, and at a 5 percent level roughly two false positives are expected under the null of no differences anywhere. Correcting with a Bonferroni factor or a false-discovery procedure is necessary when the comparisons are exploratory, and the correction is not optional when the winner is selected from the results.

The test also says nothing about which model to deploy. A model with a slightly worse average error and a much better tail behaviour, or a much lower inference cost, or a better calibration profile, can be the right choice despite losing the test. The test answers one narrow question, whether the observed difference exceeds what the evaluation procedure’s noise would produce, and the decision incorporates the answer along with everything the test does not measure.

The choice of test statistic interacts with the choice of metric. A paired test on accuracy treats all errors as equal; the same test on a cost-weighted loss treats them differently and can reach the opposite conclusion, since the two models may differ mainly on the errors that the cost function weights heavily. The metric selection described in Macro, Micro, and Weighted Averaging in Multiclass Metrics and the threshold selection in Selecting a Decision Threshold from the Confusion Matrix both determine what the paired differences are differences of.

Finally, a test on a fixed test set is a test of the models on that set. It does not account for the variability of the split itself, so a difference that is significant on one partition may reverse on another. The only procedure that addresses that variability is one that resamples the partition, which is the reason the repeated two-fold schemes exist and the reason a single-split McNemar result should be reported as conditional on the split.