Bagged trees stay alike because the same strong feature wins their top split. A random forest lets each split choose from a random subset of features, which makes the trees disagree. Measure the effect on load_breast_cancer and see why adding trees never overfits.
ML02.2.3L2 Intermediate25 minIn review (what this means)
The maths and code on this page are checked by automated tests on every change, but an independent reader has not signed it off yet. Spot a mistake or a confusing step? Tell us.
Explain why bagged trees stay correlated, using the variance formula of ML02.2.1.
Change a from-scratch tree grower so that each split searches a random subset of max_features features.
Measure, on load_breast_cancer, how lowering max_features makes the trees’ errors less alike at a small cost in each tree’s accuracy.
Use RandomForestClassifier and ExtraTreesClassifier, and explain why test error levels off rather than rising as trees are added.
The question
Bagging cannot push the variance of its vote below \(\rho\sigma^2\), where \(\rho\) is the correlation between its trees. Once there are many trees, that floor is all the variance that is left, and bagged trees are alike. Why are they alike, and how can we make them disagree without making each of them much worse?
From the last lesson
1. What fraction of the distinct points does a large bootstrap sample hold?
Show answer
About \(1 - 1/e \approx 0.632\); each point is left out with chance \({(1 - 1/n)^n} \approx 0.368\).
2. Why does bagging help a deep tree but not a least-squares line?
Show answer
A deep tree is unstable, so trees on different samples differ and their average is smoother. The average of bootstrap lines lands almost exactly on the original line.
Intuition
Grow 200 bagged trees on 398 patients of load_breast_cancer (30 features) and ask which feature each tree splits on first. Almost every tree asks one of the same few questions.
ML02.2.3-F1
The first question of each of 200 trees. Bagged trees open with “worst perimeter” half the time, and with one of only five features always. When each split may only choose from five features drawn at random, the first questions spread over seventeen features.
The top split decides how the rest of the tree looks, so bagged trees that share their top split share much of their structure, and they make many of the same mistakes. That is a large \(\rho\).
A random forest breaks the habit. At every split it draws a few features at random and lets only those compete. The strongest feature is often not drawn, so another question gets its turn.
Build it up
Step 1. One change to the grower. At each node, before searching for a split, draw max_features = \(m\) of the \(d\) features at random, without replacement. Search only those for the best split. The next node draws again.
ML02.2.3-F2
Feature subsampling with \(d = 30\) and \(m = 5\). Each node draws its own five features and splits on the best of them.
Step 2. What it costs. A tree whose split may not use the best feature makes a slightly worse split, so each tree is a little less accurate and a little more variable: \(\sigma^2\) goes up.
Step 3. What it buys. Different trees now open with different questions, so their errors overlap less: \(\rho\) goes down. In \(\rho\sigma^2 + {(1-\rho)\sigma^2/B}\) the floor \(\rho\sigma^2\) falls if \(\rho\) falls faster than \(\sigma^2\) rises, and with many trees the floor is all that matters.
Step 4. The two ends. With \(m = d\) every feature is always drawn, and a random forest is bagging. With \(m = 1\) each split uses one random feature and only picks its threshold well: the trees disagree most but are weakest. The usual default sits between: \(m = \lfloor\sqrt{d}\,\rfloor\) for classification.
The formal statement
NoteAlgorithm: random forest
Repeat \(B\) times, once for each tree:
Draw a bootstrap sample of size \(n\) from the training data.
Grow a tree on it. At every node, choose max_features of the \(d\) features at random, find the best split among them only, and split; stop when the node is pure or a size limit is reached.
Predict by averaging the \(B\) trees (regression) or by their majority vote (classification).
The usual choices, from Breiman’s recommendations, are \(\lfloor\sqrt{d}\,\rfloor\) features and leaves of one point for classification, and \(\lfloor d/3 \rfloor\) features and at least five points per leaf for regression. scikit-learn’s RandomForestClassifier uses max_features="sqrt", which is 5 for \(d = 30\). Its RandomForestRegressor uses max_features=1.0, all the features, so by default it is bagging.
Measuring the trade-off. On the 171 test patients, record for each tree which patients it gets wrong. For two trees, the correlation between their two lists of mistakes (1 for wrong, 0 for right) says how much they err together. Average it over all pairs of the 200 trees:
\(m\)
errors alike
one tree
forest
30 (bagging)
0.485
0.913
0.924
5 (\(\sqrt{30}\))
0.403
0.911
0.953
1
0.316
0.886
0.936
The columns are the mean correlation of the trees’ mistakes, the mean test accuracy of one tree, and the test accuracy of the forest of 200. Going from 30 features to 5 cuts the shared mistakes and costs one tree almost nothing, and the forest gains about three points. Going down to one feature cuts the sharing further, but each tree loses about two and a half points of accuracy, and the forest is worse than at 5.
ML02.2.3-F4
The trade-off over every \(m\). Fewer features per split make the trees’ mistakes less alike (left) while one tree’s accuracy barely moves until \(m\) is very small (right). The forest is best in between. With 171 test patients, one patient is 0.006 of accuracy, so read the bumps loosely.
Go deeper: the correlation in the formula, measured directly
The \(\rho\) of ML02.2.1 is a correlation over training sets: draw a new training set, grow two trees, and see how their predictions at the same input move together. By the formula, a forest of 100 trees has variance \({\rho\sigma^2 + (1-\rho)\sigma^2/100}\), so the ratio of its variance to one tree’s is \(\rho\) plus about 0.01. Repeating the fit on 30 random training sets of 250 patients (predicted probabilities of class 1 on the test patients) gives ratios of about 0.11 for \(m = 30\), 0.04 for \(m = 5\) and 0.02 for \(m = 1\), so \(\rho\) is about 0.10, 0.03 and 0.01: it falls in the same order as the table, and it is small, as Hastie, Tibshirani and Friedman report for bootstrapped trees (Section 15.2). The same runs show the cost: one tree’s variance grows from about 0.042 to 0.048 and 0.074 as \(m\) falls from 30 to 5 and 1. The mistake correlation in the table is a cheaper measure that moves the same way.
Why adding trees does not overfit. For a fixed training set, the forest’s vote is an average over the random draws (samples and feature subsets). As \(B\) grows, that average settles on its limit, the vote of infinitely many trees, by the law of large numbers. Breiman proved that the forest’s error converges as trees are added (Theorem 1.2). Adding trees moves the forest towards a fixed model; it does not make the model more complex. What can overfit is each tree being grown too deep, which is controlled by min_samples_leaf and max_depth, not by \(B\).
Worked example
The twelve points with \(m = 1\): two possible roots. With \(d = 2\), \(m = 1\) means each node draws one of the two features. Suppose a tree is grown on all twelve points. If the root draws \(x_1\), the best split is the one bagging always takes, \(x_1 \leq 3.5\), with weighted Gini \(5/18\). If it draws \(x_2\), the candidates are the midpoints 1.5, 2.5, 3.5 and 4.5.
The best is \(x_2 \leq 3.5\). Below it are 5 points of class 0 and 3 of class 1, so
The decrease from the root’s \(1/2\) is \(1/16\), against \(2/9\) for \(x_1\). The other thresholds give weighted Gini \(13/27 \approx 0.481\) (at 1.5 and at 4.5) and \(4/9 \approx 0.444\) (at 2.5).
ML02.2.3-F3
The two roots a tree can have when each node draws one feature. The \(x_2\) root is a much weaker first question, but it sends the tree down a different path from the \(x_1\) trees.
So about half the trees open with the weaker question, and their later splits must repair it. Those trees are worse alone, but they make different mistakes from the \(x_1\) trees. In the code below, 24 of 50 trees open with \(x_2\) under \(m = 1\), against 9 of 50 under bagging (where only the bootstrap sample can make \(x_2\) win).
Code
The grower of ML02.2.2 with one change: a random order of the features at each node, of which only the first max_features compete. If none of them can split the node (all their values are equal there), the remaining features are tried, as scikit-learn does.
import numpy as npX = np.array([(1, 1), (2, 1), (1, 2), (2, 3), (3, 2), (5, 5), (4, 1), (5, 2), (5, 3), (4, 4), (2, 5), (6, 5)], dtype=float)y = np.array([0] *6+ [1] *6)def gini(labels): p = np.bincount(labels, minlength=2) /len(labels)return1- np.sum(p **2)def best_split(X, y, features): best =Nonefor j in features: values = np.unique(X[:, j])for s in (values[:-1] + values[1:]) /2: left = X[:, j] <= s score = (left.sum() * gini(y[left]) + (~left).sum() * gini(y[~left])) /len(y)if best isNoneor score < best[0] -1e-12: best = (score, j, s)return bestdef grow(X, y, rng, max_features=None):if gini(y) ==0:return {"leaf": int(y[0])} d = X.shape[1] order = np.arange(d) if max_features isNoneelse rng.permutation(d) # the new line m = d if max_features isNoneelse max_features _, j, s = best_split(X, y, order[:m]) or best_split(X, y, order[m:]) left = X[:, j] <= sreturn {"j": j, "s": s, "left": grow(X[left], y[left], rng, max_features),"right": grow(X[~left], y[~left], rng, max_features)}def forest(X, y, B, seed, max_features=None): rng = np.random.default_rng(seed) trees = []for _ inrange(B): idx = rng.integers(0, len(y), size=len(y)) trees.append(grow(X[idx], y[idx], rng, max_features))return treesbagged = forest(X, y, 50, seed=0)random_forest = forest(X, y, 50, seed=0, max_features=1)print("roots on x2, bagging:", sum(t.get("j") ==1for t in bagged)," roots on x2, max_features=1:", sum(t.get("j") ==1for t in random_forest))score, j, s = best_split(X, y, [1])print(f"root on all twelve points, x2 only: x2 <= {s:g}, weighted Gini {score:.4f}")
roots on x2, bagging: 9 roots on x2, max_features=1: 24
root on all twelve points, x2 only: x2 <= 3.5, weighted Gini 0.4375
Now the library on load_breast_cancer, with the 70 / 30 split used throughout the course. Each fitted forest keeps its trees in estimators_, so we can ask every tree for its test predictions.
from sklearn.datasets import load_breast_cancerfrom sklearn.ensemble import ExtraTreesClassifier, RandomForestClassifierfrom sklearn.model_selection import train_test_splitdata = load_breast_cancer()X_train, X_test, y_train, y_test = train_test_split( data.data, data.target, test_size=0.3, random_state=0, stratify=data.target)def mistakes_alike(model):"""Mean correlation, over all pairs of trees, of their 0/1 lists of test mistakes.""" wrong = np.array([tree.predict(X_test) != y_test for tree in model.estimators_], dtype=float) corr = np.corrcoef(wrong)return np.nanmean(corr[np.triu_indices(len(wrong), 1)]), 1- wrong.mean()rows = {}for m in (30, "sqrt", 1): model = RandomForestClassifier(n_estimators=200, max_features=m, random_state=0).fit(X_train, y_train) alike, one_tree = mistakes_alike(model) rows[m] = (alike, one_tree, model.score(X_test, y_test))print(f"max_features={m!s:5s} mistakes alike {alike:.3f} one tree {one_tree:.3f} forest {rows[m][2]:.3f}")extra = ExtraTreesClassifier(n_estimators=200, random_state=0).fit(X_train, y_train)print("extra trees: mistakes alike", round(mistakes_alike(extra)[0], 3), " forest", round(extra.score(X_test, y_test), 3))
max_features=30 mistakes alike 0.485 one tree 0.913 forest 0.924
max_features=sqrt mistakes alike 0.403 one tree 0.911 forest 0.953
max_features=1 mistakes alike 0.316 one tree 0.886 forest 0.936
extra trees: mistakes alike 0.368 forest 0.936
ExtraTreesClassifier goes one step further. Besides drawing features, it draws each candidate feature’s threshold at random and keeps the best of these random splits, and by default it grows every tree on the whole training set instead of a bootstrap sample. Its trees’ mistakes are less alike (0.368) and here it scores 0.936, between bagging and the random forest.
Explore
The vote grid of lesson ML02.2.2 has a feature subsampling switch. With only two features it draws one at each split, as in the worked example. Turn it on with the forty noisy points and compare the share of the plane with a split vote.
Pitfalls
ML02.2.3-F5
Wrong beside right. With a few trees, the forest’s test error depends on luck: five seeds disagree. With hundreds, every seed settles near the same error, and the curve never turns up.
“More trees will overfit, so keep the forest small.”
Adding trees only brings the vote closer to its limit; the test error levels off. A small forest is not safer, just noisier. Grow trees until the error stops changing; the cost is time, not accuracy.
“The fewer features per split, the better, since the trees disagree more.”
Disagreement is only half the recipe; the members must also be good. With \(m = 1\) each tree lost about two and a half points of accuracy and the forest did worse than with \(m = 5\). When most features are noise, a small \(m\) often draws no useful feature at all. Treat max_features as a tuning parameter.
“RandomForestRegressor decorrelates its trees by default.”
Its default max_features=1.0 lets every split see every feature, which is bagged trees. For regression, set max_features yourself (a third of the features is a common start).
Check yourself
Recall
1. What does a random forest change in the tree grower?
Show answer
At every node it draws max_features of the \(d\) features at random and searches only those for the best split.
2. Which term of \(\rho\sigma^2 + {(1-\rho)\sigma^2/B}\) does feature subsampling target, and what does it cost?
Show answer
It lowers \(\rho\), and so the floor \(\rho\sigma^2\). The cost is a slightly larger \(\sigma^2\): each tree is a little worse.
3. What is the default max_features of RandomForestClassifier, and what is it for 30 features?
Show answer
"sqrt", the square root of the number of features rounded down: 5 for 30 features.
4. Why does adding trees not make a random forest overfit?
Show answer
The vote is an average over random draws; adding trees moves it towards a fixed limit, the vote of infinitely many trees, rather than making the model more complex.
5. How do extremely randomised trees differ from a random forest?
Show answer
They also draw the threshold of each candidate feature at random and keep the best of these random splits, and by default they grow each tree on the whole training set, not a bootstrap sample.
Exercises
1.★ A data set has 64 features. What max_features does the square-root rule give, and what fraction of nodes, on average, gets to consider the single strongest feature?
Show solution
\(\sqrt{64} = 8\). Each node draws 8 of 64 features without replacement, so a given feature is among them with chance \(8/64 = 1/8\).
2.★★ On the twelve points, a tree with \(m = 1\) draws \(x_2\) at the root. Check by hand that \(x_2 \leq 2.5\) has weighted Gini \(4/9\), and say why the root still picks \(x_2 \leq 3.5\).
Show solution
Below 2.5 are the points with \(x_2 \in \{1, 2\}\): (1, 1), (2, 1), (1, 2), (3, 2) of class 0 and (4, 1), (5, 2) of class 1, so 4 : 2 and Gini \(1 - {(2/3)^2} - {(1/3)^2} = 4/9\). Above are the other six, 2 : 4, with the same Gini \(4/9\). The weighted Gini is \(\tfrac12\cdot\tfrac49 + \tfrac12\cdot\tfrac49 = 4/9\). That is larger than \(7/16\), since \({4 \times 16} = 64 > 63 = {7 \times 9}\), so \(x_2 \leq 3.5\) wins.
3.★★★ Suppose trees in a forest have \(\sigma^2 = 1\) and \(\rho = 0.5\) with bagging, and that feature subsampling changes these to \(\sigma^2 = 1.2\) and \(\rho = 0.3\). For which numbers of trees \(B\) does the forest have the smaller variance? What happens as \(B\) grows?
Show solution
Bagging: \(0.5 + 0.5/B\). Forest: \({0.3 \times 1.2} + {0.7 \times 1.2}/B = 0.36 + 0.84/B\). The forest is smaller when \(0.36 + 0.84/B < 0.5 + 0.5/B\), that is \(0.34/B < 0.14\), or \(B > 2.43\). So from three trees on the forest wins, and as \(B\) grows the two tend to 0.5 and 0.36. With one or two trees the noisier trees lose.
Summary card
A random forest is bagging plus a random choice of features at every split.
ML02.2.3-F1
Bagged trees ask the same first question; a forest’s do not.
The change. At each node, search only max_features = \(m\) randomly drawn features.
The trade. Lower \(\rho\) (the floor \(\rho\sigma^2\) falls), slightly higher \(\sigma^2\).
Defaults.\(\lfloor\sqrt{d}\rfloor\) for classification ("sqrt"); scikit-learn’s regressor uses all features, which is bagging.
Number of trees. Test error levels off as \(B\) grows; more trees cost time, not accuracy.
Sources. Each was opened and checked against this lesson on 15 November 2026.
Trevor Hastie, Robert Tibshirani and Jerome Friedman, The Elements of Statistical Learning, 2nd edition, corrected 12th printing. Section 15.2 and Algorithm 15.1: select \(m \leq p\) variables at random before each split, which by (15.1) reduces the variance of the average; for bootstrapped trees \(\rho\) is typically small. Section 15.3: the inventors’ defaults \(\lfloor\sqrt{p}\rfloor\) with minimum node size one for classification and \(\lfloor p/3\rfloor\) with minimum node size five for regression. Section 15.3.4: increasing \(B\) does not cause the forest to overfit, though fully grown trees can, and small \(m\) performs poorly when few variables are relevant.
Leo Breiman, Random Forests, January 2001 (published in Machine Learning 45, 5 to 32). Theorem 1.2: the generalisation error converges as the number of trees increases, which “explains why random forests do not overfit as more trees are added”; Section 4: random input selection, including one feature per split.
scikit-learn developers, User Guide, Section 1.11.2: Random forests and other randomized tree ensembles. Section 1.11.2.1 on the random subset of features at each split, 1.11.2.2 on extremely randomised trees (random thresholds, the best of them kept), and 1.11.2.3 on the defaults: max_features=1.0 (equivalent to bagged trees) for regression and "sqrt" for classification, and no bootstrap by default for extra trees.
