Bootstrap Uncertainty and Model Comparisons, machine learning lesson

Two regression models were fitted earlier and frozen. On four held-out cases model A has a mean absolute error of 3 units and model B one of 4 units. A different set of held-out cases would give different numbers even though neither model changes, so the question is how much of the one-unit gap could come from which cases happened to be drawn. This lesson uses the bootstrap to measure the variability of a metric and of a paired difference, decides what should be resampled, and states what the resulting interval does and does not cover.

Key terms

Metric uncertainty

Definition Let a fitted model $\hat{f}$ be frozen and scored on $n$ evaluation cases drawn independently from a target population. A metric that averages per-case losses, such as the mean absolute error of the predictions $\hat{y}_i = \hat{f}(\mathbf{x}_i)$ ,

\operatorname{MAE} = \frac{1}{n} \sum_{i=1}^{n} \lvert y_i - \hat{y}_i \rvert ,

is an estimate of the model’s population risk, here $E\bigl[\lvert Y - \hat{f}(\mathbf{X}) \rvert\bigr]$ for a new case from that population. Metric uncertainty is the variability of this estimate over repeated evaluation sets of size $n$ with the model held fixed. For a mean of independent per-case losses whose standard deviation is $\sigma_\ell$ , the standard error is $\sigma_\ell / \sqrt{n}$ . The variation of the whole procedure, from retraining on new training data and repeating the tuning, is a different quantity, and measuring it requires repeating those steps.

In plain words A held-out score is a measurement on particular cases, and another sample of cases would give the same model a different score. Metric uncertainty says how much the score might move for this frozen model. It does not say how much a retrained or retuned model would differ, and it says nothing about cases from a population that the evaluation set does not represent. Scores from cross-validation need extra care. The fold training sets overlap and each fold is scored by a different model, so the standard deviation of the $k$ fold scores divided by $\sqrt{k}$ is not automatically a valid standard error.

Example Four constructed held-out cases, measured in outcome units, give the following predictions and absolute errors.

Case	Outcome	Model A	Model B	A error	B error
$1$	$10$	$9$	$7$	$1$	$3$
$2$	$20$	$16$	$17$	$4$	$3$
$3$	$30$	$28$	$26$	$2$	$4$
$4$	$40$	$35$	$34$	$5$	$6$

Model A has MAE $12/4 = 3$ units and model B has MAE $16/4 = 4$ units. The plug-in variance of A’s errors, with denominator $n$ , is $10/4 = 2.5$ , so the estimated standard error of A’s MAE is $\sqrt{2.5/4} \approx 0.79$ units. Four cases are far too few to pin down either number, and they serve here only to make every step visible.

Bootstrap resampling

Definition Suppose the $n$ evaluation cases are independent draws from the target population and the models are frozen. A bootstrap resample draws case indices $i_1^*, \dots, i_n^*$ independently and uniformly from $\{1, \dots, n\}$ , with replacement, and recomputes the statistic $T$ on the selected cases to give $T^*$ . This is the same as drawing $n$ cases from the empirical distribution, which puts probability $1/n$ on each observed case. Repeating the draw $B$ times gives $T_1^*, \dots, T_B^*$ . When several models are compared, all of them are scored on the same resampled indices. The statistic, the target population and the independent sampling unit are fixed before any resampling.

In plain words The observed cases stand in for the population, and new evaluation sets are drawn from them. Because the draws are with replacement, a case can appear several times in a resample or not at all. Resampling reuses the information in the observed cases and adds none, so it approximates a repeated-data experiment rather than performing one. Nothing is refitted, since the models are frozen and only the evaluation cases change.

Example The resample made of cases 1, 1, 2 and 4 gives model A the errors 1, 1, 4 and 5, an MAE of $11/4 = 2.75$ , and gives model B the errors 3, 3, 3 and 6, an MAE of $15/4 = 3.75$ . The difference A minus B is $-1$ , as in the original data. The resample made of case 2 four times gives A an MAE of 4 and B an MAE of 3, a difference of $+1$ .

Bootstrap distribution

Definition The bootstrap distribution of a statistic $T$ is the distribution of $T^*$ when the resample is drawn from the empirical distribution of the $n$ cases. It weights the $n^n$ ordered resamples equally. For very small $n$ it can be listed exactly, and otherwise it is approximated by the $B$ simulated values, with a Monte Carlo error that shrinks as $B$ grows. Its standard deviation is the bootstrap standard error of $T$ . When $T$ is the mean of per-case values $v_1, \dots, v_n$ , the exact bootstrap standard error is

\begin{gathered} \operatorname{SE}_{\text{boot}} = \frac{\hat{\sigma}}{\sqrt{n}}, \\[0.4em] \hat{\sigma}^2 = \frac{1}{n} \sum_{i=1}^{n} (v_i - \bar{v})^2 . \end{gathered}

In plain words The bootstrap distribution shows the range and concentration of values the statistic takes when the evaluation set is redrawn from the observed cases, and its spread estimates metric uncertainty. A larger $B$ makes the simulated distribution a closer copy of the exact bootstrap distribution, but it adds no information about the population, which comes only from the $n$ cases. The distribution is centered near the observed statistic, not at the unknown population value, so it describes variability and does not locate the truth.

Example The paired differences of the four cases, A error minus B error, are $-2$ , $1$ , $-2$ and $-1$ . Listing all $4^4 = 256$ ordered resamples gives the exact bootstrap distribution of their mean. Its smallest value $-2$ comes from the 16 resamples that use only cases 1 and 3, and its largest value $1$ comes from the single resample that uses case 2 four times. Its mean is $-1$ , the observed difference, and its standard deviation is $\sqrt{1.5/4} \approx 0.61$ units, which matches the formula because the differences have plug-in variance $1.5$ . Of the 256 resamples, 19, about 7 percent, give a difference of zero or more.

Percentile interval

Definition Sort the $B$ bootstrap values as $T^*_{(1)} \le \dots \le T^*_{(B)}$ . With the nearest-rank rule, the $u$ quantile for $0 < u < 1$ is

q^*_u = T^*_{(\lceil uB \rceil)},

the smallest bootstrap value with at least a fraction $u$ of the values at or below it. The percentile interval with nominal level $1 - \alpha$ is

\bigl[\, q^*_{\alpha/2}, \; q^*_{1 - \alpha/2} \,\bigr].

A confidence procedure with level $1 - \alpha$ for a fixed population quantity $\theta$ produces intervals that contain $\theta$ with probability $1 - \alpha$ over repeated samples. The percentile interval reaches this coverage only approximately, under conditions such as independent sampling of the resampled units, a sample large enough for the bootstrap distribution to resemble the sampling distribution, and a statistic that behaves regularly.

In plain words The interval keeps the middle of the bootstrap distribution and drops a fraction $\alpha/2$ in each tail. Its level describes the procedure over repeated samples. Once one interval has been computed, $\theta$ is a fixed number that is either inside it or not, and saying that it lies inside with probability $0.95$ needs an additional probability model. The approximation can be poor for very small samples, rare events, parameters near a boundary, irregular statistics such as a maximum, and populations that the evaluation cases do not represent. With a small discrete bootstrap distribution the quantile rule matters, and software that interpolates between ranks can give slightly different endpoints.

Example For the 256 paired differences and $\alpha = 0.05$ , the ranks are $\lceil 0.025 \cdot 256 \rceil = 7$ and $\lceil 0.975 \cdot 256 \rceil = 250$ . The value at rank 7 is $-2$ , since 16 resamples give $-2$ . The value at rank 250 is $0.25$ , since 243 resamples give $0$ or less and the next 8 give $0.25$ . The nominal 95 percent percentile interval for the difference in MAE is therefore $[-2, 0.25]$ units. It contains zero, so this approximation does not clearly separate the models even though the point estimate favors model A. Containing zero does not show that the models perform equally well, and with four cases the stated level is only a rough guide.

Paired comparison

Definition Let frozen models A and B be scored on the same $n$ cases, with per-case losses $\ell_{A,i}$ and $\ell_{B,i}$ . A paired comparison works with the casewise differences $d_i = \ell_{A,i} - \ell_{B,i}$ , whose mean $\bar{d}$ equals the metric of A minus the metric of B when the metric averages per-case losses. If the cases are independent and the per-case losses have variances $\sigma_A^2$ and $\sigma_B^2$ and covariance $\sigma_{AB}$ , then

\begin{gathered} \sigma_d^2 = \sigma_A^2 + \sigma_B^2 - 2\sigma_{AB}, \\[0.4em] \operatorname{SE}(\bar{d}) = \sigma_d / \sqrt{n}. \end{gathered}

The paired bootstrap draws one set of case indices for each resample and computes the statistic for both models on those same cases. For a metric that is not a mean of per-case losses, such as the root mean squared error or the ROC AUC, there are no casewise differences, but the paired bootstrap still applies by computing both metrics on each shared resample.

In plain words Some cases are hard for every model. Pairing keeps each case’s difficulty attached to both models, so the comparison measures how differently the models handle the same cases. Resampling the two models’ errors separately treats them as if they came from different evaluation sets. When the same cases are hard for both models, the covariance is positive and separate resampling overstates the variability of the difference. Fix the sign convention before computing. Here the difference is A minus B for an error metric, so negative values favor model A.

Example The four differences $-2$ , $1$ , $-2$ and $-1$ have mean $-1$ . The per-case errors have plug-in variances $2.5$ for A and $1.5$ for B and plug-in covariance $1.25$ , so the differences have variance $2.5 + 1.5 - 2 \cdot 1.25 = 1.5$ , and the paired bootstrap standard error is $\sqrt{1.5/4} \approx 0.61$ units. Resampling the two models independently gives $\sqrt{(2.5 + 1.5)/4} = 1$ unit. The independent version is larger because it discards the fact that case 4 is the hardest case for both models.

Independent sampling unit

Definition The independent sampling unit is the unit drawn independently from the target population, such as a customer, a patient, a household or a site. A bootstrap for such data resamples whole units with replacement and keeps all rows of each selected unit together, and a paired comparison applies the same resampled units to both models. The statistic must also state its weighting. A row-weighted metric averages over all rows, while a unit-weighted metric first averages within each unit and then over units, and the two estimate different population quantities. Time-ordered data, where errors on nearby days are dependent, need schemes such as resampling blocks of consecutive periods, which rest on assumptions of their own, and no resampling scheme represents a future drift that the data do not contain.

In plain words Resample what was independently sampled. If the rows of one customer resemble each other, resampling rows treats them as separate pieces of evidence and usually makes the metric look more certain than it is. A resampling function in a library cannot know how the data were collected, so the unit and the weighting are decided from the design and from the question the metric answers.

Example Customer A has 3 visits, each with absolute error 0, and customer B has 1 visit with absolute error 6. The visit-weighted MAE is $6/4 = 1.5$ and the customer-weighted MAE is $(0 + 6)/2 = 3$ . Neither is wrong, since they answer different questions. Resampling customers gives four equally likely ordered resamples, AA, AB, BA and BB, with visit-weighted MAEs 0, 1.5, 1.5 and 6 and a bootstrap standard error of $2.25$ . Resampling the four visits instead gives a standard error of about $1.30$ , and it produces resamples, such as two of customer A’s visits with customer B’s single visit drawn twice, that no draw of customers could produce. Two customers are far too few for any interval, but the direction of the difference is the usual one when rows of a unit resemble each other.

Check yourself

Two frozen models have absolute errors 2, 0 and 4 for model A and 1, 1 and 5 for model B on three new independent cases. Find the paired mean difference A minus B. Then find it for the resample made of cases 3, 3 and 1, and for the resample made of case 1 three times. Does this bootstrap measure the uncertainty that comes from retraining the models?

Show the answer

The casewise differences are $2 - 1 = 1$ , $0 - 1 = -1$ and $4 - 5 = -1$ , so the paired mean difference is $-1/3$ , which equals the MAE of A, $2$ , minus the MAE of B, $7/3$ . The resample of cases 3, 3 and 1 selects the differences $-1$ , $-1$ and $1$ , with mean $-1/3$ again. That equality is a coincidence of this resample. Case 1 drawn three times gives $+1$ .

It does not measure retraining uncertainty. Both models stay frozen, so the bootstrap describes how their evaluation statistic varies when the cases are resampled. Variation from new training samples, from repeating the tuning, and the optimism of any search already run on these cases are all outside it.

For the same three differences, find the exact bootstrap distribution of the mean difference, its standard deviation, and the nominal 90 percent percentile interval with the nearest-rank rule. Does an interval that contains zero show that the models are equally good?

Show the answer

There are $3^3 = 27$ ordered resamples. Case 1 has difference $+1$ and cases 2 and 3 have $-1$ , so if case 1 is drawn $K$ times the mean is $(2K - 3)/3$ . Case 1 is never drawn in $2^3 = 8$ resamples, drawn once in $3 \cdot 2^2 = 12$ , twice in $3 \cdot 2 = 6$ and three times in $1$ . The bootstrap distribution therefore puts $8/27$ on $-1$ , $12/27$ on $-1/3$ , $6/27$ on $1/3$ and $1/27$ on $1$ .

The differences have plug-in variance $8/9$ , so the bootstrap standard deviation is $\sqrt{(8/9)/3} = \sqrt{8/27} \approx 0.54$ . The nearest ranks are $\lceil 0.05 \cdot 27 \rceil = 2$ and $\lceil 0.95 \cdot 27 \rceil = 26$ . Ranks 1 to 8 hold $-1$ and ranks 21 to 26 hold $1/3$ , so the interval is $[-1, 1/3]$ .

The interval contains zero, but that does not show the models are equally good. It shows only that three cases cannot separate them under this approximation, and three cases are far too few for the nominal level to mean much.

An evaluation set holds 500 visits from 60 customers, who were sampled independently. A colleague bootstraps the 500 visit-level errors of model A and of model B separately, takes the 2.5th and 97.5th percentiles of the difference in MAE, and says that after deployment model A will be at most that much worse than model B. Name the problems and describe a better analysis.

Show the answer

The visits of one customer are dependent, so the customer is the independent sampling unit. Resampling visits treats them as independent and usually understates the uncertainty. Resampling the two models separately breaks the pairing, so the shared difficulty of each customer’s visits no longer cancels in the difference. The weighting is also unstated, and a visit-weighted MAE answers a different question from a customer-weighted one.

A better analysis draws 60 customers with replacement in each resample, keeps all of their visits, computes both models’ MAE on those same visits with the chosen weighting, and records the difference. The percentile interval of these differences describes, approximately, the evaluation uncertainty of the two frozen models for customers like those sampled. It is not a guarantee about deployment. It leaves out retraining, a population that changes over time and customers unlike the ones in the evaluation set.

Bootstrap Uncertainty and Model Comparisons

Key terms

Metric uncertainty

Bootstrap resampling

Bootstrap distribution

Percentile interval

Paired comparison

Independent sampling unit

Check yourself

How this lesson connects

Builds on

Used later in