Bagging and Random Forests

Definition Let a training set hold $n$ rows. A bootstrap sample draws $n$ row indices $I_1, \dots, I_n$ independently and uniformly from $\{1, \dots, n\}$, that is, with replacement, and contains the rows with those indices, repeats included. The number of copies of row $i$ has a binomial distribution with $n$ trials and success probability $1/n$, so it averages $1$, and the probability that row $i$ is missing from the sample is

which increases with $n$ toward $e^{-1} \approx 0.368$. On average a sample therefore contains the fraction $1 - (1 - 1/n)^n$ of the distinct rows, about $0.632$ for large $n$. These probabilities come from the index draws alone, whatever the rows contain. A bootstrap sample reuses the same data with random multiplicities and is not new data. In bagging it is part of how the model is trained, which is a different job from the bootstrap in Bootstrap Uncertainty and Model Comparisons, where resampling measures how much a statistic varies.

Definition Bagging, short for bootstrap aggregating, takes a learning procedure, a training set and a number $B \ge 1$ of models. It draws $B$ independent bootstrap samples, fits the procedure to each one, counting a repeated row as many times as it appears, and combines the fitted models $\hat{f}_1, \dots, \hat{f}_B$. For regression the combination is the average

For classification it is either a majority vote of the predicted classes, with a rule for ties, or an average of the estimated class probabilities followed by choosing the most probable class, and the two can disagree. In regression the $B$ fits have the same distribution, so their average has the same expected prediction as a single bootstrap fit and never a larger variance. Bagging works on variance, not on bias. It helps most for unstable procedures such as deep trees, whose fits change a lot when a few rows change, and it changes little for stable procedures.

Definition A random forest is bagging applied to decision trees with one more source of randomness, random feature subsets. Each tree is fitted to its own bootstrap sample, and at every node, before the split search, a random subset of $m_{\text{try}}$ of the $p$ features is drawn without replacement, independently of all other nodes and trees. The best split is searched only among the features in that subset. The size $m_{\text{try}}$ is a hyperparameter with $1 \le m_{\text{try}} \le p$, and $m_{\text{try}} = p$ gives plain bagged trees. Common defaults are about $\sqrt{p}$ for classification, while libraries differ for regression, some using about $p/3$ and some all $p$ features, so it is worth tuning on validation data. The trees are usually grown deep and left unpruned, and their predictions are combined as in bagging.

Definition Fix an input $\mathbf{x}$, and let $T_1, \dots, T_B$ be the predictions of $B$ trees at $\mathbf{x}$, random through the training sample and through the random draws of the algorithm. Assume each $T_b$ has variance $\sigma^2$ and every pair of distinct trees has correlation $\rho$. The variance of the average $\bar{T}$ is the sum of the $B$ variances $\sigma^2$ and the $B(B - 1)$ covariances $\rho\sigma^2$, divided by $B^2$, which gives

These variances and covariances are possible only when $\rho \ge -1/(B - 1)$. If $\rho > 0$, the variance falls as $B$ grows but never below the floor $\rho\sigma^2$. If $\rho = 1$, averaging does not help at all, and if $\rho = 0$, the variance is $\sigma^2/B$. This is a model with equal variances and equal correlations, a way to see what correlation does, and not a measured property of a fitted forest. Averaging identically distributed predictions does not change their mean, so whatever bias the trees have, the average keeps.

Definition For a fixed input $\mathbf{x}$ and two distinct trees $b \ne b'$ of an ensemble, with predictions $T_b$ and $T_{b'}$ at $\mathbf{x}$, the correlation between trees is

taken over the randomness of the training sample and of the bootstrap and feature draws. It concerns the predictions of different trees at the same input, not the correlation between features. It is usually positive, because every tree is fitted to the same training set and strong features tend to win the same splits. A smaller $m_{\text{try}}$ usually lowers $\rho(\mathbf{x})$, but it can raise the variance $\sigma^2(\mathbf{x})$ and the bias of each tree, because the trees must often split on weaker features. Lower correlation therefore lowers the ensemble variance only when it is not outweighed by worse trees, and when most features are noise a small $m_{\text{try}}$ can hurt. Within one fitted forest the trees share the training set, so the spread of their predictions at one input shows only the variation that comes from the random draws, and it cannot reveal $\rho(\mathbf{x})$ by itself.

Definition In a bagged ensemble or random forest with $B$ trees, row $i$ of the training set is out of bag for tree $b$ when it is missing from that tree’s bootstrap sample. Let $O_i$ be the set of such trees. When $O_i$ is not empty, the out-of-bag prediction for row $i$ combines only the trees in $O_i$, and the out-of-bag error is the average loss of these predictions over the rows that have one, reported together with how many rows that is. Because the samples are independent, a row has no out-of-bag prediction with probability $\bigl(1 - (1 - 1/n)^n\bigr)^B$, which shrinks quickly as $B$ grows, and with many trees each out-of-bag prediction uses about $37$ percent of them. When the rows are independent draws from the population the model will serve, and no preprocessing step such as imputation or feature selection was fitted using all the rows, the out-of-bag error estimates the error on new rows without a separate validation set. It is not valid when rows come in related groups, such as several rows from one customer, since trees that saw the customer’s other rows predict the omitted one too easily, or when the rows are ordered in time and the model must predict the future. Once the out-of-bag error has been used to choose settings such as depth or $m_{\text{try}}$, it is selection evidence and no longer an independent final test.