Bagging & Random Forests

Table of Contents

1. Learning Objectives
2. Notation
3. Core Intuition
4. Bootstrap Aggregation (Bagging)
5. Variance Reduction Analysis
6. Random Forests: Decorrelation via Feature Subsampling
7. Out-of-Bag Error Estimation
8. Feature Importance
9. Theoretical Guarantees
10. Common Pitfalls
11. Summary
12. Exercises

Learning Objectives

1. Derive why averaging reduces variance but not bias.
2. Explain the bootstrap and its role in generating diverse base learners.
3. Derive the variance of bagged estimators in terms of pairwise correlation.
4. Explain how random feature subsampling reduces correlation between trees.
5. Derive the out-of-bag error and its relationship to leave-one-out cross-validation.

Notation

• $B$ — number of bootstrap samples (trees)
• $\hat{f}_b(\mathbf{x})$ — prediction of $b$-th tree
• $\hat{f}_{\text{bag}}(\mathbf{x}) = \frac{1}{B}\sum_{b=1}^B \hat{f}_b(\mathbf{x})$ — bagged prediction
• $\rho$ — average pairwise correlation between tree predictions
• $m$ — number of features randomly selected at each split ($m \leq d$)

Core Intuition

Decision trees are high-variance estimators: small data perturbations lead to very different trees. If we could train many trees on independent datasets and average them, variance would decrease by a factor of $1/B$. Since we only have one dataset, we approximate independent datasets via bootstrap resampling. Random forests add feature subsampling at each split to further decorrelate trees, dramatically improving the variance reduction.

Bootstrap Aggregation (Bagging)

Algorithm:

1. For $b = 1, \ldots, B$:
   • Draw a bootstrap sample $\mathcal{D}_b$ of size $n$ with replacement from $\mathcal{D}$.
   • Fit a decision tree $\hat{f}_b$ on $\mathcal{D}_b$ (no pruning — grow to full depth).
2. Predict: $\hat{f}_{\text{bag}}(\mathbf{x}) = \frac{1}{B}\sum_{b=1}^B \hat{f}_b(\mathbf{x})$ (regression) or majority vote (classification).

Variance Reduction Analysis

Let each tree have variance $\sigma^2$ and pairwise correlation $\rho$. The variance of the average of $B$ correlated estimators:

Derivation. Expand:

As $B \to \infty$: $\text{Var} \to \rho\sigma^2$. The irreducible floor is determined by correlation $\rho$.

Random Forests: Decorrelation via Feature Subsampling

Key modification: At each split, only consider a random subset of $m$ features (out of $d$). This reduces $\rho$ without increasing individual tree variance much.

Typical choices:

• Classification: $m = \lfloor\sqrt{d}\rfloor$
• Regression: $m = \lfloor d/3\rfloor$

Effect: If a few features are very strong, bagged trees will all split on them first → high correlation. Random subsampling forces trees to find different structures → lower $\rho$ → lower ensemble variance.

Out-of-Bag Error Estimation

Each bootstrap sample includes approximately $1 - (1-1/n)^n \approx 1 - 1/e \approx 63.2\%$ of the original data. The remaining $\sim 36.8\%$ form the out-of-bag (OOB) set for that tree.

OOB prediction for $x_i$: Average predictions from all trees whose bootstrap sample did not include $x_i$:

OOB error $= \frac{1}{n}\sum_i\ell(\hat{f}_{\text{OOB}}(\mathbf{x}_i), y_i)$.

This provides an unbiased estimate of test error without requiring a held-out set (equivalent to leave-one-out CV asymptotically).

Feature Importance

Permutation importance: For feature $j$, randomly permute values of $x_j$ in the OOB data and measure increase in OOB error:

Gini importance: Sum of impurity reductions across all splits on feature $j$ across all trees.

Theoretical Guarantees

Theorem (Breiman, 2001). The generalization error of a random forest satisfies:

where $s$ is the strength (margin) of individual trees and $\bar{\rho}$ is mean correlation. Low correlation and high individual strength guarantee low error.

Common Pitfalls

Pitfall 1. Using too few trees. The OOB error stabilizes around $B = 500$–$1000$; there is no overfitting from increasing $B$ (variance monotonically decreases).

Pitfall 2. Expecting random forests to extrapolate. Trees partition the observed feature space; predictions outside the training range default to the nearest leaf value.

Pitfall 3. Interpreting Gini importance as causal. Correlated features share importance; permutation importance on OOB data is more reliable.

Summary

• Bagging reduces variance by averaging bootstrap-trained trees.
• Ensemble variance = $\rho\sigma^2 + (1-\rho)\sigma^2/B$; the floor is set by inter-tree correlation.
• Random forests reduce $\rho$ via random feature subsampling at each split.
• OOB error provides a free estimate of generalization without a separate test set.
• More trees never hurts (no overfitting from larger $B$).

Exercises

Exercise 1. Derive equation (2) for the variance of the average of $B$ correlated estimators.

Exercise 2. Show that the probability of a sample being OOB for a given tree converges to $1/e$ as $n \to \infty$.

Exercise 3. For a 1D regression problem where the true function is linear, show that a single decision tree has high variance but averaging many trees reduces this.

Exercise 4. Prove that the bagged predictor has the same bias as a single tree (bias is unchanged by averaging).

Exercise 5. Design an example where reducing $m$ from $d$ to $\sqrt{d}$ dramatically reduces ensemble variance.