Concept25 minBefore this:Decision Trees

Random Forest

How do many wobbly trees make one steady prediction?

The situation

Your deep decision tree changes completely when a single applicant is relabelled. The interviewer asks:

How does a random forest improve on one deep tree?

Eight loan applicants, four features

Everything on this page uses the same tiny dataset. A bank wants to predict whether an applicant will repay. The numbers are made up for teaching illustrative, but the labs in this lesson run real computations on them.

#	credit score	income (k/mo)	debt ratio	years at job	repaid?

One feature, credit score, separates these eight perfectly (650 and below never repaid). Remember that; it is what makes plain bagging fail, as The answer that sounds right shows.

One decision tree is sharp but unstable

A decision tree asks yes/no questions about features until it reaches a leaf with an answer. Grown deep, it fits its training data almost perfectly, so its bias is low. The catch is variance: scikit-learn's own docs warn that "small variations in the data might result in a completely different tree being generated" sklearn trees. Watch it happen with one relabelled applicant.

Swipe sideways to see the whole diagram.

Trained on the eight rows, the best first question is "credit ≤ 650?". It splits the data perfectly.
Now relabel one applicant, #6, from not repaid to repaid. Nothing else changes.
The tree's first question flips to a different feature entirely, "debt ratio ≤ 0.42?", because that is now the perfect split.
Ask both trees about a new applicant with credit 640 and a debt ratio of 0.20. They disagree.
That is high variance: the model's answer depends heavily on which exact rows it happened to see.

High variance means the error you see on new data is mostly noise from the particular sample, not a lack of capacity. The classic fix for variance is averaging. The rest of the page is about how to average trees so that it actually works.

The idea

Think of asking a crowd for an estimate. A crowd only beats one person if people make different mistakes, because mistakes that differ cancel out. A forest makes its trees disagree: each one sees different rows, and each split sees only a few features.

Illustrative. Different rows and features make the trees disagree, and the combined answer is steadier.

Play

Try to break it. Set the correlation between trees to 0.9 and add as many trees as you can. Then lower the correlation.

Make the trees disagree, but keep each one good

Averaging only cancels mistakes that differ

Here is the one equation the whole method follows from. Average B trees whose predictions each have variance σ² and are correlated with each other by ρ ESL Eq. 15.1, p. 588:

Hastie, Tibshirani & Friedman, Elements of Statistical Learning, §15.2 · hover any symbol for its meaning.

Correlation between trees ρ Number of trees B

Variance of the average — (one tree = 1.00; red = the floor ρσ², teal = what more trees still remove)

Set ρ to 0.9 (very similar trees, like plain bagging with one dominant feature) and B to 500: the variance only drops to about 0.9. Set ρ to 0.3: it drops to about 0.3. The forest's job is to lower ρ without making each tree much worse. Breiman calls these two quantities the correlation and the strength of the trees, and the random-features section shows his bound with both.

Why only variance? Bagged trees are identically distributed, so the average has the same bias as one tree. ESL: "the only hope of improvement is through variance reduction" ESL p. 588. That is also why forests use deep, low-bias trees.

Now say why: why can't more trees fix high correlation, and what does a forest do to lower it?

Maths

In one breath

A single decision tree is accurate on the data it saw but changes wildly when the data changes a little. A random forest grows hundreds of trees, each on a bootstrap sample of the rows and each choosing every split from a random handful of features, then lets them vote. The randomness makes the trees disagree, and averaging trees that disagree cancels their mistakes.After this you can derive why it works (the variance formula), explain every knob (n_estimators, max_features, bootstrap, oob_score), and answer the usual interview follow-ups.

random forestsingle tree / plain bagginginjected randomnessrepaid (Y)not repaid (N) / failurenumbers

How one tree picks a split

Gini impurity: how mixed is a group?

At each node, a tree (CART, which scikit-learn implements) tries every feature and every threshold, and keeps the split whose two children are the least mixed. Mixedness is measured with Gini impurity: 0 when a group is all one class, 0.5 when two classes are 50/50 sklearn §1.10.7.

scikit-learn's mathematical formulation for classification trees sklearn §1.10.7 · hover any symbol for its meaning.

Try it on the eight applicants

Feature Threshold (go left if value ≤)

Split score — (0 = perfect; 0.5 = useless for a 4/4 node)

Try every feature: only credit score reaches 0. A greedy tree will always take it first, and that is about to matter.

Bootstrap the rows

Every tree trains on a resampled copy of the data

Start with the N = 8 training rows.
Draw 8 rows at random, putting each one back before the next draw. scikit-learn does exactly this with randint(0, n, n) _forest.py.
Some rows get picked twice or more, so this tree effectively weights them more.
Some rows are never picked. They are "out of bag" for this tree, which gives a free test set (see the out-of-bag section).

How many rows does a tree miss? Each draw misses a given row with probability 1 − 1/N, and there are N independent draws:

Standard bootstrap result; Breiman: "about one-third of the instances are left out" Breiman 2001, p. 8.

Training rows N

Left out of each tree: — · seen: —

Why keep bootstrapping once features are random?

Breiman gives two reasons: bagging "seems to enhance accuracy when random features are used", and the left-out rows give running estimates of error, strength and correlation p. 8. scikit-learn: bootstrap=True by default; turn it off and every tree sees all rows (as Extra-Trees do).

A random handful of features at every split

Hide the star feature sometimes

This is the move that turns bagging into a random forest. Before each split, the tree may only look at m features drawn at random from all p. It picks the best split among those m, and the next node draws a fresh m ESL Alg. 15.1.

Swipe sideways to see the whole diagram.

At the root, the tree could consider all four features, and credit score would win every time.
Instead, draw m of them at random. Here m = 2, and credit score is not among them.
The node splits on the best of what it was offered. It is a weaker split than credit score, on purpose.
Every child node draws its own fresh m. Credit score will still be used, just not always first, and not always in the same place.
That forced variety is what lowers the correlation ρ between trees.

Check it: grow 60 trees with m features per split

Same experiment as the bagging lab in The answer that sounds right, but now you choose m. With m = 4 it is plain bagging. Watch the first-split feature spread out as m drops.

Features per split m

The trade-off, in Breiman's own bound

Lower m means less correlated trees, but each tree is also a bit weaker. The authors put it plainly: "Reducing m reduces both the correlation and the strength" Breiman & Cutler. Breiman's Theorem 2.3 bounds the forest's error with exactly these two numbers:

Breiman 2001, Theorem 2.3 p. 6. He adds that the bound "is likely to be loose".

Mean correlation ρ̄ Strength s

Upper bound on error —

What m to use

Source	Classification	Regression
Inventors' recommendation (via ESL)	⌊√p⌋, min node size 1	⌊p/3⌋, min node size 5
scikit-learn default	"sqrt"	1.0 = all features (plain bagging)
Breiman's 2001 experiments	m = 1 and m = ⌊log₂p + 1⌋, picked by out-of-bag error

Sources: ESL §15.3, p. 592; sklearn ensembles, which also notes 0.3 "is a typical default in the literature" for regression; Breiman p. 9.

It is not very sensitive to m

Across Breiman's 20 datasets, the average absolute difference in test error between m = 1 and the larger m was under 1%. "It was surprising that using a single randomly chosen input variable to split on at each node could produce good accuracy" p. 11. ESL adds that the best m is problem-dependent and worth tuning (their Figure 15.3: m = 6 beats the default 2).

What breaks without it

Set m = p and you are back to bagging: scikit-learn calls max_features=1.0 "equivalent to bagged trees". On data with one dominant feature, like ours, the trees stay correlated and the variance floor ρσ² stays high.

Combine the trees

Vote, or average the probabilities

For regression the forest averages the trees' numbers. For classification the original paper lets each tree cast one vote Def. 1.1, p. 2.

ESL Eq. 15.2, p. 589 · hover any symbol for its meaning.

Here is a detail many explanations miss: scikit-learn does not take a majority vote. Its classifier averages each tree's predicted class probabilities ("in contrast to the original publication") sklearn ensembles; the code divides the summed predict_proba by the number of trees _forest.py. Usually they agree. Not always:

Each tree's probability that the applicant repays (leaf = share of repaid rows in that leaf). Example values, drag them.

Do more trees overfit?

No. Breiman's Theorem 1.2: as trees are added the error converges to a limit, "this result explains why random forests do not overfit as more trees are added" p. 4. More trees only cost time.

But the forest itself can still overfit

ESL is careful here: adding trees does not overfit, but the limit, an average of fully grown trees, "can overfit the data" and "incur unnecessary variance"; controlling depth gives small gains in some studies, though full trees "seldom cost much" ESL §15.3.4, p. 596. The authors' site says "Random forests does not overfit" Breiman & Cutler. Both are right about different things: B does not overfit; depth and leaf size can. my take

Out-of-bag error

Every row is a test row for about a third of the trees

Take one training row, applicant #2.
Look at the forest. Each tree trained on its own bootstrap sample, so some trees saw #2 and some did not.
Let only the trees that never saw #2 predict it. For them, #2 is genuinely new data.
Do this for every row and compare with the truth. That error rate is the out-of-bag (OOB) error, a test-set estimate without holding any data back.

Breiman cites evidence that the OOB estimate "is as accurate as using a test set of the same size as the training set", and notes it is unbiased once you run past the point where the error has converged p. 8. ESL: almost identical to N-fold cross-validation, so you can stop adding trees once OOB error stabilizes ESL §15.3.1, p. 592. In scikit-learn: oob_score=True, available only with bootstrap=True.

Feature importance

Shuffle a column and see how much worse it gets

Measure the fitted forest's error on rows it did not train on (out-of-bag or a validation set).
Randomly shuffle one feature's column. This breaks its link to the label but keeps its distribution.
If error jumps, the model leaned on that feature. The numbers here are illustrative.
If error barely moves, the model did not need it. Repeat for every feature.

sklearn permutation importance; Breiman's original version permutes each variable in the out-of-bag rows p. 19.

	Impurity importance (MDI) · `feature_importances_`	Permutation importance
Computed from	how much each feature's splits reduced Gini, on the training data	score drop when the feature is shuffled, on held-out data
Speed	free, already computed	needs extra predictions (K × features)
Known bias	favours features with many unique values; can rank useless features high when the model overfits	correlated features share the credit, so both can look unimportant

Do not trust the default bar chart blindly

scikit-learn: impurity-based importances "favor high cardinality features" and are computed on training data, so they "do not necessarily inform us on which features are most important" for new data sklearn. Strobl et al. (2007) showed the measures are unreliable when predictors differ in scale or number of categories, and a 2008 follow-up found bias toward correlated predictors Strobl 2007. For correlated features, scikit-learn suggests clustering them and keeping one per cluster.

In practice

Everything in one picture

Swipe sideways to see the whole diagram.

Start with N training rows and p features.
Make B bootstrap samples, one per tree.
Grow each tree to full depth on its sample, offering only m random features at every split. Trees are independent, so they train in parallel (n_jobs).
To predict, run the input down every tree and combine: vote (paper) or average probabilities (scikit-learn); average for regression.
The rows each tree left out give the OOB error and permutation importances for free.
That is the whole method. Every piece exists to keep the trees strong but decorrelated.

When to use it

Reach for it as a strong, low-effort baseline on tabular data, when you want a built-in validation score (OOB), robustness to label noise, and trivial parallelism. Look elsewhere when the last point of accuracy matters (try gradient boosting), when you must extrapolate beyond the training range, or when the data are images, text or audio.

The answer that sounds right

Averaging copies does nothing

Just average many trees? They come out the same

Idea one: train 100 trees and average them. On the same data, a tree-growing algorithm with no randomness builds the same tree 100 times. The average of 100 identical answers is that answer.

Idea two, bagging (Breiman, 1996): give each tree a different bootstrap sample, the rows drawn at random with replacement Breiman 1996. Better, but there is a trap. When one feature is much stronger than the rest, most samples still split on it first, so the trees stay similar.

Swipe sideways to see the whole diagram.

Bootstrap sample 1 repeats row 1 and leaves out row 3. Its best first split is still credit score.
Sample 2 is different again. The threshold moves a little, from 670 to 655, but the question is the same.
Sample 3: same story. Credit score separates any sample of these rows perfectly, so it usually wins. Only now and then does a sample happen to let another feature tie.
The trees make the same mistakes on the same applicants. Averaging only helps when their mistakes differ.

Check it yourself: grow 60 bagged trees

This grows 60 one-split trees, each on its own bootstrap sample, letting every split consider all four features (that is plain bagging). It counts which feature each tree splits on first.

The lesson, and where it bends

The lesson. Averaging reduces variance only as far as the averaged models disagree. A random forest is a recipe for cheap disagreement: random rows per tree, random features per split, deep trees that are individually low-bias. Everything else (OOB error, importance, parallelism) falls out of that design.

It does not reduce bias. The average has a single tree's bias, so if deep trees cannot represent the pattern, more trees will not help (ESL p. 588).
Default importances mislead. Use permutation importance on held-out data, and watch correlated features.
Regression forests cannot extrapolate. Every leaf predicts an average of training targets, so the forest never predicts beyond the range of y it saw. my take
Size and latency. Hundreds of deep trees take memory and per-prediction time; limit depth or leaf size if it matters (sklearn).
Usually behind tuned boosting on accuracy in recent tabular benchmarks, but far less sensitive to settings.

What came after

Extra-Trees (Geurts et al., 2006) go further: random features and random thresholds, and by default no bootstrap, trading a bit more bias for a bit less variance Geurts 2006. Gradient boosting (XGBoost, LightGBM) takes AdaBoost's sequential route and now usually leads tabular benchmarks.

Say it

How does a random forest improve on one deep tree?

Say your answer out loud

Aim for 30 seconds. It feels different from reading it, and that's the point.

Tick what you covered

A forest averages many deep trees, which each have low bias and high variance.
Averaging only reduces variance if the trees make different mistakes.
Each tree trains on a bootstrap sample of the rows.
Each split considers only a random subset of features, so a dominant feature can't make every tree the same.
The rows a tree didn't see give a free out-of-bag error estimate.
It reduces variance, not bias.