Paired Bootstrap

When you compare two systems on the same test items, the difference in their average scores is a number from one particular sample of items. A different sample would give a different difference. The paired bootstrap estimates how much that difference would vary, and so gives a confidence interval, by resampling the items themselves.

Procedure

Let \(a_i\) and \(b_i\) be the scores of systems A and B on item \(i=1,\dots,n\), and let \(\delta_i=b_i-a_i\) be the per-item difference. The observed mean difference is \(\bar\delta\).

1. Draw \(n\) item indices with replacement from \(\{1,\dots,n\}\).
2. Compute the mean of \(\delta_i\) over the drawn indices.
3. Repeat many times, for example 5,000.
4. Sort the resampled means. The 2.5th and 97.5th percentiles form a 95% percentile interval.

Resampling mimics drawing new test sets from the same population of items, using the observed items as a stand-in for that population. The pairing is in step 1: the same drawn items are used for both systems, so each system is evaluated on the same resampled set and what is resampled is the difference per item.

Why pairing helps

Some items are easy for every system and some are hard for every system. That shared difficulty varies a lot across items but cancels out in \(\delta_i\). An unpaired bootstrap resamples A's scores and B's scores independently and keeps the item-to-item variation in both. The next program builds hypothetical per-query scores for 60 queries in which each system's score is the query's difficulty plus its own noise, with B better by 0.04 on average.

import random, statistics as st
random.seed(7)
n = 60
difficulty = [random.betavariate(2, 2) for _ in range(n)]
clip = lambda x: min(1, max(0, x))
A = [clip(d + random.gauss(0.00, 0.08)) for d in difficulty]
B = [clip(d + random.gauss(0.04, 0.08)) for d in difficulty]
D = [b - a for a, b in zip(A, B)]
print("mean A %.3f  mean B %.3f  mean diff %.3f" % (st.mean(A), st.mean(B), st.mean(D)))

def interval(stat, R=5000):
    out = sorted(stat() for _ in range(R))
    return out[int(0.025 * R)], out[int(0.975 * R) - 1]

def paired():
    idx = [random.randrange(n) for _ in range(n)]
    return st.mean(D[i] for i in idx)

def unpaired():
    ia = [random.randrange(n) for _ in range(n)]
    ib = [random.randrange(n) for _ in range(n)]
    return st.mean(B[i] for i in ib) - st.mean(A[i] for i in ia)

print("paired   95%% interval: [%.3f, %.3f]" % interval(paired))
print("unpaired 95%% interval: [%.3f, %.3f]" % interval(unpaired))

Output:

mean A 0.520  mean B 0.547  mean diff 0.027
paired   95% interval: [-0.002, 0.056]
unpaired 95% interval: [-0.060, 0.114]

The unpaired interval is about three times as wide as the paired one (0.174 versus 0.058). Its lower end is far below zero, while the paired interval nearly excludes zero. The gap is the shared difficulty variation that pairing removes.

Reading the interval

If the 95% interval excludes zero, the data support a difference of the observed sign at this sample size. If it includes zero, as the paired interval above nearly does, the data do not distinguish A from B at this sample size, and a larger test set would help. The interval covers only the sampling of items. It does not cover differences between the test set and real traffic, training randomness (run several seeds if the system is trained), or noise in the labels.

Conditions and variants

• Items must be exchangeable draws. If items come in groups, such as several questions about one document or messages in one thread, they are correlated, and resampling single items makes the interval too narrow. Resample whole groups instead (cluster bootstrap). To estimate a mean over items, carry each drawn group’s sum of paired differences and item count, and divide the total sum by the total count. Averaging group means equally instead estimates a mean over groups; these differ when group sizes differ. For a stratified test set, resample within each stratum using the same drawn indices for A and B, then combine the stratum mean differences with the population weights. If the independent unit is a group, preserve whole groups within those strata.
• For skewed or bounded metrics, or very small \(n\), the percentile interval can be inaccurate. With fewer than a few dozen items, treat the result as rough.
• For metrics that are not a mean over items, such as F1 over a pooled count, recompute the metric on each resample rather than averaging a per-item score.
• Many comparisons raise the chance that one interval excludes zero by luck. Decide the comparisons in advance.
• The bootstrap needs only the per-item scores of both systems, which is why storing per-item outputs, not only aggregate metrics, pays off.