Bootstrap
Section of Estimating error rates, part of Statistical learning
Bootstrap
| Type | Section |
| Taught in | Estimating error rates |
| Part | Statistical learning |
| Questions using it | 7 |
A holdout and a cross-validation fold both train on a subset and test on the complement. The bootstrap builds the training set differently (Efron, 1981, 1983). A non-parametric bootstrap sample of size n is drawn with replacement from the observed n cases, that is, from the empirical distribution. Some observations are missing from the draw and others appear more than once.
The probability that a given observation enters a bootstrap sample is one minus the probability that it is left out of all n draws,
1-\Bigl(1-\frac1n\Bigr)^n.
Write 1-1/n=\exp\bigl(\log(1-1/n)\bigr). Then
\Bigl(1-\frac1n\Bigr)^n =\exp\Bigl(n\log\bigl(1-\tfrac1n\bigr)\Bigr).
The expansion \log(1-1/n)=-1/n-1/(2n^2)+O(n^{-3}) gives n\log(1-1/n)\to -1, so
\Bigl(1-\frac1n\Bigr)^n\to e^{-1} \qquad\text{and}\qquad 1-\Bigl(1-\frac1n\Bigr)^n\to 1-e^{-1}\approx 0.632
as n\to\infty. For n=10 the inclusion probability is 0.651. For n=100 it is 0.634. The expected number of distinct observations in a bootstrap sample is therefore about 0.632n. The cases left out are a test set that the draw itself created. The right-hand panel of that limit is the curve of inclusion probability against sample size: it has already fallen close to 0.632 by n=50.
Definition 1 (Bootstrap error and the .632 correction) Efron’s bootstrap estimator scores each observation only on the bootstrap samples that excluded it. If C_{-i} is the set of bootstrap samples that do not contain observation i, and \eta_b is the classifier trained on bootstrap sample b,
\widehat{\mathrm{Err}}^{(\mathrm{BOOT})} =\frac1n\sum_{i=1}^n \frac{1}{|C_{-i}|} \sum_{b\in C_{-i}} Q\bigl(y_i,\eta_b(x_i)\bigr).
Each case is tested only by rules that did not see it, the same discipline as cross-validation. Because each bootstrap training set contains only about 0.632n distinct observations, the trained rules are weaker than a rule trained on all n distinct cases, and \widehat{\mathrm{Err}}^{(\mathrm{BOOT})} is generally biased upward.
The .632 estimator pulls that upward bias back toward the apparent error, with weights taken from the limiting inclusion probability and its complement:
\widehat{\mathrm{Err}}^{(.632)} =0.368\,\mathrm{err}+0.632\,\widehat{\mathrm{Err}}^{(\mathrm{BOOT})}.
The weight 0.632 is the limiting probability that a case is inside the bootstrap sample, and 0.368=1-0.632 is the limiting probability that it is left out. The formula combines the optimistic apparent error with the pessimistic out-of-bag bootstrap error. It is a correction with assumptions, not an identity that recovers the unknown generalisation error. Severe overfitting can still make it optimistic. Compare it with a resampling design suited to the full fitting procedure, rather than treating the numerical weights as a guarantee.
Used in
- Taught in Estimating error rates
- Also used in Mixtures and the EM algorithm · Ensembles, random forests, and boosting
- Questions that use it (7) — Label switching · The 0.632 rule (answer) · A tempting wrong turn (answer) · Variance of an average (answer) · Out-of-bag counts · A tempting wrong turn (answer) · Why an ensemble might improve a tree
- All 7 questions on Estimating error rates
See also
Bagging · Bootstrap error and the correction · Random forest · Fixed-rule error · Confusion matrix · Apparent error · Leave-one-out cross-validation · -fold cross-validation