Random Forest

Decision trees are accurate on training data but unstable — high variance. Leo Breiman's insight (2001): don't fight the variance of one tree; average many diverse trees and let their errors cancel. The result is one of the most reliable algorithms in all of ML — a near-unbeatable default for tabular data with essentially no tuning.

The statistics of averaging

Average \(B\) estimators, each with variance \(\sigma^2\) and pairwise correlation \(\rho\). The ensemble's variance is

The second term vanishes as \(B\) grows — but the first does not. Averaging identical trees achieves nothing (\(\rho = 1\)); the whole game is making trees accurate yet decorrelated. Random forests inject randomness twice:

1. Bagging (bootstrap aggregating)

Each tree trains on a bootstrap sample: \(n\) rows drawn with replacement from the training set. Each sample leaves out about \(1 - (1 - 1/n)^n \approx 1/e \approx 37\%\) of the rows, so every tree sees a different perturbed dataset.

2. Feature subsampling

At every split, only a random subset of features is eligible (typically \(\sqrt{d}\) for classification, \(d/3\) for regression). Without this, all trees would open with the same dominant feature and remain highly correlated; restricting candidates forces different trees to discover different structure — this is the step that turns bagging into a random forest.

Prediction: majority vote (classification) or mean (regression) over all trees.

flowchart TD
    D[Training data] --> B1[bootstrap 1] & B2[bootstrap 2] & B3[bootstrap ...B]
    B1 --> T1[tree 1<br><small>√d features/split</small>]
    B2 --> T2[tree 2]
    B3 --> T3[tree B]
    T1 & T2 & T3 --> V[vote / average]

The single tree carves noise islands with hard 0/1 confidence; the forest's averaged vote yields a smooth, calibrated-looking boundary that ignores individual noise points — variance visibly averaged away.

Out-of-bag evaluation: free validation

The ~37% of rows a tree never saw are its out-of-bag (OOB) samples. Predict each row using only the trees that didn't train on it, and you get an honest generalization estimate without a validation split — conceptually a built-in cross-validation:

from sklearn.ensemble import RandomForestClassifier

rf = RandomForestClassifier(
    n_estimators=300,        # more = better, plateaus; never overfits via B
    max_features='sqrt',     # the decorrelation knob
    min_samples_leaf=1,      # tree depth control if needed
    oob_score=True,
    n_jobs=-1,               # trees train in parallel
    random_state=0,
)
rf.fit(X_train, y_train)
rf.oob_score_                # ≈ honest accuracy estimate, no split spent

Key facts about \(B\) (n_estimators): adding trees cannot overfit — it only stabilizes the average (the \((1-\rho)\sigma^2/B\) term shrinks). Performance plateaus; the only cost of more trees is compute. Overfitting, when it happens, comes from the individual trees being too deep on too-noisy data — control with min_samples_leaf or max_depth.

Feature importance

Two standard measures:

• Impurity-based (rf.feature_importances_): total impurity decrease contributed by each feature across all trees. Fast, but biased toward high-cardinality features (more possible thresholds = more chances to look useful) and computed on training data;
• Permutation importance: shuffle one feature's column in validation data and measure the score drop. Slower, model-agnostic, and more trustworthy — the bridge to Explainability.

from sklearn.inspection import permutation_importance
imp = permutation_importance(rf, X_val, y_val, n_repeats=10, random_state=0)

Practical profile

What averaging does, and what it cannot do

The argument for a forest is a variance argument. Each tree is grown on its own bootstrap sample and sees only a subset of features at each node, so each one is unstable — small changes in the data swing it. Averaging unstable, roughly unbiased predictors cancels the swings.

The left panel below shows the individual trees; the right, their vote:

Two things to notice, and the second is the one usually missed.

The left panel never improves. Add fifty trees and each of them is exactly as jittery as the first. Bagging does not produce better trees — it produces a better average of the same bad trees.

The error curve flattens. Past a few dozen trees, more trees buy nothing. That is not a convergence bug: averaging attacks variance and leaves bias untouched. If the flat part of that curve is too high, adding trees is the one thing guaranteed not to help — you need deeper trees, better features, or a different model. It is also why n_estimators is a budget question rather than a tuning question: more is never worse, just slower.

Class materials

References

• Ho, T. K. "Random Decision Forests." ICDAR (1995). DOI
• Breiman, L. "Random Forests." Machine Learning 45 (2001). DOI

The full course bibliography is on the references page.

Quiz