03 / Resources/Ensemble Learning · Random Forests

Interactive Diagnostic Essay · Topic 10

Random Forests: Many Trees, One Verdict

A single decision tree is brittle — nudge one row and the whole structure redraws itself. Plant a few hundred on resampled data, force each to inspect a random slice of the features, and let them vote. That is a random forest, and it remains one of the best out-of-the-box models in existence.

01 / The Wisdom of Crowds

Why a Committee Beats a Genius

In 1785 — before gradient descent, before computers, before “algorithm” meant anything to anyone — the Marquis de Condorcet proved something quietly radical about groups. If every voter is right more often than a coin flip, and their mistakes are not copies of each other, then adding voters makes the majority more likely to be right. Not slightly. Monotonically, all the way toward certainty.

Translate that into machine learning and the arithmetic is startling. One decision tree at 60% accuracy is barely useful. Three such trees, voting, land near 65%. Eleven reach roughly 75%. The trees did not get smarter — the errors simply stopped agreeing.

P(\text{majority correct}) \to 1 \quad \text{as } B \to \infty

provided each voter has

p > \tfrac{1}{2}

and the errors are (nearly) independent.

Both caveats carry the whole theorem. Voters must beat chance — a committee of worse-than-random members is just confidently wrong. And their votes must be only weakly correlated: if every tree memorises the same quirk, three copies of one opinion add nothing at all. Condorcet supplied the idea; two centuries later Leo Breiman supplied the machinery.

FIVE TREES · FIVE VOTES · ONE VERDICT8s loop

YES · 3

NO · 2

Majority → YES

trees sprout · no two leave the same way · three chips beat two

02 / Bagging

Bagging: Many Datasets You Do Not Actually Have

A deep decision tree is a low-bias, high-variance learner: hand it a different training set and you get a visibly different tree. Bagging turns that vice into a virtue by manufacturing the datasets. Draw $n$ rows from the training set with replacement — a bootstrap sample — so some rows appear twice and others never appear at all.

Exactly how many never appear? The chance a given row is skipped on a single draw is $1 - 1/n$ ; over $n$ independent draws that compounds to $(1 - 1/n)^n$ , which converges to $1/e \approx 0.368$ . So every bootstrap sample contains about 63.2% of the original rows — and the missing third is not waste, as Section 05 will show.

Train one unpruned tree per bootstrap sample. Each is individually noisy, but the noise now points in different directions. Averaging $B$ such learners leaves the bias roughly untouched and divides the independent part of the variance by $B$ .

Plain bagging looks like the whole story — until you notice the trees still consider every feature at every split. On a dataset with one dominant predictor, all of them make the same first cut and the mistakes re-correlate. That flaw is what the next section fixes.

What the Bootstrap Keeps

\Pr(\text{row included}) = 1 - \left(1 - \frac{1}{n}\right)^{n} \to 1 - \frac{1}{e} \approx 0.632

Variance of an Independent Average

\mathrm{Var}\!\left(\frac{1}{B}\sum_{b=1}^{B} h_b(x)\right) = \frac{1}{B}\,\mathrm{Var}(h(x))

The assumption this quietly makes — independence — is the one reality breaks.

03 / Where the Randomness Goes

The Second Coin Flip: Random Splits

A random forest adds one more ingredient. At every split of every tree, only a random subset of the features is considered — typically $\sqrt{p}$ of them for classification and $p/3$ for regression. With four features a tree chooses among two; with a hundred it chooses among ten.

Because the candidate set is redrawn at each node, a feature that would have monopolised every split is sometimes not even on the ballot. Trees grown on different bootstrap samples now diverge in structure, not merely in noise — which is exactly the decorrelation Condorcet's theorem was asking for.

The One Formula to Remember

\mathrm{Var}\!\left(\frac{1}{B}\sum_{b=1}^{B} h_b(x)\right) = \rho\,\sigma^2 + \frac{1-\rho}{B}\,\sigma^2

where

\sigma^2

is the variance of a single tree and

\rho

is the pairwise correlation between any two trees.

Read it slowly. The second term, $(1-\rho)\sigma^2/B$ , is the good news: it shrinks toward zero as you add trees, so more trees always help. The first term, $\rho\sigma^2$ , is the ceiling. No matter how many trees you plant, the forest can never beat $\rho\sigma^2$ — the portion of the error the trees share. Lowering the correlation $\rho$ is therefore the only lever that moves the floor, and random feature selection is precisely that lever. Breiman put it bluntly: better forests have lower correlation between trees and individually stronger trees.

04 / The Vote

One Tree, One Vote

For classification each tree returns a class label and the forest returns the plurality. For regression each tree returns a number and the forest returns the mean:

\hat{y}(x) = \operatorname*{arg\,max}_{c \in \mathcal{C}} \sum_{b=1}^{B} \mathbb{1}\!\left[\, h_b(x) = c \,\right]

\hat{y}(x) = \frac{1}{B} \sum_{b=1}^{B} h_b(x)

Many libraries are subtler than a hard show of hands. scikit-learn averages the predicted leaf probabilities and takes the argmax — a soft vote that weighs confidence, not just the label. It usually behaves a little better, especially near a decision boundary.

A worked tally: five trees answer a yes/no question and vote Y, Y, N, Y, N. Three to two for yes, so the forest predicts yes — even though two of the five disagree, and one of them is a deep, confident tree. With an even number of trees the vote can tie; the tie is broken by whichever class the averaged probability vector ranks first, which is a good reason to leave the tree count odd and generous.

Five Trees, Five Votes

tree_1Y

tree_2Y

tree_3N

tree_4Y

tree_5N

YES · 3

NO · 2

05 / Reading the Forest

Feature Importance and a Free Validation Set

IMPURITY IMPORTANCE

Sum the weighted impurity decrease every time a feature is used to split, across every tree, and normalise. It is fast and comes free with training — but it is biased toward high-cardinality features. A feature with many distinct values gets more chances to split and quietly inflates its score; a random ID column can look important.

PERMUTATION IMPORTANCE

Shuffle one feature's column on held-out data and measure the drop in accuracy. Unbiased and model-agnostic — but it costs a fresh prediction pass per feature, and it splits credit between correlated features: when either of two twins can carry the signal, breaking one barely hurts. Report both and read the disagreement.

Then there is the validation set you never had to carve out. Each tree is trained on its bootstrap sample and never sees the ~36.8% of rows it left out. Score every training row using only the trees for which it was out-of-bag, let them vote, and you have an honest error estimate for the price of training:

\mathrm{OOB\ error} = \frac{1}{n} \sum_{i=1}^{n} \mathbb{1}\!\left[\, \hat{y}^{\,\mathrm{oob}}_i \neq y_i \,\right]

Out-of-bag error tracks test error closely enough to tune hyperparameters without touching the test set — which is why turning bootstrap off is a quiet act of self-harm: it deletes the free validation estimate along with the resampling.

THE 63 / 37 SPLIT

63.2% in the bag: used to grow this tree. 36.8% out of the bag: used to grade it. Every tree brings its own exam paper.

06 / Field Notes

Knobs That Matter, and When to Reach for Something Else

n_estimators

More trees never overfit. Variance falls monotonically, then plateaus; the only real cost is time. 100–500 is the usual working range.

max_features

sqrt(p) for classification, p/3 for regression are the defaults. Lower it for more decorrelation, raise it for individually stronger — and more correlated — trees.

max_depth / min_samples_leaf

The genuine regularisers. Cap depth or grow leaf size when trees are enormous or memory-bound; leave them loose otherwise and let the ensemble do the smoothing.

bootstrap / oob_score

Keep bootstrap on and OOB scoring enabled. Turning bootstrap off removes both the resampling diversity and the free validation estimate in one stroke.

WHERE BOOSTING WINS

Gradient boosting grows trees sequentially, each one fitted to the residual errors the ensemble still makes. When the signal is subtle and the data is clean, that focus extracts meaning a forest's parallel vote never will — which is why boosted trees dominate tabular leaderboards.

WHERE FORESTS WIN

· Noisy labels and heterogeneous features
· Training that must parallelise across cores
· A strong model before any tuning at all
· Free out-of-bag validation as a sanity check

← Topic 09: Recurrent Networks Topic 11: Bias-Variance Tradeoff →

Adapted from MLU-Explain (Amazon, CC BY-SA 4.0).

Back to Archive Index →