module 06
Bagging and Random Forests
Bagging Predictors
Leo Breiman
Train many copies of a model, each on a random resample of the data, then let them vote. Models that change a lot with small data changes, like trees, become much more accurate this way.
Random Forests
Leo Breiman
Bagging, plus one twist: each split in each tree may only look at a random few features. The trees become less alike, so their mistakes cancel better. The paper also shows how to measure test error and feature importance for free from the rows each tree never saw.
the problem
A single deep tree is unstable: move a few training points and the whole tree can change. It gets the general shape right but is jumpy. Breiman's idea: keep many trees and let them vote, so the jumps cancel out.
averaging trees smooths the boundary
● filled class · ○ hollow class · darker background = more confident it's the filled class
bagging: many trees on resampled data
- Make a new training set by picking rows at random with replacement (a bootstrap sample).
- Grow a tree on it.
- Repeat many times, then vote (or average, for numbers).
Each bootstrap sample contains about 63% of the distinct rows. The rest, about 37%, were never seen by that tree. These are its out-of-bag rows.
Bagging helps most when the model is unstable, like deep trees. It does little for models that barely change with the data.
random forests: make the trees disagree
Averaging only helps if the trees make different mistakes. Bagged trees are still quite alike, because the strongest feature wins the first question in almost every tree.
The fix: at every split, a tree may only look at a few randomly chosen features
(max_features). Each tree gets a bit weaker, but the trees become much less alike,
and the vote gets better.
Breiman made this precise with two numbers: the strength of the trees (how accurate each is) and their correlation (how alike their mistakes are). The forest's error is bounded by both, and fewer features per split trades a little strength for a lot less correlation.
free extras
- Out-of-bag error. Judge each row using only the trees that never saw it. You get a test-error estimate without holding any data back.
- Adding trees never hurts. The error settles down as trees are added, so more trees only cost time.
error as trees are added
- Which features matter. Shuffle one feature among each tree's out-of-bag rows and see how much worse it gets. The bigger the drop, the more that feature matters.
how the code works
| idea | in forest.py |
|---|---|
| bagging | Bagging(...), which is a forest that looks at all features |
| random features per split | max_features, passed down to each tree |
| out-of-bag error as trees are added | history()["oob_error"], oob_score_ |
| boundary after 1, 2, 3… trees | staged_predict |
| feature importance two ways | feature_importances(), permutation_importance() |
| strength and correlation | strength_correlation(X, y) |
One detail: a tree trained on a bootstrap sample might never see some class, so its
probabilities have fewer columns. _tree_proba lines them up with the full list of
classes.
what the demo checks
Run uv run python examples/06_forest.py (about 45 seconds, because every tree is
pure NumPy).
- Measured share of distinct rows: 0.6309, against the theory's 0.6321.
- One tree: 0.710 test accuracy. Bagging: 0.799. Random forest: 0.786. Here the random forest loses slightly, because only 5 of the 12 features carry signal, so a random handful often misses all of them.
- Two single trees trained on fresh data disagree on 33.7% of points; two forests on 17.7%.
- Bagging deep trees helps a lot (0.710 → 0.800). Bagging one-question trees does nothing (0.721 → 0.713), as predicted.
- The quick built-in importance gives a pure-noise feature more credit than the truly useful one. Shuffle-based importance gets it right.
when it goes wrong
- Too few features per split when only a few features matter: trees rarely see the signal.
- Trusting the quick importance score: it favours features with many distinct values.
- Predicting outside the training range: like trees, a forest predicts a flat value beyond the data.