30  Bagging and Random Forests

A single deep tree has low bias and high variance (Section 28.3). Averaging many such trees, each fitted to a different random sample of the data, keeps the low bias and reduces the variance. This chapter describes bootstrap aggregation, random forests, the out-of-bag estimate of error, and the variable importance measures of forests.

30.1 Bootstrap aggregation

Bagging, short for bootstrap aggregation, fits the same learning procedure to \(B\) bootstrap samples of the training data (Section 10.6) and averages the \(B\) predictions (Breiman 1996):

\[ \hat f_{\text{bag}}(x) = \frac{1}{B} \sum_{b=1}^{B} \hat f^{*b}(x), \tag{30.1}\]

where \(\hat f^{*b}\) is the model fitted to the \(b\)-th bootstrap sample. For classification, the class probabilities or the votes of the \(B\) models are averaged. Bagging helps most for unstable procedures, those whose fit changes substantially with small changes in the data, such as deep trees; it changes little for stable procedures such as linear regression.

Figure 30.1 compares a single deep regression tree with the average of 200 trees fitted to bootstrap samples of the same data.

Figure 30.1: A single fully grown regression tree and the average of 200 trees grown on bootstrap samples (bagging), fitted to 100 simulated cases.

The single tree follows the noise of individual cases; the bagged average is smoother, since the noise-driven parts of individual trees differ between bootstrap samples and average out.

30.2 Variance of an average

If each of \(B\) fitted functions has variance \(\sigma^2\) at a point, and every pair has correlation \(\rho\), the variance of their average is

\[ \operatorname{Var}\left(\frac{1}{B}\sum_{b=1}^{B} \hat f^{*b}(x)\right) = \rho \sigma^2 + \frac{1 - \rho}{B} \sigma^2 \tag{30.2}\]

(AMDS: Covariance and correlation). As \(B\) grows, the second term vanishes and the variance approaches \(\rho \sigma^2\). Adding trees cannot reduce the variance below that floor; reducing the correlation between trees can. Trees fitted to bootstrap samples of the same data are strongly correlated, since the same strong features dominate their first splits.

30.3 Random forests

Random forests decorrelate the trees by restricting each split to a random subset of \(m\) of the \(p\) features, drawn anew at every split (Breiman 2001). A feature that would dominate every tree is unavailable at some splits, and other features enter. Smaller \(m\) gives less correlated trees and higher variance per tree. Hastie et al. (2009) recommend \(m = \lfloor\sqrt p\rfloor\) for classification and \(\lfloor p/3 \rfloor\) for regression as defaults; the ranger implementation uses \(\lfloor\sqrt p\rfloor\) for both by default (Wright and Ziegler 2017). With \(m = p\), a random forest is bagging of trees.

The main hyperparameters are:

  • the number of features per split, \(m\) (mtry), the most influential;
  • the minimum size of a leaf, or the maximum depth, which control the variance of each tree;
  • the number of trees \(B\), which should be large enough for the average to stabilize, and does not cause overfitting as it grows;
  • the size of each sample and whether it is drawn with or without replacement.

Random forests usually perform well with their default settings, and tuning improves them modestly (Probst et al. 2019). Extremely randomized trees further randomize the split points (Geurts et al. 2006). For classification, averaging the class proportions of the leaves, rather than the votes, gives a probability forest, a consistent estimator of the class probabilities (Malley et al. 2012). Retaining the outcomes in each leaf, rather than their mean, gives a quantile regression forest, which estimates conditional quantiles of the outcome (Meinshausen 2006).

30.4 Out-of-bag error

Each bootstrap sample leaves out about 37% of the cases (Section 10.6). For each training case, the trees whose sample did not include it form a forest that has not seen it; their averaged prediction is the case’s out-of-bag (OOB) prediction. The error of the OOB predictions estimates the error on new cases without a separate test set or resampling loop, at no additional cost. Each OOB prediction averages about a third of the trees, so the OOB error is slightly pessimistic for the full forest.

30.5 Variable importance

Forests provide two common measures of the importance of each feature:

  • Impurity importance sums, over all splits on the feature in all trees, the decrease in impurity (Gini index or variance). It is computed from the training data and favors features with many possible split points, such as continuous features or categorical features with many levels, even when they carry no information (Strobl et al. 2007).
  • Permutation importance measures the increase in the OOB error when the values of the feature are randomly permuted, which breaks its association with the outcome. It is computed on held-out cases. Correlated features share importance: permuting one leaves its information available through the others.

Both measure how much the fitted forest uses a feature, not whether the feature causes the outcome (Section 2.2). Chapter 38 develops these and other explanation methods.

30.6 Properties

  • Random forests inherit the strengths of trees: interactions, mixed feature types, no scaling, invariance to monotone transformations.
  • They reduce the variance of trees substantially, but do not remove the step-function structure: a smooth or linear effect is represented by an average of steps.
  • Their predictions for a case lie within the range of the training outcomes, so they do not extrapolate.
  • They are parallel: the trees are independent and can be grown simultaneously.

30.7 Summary

  • Bagging averages a procedure fitted to bootstrap samples, reducing the variance of unstable learners such as deep trees.
  • The variance of an average of correlated predictions approaches \(\rho \sigma^2\); random forests reduce \(\rho\) by sampling features at each split.
  • The out-of-bag error estimates performance on new cases without resampling.
  • Impurity importance favors features with many split points; permutation importance is computed on held-out cases.

30.8 Further reading