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.
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
-
One tree is jumpy
Grow a full tree on a slightly different set of rows and you get a noticeably different tree.
These are the training cases from the decision-trees lesson: class 0 as cyan circles, class 1 as violet triangles. Each small map comes from one tree, grown until its leaves are pure, on its own random resample of the rows. Each map shows only the distinct rows its tree saw, and that count is above the map.
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.
Under each map is its tree's accuracy on the test cases. The three trees score , and . One full tree grown on all the rows scores .
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 , 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.
-
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.
Draw one of the rows at random, note it, put it back, and repeat times. The result is a bootstrap sample: the same size as the data, but some rows come up twice or more and others not at all.
This is tree 1's sample. It holds distinct rows, of the data. The other rows were left out; they have a dashed ring. A small ×2, ×3 and so on marks a row drawn more than once. The bars count the rows by how many times each was drawn.
How many distinct rows should we expect? For 80 rows the answer is 1 − (1 − 1/80)⁸⁰ = , or . One sample can miss that by a few rows. Across all 101 samples drawn for the bagged trees on this page, the average is .
So a bootstrap sample leaves out about a third of the rows: on average for 80 rows.
The maths
With rows, one draw misses a given row with probability . The draws are independent, so
For this is . Adding up over the rows, the expected share of distinct rows in a sample is , which is here.
As grows, approaches , so the share approaches . For 80 rows we are already close to that limit.
-
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.
With one tree (tree 1, which saw of the 80 rows), test accuracy is , below the full tree's . With 101 trees the vote scores , above the single full tree (the dotted line on the chart).
Watch the map settle as B grows. Going from 1 tree to 3, of its cells change class; going from 51 trees to 101, only do.
The maths
Write for the class tree predicts. The bagged prediction is the majority class:
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.
-
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.
You can see it in the first question each tree asks. Of the 101 bagged trees, ask about x₂ first. In the forest the first question is about x₂ in trees and about x₁ in .
Here is what that did on this data, with 101 trees each. One forest tree scores on the test cases on average, against for one bagged tree: each tree got a little worse. Two forest trees disagree on of the test cases on average, against for two bagged trees. And the vote of 101 forest trees scores , against for bagging.
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 predictions at the same point, each with variance , and every pair with correlation . Here and describe how the predictions vary over random training samples; they are not computed from data on this page. The variance of their average is
More trees shrink the second term towards 0, but not the first. Lowering the correlation lowers it, as long as each tree's variance 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.
-
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.
With one tree, only the rows it left out get a vote; the other are left out of the score. From B = on the slider, every row has at least one OOB tree.
With 101 trees the forest's OOB accuracy is , and its accuracy on the separate test cases is . For bagging the same pair is and . The OOB score came from the training data alone.
The maths
Write for the rows in tree 's bootstrap sample. Row 's OOB vote uses only the trees with . 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 , 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 samples, and has no OOB vote, is .
Quick check
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.
Further reading
- 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".
- 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 .