module 06

Bagging and Random Forests

free pdf

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.

free pdf

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

test 0.879

● filled class · ○ hollow class · darker background = more confident it's the filled class

one tree gives blocky, jumpy regions. each tree in the forest saw a different random resample, so their mistakes differ. averaging them gives soft, smooth regions.

bagging: many trees on resampled data

  1. Make a new training set by picking rows at random with replacement (a bootstrap sample).
  2. Grow a tree on it.
  3. 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

2040608010000.050.10.150.20.250.3number of treeserror
out-of-bag errortest error
out-of-bag error (each point judged only by trees that never saw it) tracks the error on fresh test data, without holding any data back. both settle down as trees are added; more trees never make it worse.
  • 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.