Bagging and random forests

Section of Ensembles, random forests, and boosting, part of Statistical learning

Type	Section
Taught in	Ensembles, random forests, and boosting
Part	Statistical learning

Trees are useful base learners because they can represent nonlinear interactions and can change under resampling. Random forests commonly grow deep trees. They need not be weak in the precise boosting sense of having only a small advantage over chance. The ensemble’s benefit depends on how member errors combine (Breiman, 1996, 2001).

Ho’s random-subspace ensembles are built from different predictor subsets. Breiman’s random forest uses random predictor subsets at individual splits, together with randomised tree construction. These choices create different trees without requiring different measured datasets.

A new x lands in one leaf of each tree. A hard vote takes the majority of the leaf labels. A soft vote uses the class proportions in the leaf as an estimate of \mathbb{P}(\mathrm{class}=g\mid x,\text{tree }t), a piecewise-constant estimate of the posterior, and averages those probabilities. The soft aggregate predicts

g^*=\operatorname{arg\,max}_{g\in\{1,\ldots,G\}} \frac1T\sum_{t=1}^T \widehat{\mathbb{P}}(\mathrm{class}=g\mid x,\text{tree }t).

Ho varied the columns. Bagging, bootstrap aggregation, varies the rows. Each model is fit on a non-parametric bootstrap resample, and the fitted models are averaged or voted. The bootstrap is the same resample used for the error-rate estimator on Estimating error rates: about 0.632n distinct cases appear in each draw. Bagging improves unstable fits, trees and neural networks among them, and does little for linear discriminant analysis, as the diversity calculation already showed. A random forest combines the bootstrap sample with a random subset of variables at each split.

At each split of a classification tree the forest offers only about \sqrt{p} randomly chosen coordinates, where p is the number of predictors. The restriction forces trees to split on different variables even when their bootstrap samples are similar. The \sqrt{p} choice is a heuristic, not a consequence of the diversity identity.

Definition 1 (Random forest) For t=1,\ldots,T, build a forest of T trees as follows.

Generate a bootstrap sample (X^{(t)},y^{(t)}) from the training data.
Fit a tree f_t to (X^{(t)},y^{(t)}). At each node: (a) randomly select k explanatory variables; (b) determine the best explanatory variable and split among them; (c) add this split to the tree. Repeat (a)–(c) until a stopping criterion is met.

For a new observation x the forest predicts, for regression, f(x)=\frac1T\sum_t f_t(x), and for classification

f(x)=\operatorname{arg\,max}_g\sum_{t=1}^T I\bigl(f_t(x)=g\bigr),

or the soft aggregate above if each tree produces class probabilities.

Article: Random forest →

Each node sees only k candidate variables, but a tree has many nodes, so one tree still has chances to split on a substantial fraction of the predictors. The restriction bites locally, at the choice of each split, which is enough to make neighbouring trees disagree.

Why decorrelating the trees helps

Main article: Why decorrelating the trees helps

The diversity term said that disagreement helps. The variance of an average says the same thing with a correlation. Suppose the T tree predictions at a fixed x each have variance \sigma^2 and every pair has correlation \rho. Expand the variance of the sum, using \operatorname{Var}(f_t)=\sigma^2 and \operatorname{Cov}(f_t,f_s)=\rho\sigma^2 for t\ne s. There are T variance terms and T(T-1) covariance terms:

\begin{align*} \operatorname{Var}\Biggl(\frac1T\sum_{t=1}^T f_t\Biggr) &=\frac{1}{T^2}\Bigl(T\sigma^2+T(T-1)\rho\sigma^2\Bigr)\\ &=\frac{\sigma^2}{T}\bigl(1+(T-1)\rho\bigr)\\ &=\rho\sigma^2+\frac{1-\rho}{T}\sigma^2. \end{align*}

Adding trees shrinks only the second term. The first term, \rho\sigma^2, is a floor set by the correlation between trees, and no number of additional copies of a highly correlated tree will remove it. The calculation assumes a common variance and a common pairwise correlation. It does not assume normality. Bootstrap samples reduce \rho somewhat, because each tree misses a different third of the cases: the omission probability (1-1/n)^n tends to e^{-1}\approx 0.368. Restricting each split to k random variables reduces \rho much more, because the trees are then forbidden from always cutting on the same strongest predictor. That reduction in \rho is the quantitative form of the diversity term. The reason to randomise the candidate predictors is to lower the floor, not to improve any one tree.

The three free quantities

Main article: Random-forest tuning parameters

Three quantities are still free: k, the number of predictors offered at each split; a control on tree size, such as a maximum depth or a minimum leaf size; and T, the number of trees. Rules of thumb often suffice. A search has to stay off the test set. Nested cross-validation puts the search inside the assessment. A simpler design uses one cross-validation to choose the triple and a separate test set to estimate the error of the chosen forest.

The variance formula says the second term falls as T grows and the correlation floor does not, so extra trees help until that floor dominates. They do not start to over-fit in the way an extra leaf of a single tree does. Computation grows linearly in T, both to train and to predict. The default in the randomForest implementation is 500 trees. Searching over T is rarely worth the fits. Computing time is the practical limit.

The variance formula wants \rho small, and a single tree wants enough variables to be accurate. So k has to be large enough for each tree to have a tolerable error and small enough for the trees to disagree. The usual suggestions are k=\sqrt{p} for classification and k=p/3 for regression, the defaults in randomForest.

A maximum depth is one control on tree size, and trees are often asymmetric, so a depth limit cuts some branches that still have cases to split and spares others that do not. The minimum number of observations in a leaf is the control in that implementation, with default 1 for classification and 5 for regression. The classification default places no limit on size: a leaf may be a single case. A maximum number of leaves is a related control and has no default.

The defaults tend to produce large trees, each fitted on its random variable sets, diverse because of the bootstrap and the restriction on k, and individually accurate enough that the first term of the diversity identity stays tolerable. Whether those defaults are enough depends on the problem: the complexity of the target, including the Bayes rule, the number of predictors, their associations with the response and with each other, and the sample size. A search over k and the leaf size is sometimes needed. The number of trees can stay at the default while that search is done.

Out-of-bag estimation and variable importance

Main article: Out-of-bag estimation and variable importance

An observation is absent from a size-n bootstrap sample with probability (1-1/n)^n\approx 0.368. Its out-of-bag prediction therefore uses about 36.8\% of the trees, not most of them. Aggregate only those trees, then compare the prediction with its label. This estimates performance of the specified fitting recipe, with finite-forest and resampling effects. If out-of-bag scores select among recipes, the selected minimum also contains selection optimism. Use a separate assessment of that selection procedure.

The average that lowers the variance also removes the single readable tree. Individual trees can still be inspected, and they were built to disagree, so reading one of them does not describe the forest. A partial substitute ranks the predictors. Count how often each variable is chosen for a split, or how much total impurity reduction it contributes, or how much the error rises when its values are permuted and the forest is applied again. The rank is a summary of predictive contribution inside this fit. It is not a ranking of causal effects, and correlated predictors can share or mask one another’s rank. The same two devices, random subsets of predictors and random subsets of cases, can be wrapped around base learners other than trees. Trees remain the usual choice because they are fast, unstable in the way the diversity term requires, and individually limited enough that no one tree dominates the average.

On a fixed iris training set, the out-of-bag error of a forest falls as trees are added and then levels off, separately for setosa, versicolor, virginica, and the overall rate. A permutation-importance bar on the same fit is largest for the two petal measurements. Those curves are one seeded fit, not a sampling distribution.

Bagging and random forests

Why decorrelating the trees helps

The three free quantities

Out-of-bag estimation and variable importance

Used in

See also