Simple Algorithm
Artificial Intelligence · Deep Layer · 26 min

Experimental Design & Statistical Testing

Significance, multiple comparisons and honest benchmarks.

A new model beats the old one by 0.4 points. Is it better, or did it draw a luckier seed, a friendlier test set, or more tuning runs? Many machine-learning comparisons never ask. This lesson builds the statistics: what varies, which tests respect the pairing created by a shared test set, what Dietterich's 1998 study found about popular tests, how many examples a comparison needs, and how to keep many comparisons honest.

What you’ll learn

  • Separate the sources of variance in a comparison, and derive the variance of a paired accuracy difference and the sample size it implies.
  • Prove McNemar's null distribution, and apply the exact test and the paired bootstrap.
  • Summarize Dietterich's (1998) findings on resampled t-tests, McNemar's test and the 5×2cv test.
  • Prove that Bonferroni and Holm control the family-wise error rate, and state the Benjamini–Hochberg guarantee for the false discovery rate.

What varies, and the paired advantage

First fix the question. (A) Is this trained model ff better than gg on this distribution? Then only the test sample is random. (B) Is learning algorithm A\mathcal A better than B\mathcal B on datasets of this kind and size? Then the training set, initialization, data order and hyperparameter search are random too. Bouthillier et al. (2021) measured these sources in deep-learning benchmarks, found data sampling among the largest, and recommended randomizing as many sources as possible. Question (B) needs repeated training runs; question (A) needs a good test of a single split.

DerivationVariance of a paired difference
  1. E[D]=pb−pc=af−ag,Var⁡(D)=pb+pc−(pb−pc)2\E[D]=p_b-p_c=a_f-a_g,\qquad\Var(D)=p_b+p_c-(p_b-p_c)^2

    On a shared test set let Di=1[f right on i]−1[g right on i]∈{−1,0,1}D_i=\mathbf 1[f\text{ right on }i]-\mathbf 1[g\text{ right on }i]\in\{-1,0,1\}, with Pr⁡(D=1)=pb\Pr(D=1)=p_b and Pr⁡(D=−1)=pc\Pr(D=-1)=p_c, the two disagreement probabilities. The accuracy difference is the mean of the DiD_i:

  2. Var⁡paired(Δ^)=pb+pc−(pb−pc)2nvs.Var⁡indep(Δ^)=af(1−af)+ag(1−ag)n\Var_{\text{paired}}(\hat\Delta)=\frac{p_b+p_c-(p_b-p_c)^2}{n}\qquad\text{vs.}\qquad\Var_{\text{indep}}(\hat\Delta)=\frac{a_f(1-a_f)+a_g(1-a_g)}{n}

    So the paired estimate has variance driven by how often the models disagree, not by their accuracy. Treating the two accuracies as independent proportions gives instead

  3. n≈(z1−α/2+z1−β)2 Var⁡(D)δ2=7.85×0.03990.012≈3,100(vs. 13,500 unpaired)n\approx\frac{(z_{1-\alpha/2}+z_{1-\beta})^2\,\Var(D)}{\delta^2}=\frac{7.85\times0.0399}{0.01^2}\approx3{,}100\quad(\text{vs. }13{,}500\text{ unpaired})

    With a=0.90a=0.90 versus 0.910.91, 4% disagreement and n=10,000n=10{,}000: standard errors of 0.20 points paired against 0.41 unpaired. For a two-sided level-α\alpha test with power 1−β1-\beta against a difference δ\delta, the required size is

Predict before you look

Two models near 90% accuracy disagree on 4% of examples. With a paired test at α=0.05\alpha=0.05 and 80% power, roughly how many test examples do you need to detect a true difference of 1 point? And how many if the models disagreed on 10%?

Show the answer

3100

n≈7.85×(0.04−0.0001)/0.0001≈3,130n\approx7.85\times(0.04-0.0001)/0.0001\approx3{,}130. At 10% disagreement, Var⁡(D)≈0.0999\Var(D)\approx0.0999 and n≈7,800n\approx7{,}800. Card et al. (2020) found that many NLP comparisons on standard test sets are underpowered for the small gains they report.

Paired tests: McNemar and the bootstrap

Cross-tabulate the two models on the test set: bb examples where only ff is right, cc where only gg is right, and the rest where they agree. Agreements say nothing about which model is better; the test lives on the b+cb+c discordant pairs.

DerivationProof
  1. Pr⁡(Di=1∣Di≠0)=pbpb+pc =H0 12\Pr(D_i=1\mid D_i\neq0)=\frac{p_b}{p_b+p_c}\ \overset{H_0}{=}\ \frac12

    Each example falls independently into one of four cells, with probabilities p11,pb,pc,p00p_{11},p_b,p_c,p_{00}. Given that an example is discordant, it favors ff with probability

  2. b ∣ (b+c=m) ∼ Binomial(m,12)under H0b\ \big|\ (b+c=m)\ \sim\ \mathrm{Binomial}\big(m,\tfrac12\big)\quad\text{under }H_0

    Independence across examples makes the discordant examples' directions i.i.d. coin flips, whichever examples turn out to be discordant:

python
import numpy as np

def paired_bootstrap_ci(correct_f, correct_g, B=10_000, level=0.95, seed=0):
    """Percentile CI for acc(f) - acc(g), resampling test examples jointly."""
    d = np.asarray(correct_f, float) - np.asarray(correct_g, float)
    rng = np.random.default_rng(seed)
    idx = rng.integers(0, len(d), size=(B, len(d)))   # B resampled test sets
    means = d[idx].mean(axis=1)
    lo, hi = np.quantile(means, [(1 - level) / 2, (1 + level) / 2])
    return d.mean(), (lo, hi)

Resample examples, keeping both models' outcomes together, so the pairing survives. For b=6b=6, c=0c=0 the interval is about [0.02,0.11][0.02,0.11], in line with McNemar. With very few discordant pairs the percentile bootstrap is anticonservative: for b=5b=5, c=0c=0 it gives about [0.01,0.10][0.01,0.10], excluding zero, while the exact test gives p=0.0625p=0.0625.

Test (Dietterich, 1998)What it doesFinding
Difference of two proportionszz-test treating the two accuracies as independenthigh type I error in some settings; avoid
Resampled paired tt-testtt-test over repeated random train/test splitshigh type I error: overlapping splits make the differences correlated, so the variance is underestimated
10-fold CV paired tt-testtt-test over the ten fold differencessomewhat elevated type I error; the most power
McNemarone split, discordant pairslow type I error; the choice when an algorithm can be trained only once
5×2cv paired tt-testfive replications of 2-fold CVacceptable type I error, slightly more power than McNemar; recommended when ten training runs are affordable
The 5×2cv statistic is t~=p1(1)/15∑i=15si2\tilde t=p_1^{(1)}\big/\sqrt{\tfrac15\sum_{i=1}^5s_i^2}, where pi(j)p_i^{(j)} is the error difference on fold jj of replication ii and si2s_i^2 the variance of the pair; under H0H_0 it is approximately t5t_5. Nadeau and Bengio (2003) instead inflate the resampled test's variance by 1J+ntestntrain\tfrac1J+\tfrac{n_{\text{test}}}{n_{\text{train}}}, and Bengio and Grandvalet (2004) proved that no unbiased estimator of the variance of KK-fold cross-validation exists.

Many comparisons

Each test controls its own false-positive rate at α\alpha. Run mm of them and the probability of at least one false positive, the family-wise error rate (FWER), can approach mαm\alpha. Benchmark tables compare many models, datasets, metrics and ablations at once, and leaderboards thousands.

DerivationProofs
  1. Pr⁡(⋃i∈I0{pi≤αm})≤∑i∈I0Pr⁡(pi≤αm)≤m0 αm≤α\Pr\Big(\bigcup_{i\in I_0}\{p_i\le\tfrac\alpha m\}\Big)\le\sum_{i\in I_0}\Pr\big(p_i\le\tfrac\alpha m\big)\le\frac{m_0\,\alpha}{m}\le\alpha

    Let I0I_0 be the m0m_0 true nulls; under HiH_i, Pr⁡(pi≤u)≤u\Pr(p_i\le u)\le u. Bonferroni by the union bound:

  2. false rejection ⇒ min⁡i∈I0pi≤αm−j∗+1≤αm0 ⇒ Pr⁡≤m0⋅αm0=α\text{false rejection}\ \Rightarrow\ \min_{i\in I_0}p_i\le\frac{\alpha}{m-j^*+1}\le\frac{\alpha}{m_0}\ \Rightarrow\ \Pr\le m_0\cdot\frac{\alpha}{m_0}=\alpha

    Holm: let j∗j^* be the rank of the smallest true-null p-value. Only false nulls precede it, so j∗−1≤m−m0j^*-1\le m-m_0. A false rejection requires reaching step j∗j^* and passing it:

  3. k=max⁡{j: p(j)≤jm α},FDR≤m0m α(independent or positively dependent p-values)k=\max\Big\{j:\ p_{(j)}\le\frac jm\,\alpha\Big\},\qquad\mathrm{FDR}\le\frac{m_0}{m}\,\alpha\quad\text{(independent or positively dependent p-values)}

    For large families, controlling the false discovery rate, FDR=E[V/max⁡(R,1)]\mathrm{FDR}=\E[V/\max(R,1)] with VV false and RR total rejections, is often more useful. Benjamini and Hochberg (1995) reject the kk smallest p-values, where

Check your understanding

Five comparisons give p-values 0.001,0.008,0.012,0.03,0.20.001, 0.008, 0.012, 0.03, 0.2. At α=0.05\alpha=0.05, how many hypotheses does Holm's procedure reject?

  1. 1
  2. 2
  3. 3
  4. 4
Show the answer

C. 3

Holm's thresholds are 0.05/5,0.05/4,0.05/3,0.05/2,0.050.05/5, 0.05/4, 0.05/3, 0.05/2, 0.05, that is 0.01,0.0125,0.0167,0.025,0.050.01, 0.0125, 0.0167, 0.025, 0.05. The first three p-values pass; 0.03>0.0250.03>0.025 stops the procedure. Bonferroni (all thresholds 0.010.01) rejects 2, and Benjamini–Hochberg (thresholds 0.01,0.02,0.03,0.04,0.050.01, 0.02, 0.03, 0.04, 0.05) rejects 4.

Across datasets, Demšar (2006) recommends the Wilcoxon signed-rank test on per-dataset differences for two classifiers, rather than a tt-test over incommensurable scores or a count of wins, and for several classifiers the Friedman test on ranks followed by a post-hoc test. Implicit comparisons count too: trying many variants and reporting the one that worked is a multiple comparison even if only one test is ever run, Gelman and Loken's "garden of forking paths".

Honest benchmarks

Tuning effort is a hidden variable. Melis, Dyer and Blunsom (2018) found that carefully tuned standard LSTMs outperformed more recent architectures on language-modeling benchmarks. Lucic et al. (2018) found that, with equal hyperparameter budgets and enough random restarts, most GAN variants reached similar scores. Henderson et al. (2018) showed that deep reinforcement-learning results swing with random seeds and implementation details, and Agarwal et al. (2021) proposed reporting interquartile means with stratified bootstrap intervals when only a few runs are affordable. How adaptive reuse of a test set biases leaderboards is covered in Measuring Intelligence & AGI, and contamination of language-model benchmarks in Evaluating Language Models.

Key takeaways

  • Decide whether you are comparing trained models (only the test sample varies) or algorithms (training data, seeds and tuning vary too).
  • A paired difference has variance [pb+pc−(pb−pc)2]/n[p_b+p_c-(p_b-p_c)^2]/n, set by disagreement; detecting 1 point at 4% disagreement takes about 3,100 test examples, against 13,500 unpaired.
  • McNemar's exact test conditions on the discordant pairs (b∼Bin(b+c,12)b\sim\mathrm{Bin}(b+c,\tfrac12) under H0H_0); the paired bootstrap resamples examples jointly and is unreliable when b+cb+c is tiny.
  • Dietterich (1998): avoid the resampled tt-test and independent-proportions tests; use McNemar for a single run or 5×2cv when ten runs are affordable.
  • Bonferroni and Holm control the FWER under any dependence (union bound); Benjamini–Hochberg controls the FDR at (m0/m)α(m_0/m)\alpha.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

Why is a paired comparison of two models on one test set much more sensitive than comparing their accuracies as independent proportions?

  1. Pairing doubles the effective number of test examples
  2. Both models get most examples right or wrong together; pairing cancels that shared variation, leaving variance set by how often they disagree
  3. The paired test assumes the models are independent
  4. Pairing removes the need for a significance level
Show the answer

B. Both models get most examples right or wrong together; pairing cancels that shared variation, leaving variance set by how often they disagree

Var⁡(D)=pb+pc−(pb−pc)2\Var(D)=p_b+p_c-(p_b-p_c)^2 depends only on disagreements. Highly correlated models disagree rarely, so the paired standard error is small even when each accuracy alone is noisy.

Question 2

Models ff and gg disagree on 12 test examples: ff is right on 9 of them and gg on 3. What is the exact two-sided McNemar p-value?

  1. About 0.07
  2. It cannot be computed without the number of examples on which they agree
  3. About 0.15
  4. About 0.0005
Show the answer

C. About 0.15

Under H0H_0, b∼Bin(12,12)b\sim\mathrm{Bin}(12,\tfrac12): 2Pr⁡(b≤3)=2 (1+12+66+220)/4096=598/4096≈0.1462\Pr(b\le3)=2\,(1+12+66+220)/4096=598/4096\approx0.146. Not significant at 5%, despite a 3-to-1 split.

Question 3

Why did Dietterich (1998) find that the paired tt-test over repeated random train/test splits rejects true null hypotheses too often?

  1. The splits overlap, so the differences are positively correlated and their sample variance underestimates the true variance
  2. The tt distribution has heavier tails than the normal
  3. Random splits always favor the more complex algorithm
  4. It uses too few splits to be valid
Show the answer

A. The splits overlap, so the differences are positively correlated and their sample variance underestimates the true variance

The tt-test assumes independent differences. Training and test sets reused across splits make them dependent, so the variance is underestimated and the statistic is inflated. Nadeau and Bengio's correction inflates the variance accordingly.

Question 4

A screen of 200 ablations is analyzed with the Benjamini–Hochberg procedure at 5%. What does this guarantee (for independent p-values)?

  1. The probability of any false discovery is at most 5%
  2. Each rejected hypothesis has p-value at most 0.05/200
  3. On average, at most 5% of the rejected hypotheses are false discoveries
  4. At least 95% of the real effects are detected
Show the answer

C. On average, at most 5% of the rejected hypotheses are false discoveries

FDR is the expected fraction of false discoveries among the rejections. It allows some false positives in exchange for much more power than FWER control when the family is large.

Further reading

  • T. G. Dietterich, "Approximate statistical tests for comparing supervised classification learning algorithms," Neural Computation 10, 1895–1923 (1998).
  • J. Demšar, "Statistical comparisons of classifiers over multiple data sets," Journal of Machine Learning Research 7, 1–30 (2006).
  • C. Nadeau & Y. Bengio, "Inference for the generalization error," Machine Learning 52, 239–281 (2003).
  • Y. Benjamini & Y. Hochberg, "Controlling the false discovery rate: a practical and powerful approach to multiple testing," Journal of the Royal Statistical Society B 57, 289–300 (1995).
  • B. Efron & R. J. Tibshirani, An Introduction to the Bootstrap (Chapman & Hall, 1993).