Module 6: Ensembles: random forests and boosting · Lesson 6.2 · about 20 min
Bagging and bootstrap samples
To get many different models from one dataset, train each on a bootstrap sample: n rows drawn with replacement. About a third of the rows are left out each time, which gives a free test set. Draw samples and count.
Module 6 · about 20 minutes · read first: 1.6, 6.1. You’ll be able to draw a bootstrap sample, explain the 63 % rule, and describe bagging and out-of-bag scores.
1. Why this matters
Lesson 6.1 showed that a crowd of models helps only if they differ. The bootstrap is the simplest way to make many different datasets from one, and it is used far beyond machine learning: statisticians use it to put error bars on almost any estimate. Bagging, the ensemble built on it, is the “random” half of random forests.
2. Sampling with replacement
Imagine writing each row of your data on a ball and putting the balls in a bag. A bootstrap sample of rows is made by drawing a ball, writing down its row, putting it back, and repeating times. So:
- it has the same size as the original data;
- some rows come up twice or more;
- some never come up. These are the out-of-bag (OOB) rows.
For large , about 63.2 % of the rows appear at least once and 36.8 % are left out. (With only 12 rows the share drawn is a little higher, about 65 %.)
Five houses with prices (in $1,000s) 200, 220, 250, 300, 500. Their mean is 294.
Draw five times with replacement. Sample 1: 200, 200, 250, 300, 500. The 200 came up twice; the 220 never did. Mean 290.
Draw again. Sample 2: 220, 250, 250, 300, 300. This time the $500k house is out of the bag. Mean 264.
And again. Sample 3: 200, 220, 220, 250, 500. Mean 278.
Read the spread. The means range from 264 to 290. Over hundreds of samples, that spread shows how much the mean would move with a new set of five houses: a bootstrap error bar.
3. Bagging
Bagging (bootstrap aggregating, Leo Breiman, 1996):
- Draw bootstrap samples (say 100).
- Train one model on each. Use a model that overfits easily, so each one comes out different: deep, unpruned trees are ideal.
- Predict by averaging (numbers) or voting (classes).
Each deep tree has low bias (it can fit the pattern) and high variance (it changes a lot with the data). Averaging keeps the low bias and cuts the variance. Bagging does little for steady models such as linear regression, whose fits barely change from sample to sample.
- B
- The number of bootstrap samples, and so the number of models.
- fb(x)
- The prediction of the model trained on sample b.
- (1/B) Σ fb(x)
- The bagged prediction: the average of all B models.
- (1 − 1/n)n ≈ 0.368
- The chance a given row is left out of one sample.
- Physical meaning
- Asking 100 friends to each skim a different, partly overlapping pile of reviews before recommending a film, then going with the most common recommendation. Each friend is a bit unreliable; together they are steady.
Out-of-bag score. Each row was left out by about a third of the trees. Predict it using just those trees and compare with the truth. Over all rows, that gives a test-like score for free, without setting aside a validation set.
“Drawing with replacement just wastes rows: some are repeated and a third are thrown away.” It is the point. The repeats and gaps are what make each sample, and so each model, different. And the rows left out are not wasted: they become a free test set for the models that never saw them.
Maths and principle
Principle: treat the sample as a stand-in for the population, and resample it to see how much a model would change with different data.
The 63.2 % rule: a given row is missed by one draw with probability , and by all draws with probability
so it is in the sample with probability .
The bagged prediction for numbers, with models :
Try it: with , what is the chance that a given row is left out of a bootstrap sample? (.)
4. Worked example
Made-up numbers. Five houses with prices (in $1,000s) 200, 220, 250, 300, 500. Three bootstrap samples:
| sample | rows drawn | mean price |
|---|---|---|
| 1 | 200, 200, 250, 300, 500 | 290 |
| 2 | 220, 250, 250, 300, 300 | 264 |
| 3 | 200, 220, 220, 250, 500 | 278 |
The original mean is 294; the three bootstrap means spread from 264 to 290. That spread, worked out over hundreds of samples, estimates how much the mean would move with a new set of five houses: a bootstrap error bar. Sample 2 never drew the $500k house: it is out-of-bag there, and a model trained on sample 2 could be tested on it.
5. Practice
- In the simulation, draw 100 samples. What share of different rows do you get on average?
- Why do deep trees suit bagging better than shallow ones?
- What is the out-of-bag score, and why is it useful?
Answers
- Close to 65 % for 12 rows (), heading to 63.2 % for large data.
- Deep trees change a lot from sample to sample (high variance), which averaging removes; shallow trees are all alike, so their average is no better.
- Each row is scored only by the trees that did not see it: an honest estimate of test accuracy without a separate validation set.
- A bootstrap sample draws n rows with replacement: same size, some rows repeated, about 36.8 % left out.
- Bagging trains one model per bootstrap sample and averages or votes.
- It works best with unstable, high-variance models such as deep trees.
- Rows a model never saw (out-of-bag) give a free, honest test score.
Try it on your own data: the bootstrap test tool draws thousands of bootstrap samples from your own numbers and gives the error bar on their mean.
New words: bootstrap sample, sampling with replacement, out-of-bag, bagging, aggregate.
Check yourself
Sources
- Breiman (1996), Bagging predictors, Machine Learning 24, 123-140 https://doi.org/10.1007/BF00058655
- Efron (1979), Bootstrap methods: another look at the jackknife, The Annals of Statistics 7(1), 1-26 https://doi.org/10.1214/aos/1176344552
- James, Witten, Hastie and Tibshirani (2021), An Introduction to Statistical Learning, 2nd edition, Springer, Sections 5.2 (The bootstrap) and 8.2.1 (Bagging) https://www.statlearning.com/
Your ticks stay in this browser. Save them as a file on the course home.
Updated 2026-11-22. Numbers in the examples are made up to show the idea unless a source is given. Simulations run in your browser; nothing you type is sent anywhere.