The median body mass index (BMI) of the 442 patients in the diabetes study is 25.70. How precise is that number? For a mean there is a formula: the standard deviation divided by $\sqrt{n}$. For a median there is no simple exact formula, and the large-sample approximation depends on the height of the population's density at its median, which is itself hard to estimate. The same problem arises for a correlation, a ratio, a regression coefficient when the textbook assumptions fail, or the error rate of a classifier.
The bootstrap, introduced by Efron (1979), answers all of these questions the same way. If many samples could be drawn from the population, the spread of the median across them would show its precision directly. Only one sample exists, so the bootstrap draws new samples from the sample itself, computes the median of each, and uses their spread. It replaces a formula with computation, and it works for almost any statistic. This article covers how and why it works, checks its accuracy by simulation, shows where it fails, and then turns to its use in estimating the prediction error of a model, the subject of this topic.
The idea: resample the sample
Suppose $z_1, \dots, z_n$ are an independent sample from an unknown distribution $F$, and $\hat{\theta} = s(z_1, \dots, z_n)$ is a statistic such as their median. Its standard error is the standard deviation of $\hat{\theta}$ over repeated samples of size $n$ from $F$. It cannot be computed, because $F$ is unknown.
The best available estimate of $F$ is the empirical distribution $\hat{F}$, which puts probability $1/n$ on each observed value. The bootstrap's step is to compute the standard error with $\hat{F}$ in place of $F$: to ask how much $\hat{\theta}$ would vary if the population were exactly the sample. This substitution is the plug-in principle. Drawing a sample of size $n$ from $\hat{F}$ means drawing $n$ times from the observed values, each time choosing each value with probability $1/n$, that is, sampling with replacement. Such a draw is a bootstrap sample, written $z^{*1}$.
The standard error under $\hat{F}$ could in principle be computed exactly, by enumerating all possible bootstrap samples, but their number is astronomical for any real $n$. Instead, draw $B$ bootstrap samples at random, compute the statistic on each, $\hat{\theta}^{*1}, \dots, \hat{\theta}^{*B}$, and take their standard deviation (Hastie, Tibshirani and Friedman, 2009, eq. 7.53; James, Witten, Hastie and Tibshirani, 2021, eq. 5.8):
$$\widehat{\mathrm{SE}}_B = \sqrt{\frac{1}{B - 1} \sum_{b=1}^{B} \bigl(\hat{\theta}^{*b} - \bar{\theta}^{*}\bigr)^2}, \qquad \bar{\theta}^{*} = \frac{1}{B} \sum_{b=1}^{B} \hat{\theta}^{*b}.$$
Two approximations are stacked here. The first, $\hat{F}$ for $F$, is the statistical one, and its quality depends on the sample size and the statistic. The second, $B$ random resamples for all of them, is a Monte Carlo approximation that can be made as accurate as computing time allows.
What a bootstrap sample looks like
A bootstrap sample of the 442 patients is 442 draws with replacement from the 442. In the first one drawn by the article's script (seed 742), 179 patients appear once, 74 twice, 21 three times and 12 four or more times, while 156 do not appear at all. A given patient is missed by one draw with probability $1 - 1/n$, and by all $n$ draws with probability $(1 - 1/n)^n$, so the probability that it appears is
$$1 - \Bigl(1 - \frac{1}{n}\Bigr)^n \;\to\; 1 - e^{-1} \approx 0.632 \quad \text{as } n \to \infty.$$
This is 0.6723 for $n = 5$, 0.6513 for $n = 10$ and 0.6325 for $n = 442$; over 10,000 bootstrap samples of the diabetes data, the share of distinct patients averaged 0.6327. Random Forests puts the roughly 37% of cases left out of each sample, the out-of-bag cases, to work as a built-in test set. The number 0.632 returns below.
Standard errors and percentile intervals
The median BMI
From $B = 2{,}000$ bootstrap samples of the 442 BMI values, the bootstrap standard error of the median is 0.215. The bootstrap medians take only 34 distinct values, because a median is always one of the data values or the midpoint of two, and BMI is recorded to one decimal place; the bootstrap distribution of a median is lumpy for that reason, but its spread is still informative.
The bootstrap distribution also gives a confidence interval directly. The percentile interval at level 95% runs from the 2.5th to the 97.5th percentile of the $B$ bootstrap values: here 25.35 to 26.20. Its logic is that the bootstrap values vary around $\hat{\theta}$ roughly as $\hat{\theta}$ varies around the true value, so the range that holds the middle 95% of them is a plausible range for the truth. That reasoning is exact only under conditions (the bootstrap distribution must be unbiased and of the right shape), which is why the coverage checks below matter.
A regression slope
A least-squares regression of disease progression on BMI alone, as in Simple Linear Regression, gives a slope of 10.233 progression units per unit of BMI. Its textbook standard error, from the formula that assumes errors of constant variance, is 0.674.
The bootstrap can resample a regression in two ways. Pairs (or case) resampling draws whole patients, each with their BMI and progression, and refits the line to each bootstrap sample. Residual resampling keeps the inputs fixed and adds resampled residuals to the fitted values; it assumes the errors are exchangeable, which is the same constant-variance assumption as the textbook formula. Pairs resampling makes no such assumption. With $B = 2{,}000$:
| Standard error of the slope | Value |
|---|---|
| Textbook formula (constant error variance) | 0.674 |
| Bootstrap, resampling patients | 0.607 |
| Heteroskedasticity-robust (sandwich, HC0) | 0.613 |
The pairs bootstrap agrees with the robust standard error, the White (1980) estimator described in Linear Regression Assumptions, to within 1%, and not with the textbook one. That is what one would hope: both measure the slope's variability without assuming constant error variance. Here the spread of progression is not the same at all levels of BMI, and the textbook formula overstates the slope's uncertainty by about 10%. The 95% percentile interval, 9.04 to 11.44, is correspondingly narrower than the textbook $t$ interval, 8.91 to 11.56. The same article discusses when unequal variance matters and what else can be done about it.
The bootstrap also estimates bias: the mean of the bootstrap slopes minus the original slope, here $+0.024$, about 4% of a standard error. A bias estimate this small relative to the standard error is noise and is best ignored; correcting for it would add variance without a reliable gain.
How many resamples?
$B$ controls only the Monte Carlo error, the variation that would disappear with infinitely many resamples. To see its size, the bootstrap standard error of the slope was computed 200 times for each of several values of $B$:
| $B$ | Mean bootstrap SE | SD across 200 repetitions | Relative SD |
|---|---|---|---|
| 25 | 0.615 | 0.089 | 14.4% |
| 50 | 0.610 | 0.065 | 10.7% |
| 100 | 0.617 | 0.046 | 7.5% |
| 200 | 0.614 | 0.030 | 4.9% |
| 1,000 | 0.616 | 0.015 | 2.4% |
The relative error falls like $1/\sqrt{2B}$, the sampling error of a standard deviation estimated from $B$ values: about 7% at $B = 100$, enough for a standard error reported to two significant figures. Percentile intervals depend on the tails of the bootstrap distribution, which few resamples describe poorly, so they need $B$ in the thousands. Computing is rarely the constraint for a statistic like a median or a slope, and $B = 2{,}000$ or more costs a fraction of a second.
Checking the bootstrap by simulation
On real data the true standard error is unknown, so the bootstrap cannot be checked there. In a simulation, the population is known and the truth can be computed. The population here is an exponential distribution with mean 1, which is strongly skewed to the right, like incomes, waiting times or many laboratory measurements.
The standard error of a median
For samples of $n = 25$, the true standard deviation of the sample median, computed from 200,000 samples, is 0.2014. For each of 1,000 samples of 25, the bootstrap standard error was computed with $B = 1{,}000$.
On average the bootstrap gets the standard error about right: the 1,000 estimates have a mean of 0.2173 and a median of 0.2132, within 8% of the truth. Any single estimate is much less accurate. The middle 80% run from 0.1298 to 0.3041, so one sample of 25 can give a standard error a third too small or half too large. That is not a failure of the bootstrap. A sample of 25 contains limited information about the shape of the population near its median, and no method can extract more. Raising $B$ would not help, because the variation comes from the sample, not from the resampling.
Coverage of percentile intervals
A 95% confidence interval should contain the true value in 95% of samples. For the mean of the exponential population, 4,000 samples were drawn at each of four sizes, and two intervals computed from each: the textbook $t$ interval and the bootstrap percentile interval with $B = 2{,}000$.
| $n$ | $t$ interval | Bootstrap percentile |
|---|---|---|
| 10 | 0.896 | 0.854 |
| 20 | 0.919 | 0.903 |
| 40 | 0.938 | 0.933 |
| 80 | 0.940 | 0.934 |
For a skewed population and small samples, the percentile interval covers the mean less often than the $t$ interval, which itself falls short. The reason is that the bootstrap distribution of the mean is centered on the sample mean and inherits the sample's own spread. A sample that missed the long right tail has both a low mean and a small spread, so its interval is too low and too narrow together. The same failure of the $t$ interval, and its cause, are worked out in the course wiki's Confidence Intervals for a Mean. The bootstrap does not remove it; resampling a sample that lacks the tail cannot create one. For the median, which does not depend on the tail, the percentile interval did well: coverage 0.952 at $n = 25$ and 0.946 at $n = 80$.
Refinements of the percentile interval adjust its endpoints for bias and skewness in the bootstrap distribution. The most widely used, the bias-corrected and accelerated (BCa) interval, is the default in SciPy's scipy.stats.bootstrap. They improve coverage in many settings but cannot add information a small sample lacks. A bootstrap interval for a difference in means is worked in the course wiki's Significance Testing.
Where the bootstrap fails
The bootstrap works when the statistic depends smoothly on the empirical distribution, as means, medians, regression coefficients and correlations do. It fails for statistics that depend on the extremes of the sample. The sample maximum is the standard example. For 50 values drawn from a uniform distribution on $[0, 1]$, the true maximum of the population is 1, and the sample maximum is always below it. A bootstrap sample contains the sample's own maximum, and so reproduces it exactly, whenever that observation is drawn at least once, which happens with probability $1 - (1 - 1/50)^{50} = 0.636$. In 10,000 bootstrap samples, 63.2% had exactly the original maximum. The bootstrap distribution therefore has a spike at the observed value and never goes beyond it, while the true sampling distribution is continuous and lies entirely below 1. No bootstrap interval built from it can be trusted.
Other limits are less dramatic but more common:
- The sample must represent the population. A biased or tiny sample produces bootstrap samples with the same bias, and a precise-looking standard error around the wrong value.
- The resampling must match how the data were collected. Resampling individual observations assumes they are independent. Time series, repeated measurements on the same patients and clustered samples need resampling of blocks, patients or clusters instead.
- Selection steps must be resampled too. If a model's inputs were chosen by a search, the usual standard errors of the chosen model's coefficients are not valid, because they ignore the search (Hastie et al., 2009, §3.3.2). A bootstrap can account for the search only if the search is repeated on each bootstrap sample; resampling the final model alone ignores it in the same way.
Estimating prediction error by the bootstrap
The bootstrap can also estimate how well a model predicts new data, the question that cross-validation answers. The obvious version does not work, and the reasons why lead to estimators that do.
The naive bootstrap
Fit the model to each bootstrap sample, and measure its error on the original dataset (Hastie et al., 2009, eq. 7.54):
$$\widehat{\mathrm{Err}}_{\text{boot}} = \frac{1}{B} \frac{1}{n} \sum_{b=1}^{B} \sum_{i=1}^{n} L\bigl(y_i, \hat{f}^{*b}(x_i)\bigr).$$
The training and test data overlap: each bootstrap sample contains about 63% of the original observations, and a model is evaluated on many cases it was fitted to. Hastie et al. (2009, §7.11) give a stark example. Suppose two equal classes and inputs that carry no information about them, so that every classifier has a true error rate of 0.5, and use the 1-nearest-neighbor classifier. A case that is in the bootstrap sample is its own nearest neighbor and is classified correctly; a case that is not is classified at random. The expected naive estimate is therefore $0.5 \times 0.368 = 0.184$, far below 0.5.
The leave-one-out bootstrap
The fix mirrors cross-validation: evaluate each case only with the models that did not see it. Let $C^{-i}$ be the set of bootstrap samples that do not contain case $i$. The leave-one-out bootstrap estimate is (Hastie et al., 2009, eq. 7.56)
$$\widehat{\mathrm{Err}}^{(1)} = \frac{1}{n} \sum_{i=1}^{n} \frac{1}{|C^{-i}|} \sum_{b \in C^{-i}} L\bigl(y_i, \hat{f}^{*b}(x_i)\bigr).$$
Each case is out of bag in about 37% of the bootstrap samples, so with $B = 200$ every case has around 74 models to average over. This is the bootstrap analogue of out-of-bag error in Random Forests, where each case is predicted by the trees that did not see it. A closely related procedure, common in practice, records the error on the out-of-bag cases separately for each bootstrap round and averages the rounds; it weights cases slightly differently but estimates the same thing.
The leave-one-out bootstrap has the opposite problem from the naive one. Each model is fitted to a bootstrap sample containing only about $0.632n$ distinct cases, so it behaves roughly like a model fitted to a training set of that size, and its error is biased upward in the way that 2-fold cross-validation is (Hastie et al., 2009, §7.11).
The .632 and .632+ estimators
Efron (1983) proposed to cancel the two biases by mixing the optimistic training error $\overline{\mathrm{err}}$ with the pessimistic leave-one-out bootstrap:
$$\widehat{\mathrm{Err}}^{(.632)} = 0.368 \cdot \overline{\mathrm{err}} + 0.632 \cdot \widehat{\mathrm{Err}}^{(1)}.$$
The weights come from the inclusion probability $1 - e^{-1}$ derived above. Its derivation is not simple, and Hastie et al. (2009, §7.11) describe it informally as pulling the leave-one-out bootstrap down toward the training error.
The .632 estimator fails when a model fits its training data perfectly. In the no-information example above, the 1-nearest-neighbor classifier has $\overline{\mathrm{err}} = 0$ and $\widehat{\mathrm{Err}}^{(1)} \approx 0.5$, so the .632 estimate is about $0.632 \times 0.5 = 0.316$, while the truth is 0.5. Efron and Tibshirani (1997) corrected this with the .632+ estimator, which gives more weight to $\widehat{\mathrm{Err}}^{(1)}$ the more the model overfits. It first estimates the no-information error rate $\hat{\gamma}$, the error the model would make if inputs and outputs were unrelated, by evaluating its predictions on all $n^2$ pairings of inputs with outcomes. The relative overfitting rate
$$\hat{R} = \frac{\widehat{\mathrm{Err}}^{(1)} - \overline{\mathrm{err}}}{\hat{\gamma} - \overline{\mathrm{err}}}$$
runs from 0, when the leave-one-out bootstrap error equals the training error (no overfitting), to 1, when it equals the no-information rate. The weight on $\widehat{\mathrm{Err}}^{(1)}$ is then $\hat{w} = 0.632 / (1 - 0.368 \hat{R})$, which runs from 0.632 to 1 (Hastie et al., 2009, eqs. 7.58 to 7.61):
$$\widehat{\mathrm{Err}}^{(.632+)} = (1 - \hat{w}) \cdot \overline{\mathrm{err}} + \hat{w} \cdot \widehat{\mathrm{Err}}^{(1)}.$$
The article's script also caps $\widehat{\mathrm{Err}}^{(1)}$ at $\hat{\gamma}$ and keeps $\hat{R}$ between 0 and 1, so that the weight stays in that range.
A comparison by simulation
The estimators were compared in the simulation used for cross-validation: training sets of 40 points with $x$ uniform on $[0, 1]$, $y = \sin(5x)$ plus normal noise with standard deviation 0.3, a cubic fitted by least squares and 1-nearest-neighbor regression, 1,000 training sets (seed 742) and $B = 200$. The true conditional error of each fitted model is known, and its average over training sets, the expected error, is the target.
| Cubic (expected error 0.1051) | Mean | Bias | SD |
|---|---|---|---|
| Training error | 0.0828 | −0.0223 | 0.0189 |
| Naive bootstrap | 0.0941 | −0.0110 | 0.0217 |
| Leave-one-out bootstrap | 0.1190 | +0.0139 | 0.0289 |
| .632 | 0.1056 | +0.0006 | 0.0249 |
| .632+ | 0.1060 | +0.0009 | 0.0251 |
| 10-fold cross-validation | 0.1060 | +0.0009 | 0.0258 |
| 1-nearest neighbor (expected error 0.1844) | Mean | Bias | SD |
|---|---|---|---|
| Training error | 0.0000 | −0.1844 | 0.0000 |
| Naive bootstrap | 0.0690 | −0.1153 | 0.0174 |
| Leave-one-out bootstrap | 0.1900 | +0.0056 | 0.0477 |
| .632 | 0.1201 | −0.0643 | 0.0302 |
| .632+ | 0.1285 | −0.0559 | 0.0343 |
| 10-fold cross-validation | 0.1851 | +0.0007 | 0.0546 |
For the cubic, a "light fitting" method in the phrase of Hastie et al. (2009, §7.11), the picture is the textbook one. Training error and the naive bootstrap are optimistic, the leave-one-out bootstrap is pessimistic by 13%, and the .632 and .632+ estimators correct it almost exactly, with slightly less variance than 10-fold cross-validation.
For 1-nearest-neighbor regression the corrections go wrong. The training error is zero, so the .632 estimate is just 0.632 times the leave-one-out bootstrap, 35% too low. The .632+ estimator helps only a little, because the relative overfitting rate is far below 1: the leave-one-out bootstrap error, about 0.19, is much smaller than the no-information error, so the formula judges the overfitting to be moderate and applies little correction. Meanwhile the leave-one-out bootstrap itself is nearly unbiased here, since the error of 1-nearest-neighbor regression changes little with the size of the training set: 0.193 with 20 points against 0.184 with 40, in the simulation of Cross-Validation. The .632 family is built for one shape of learning curve, and a method with a different shape defeats it.
The no-information classification example of Hastie et al. (2009) reproduces their numbers: over 200 datasets of 50 cases with five irrelevant inputs, the naive bootstrap averaged 0.184, the .632 estimator 0.319, the leave-one-out bootstrap 0.505 and the .632+ estimator 0.466. The .632+ estimator is right when $\hat{R} = 1$; in datasets where the leave-one-out bootstrap came out slightly below 0.5 by chance, $\hat{R}$ fell below 1 and the estimate dropped with it.
The practical lesson is the one Hastie et al. (2009, §7.11.1) draw from their own comparisons: in their examples, cross-validation and the bootstrap selected models about equally well and estimated the error of the chosen model about equally well. Cross-validation is simpler to reason about and does not depend on how a method overfits, which is why it is the more common choice. The bootstrap's strength lies in the first half of this article, measuring the uncertainty of an estimate, where cross-validation has nothing to offer.
The diabetes data
For the ten-input linear regression on the diabetes data, 200 bootstrap rounds gave out-of-bag sets of 140 to 181 patients (mean 162.9). The out-of-bag MSE averaged 3,081.3 over the rounds, with a standard deviation of 255.6; the leave-one-out bootstrap estimate is 3,074.2, every patient having been out of bag in at least 53 rounds. Both are above the 10-fold cross-validation estimate of 2,985.2 and the leave-one-out value of 3,001.8 from Cross-Validation, as expected from models fitted to about 280 distinct patients rather than 398 or 441. The .632 estimate, $0.368 \times 2{,}859.7 + 0.632 \times 3{,}074.2 = 2{,}995.3$, lands between the 10-fold and leave-one-out values.
The spread of the per-round errors needs careful reading. Their 2.5th and 97.5th percentiles, 2,503 and 3,557, show how much a single round's estimate varies, each from about 160 patients and one bootstrap model. They are not a 95% confidence interval for the model's error. The leave-one-out bootstrap averages over all the rounds and is much less variable than any one of them; an interval for it would need a further layer of resampling.
In Python
import numpy as np
from scipy import stats
from sklearn.datasets import load_diabetes
X, y = load_diabetes(return_X_y=True, scaled=False)
bmi = X[:, 2]
rng = np.random.default_rng(0)
# by hand: B bootstrap samples of the row indices
idx = rng.integers(0, len(y), size=(2000, len(y)))
med = np.median(bmi[idx], axis=1)
print(med.std(ddof=1), np.percentile(med, [2.5, 97.5])) # 0.217 [25.35 26.2]
def slope(i):
x, t = bmi[i], y[i]
return np.cov(x, t)[0, 1] / np.var(x, ddof=1)
print(np.std([slope(i) for i in idx], ddof=1)) # 0.612
# SciPy: percentile or BCa intervals for any statistic
res = stats.bootstrap((bmi,), np.median, n_resamples=2000, method="percentile", rng=rng)
print(res.standard_error, res.confidence_interval) # 0.214, (25.35, 26.2)
Drawing indices rather than rows keeps the cases together: the same idx resamples patients for any statistic computed from their BMI and progression jointly, as the slope is. scikit-learn's sklearn.utils.resample(X, y, replace=True, random_state=...) does the same for arrays and data frames, and the out-of-bag cases are those whose indices do not appear in the sample. For bagged models, oob_score=True computes out-of-bag error during fitting (see Random Forests). The numbers in this article are computed by tools/experiments/data-science/bootstrap-method.py in the site's repository.
References
- Efron, B. (1979). Bootstrap methods: Another look at the jackknife. The Annals of Statistics, 7(1), 1–26. record
- Efron, B. (1983). Estimating the error rate of a prediction rule: Improvement on cross-validation. Journal of the American Statistical Association, 78(382), 316–331. record
- Efron, B., and Tibshirani, R. (1997). Improvements on cross-validation: The .632+ bootstrap method. Journal of the American Statistical Association, 92(438), 548–560. record
- Hastie, T., Tibshirani, R., and Friedman, J. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2nd ed.). Springer. record · 23 pages
- James, G., Witten, D., Hastie, T., and Tibshirani, R. (2021). An Introduction to Statistical Learning with Applications in R (2nd ed.). Springer. record · 30 pages
- White, H. (1980). A heteroskedasticity-consistent covariance matrix estimator and a direct test for heteroskedasticity. Econometrica, 48(4), 817–838. record · 2 pages