Skip to the lesson
ML Explorer Reju Sam John

ML Explorer · Level 3 · Classic ML

Bagging and random forests

One tree is jumpy. Many trees, each grown on its own sample of the data, voting together, are steadier, and the rows each tree never saw give you a test score for free.

About 10 minutes · No maths needed; the maths is there if you want it

Overview

The decision trees lesson ended with a tree that fitted its training data perfectly and did worse on new cases. Here we keep the same data and grow many trees instead of one.

We look at how much a single tree changes with its data, build new training sets by resampling, let the trees vote, make them differ on purpose, and then score the vote without a test set.

The points are made up. See "About the data" at the end.

You'll learn

  • what a bootstrap sample is, and why it leaves out about a third of the rows
  • how bagging and random forests turn many jumpy trees into one steadier vote
  • how the out-of-bag rows give a test-like score without a separate test set
  1. One tree is jumpy

    Grow a full tree on a slightly different set of rows and you get a noticeably different tree.

    Compare the three maps. The broad shape is similar, but the small boxes, where the tree chased a few points, move around from tree to tree.

    A model that changes a lot when its data change a little is said to have high variance. Full trees are a classic example.

    The maths

    Variance here means how much the fitted model, and so its prediction at a fixed point x\mathbf{x}, would change from one training set to another drawn from the same source. It is about the method, not about one fitted tree.

    A fully grown tree carves the plot into small boxes around single points, so one changed row can change a box. A shallow tree changes less, but it cannot follow the shape of the data as closely.

  2. The bootstrap

    To get a new training set from the one you have, draw rows at random with replacement, as many as you started with.

    The maths

    With nn rows, one draw misses a given row with probability 1−1/n1 - 1/n. The nn draws are independent, so

    P(a given row is left out)=(1−1n)nP(\text{a given row is left out}) = \left(1 - \frac{1}{n}\right)^{n}

    For n=80n = 80 this is . Adding up over the rows, the expected share of distinct rows in a sample is 1−(1−1/n)n1 - (1 - 1/n)^n, which is here.

    As nn grows, (1−1/n)n(1 - 1/n)^n approaches e−1e^{-1}, so the share approaches 1−1/e≈1 - 1/e \approx . For 80 rows we are already close to that limit.

  3. Bagging: let the trees vote

    Grow one full tree on each of B bootstrap samples. To label a case, every tree votes, and the majority wins.

    This is bagging, short for bootstrap aggregating. The trees disagree in different places, so when they vote, many of the quirks of single trees are outvoted.

    Move the slider through B = 1, 3, 5, 11, 25, 51 or 101 trees. The map shows the vote. With odd B the vote can never tie.

    The maths

    Write f^b(x)∈{0,1}\hat{f}_b(\mathbf{x}) \in \{0, 1\} for the class tree bb predicts. The bagged prediction is the majority class:

    y^=1  if  1B∑b=1Bf^b(x)>12,  otherwise  y^=0\hat{y} = 1 \ \text{ if } \ \frac{1}{B}\sum_{b=1}^{B} \hat{f}_b(\mathbf{x}) > \tfrac{1}{2}, \ \text{ otherwise } \ \hat{y} = 0

    For a number rather than a class (regression), bagging averages the trees' predictions instead of taking a vote.

    Bagging needs no new kind of model: it runs the same method many times on resampled data and combines the answers.

  4. Random forests: make the trees differ

    A random forest is bagging with one more twist: at each split, a tree may look only at a random subset of the features.

    Here there are only two features, so each split looks at one of them, chosen at random, instead of both. A different tree, or a different split in the same tree, may get the other feature.

    Bagged trees all choose from the same features, so they tend to look alike. A vote cancels mistakes only where the trees disagree. Hiding features at random makes the trees less alike.

    That is one dataset and one random seed, so read it as what happened here, not a promise. The chart shows both methods for every B.

    The maths

    Why disagreement helps is clearest for averaging numbers, the regression case. Take BB predictions at the same point, each with variance σ2\sigma^2, and every pair with correlation ρ\rho. Here σ2\sigma^2 and ρ\rho describe how the predictions vary over random training samples; they are not computed from data on this page. The variance of their average is

    Var⁡ ⁣(1B∑b=1Bf^b(x))=ρ σ2+1−ρB σ2\operatorname{Var}\!\left(\frac{1}{B}\sum_{b=1}^{B} \hat{f}_b(\mathbf{x})\right) = \rho\,\sigma^2 + \frac{1-\rho}{B}\,\sigma^2

    More trees shrink the second term towards 0, but not the first. Lowering the correlation ρ\rho lowers it, as long as each tree's variance σ2\sigma^2 does not grow by more; that is the trade a random forest makes. Our trees vote on classes rather than average numbers, so this formula is the reason for the idea, not a calculation of the votes above.

    The ISLR section below describes the usual choice as about the square root of the number of features at each split. With 2 features that rounds to 1, the choice here. If the chosen feature cannot lower the impurity at a node at all, this page lets the split use the other feature, as some widely used software does.

  5. Out-of-bag: a free test

    Every tree left out about a third of the rows. Those rows can test it.

    For each training row, take only the trees whose bootstrap sample did not include it, and let them vote. That vote is the row's out-of-bag (OOB) prediction. No tree that saw the row gets a say, so it works like a prediction for a new case.

    The OOB accuracy is the share of rows whose OOB prediction is right. A row that every tree saw has no OOB vote, so it is left out of the score.

    The maths

    Write SbS_b for the rows in tree bb's bootstrap sample. Row ii's OOB vote uses only the trees with i∉Sbi \notin S_b. With an even number of such trees the vote can tie; this page then predicts class 0.

    Each row is left out of a tree's sample with probability (1−1/n)n(1 - 1/n)^n, about 37%, so its OOB vote comes from about 37% of the trees. The OOB score therefore judges a smaller forest than the full one. The samples are independent, so the chance that a row is in all BB samples, and has no OOB vote, is (1−(1−1/n)n)B\left(1 - (1 - 1/n)^n\right)^B.

Quick check

About what fraction of the 80 rows does a bootstrap sample leave out?

The sample has 80 rows, but they are drawn with replacement, so some rows repeat and others are never drawn. Tree 1's sample left out rows.

Right. Each row is missed with probability (1 − 1/80)⁸⁰ = , close to the limit 1/e.

Too many. With 80 draws, each row has 80 chances to be picked, so most rows are picked at least once: on average of them.

That is the share the sample keeps, about . The share it leaves out is the rest, .

Why does a random forest let each split look at only a random subset of the features?

No. Here one forest tree scored on average, against for a bagged tree. The gain is in the vote, not in each tree.

Right. Trees that see every feature tend to agree, mistakes included. Hiding features at random makes them differ, and a vote only cancels mistakes where trees disagree.

The subset is drawn afresh at every split, so every feature still gets considered at many splits. Nothing is dropped.

A random forest uses both: a bootstrap sample for each tree, and a random subset of features at each split.

Lesson complete

  • A full decision tree has high variance: a small change in the data changes the tree.
  • A bootstrap sample draws n rows with replacement. It leaves out each row with probability (1 − 1/n)ⁿ, close to 1/e ≈ 37%.
  • Bagging grows a tree on each of B bootstrap samples and takes a vote. A random forest also lets each split see only a random subset of the features, so the trees differ more.
  • The out-of-bag vote for a row uses only trees that never saw it, which gives a test-like score from the training data.

Common misconceptions

  • "A bootstrap sample is a random two thirds of the rows." It has n rows, drawn with repeats, and on average only about two thirds of the original rows appear in it.
  • "More trees means more overfitting." Adding trees makes the vote settle down, not chase the training data harder. Each tree can still overfit; B is not the knob for that.
  • "Each forest tree must be better than a bagged tree." Here each one was a little worse. The forest wins, when it does, because its trees disagree more.
Next lesson: Gradient boosting →

Further reading

  1. James, Witten, Hastie & Tibshirani, An Introduction to Statistical Learning (2nd ed.), Section 8.2.1, "Bagging", which includes "Out-of-Bag Error Estimation", and Section 8.2.2, "Random Forests".
  2. Hastie, Tibshirani & Friedman, The Elements of Statistical Learning (2nd ed.), Chapter 15, "Random Forests", in particular Section 15.3.1, "Out of Bag Samples", and Section 15.4.1, "Variance and the De-Correlation Effect".

About the data. The cases are the ones from the decision-trees lesson. Each point has x₁ = 10u₁ and x₂ = 10u₂, where u₁ and u₂ are uniform draws between 0 and 1 from mulberry32. Its class is 1 if (x₁ > 5 and x₂ > 3) or (x₁ < 3 and x₂ > 7), and 0 otherwise. Then a third draw u₃ flips the label if u₃ < 0.1. The 80 training cases use seed 99 and the 400 test cases seed 100. Both forests use mulberry32 seed 10: for each tree in turn, 80 draws u pick its bootstrap rows (row ⌊80u⌋, counting from 0), and the random forest takes one more draw at each node to choose its feature. So tree 1 has the same sample in both forests, and later samples differ. Every tree is grown until no split lowers its impurity. A leaf tie, and a tied out-of-bag vote, go to class 0. The maps colour a grid of 42 × 42 cells (32 × 32 in the small maps) by the prediction at each cell's centre. Displayed values are rounded; the calculations are not.

If this helped, you can .