Home / Learn / Data & AI / ML foundations / Lesson 6.2
All lessons

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.

Key points, meanings and formulas on one page: choose "Save as PDF" in the print box.

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.

From one dataset you can make many slightly different ones by drawing rows at random and putting each back, then train a model on each and let them vote.

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 n rows is made by drawing a ball, writing down its row, putting it back, and repeating n 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.
Try it: draw bootstrap samples
this sample: different rows
left out (out-of-bag)
average share of different rows
Each tile is one of 12 training rows; the number under it is how many times this sample picked it. Picks are made with replacement, so a row can be picked again. Dashed tiles were not picked at all: they make a free test set for the model built on this sample. For large data the share of different rows tends to 1 − 1/e ≈ 63.2 %.

For large n, 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):

  1. Draw B bootstrap samples (say 100).
  2. Train one model on each. Use a model that overfits easily, so each one comes out different: deep, unpruned trees are ideal.
  3. 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 1−1/n, and by all n draws with probability

(1−1n)n⟶e−1≈0.368(n→∞)

so it is in the sample with probability 1−e−1≈0.632.

The bagged prediction for numbers, with models f1,…,fB:

fˆbag(𝐱)=1B∑b=1Bfb(𝐱)

Try it: with n=4, what is the chance that a given row is left out of a bootstrap sample? ((3/4)4=81/256≈0.316.)

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

  1. In the simulation, draw 100 samples. What share of different rows do you get on average?
  2. Why do deep trees suit bagging better than shallow ones?
  3. What is the out-of-bag score, and why is it useful?
Answers
  1. Close to 65 % for 12 rows (1−(11/12)12≈0.648), heading to 63.2 % for large data.
  2. 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.
  3. 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

1A bootstrap sample of a 1,000-row dataset has:
2Bagging stands for:
3The out-of-bag rows of a tree are:

Sources

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.