Random Forests

Averaging many decorrelated trees. Why bagged trees are correlated, the variance of an average of correlated predictions derived and its floor, random input selection at each split, correlation and variance measured on Friedman's synthetic problem, out-of-bag error derived and compared with cross-validation, variable importance by impurity and by permutation, and random forests against single trees and linear regression on breast cancer and diabetes data.

A single decision tree is easy to read but unreliable. Introduction to Decision Trees fitted depth-2 trees to 200 bootstrap samples of the same 569 breast cancer tumors and found five different measurements at the root, with the original tree's root question appearing in only 13 of them; two such trees disagreed on a median 6.3% of the diagnoses. That variability is the main reason a tree predicts new cases less well than it seems to fit its training data. A random forest grows hundreds of trees, each on a resampled copy of the data and each forced to vary its choices, and averages them. The result predicts better than any of its trees and is far more stable, at the price of the single readable tree.

The method is due to Breiman (2001), who combined two ideas: bagging, his own earlier method of averaging models fitted to bootstrap samples (Breiman, 1996a), and random selection of the inputs considered at each split, which he traces to Amit and Geman's search over random subsets of features at each node and to Ho's random subspace method, which gives each tree a random subset of the features. This article derives why the combination works, measures the quantities the derivation depends on, and shows how a forest estimates its own error without a test set.

Bagging in brief

Bagging, short for bootstrap aggregating, is a general way to reduce the variance of any unstable method, and the Ensemble Techniques topic treats it in full. Applied to trees it takes three steps (James, Witten, Hastie and Tibshirani, 2021, §8.2.1):

  1. Draw $B$ bootstrap samples from the $n$ training cases: each is $n$ cases drawn at random with replacement, so some cases appear more than once and others not at all (see The Bootstrap Method).
  2. Grow a tree on each sample. The trees are grown deep and not pruned, so each has low bias and high variance.
  3. Predict by averaging the $B$ trees' predictions for a regression problem, or by majority vote over their predicted classes for a classification problem.

On the breast cancer data, 10-fold cross-validated accuracy rises from 0.923 for one fully grown tree to 0.961 for an average of 500 bagged trees. The improvement comes from averaging, not from better trees: each bagged tree is grown by the same procedure as the single tree, on a resampled copy of the same data. How much averaging can achieve depends on how similar the trees are, and that is the question random forests address.

The variance of an average

Fix an input $x$ and consider the prediction $T_b$ that tree $b$ makes at $x$. Over the random draw of the training data and the bootstrap sample, $T_b$ is a random variable. All $B$ trees are produced by the same procedure, so they have the same distribution; write $\sigma^2$ for the variance of one tree's prediction and $\rho$ for the correlation between the predictions of any two different trees, so that their covariance is $\rho \sigma^2$. The forest predicts the average $\bar{T} = \frac{1}{B} \sum_{b=1}^{B} T_b$. Its variance is

$$\operatorname{Var}\bigl(\bar{T}\bigr) = \frac{1}{B^2} \operatorname{Var}\Bigl(\sum_{b=1}^{B} T_b\Bigr) = \frac{1}{B^2} \Bigl[\sum_{b} \operatorname{Var}(T_b) + \sum_{b \ne b'} \operatorname{Cov}(T_b, T_{b'})\Bigr].$$

There are $B$ variance terms, each $\sigma^2$, and $B(B-1)$ ordered pairs of different trees, each with covariance $\rho\sigma^2$. So

$$\operatorname{Var}\bigl(\bar{T}\bigr) = \frac{B\sigma^2 + B(B-1)\rho\sigma^2}{B^2} = \rho\,\sigma^2 + \frac{1 - \rho}{B}\,\sigma^2.$$

When the trees are independent, $\rho = 0$ and the familiar result $\sigma^2 / B$ appears: averaging $B$ independent predictions divides the variance by $B$, the fact James et al. (2021, §8.2.1) use to motivate bagging. When they are correlated, only the second term shrinks as trees are added. The first term, $\rho\sigma^2$, does not depend on $B$ at all, and it is the variance of a forest with infinitely many trees.

The variance of an average of B equally correlated predictions, as a fraction of one prediction's variance, for four values of the correlation ρ. With independent predictions (ρ = 0) the variance keeps falling as 1/B. With any correlation it levels off at ρ, so beyond a few dozen trees the correlation, not the number of trees, decides the variance.
The variance of an average of B equally correlated predictions, as a fraction of one prediction's variance, for four values of the correlation ρ. With independent predictions (ρ = 0) the variance keeps falling as 1/B. With any correlation it levels off at ρ, so beyond a few dozen trees the correlation, not the number of trees, decides the variance.

Where the correlation comes from

The trees in a forest are not correlated because they influence each other; each is grown independently. They are correlated because they are grown from the same training data. Write $Z$ for the training set. Given $Z$, the only remaining randomness is the bootstrap sample and the forest's other random choices, which are drawn independently for each tree. Two facts then follow from conditioning on $Z$. By the law of total variance, the variance of one tree splits into

$$\sigma^2 = \operatorname{Var}_Z\bigl(\mathrm{E}[T_b \mid Z]\bigr) + \mathrm{E}_Z\bigl[\operatorname{Var}(T_b \mid Z)\bigr],$$

a part due to which training set was drawn and a part due to the resampling given the training set. And because two trees are independent given $Z$, their covariance is only the first part:

$$\operatorname{Cov}(T_b, T_{b'}) = \operatorname{Var}_Z\bigl(\mathrm{E}[T_b \mid Z]\bigr), \qquad\text{so}\qquad \rho = \frac{\operatorname{Var}_Z\bigl(\mathrm{E}[T_b \mid Z]\bigr)}{\sigma^2}.$$

The floor $\rho\sigma^2$ is the variance that comes from the training data itself, the part that would remain even after averaging every possible bootstrap tree. Averaging removes the resampling noise, $(1 - \rho)\sigma^2$, at the rate $1/B$. To lower the floor, the trees have to depend less on the particular training set, or, put the other way, the randomization within the forest has to account for a larger share of each tree's variability.

Why bagged trees are alike

Bagging leaves the floor high when a few inputs dominate. Every bagged tree searches all inputs for its root split and, on most bootstrap samples, finds the same strong input there; with the same root, the trees tend to share their next splits too, and their predictions move together. James et al. (2021, §8.2.2) describe exactly this case: with one very strong predictor, "most or all of the trees will use this strong predictor in the top split", the trees "will look quite similar to each other", and averaging highly correlated quantities "does not lead to as large of a reduction in variance".

The breast cancer data show it. In 500 bagged trees fitted to all 569 tumors, only five different measurements ever appear at the root, and worst perimeter alone accounts for 207 of the 500 roots. All five describe either the size of the nuclei or the concavity of their outlines.

The random forest

Breiman's (2001) change is small. Each tree is still grown on a bootstrap sample, deep and unpruned, but at every split the algorithm first draws a random subset of $m$ of the $p$ inputs and searches for the best split among those $m$ only. A fresh subset is drawn at each split. With $m = p$ the method is bagging. With smaller $m$, the strong input is not even available at most splits: on average a fraction $(p - m)/p$ of splits cannot consider it (James et al., 2021, §8.2.2), and other inputs get their turn.

For the breast cancer forest with $m = 5$ of the 30 measurements, the 500 roots use 19 different measurements, and the most common, worst perimeter, appears at only 72 of them. The individual trees are usually weaker than bagged trees, since many of their splits use a second-best input, but they are less alike; the measurements on Friedman's problem below put numbers on both effects. Whether the trade pays depends on the balance between the two effects, which the variance formula makes precise: lowering $\rho$ lowers the floor, while each tree's own error rises.

Breiman (2001) expressed the same balance in two bounds. For classification, the forest's generalization error is at most $\bar{\rho}(1 - s^2)/s^2$, where $s$ is the strength of the trees (how far, on average, the vote for the correct class exceeds the vote for any other) and $\bar{\rho}$ is the mean correlation between trees. For regression, assuming each tree's predictions have the same mean as the outcome, the forest's mean squared error is at most $\bar{\rho}$ times the average error of a single tree, with $\bar{\rho}$ a weighted correlation between the trees' residuals (his Theorem 11.2). In both, accuracy needs strong trees and low correlation, and the randomization, in his words, "needs to aim at low correlation" without costing too much strength.

Common choices of $m$ are about $\sqrt{p}$ for classification and $p/3$ for regression, the defaults of the R package randomForest (James et al., 2021, §8.3.3). Breiman (2001) found classification results "insensitive to the number of features selected to split each node", with one or two inputs often close to the best. scikit-learn's RandomForestClassifier uses $\sqrt{p}$ by default, but RandomForestRegressor uses all $p$ inputs by default, which makes it bagging unless max_features is set.

Correlation and variance, measured

The quantities in the derivation can be measured directly when fresh training sets can be drawn at will. Friedman's (1991) first test problem, as used by Breiman (1996a) to evaluate bagging, has ten inputs, each uniform on $[0, 1]$, and the outcome

$$y = 10 \sin(\pi x_1 x_2) + 20 (x_3 - 0.5)^2 + 10 x_4 + 5 x_5 + \varepsilon, \qquad \varepsilon \sim N(0, 1),$$

so five inputs matter, in a mix of nonlinear, interacting and linear ways, and five are noise. For each of 200 independently drawn training sets of 200 cases, forests of $B = 100$ trees were grown for $m = 1, 2, 3, 5, 7$ and 10, and their predictions recorded at 500 fixed test points. Because the true function is known, each forest's expected squared error can be split into squared bias, variance and the noise variance of 1. The variance $\sigma^2$ of one tree, the correlation $\rho$ between two trees grown on the same training set, and the forest's variance are averaged over the test points.

$m$ One tree's variance $\sigma^2$ Correlation $\rho$ Floor $\rho\sigma^2$ Forest variance Formula
1 20.54 0.022 0.46 0.70 0.66
2 17.38 0.033 0.58 0.75 0.75
3 15.34 0.040 0.62 0.80 0.76
5 12.75 0.067 0.86 0.96 0.98
7 11.60 0.090 1.05 1.12 1.15
10 (bagging) 10.84 0.115 1.25 1.32 1.35

The formula $\rho\sigma^2 + (1-\rho)\sigma^2/B$, computed from the measured $\sigma^2$ and $\rho$ at each test point, predicts the forest's variance to within a few hundredths. Three further observations follow.

The correlations are small, between 0.02 and 0.12, yet they dominate. With 100 trees in the bagged forest, the floor $\rho\sigma^2 = 1.25$ accounts for almost all of the forest variance of 1.32, and the resampling part, $(1-\rho)\sigma^2/B$, is the small remainder. Averaging has already cut the variance from 10.84 for one tree to 1.32, and adding trees cannot take it much lower. Only lowering $\rho$ can.

Smaller $m$ lowers the correlation, from 0.115 for bagging to 0.022 for $m = 1$, and with it the forest's variance, from 1.32 to 0.70. But it raises the bias, because a tree that may only split on a randomly chosen input often splits on one of the five useless ones. At $m = 1$ the squared bias is 8.88, against 3.78 for bagging.

$m$ Squared bias Forest variance Test MSE
1 8.88 0.70 10.59
2 6.04 0.75 7.79
3 4.91 0.80 6.70
5 4.07 0.96 6.03
7 3.86 1.12 5.98
10 (bagging) 3.78 1.32 6.10

The two effects balance at an intermediate value. The expected test error is lowest at $m = 7$ (5.98), close for $m = 5$ (6.03) and bagging (6.10), and much worse for $m = 1$ (10.59). In this problem, with half the inputs irrelevant, a large $m$ is needed so that most splits can find a relevant input, which matches Breiman's (2001) observation that regression forests need a relatively large number of inputs per split. Every forest is far better than a single tree, whose expected test error ranges from 15.62 to 30.43.

Friedman's problem, 200 training sets of 200 cases. Left: the correlation between two trees in the same forest falls as fewer inputs are tried at each split. Right: for forests of 100 trees, the variance falls with m but the squared bias rises, and the test error is lowest at m = 7, slightly better than bagging (m = 10). The noise variance, 1, is included in the test error.
Friedman's problem, 200 training sets of 200 cases. Left: the correlation between two trees in the same forest falls as fewer inputs are tried at each split. Right: for forests of 100 trees, the variance falls with m but the squared bias rises, and the test error is lowest at m = 7, slightly better than bagging (m = 10). The noise variance, 1, is included in the test error.

More trees do not overfit

The number of trees $B$ is not a tuning parameter in the usual sense. Breiman (2001, Theorem 1.2) showed, using the strong law of large numbers, that as trees are added the forest's generalization error converges to a limit, and drew the conclusion that random forests "do not overfit as more trees are added, but produce a limiting value of the generalization error". The forest can still overfit in the ordinary sense, through deep trees fitting noise, but adding trees only moves it closer to the infinite forest. James et al. (2021, §8.2.1) give the practical rule: use a value of $B$ large enough that the error has settled down.

Breast cancer, trained on 398 tumors and tested on 171. Test error (solid) and out-of-bag error (dashed) for bagging and a random forest with m = 5, as trees are added. Both settle after about 100 trees, well below the single tree's test error of 0.094 (dotted). The out-of-bag estimates start high when there are few trees and settle near the test error.
Breast cancer, trained on 398 tumors and tested on 171. Test error (solid) and out-of-bag error (dashed) for bagging and a random forest with m = 5, as trees are added. Both settle after about 100 trees, well below the single tree's test error of 0.094 (dotted). The out-of-bag estimates start high when there are few trees and settle near the test error.

On a held-out set of 171 tumors (30% of the data, stratified), a single fully grown tree makes 16 errors, an error rate of 0.094. With 500 trees, bagging makes 12 errors (0.070) and the random forest 8 (0.047). A test set of 171 cases cannot separate the two ensembles reliably: with 10-fold cross-validation on all 569 tumors both reach an accuracy of 0.961. For these data the gain comes from averaging, and decorrelation adds little, consistent with Breiman's finding that classification error is insensitive to $m$. Out-of-bag error for forests with $m$ = 1, 2, 3, 5, 8, 12, 20 and 30, averaged over three seeds each, lies between 0.034 and 0.041.

Out-of-bag error

A bootstrap sample of size $n$ is drawn by $n$ independent draws, each picking any particular case with probability $1/n$. A given case is missed by one draw with probability $1 - 1/n$, so it is missed by all $n$ draws, and left out of the sample, with probability

$$\Bigl(1 - \frac{1}{n}\Bigr)^n \to e^{-1} \approx 0.368 \quad\text{as } n \to \infty$$

which is why Breiman (1996b) describes each bootstrap sample as leaving out "about 37%" of the cases. The limit is reached quickly: the probability is 0.3487 for $n = 10$ and 0.3676 for $n = 569$. So each tree is grown on about 63% of the distinct cases, and the remaining 37% are its out-of-bag (OOB) cases, which it has never seen.

That gives a forest a built-in test set. For each training case, collect the predictions of only those trees for which it was out of bag, and combine them by averaging or by vote; this is the case's OOB prediction. The OOB error is the error of these predictions over all $n$ cases (Breiman, 1996b; James et al., 2021, §8.2.1). Each prediction comes from trees that did not see the case, so the OOB error is an honest estimate of the error on new data, obtained at no extra computing cost. In the 500-tree forest on all 569 tumors, each tumor is out of bag for 183.5 trees on average (between 149 and 224), a share of 0.367.

Two cautions come from Breiman (2001). The OOB prediction for a case uses only about a third of the trees, so with few trees it is the prediction of a smaller and weaker forest, and the OOB error "will tend to overestimate the current error rate"; the figure shows this at the left, where with 5 trees the forest's OOB error is 0.126 against a test error of 0.058. With enough trees the bias disappears, and James et al. (2021, §8.2.1) note that for large $B$ the OOB error is "virtually equivalent" to leave-one-out cross-validation. On the breast cancer data the forest's OOB accuracy, 0.965, is close to its 10-fold cross-validated accuracy, 0.961, which required fitting ten forests rather than one.

The OOB error makes tuning cheap. Choosing $m$ for the breast cancer forest by OOB error, as above, takes one forest per candidate value instead of ten.

Which inputs matter?

A forest of 500 trees cannot be read, but it can be summarized. Two measures of variable importance are standard.

Mean decrease in impurity adds up, for each input, the reduction in the Gini index (for classification) or RSS (for regression) produced by every split on that input, weighted by the cases reaching the split, and averages over the trees (James et al., 2021, §8.2.1). It is a by-product of growing the forest and costs nothing. Because it is computed on the training data from the splits the trees chose, it measures how much each input was used, which is not quite the same as how much it helps prediction.

Permutation importance measures prediction directly (Breiman, 2001, §10): shuffle the values of one input among the cases of a test set (or the OOB cases), breaking its link with the outcome while keeping its distribution, and record how much the forest's accuracy drops. An input the forest relies on causes a large drop; an irrelevant one causes none.

Variable importance in a random forest for the breast cancer data, for the ten measurements with the highest permutation importance. Left: mean decrease in Gini impurity on the training data. Right: the drop in test accuracy when the measurement is shuffled (10 repetitions; bars show ±1 standard deviation). The two rank the size measurements differently, and worst texture, nearly ignored by the impurity measure, ranks fourth by permutation.
Variable importance in a random forest for the breast cancer data, for the ten measurements with the highest permutation importance. Left: mean decrease in Gini impurity on the training data. Right: the drop in test accuracy when the measurement is shuffled (10 repetitions; bars show ±1 standard deviation). The two rank the size measurements differently, and worst texture, nearly ignored by the impurity measure, ranks fourth by permutation.

For the breast cancer forest the impurity measure ranks worst perimeter first (0.151), followed by worst radius, worst concave points, worst area and mean concave points. Permutation on the held-out tumors ranks worst radius first (a drop in accuracy of 0.021), then worst area and worst concave points, and puts worst perimeter only fifth. Worst perimeter, worst radius and worst area measure nearly the same thing, so the forest can substitute one for another: shuffling any one of them costs little because the others remain, while the impurity measure divides credit among them according to which happened to be chosen. Correlated inputs share importance under either measure, and neither measure says that an input causes the outcome. Worst texture shows the opposite discrepancy. It is rarely chosen for splits, ranking 13th of 30 by impurity, but when it is shuffled accuracy drops by 0.016, the fourth largest drop: it carries information that the size and shape measurements do not.

Random forests for regression

On the diabetes data used throughout the regression articles, 10-fold cross-validated $R^2$ (with the folds of Multiple Linear Regression) is 0.419 for bagging ($m = 10$), 0.443 for a random forest with $m = 3$, about $p/3$, and 0.435 with $m = 1$. All three improve substantially on the best pruned regression tree, 0.342 (see Regression Trees). None matches a linear regression on the ten inputs, 0.484. A forest averages step functions, and when the true relationship is close to a sum of straight-line effects, as it appears to be here, a linear model estimates it more efficiently from 442 cases. A random forest is a strong general-purpose method, not a guaranteed improvement over a well-chosen simpler model, and comparing the two by cross-validation is part of the job (see Model Selection).

The OOB $R^2$ values (0.425, 0.453 and 0.445 for $m = 10$, 3 and 1) are close to the cross-validated ones and rank the three forests the same way.

Strengths and costs

A random forest keeps most of what makes trees convenient: no scaling of inputs, natural handling of interactions and of several classes, and few assumptions about the form of the relationship. It adds stability and accuracy, works well with default settings, gives an error estimate for free, and grows its trees independently, so they can be built in parallel. Breiman (2001) also reported that forests were "relatively robust to outliers and noise".

The costs are the loss of the single interpretable tree, a model that is large to store and slower to evaluate (500 trees of about 21 leaves each for the breast cancer forest, against one tree of 22), and the limitations it inherits from trees: like every tree, a forest predicts a constant beyond the range of its training data, and a forest of deep trees can still fit noise in small datasets. The main alternative ensemble of trees is Boosting, which grows trees in sequence, each correcting the errors of those before, rather than independently.

In Python

from sklearn.datasets import load_breast_cancer
from sklearn.ensemble import RandomForestClassifier
from sklearn.inspection import permutation_importance
from sklearn.model_selection import train_test_split

data = load_breast_cancer()
X_train, X_test, y_train, y_test = train_test_split(
    data.data, data.target, test_size=0.3, stratify=data.target, random_state=0)

forest = RandomForestClassifier(n_estimators=500, max_features="sqrt",
                                oob_score=True, random_state=0, n_jobs=-1)
forest.fit(X_train, y_train)
print(1 - forest.oob_score_)               # out-of-bag error estimate
print(1 - forest.score(X_test, y_test))    # test error: 0.047, 8 of 171

perm = permutation_importance(forest, X_test, y_test, n_repeats=10, random_state=0)
for i in perm.importances_mean.argsort()[::-1][:5]:
    print(data.feature_names[i], round(perm.importances_mean[i], 4))

max_features is $m$; max_features=None gives bagging. oob_score=True computes the out-of-bag estimate during fitting. feature_importances_ holds the impurity-based importances. For regression, RandomForestRegressor has the same interface, but set max_features explicitly, since its default uses all inputs. The numbers in this article are computed by tools/experiments/data-science/random-forests.py in the site's repository.

References

  • Breiman, L. (1996a). Bagging predictors. Machine Learning, 24(2), 123–140. record · 3 pages
  • Breiman, L. (1996b). Out-of-bag estimation [Technical report]. Department of Statistics, University of California, Berkeley. record
  • Breiman, L. (2001). Random forests. Machine Learning, 45(1), 5–32. Quotations and section and theorem numbers follow the technical report version (Statistics Department, University of California, Berkeley, January 2001). record
  • Friedman, J. H. (1991). Multivariate adaptive regression splines. The Annals of Statistics, 19(1), 1–67. record · 4 pages
  • James, G., Witten, D., Hastie, T., and Tibshirani, R. (2021). An Introduction to Statistical Learning with Applications in R (2nd ed.). Springer. record · 30 pages
  • Wolberg, W., Mangasarian, O., Street, N., and Street, W. (1993). Breast Cancer Wisconsin (Diagnostic) [Data set]. UCI Machine Learning Repository. https://doi.org/10.24432/C5DW2B record · 14 pages