Era 2 · Foundations · 2001

12 Random Forests

Random Forests · Leo Breiman · Machine Learning
🟧 read selectively~1.5–2 horiginal ↗
The gist in 20 seconds. An ensemble of trees with randomness applied twice — bootstrap samples and random features at each split. Decorrelated trees get averaged → low variance without overfitting, plus a free OOB estimate and free feature importances. Still the default strong baseline for tabular data.

Context

A single decision tree is interpretable, but it overfits and it is unstable: change the data a little and you get a different tree. Breiman (2001) assembles those trees into a powerful, stable ensemble.

The idea and the mechanism

Randomness applied twice. Bagging: each tree is trained on a bootstrap sample (a random sample drawn with replacement). Random features: at every split the tree picks the best feature out of a random subset of features. This decorrelates the trees — they stop copying each other. The prediction is a vote (classification) or an average (regression).

probability Why averaging reduces variance — and what decorrelation has to do with it

Take B trees, each with prediction variance σ² and pairwise correlation ρ between trees. The variance of their average:

Var(1B Σb Tb) = ρ σ² + 1 − ρB σ²

The whole random-forest strategy follows from this:

  • More trees (B → ∞) kills the second term → the variance bottoms out at a floor of ρσ². That is why adding trees does not overfit — it merely converges to a limit.
  • To lower the floor itself you have to reduce the correlation ρ — which is exactly what the random choice of features at each split does. Bagging attacks (1−ρ)/B, random features attack ρ.

This is why a "random" forest beats plain bagging of trees: decorrelation matters more than averaging alone.

scikit-learn A random forest with an OOB estimate 
from sklearn.ensemble import RandomForestClassifier

rf = RandomForestClassifier(n_estimators=300, oob_score=True).fit(X, y)
print(rf.oob_score_)            # a quality estimate without a separate validation set
print(rf.feature_importances_)  # feature importances, almost for free
data bootstrap 1 bootstrap 2 bootstrap 3 tree tree tree vote/ average
Each tree gets its own bootstrap sample and its own random features; their votes are averaged. The diversity of the trees is what kills the variance.
Analogy. To guess the number of beans in a jar, do not ask one expert — ask a crowd of different people and average. If everyone looks at the jar from the same side (correlated), the crowd is wrong together. Make each of them look from their own angle (random features) and their independent errors cancel out. That is the "wisdom of crowds", and the more varied the voices, the more accurate it gets.

Why it matters

Still the default strong baseline for tabular data (alongside gradient boosting). Breiman proved that a forest does not overfit as trees are added, and threw in two practical free tools — the OOB estimate and feature importances. Bagging and decorrelation are ideas common to every ensemble.

Connections

↔ another classic10. SVM

The two pillars of classical 2000s ML: SVM (convex optimization + kernels, strong in high dimension) and the random forest (an ensemble of trees, strong on heterogeneous tabular features). Both are solid baselines outside deep learning.

↔ contrast with DL16. AlexNet

A forest does not learn a representation — it combines decisions over the features you give it. On problems where features have to be extracted from raw data (pixels, audio, text), deep networks beat it. But on structured tabular data, tree ensembles still often beat neural networks.

→ close relative31. Mixture-of-Experts

Both are "many specialists instead of one". But a forest averages all the trees (an ensemble), while MoE uses gating to activate only a few experts per input (conditional computation). Two different answers to the question "how do you combine many models?".

Questions worth asking

If a forest does not overfit with the number of trees — can I use millions?

Quality will stop improving long before that: the variance hits its floor of ρσ², and the extra trees just burn compute. Important: "does not overfit with the number of trees" is not "does not overfit at all" — trees that are too deep will still fit noise on small data. You regularize with depth and minimum leaf size, not with the number of trees.

How is a random forest different from gradient boosting — aren't both ensembles of trees?

A forest builds its trees in parallel and independently, fighting variance by averaging. Boosting builds trees sequentially, each one correcting the errors of the previous ones, fighting bias. Boosting is usually more accurate but more sensitive to tuning and to overfitting; a forest is simpler and more robust out of the box.

Feature importances are "free" — can you trust them?

With care. The standard impurity-decrease importance is biased towards features with many levels (continuous ones, say, or high-cardinality ones) and suffers when features are correlated. Permutation importance (on held-out data) or SHAP is more reliable. "Free" ≠ "unconditionally correct".

What to read in the original

Read the essentials — bagging + random features, OOB and feature importances; the convergence proof can be taken at the level of the idea (the math box above).