Bagging and random forests

The bias–variance note found the weak point of a deep tree: its bias is small and its variance is large: about the size of the noise when the training points are dense, and many times larger when they are sparse. It also found the cure in principle. An average of models trained by the same procedure has the same expectation as one of them, so it keeps the small bias, while its variance can be much smaller. The difficulty is practical: averaging over independent training sets needs many training sets, and we have one. This note uses the bootstrap to manufacture training sets from the one we have (bagging), derives how much variance the average keeps when its members are correlated, and shows how random forests lower that correlation.

Notation. $D$ is the training set of $n$ points. $T(x; \Theta)$ is a tree grown on $D$ with the randomness $\Theta$: the bootstrap sample and, for forests, the features drawn at each split. The trees of an ensemble use independent draws $\Theta_1, \dots, \Theta_B$ given $D$, and the ensemble predicts $\hat f_B(x) = \frac1B \sum_{b=1}^B T(x; \Theta_b)$ for regression, or averages the trees’ class probabilities for classification. At a fixed point $x$, $\tau^2(x)$ is the variance of one tree’s prediction (not $\sigma^2$, the noise variance of the bias–variance note) and $\rho(x)$ the correlation between two trees’ predictions, both over the randomness of $D$ and $\Theta$.

Bootstrap aggregation#

Bagging (bootstrap aggregation, Breiman, 1996):

1. Draw $B$ bootstrap samples: $n$ points from $D$ with replacement, $B$ times.
2. Grow a tree on each, usually to full depth, without pruning.
3. Average the predictions: the mean for regression, the mean of the class probabilities (or a majority vote) for classification.

A bootstrap sample stands in for a fresh training set from the same distribution, so the bagged predictor approximates the average model $E_D[\hat f_D(x)]$ of the previous note with resamples in place of new data. Because the trees are identically distributed, the expectation of their average equals the expectation of one bootstrap tree: bagging does not change the bias, apart from the small increase that comes from each tree seeing only about 63% of the distinct points (Hastie, Tibshirani and Friedman, 2009, Sections 15.2 and 15.4.2). All the gain is in the variance, so bagging helps exactly the unstable methods, those whose output changes a lot with small changes of the data: trees, subset selection, neural networks. For stable methods such as nearest neighbours it gains little and can slightly hurt (Breiman, 1996, Section 1). For least squares or a sample mean it changes almost nothing: the average of bootstrap means is the sample mean.

How much variance does an average keep?#

If the $B$ trees were independent, the variance of their average would be $\tau^2 / B$. They are not: all of them are grown from the same $D$. With pairwise correlation $\rho$ the variance of the average is

$$\operatorname{Var}\big(\hat f_B(x)\big) = \rho \tau^2 + \frac{1 - \rho}{B}\, \tau^2 .$$

The direct derivation sums the $B$ variances and the $B(B-1)$ covariances $\rho\tau^2$, as in the joint distributions note. For trees a second derivation says more: it shows where the correlation comes from. Condition on the training set and use the law of total variance:

$$\operatorname{Var}\big(\hat f_B(x)\big) = \operatorname{Var}_D\Big(E\big[\hat f_B(x) \mid D\big]\Big) + E_D\Big[\operatorname{Var}\big(\hat f_B(x) \mid D\big)\Big] .$$

Given $D$, the trees are independent draws of $\Theta$, so $E[\hat f_B(x) \mid D] = E[T(x; \Theta) \mid D]$ and $\operatorname{Var}(\hat f_B(x) \mid D) = \operatorname{Var}(T(x; \Theta) \mid D) / B$. The same law for a single tree splits its variance into the same two parts:

$$\tau^2 = \underbrace{\operatorname{Var}_D\big(E[T \mid D]\big)}_{\text{from the training set}} + \underbrace{E_D\big[\operatorname{Var}(T \mid D)\big]}_{\text{from the resampling}} .$$

The covariance of two trees has no resampling part, because given $D$ they are independent: $\operatorname{Cov}(T_1, T_2) = E_D[\operatorname{Cov}(T_1, T_2 \mid D)] + \operatorname{Cov}_D(E[T_1 \mid D], E[T_2 \mid D]) = 0 + \operatorname{Var}_D(E[T \mid D])$. So $\rho\tau^2 = \operatorname{Var}_D(E[T \mid D])$ is the part of a tree’s variance that comes from the training set, $(1 - \rho)\tau^2$ is the part that comes from the resampling, and substituting both gives the formula (Hastie, Tibshirani and Friedman, 2009, Section 15.4.1, Eqs. 15.5 and 15.9).

A worked example with toy numbers: with $\tau^2 = 1$ and $\rho = 0.3$, one tree has variance $1$, ten trees $0.3 + 0.07 = 0.37$, a hundred trees $0.307$; the floor is $0.3$. Beyond a few dozen trees, more trees buy almost nothing, and only a smaller $\rho$ helps.

Random forests: decorrelating the trees#

Bagged trees are similar because they are grown greedily from similar samples: if one feature is strongly predictive, nearly every bootstrap tree splits on it at the root, and the trees share their top structure. A random forest (Breiman, 2001) changes one line of the tree-growing algorithm: at every split, draw $m$ of the $d$ features at random and search for the best split among those $m$ only. Different trees, and different nodes of one tree, are forced to use different features, so the trees are less correlated. The individual trees become worse, with a larger bias and a larger variance, so $m$ trades $\rho$ against $\tau^2$ and the bias. The recommended defaults are $m = \lfloor \sqrt d \rfloor$ with leaves of size 1 for classification and $m = \lfloor d/3 \rfloor$ with leaves of size 5 for regression, but $m$ is a tuning parameter (Hastie, Tibshirani and Friedman, 2009, Section 15.3). Bagging is the special case $m = d$. Library defaults differ: scikit-learn’s RandomForestClassifier draws $\sqrt d$ features, but RandomForestRegressor uses all $d$, so its default regression forest is bagging.

On Friedman’s function in 10 dimensions (the setting of the previous note), estimating the two variance parts from 40 training sets of 25 trees each gives, for one tree:

	$\tau^2$	$\rho$	floor $\rho\tau^2$	bias²	variance at $B = 25$
bagging, $m = 10$	11.11	0.105	1.17	3.83	1.57
forest, $m = 3$	15.52	0.043	0.66	5.26	1.25

The forest’s trees are individually worse ($\tau^2$ rises from $11.1$ to $15.5$), but their correlation falls from $0.105$ to $0.043$, and the floor of the ensemble’s variance falls from $1.17$ to $0.66$. Here half of the features are irrelevant, the restricted search often misses the relevant ones, and the larger bias wipes out the gain: with unlimited trees, bagging’s expected test error is about $1 + 3.83 + 1.17 = 6.0$ and the forest’s about $1 + 5.26 + 0.66 = 6.9$. When the signal is spread over many features, the trade goes the other way:

Figure

Ensemble error against the number of trees

Each of the 30 features carries a little information, as the pixels of an image do. A single forest tree, limited to 5 features per split, is clearly worse than a single bagged tree, but the forest’s trees decorrelate and the forest ends lower. Both curves level off. Adding trees does not make the ensemble overfit the way extra depth does: $\hat f_B$ converges to its limit $E[T \mid D]$ as $B$ grows (Breiman, 2001, Theorem 1.2 and Section 11), and extra trees only remove the random variation around that limit. For squared error the test error averaged over the trees’ randomness falls with $B$, as the variance formula above shows; the curve of one particular forest can still fluctuate or rise slightly for a while, and a majority vote’s error rate need not fall at every $B$. That limit can still overfit the data, which is why depth or leaf size are sometimes tuned too (Hastie, Tibshirani and Friedman, 2009, Section 15.3.4).

A forest has a second reading. For regression, a tree predicts at $x$ the mean target of the training points in $x$‘s leaf, so the forest predicts a weighted average $\sum_i w_i(x) \, y_i$, where $w_i(x)$ is the average over trees of $[x_i \text{ is in } x\text{'s leaf}] / (\text{leaf size})$. This is a nearest-neighbour rule whose neighbourhoods are learned from the target: points are close if they often share a leaf, and features that do not matter do not count in the distance (Hastie, Tibshirani and Friedman, 2009, Section 15.4.3).

Out-of-bag error#

A bootstrap sample misses some points. A given point is not chosen in one draw with probability $1 - 1/n$, and in none of the $n$ draws with probability

$$\Big(1 - \frac1n\Big)^n \longrightarrow e^{-1} \approx 0.368 ,$$

so each bootstrap sample contains, on average, a fraction $1 - (1 - 1/n)^n$ of the distinct training points: $0.651$ for $n = 10$, $0.634$ for $n = 100$, $0.632$ in the limit. A simulation with $n = 100$ gives $0.634$. The same calculation is why the bootstrap fails for the maximum, in the probability course.

So every point is left out of about 36.8% of the trees, and those trees are an honest test of it. The out-of-bag (OOB) prediction of $x_i$ averages only the trees whose bootstrap sample did not contain $i$, and the OOB error is the error of these predictions over the training set (Breiman, 2001, Section 3.1). It estimates the test error without a held-out set and almost for free, much like cross-validation (Hastie, Tibshirani and Friedman, 2009, Section 15.3.1). It is slightly pessimistic for a small number of trees, because each OOB prediction averages only about $B/e$ of them. In the figure, the forest’s OOB error after 150 trees is $15.7\%$ against a test error of $14.9\%$; on the breast cancer data a forest of 300 trees has OOB accuracy $0.967$ and test accuracy $0.953$. Unlike for a single train/validation split, nothing was set aside: every point was used for training and for evaluation. The OOB error is honest only for the forest itself. Choosing $m$, the leaf size or the features by comparing OOB errors reuses the same points for selection, so the chosen setting’s OOB error is optimistic, and a step before the forest that used the targets of all points, such as selecting features by their correlation with $y$, has already seen each point’s label. When OOB results drive such choices, keep an independent test set for the final assessment.

Feature importance and its pitfalls#

A forest is not readable the way one tree is, but it can rank the features. Two measures are common.

• Impurity importance (mean decrease in impurity, MDI): add up the gains of all splits on feature $j$, over all trees, weighted by the number of points the splits see, and normalize (Hastie, Tibshirani and Friedman, 2009, Section 15.3.2). It is free, since the gains are computed during training.
• Permutation importance: shuffle the values of feature $j$ in held-out or OOB data, which breaks its link with the target and leaves its distribution intact, and measure how much the error grows (Breiman, 2001, Section 10). It works for any model.

Both have pitfalls.

• Impurity importance is computed on the training data and favours features with many distinct values. Fully grown trees split on whatever lowers the training impurity, including noise, and a continuous feature offers many more thresholds to fit noise with than a binary one (Strobl et al., 2007). In a simulation where the label depends only on $x_1$, a pure-noise binary feature $x_2$ and a pure-noise continuous feature $x_3$ get impurity importances $0.008$ and $0.331$ (against $0.661$ for $x_1$): the forest credits the continuous noise with a third of the importance. Permutation importance on held-out data gives $0.227$ for $x_1$ and $-0.016$ and $-0.008$ for the two noise features, correctly zero up to noise.
• Correlated features distort the ranking. Adding to the breast cancer data an exact copy of its most important feature (worst perimeter, impurity importance $0.134$) gives the twins $0.108$ and $0.124$, together $0.232$: the pair is over-counted, and the copy now ranks first. With $m$ features drawn per split, two copies make the same information available at more splits, so the pair takes importance from the other features. When every split sees all features, as in bagging, the twins only share it: $0.212$ and $0.204$ against $0.415$ for the feature alone. Either way, the scores of correlated features, read one at a time, do not tell how important the group is.
• Permuting a feature that is correlated with others creates impossible inputs, such as a large radius with a small perimeter, and measures the model’s behaviour where there is no data; such permutation importances can grossly overstate correlated features (Hooker, Mentch and Zhou, 2021).
• Importance is not causation. Both measures describe what a fitted model uses, not what would happen if a feature were changed.

Extremely randomized trees#

Random forests randomize the features; extremely randomized trees (extra trees, Geurts, Ernst and Wehenkel, 2006) also randomize the thresholds. At each node they draw $K$ features, draw for each a single cut point uniformly between its minimum and maximum in the node, and keep the best of these $K$ random splits. They grow every tree on the full training set rather than a bootstrap sample, to keep the bias low, and rely on the random cut points for diversity. The trees are cheaper to grow, since there is no sorting and no search over thresholds, and more strongly decorrelated. On the breast cancer split, 300 extra trees reach test accuracy $0.942$ against $0.953$ for the forest: often similar, sometimes better, depending on the data.

What changed#

	One deep tree	Bagging	Random forest
Training data per tree	all	bootstrap sample	bootstrap sample
Features per split	all $d$	all $d$	random $m$
Bias	low	≈ one tree	somewhat higher
Variance	$\tau^2$	$\rho\tau^2 + (1 - \rho)\tau^2/B$	same formula, smaller $\rho$
Validation	held-out data	out-of-bag	out-of-bag
Interpretability	readable	importances	importances

Limitations#

• The bias stays. Averaging cannot correct a systematic error shared by all trees. A forest of stumps has the bias of one randomized stump in expectation; that expectation can be an additive function of the features, but it has no interactions.
• The floor stays. Correlated trees leave $\rho\tau^2$ however many are averaged; $m$ lowers $\rho$ at the price of worse trees.
• Size and speed. Hundreds of deep trees take memory and prediction time, and the model is not readable.
• No extrapolation. A forest averages leaf means, so its predictions stay within the range of the training targets.
• Importances mislead with noisy high-cardinality features, correlated features and causal questions.

What you should remember#

• Bagging grows trees on bootstrap samples and averages them; it keeps the bias and lowers the variance, so it helps unstable, low-bias methods.
• $\operatorname{Var}(\hat f_B) = \rho\tau^2 + (1 - \rho)\tau^2/B$; by the law of total variance, $\rho\tau^2 = \operatorname{Var}_D E[T \mid D]$ is the part of the variance due to the training set, which averaging cannot remove.
• Random forests draw $m$ features per split (recommended $\sqrt d$ for classification and $d/3$ for regression; scikit-learn’s regressor uses all $d$ by default) to lower $\rho$; worse trees, better average when the signal is spread over many features.
• More trees do not overfit: the forest converges to a limiting forest and the error levels off near the floor, with small fluctuations on the way.
• Each bootstrap sample holds a fraction $1 - (1 - 1/n)^n \to 1 - 1/e \approx 0.632$ of the points; out-of-bag predictions use the other 36.8% and estimate the test error for free.
• Impurity importance favours high-cardinality and noise features; permutation importance on held-out data is safer but misleads with correlated features.

Code#

The in-bag fraction, the variance formula, $\rho$ and $\tau^2$ of bagged and forest trees by simulation, out-of-bag accuracy, extra trees and importance pitfalls:

import numpy as np
from sklearn.datasets import load_breast_cancer
from sklearn.ensemble import RandomForestRegressor, RandomForestClassifier, ExtraTreesClassifier
from sklearn.inspection import permutation_importance
from sklearn.model_selection import train_test_split

rng = np.random.default_rng(0)

# the share of training points inside one bootstrap sample: 1 - (1 - 1/n)^n, and a simulation for n = 100
print([round(1 - (1 - 1 / n) ** n, 3) for n in (10, 100, 1000)], round(1 - np.exp(-1), 3))   # [0.651, 0.634, 0.632] 0.632
print(round(float(np.mean([len(np.unique(rng.integers(0, 100, 100))) / 100 for _ in range(20_000)])), 3))   # 0.634

# variance of an average of B models with variance 1 and pairwise correlation 0.3
print([round(0.3 + 0.7 / B, 3) for B in (1, 10, 100)])          # [1.0, 0.37, 0.307]

# tau^2 and rho of single trees on Friedman's function, from 40 training sets with 25 trees each
f = lambda X: 10 * np.sin(np.pi * X[:, 0] * X[:, 1]) + 20 * (X[:, 2] - 0.5) ** 2 + 10 * X[:, 3] + 5 * X[:, 4]
Xtest = rng.random((300, 10))
for name, m in (('bagging', 1.0), ('forest', 1 / 3)):
    P = []
    for r in range(40):
        X = rng.random((200, 10)); y = f(X) + rng.normal(size=200)
        P.append([t.predict(Xtest) for t in RandomForestRegressor(25, max_features=m, random_state=r).fit(X, y).estimators_])
    P = np.array(P)                                            # training sets x trees x test points
    within = P.var(1, ddof=1).mean()                           # E_D Var(T | D) = (1 - rho) tau^2
    between = P.mean(1).var(0, ddof=1).mean() - within / 25    # Var_D E(T | D) = rho tau^2
    bias2 = ((P.mean((0, 1)) - f(Xtest)) ** 2).mean()
    print(name, round(between + within, 2), round(between / (between + within), 3), round(bias2, 2), round(between + within / 25, 2), round(between, 2))
# bagging 11.11 0.105 3.83 1.57 1.17 | forest 15.52 0.043 5.26 1.25 0.66   (tau^2, rho, bias^2, variance at B = 25, floor)

# out-of-bag accuracy against a test set; extra trees for comparison
X, y = load_breast_cancer(return_X_y=True)
names = load_breast_cancer().feature_names
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3, random_state=0, stratify=y)
rf = RandomForestClassifier(300, oob_score=True, random_state=0).fit(Xtr, ytr)
et = ExtraTreesClassifier(300, random_state=0).fit(Xtr, ytr)
print(round(rf.oob_score_, 3), round(rf.score(Xte, yte), 3), round(et.score(Xte, yte), 3))   # 0.967 0.953 0.942

# an exact copy of the most important feature: with m features per split the twins together get more than the original
top = int(np.argmax(rf.feature_importances_))
rf2 = RandomForestClassifier(300, random_state=0).fit(np.column_stack([Xtr, Xtr[:, top]]), ytr)
print(names[top], round(rf.feature_importances_[top], 3), round(rf2.feature_importances_[top], 3), round(rf2.feature_importances_[-1], 3))
# worst perimeter 0.134 0.108 0.124
# with all features at every split (bagging) the twins share the importance of the original instead
bag = RandomForestClassifier(300, max_features=None, random_state=0).fit(Xtr, ytr)
bag2 = RandomForestClassifier(300, max_features=None, random_state=0).fit(np.column_stack([Xtr, Xtr[:, top]]), ytr)
print(round(bag.feature_importances_[top], 3), round(bag2.feature_importances_[top], 3), round(bag2.feature_importances_[-1], 3))   # 0.415 0.212 0.204

# impurity versus permutation importance: the label depends on x1 only; x2 is binary noise, x3 continuous noise
Z = rng.random((1000, 3)); Z[:, 1] = Z[:, 1] < 0.5
yz = (Z[:, 0] + 0.3 * rng.normal(size=1000) > 0.5).astype(int)
rf3 = RandomForestClassifier(300, random_state=0).fit(Z[:500], yz[:500])
perm = permutation_importance(rf3, Z[500:], yz[500:], n_repeats=10, random_state=0).importances_mean
print(rf3.feature_importances_.round(3), perm.round(3))       # [0.661 0.008 0.331] [ 0.227 -0.016 -0.008]

Next#

Averaging attacks the variance and leaves the bias alone. A forest of shallow trees has the bias of one shallow tree drawn by the same randomized procedure, in expectation. The average of many stumps on different features and thresholds can follow an additive function, but no stump sees an interaction, so when the target has structure that no tree in the forest captures, no number of trees will capture it. The next note builds the ensemble the other way round: sequentially, each small tree fitted to the errors that the sum of the previous trees still makes, so that the bias falls step by step. It is gradient descent in the space of functions, and it is the strongest general method for tabular data.

References#

• L. Breiman. Bagging Predictors. Machine Learning, 24(2), 1996. Section 1 (unstable procedures), Section 4 (why bagging works).
• L. Breiman. Random Forests. Machine Learning, 45(1), 2001. Theorem 1.2 (convergence as trees are added), Section 3.1 (out-of-bag estimates), Section 10 (permutation importance), Section 11 (regression forests).
• T. Hastie, R. Tibshirani, J. Friedman. The Elements of Statistical Learning, 2nd ed. Springer, 2009. Section 8.7 (bagging), Chapter 15 (random forests: Eq. 15.1, defaults in 15.3, out-of-bag samples 15.3.1, variable importance 15.3.2, overfitting 15.3.4, the variance decomposition 15.4.1, adaptive nearest neighbours 15.4.3).
• P. Geurts, D. Ernst, L. Wehenkel. Extremely randomized trees. Machine Learning, 63(1), 2006. Section 2.1.
• C. Strobl, A.-L. Boulesteix, A. Zeileis, T. Hothorn. Bias in random forest variable importance measures: Illustrations, sources and a solution. BMC Bioinformatics, 8, 2007.
• G. Hooker, L. Mentch, S. Zhou. Unrestricted permutation forces extrapolation: variable importance requires at least one more model, or there is no free variable importance. Statistics and Computing, 31, 2021 (arXiv:1905.03151).
• E. Sokolov et al. Машинное обучение (HSE). Lecture notes, lecture 10: bagging, random forests and the bias–variance decomposition; practical session 10; practical session 11: interpreting models.