Decision trees possess high expressive power and zero bias in the limit, but suffer from an acute Achilles’ heel: extreme instability. A tiny perturbation in the training dataset can cascade down the root split, completely reconfiguring the entire downstream tree architecture. In 1996 and 2001, Leo Breiman harnessed the power of statistical averaging to convert this instability into an asset, inventing Bootstrap Aggregation (Bagging) and Random Forests—the definitive gold standard of non-linear tabular machine learning.
1. The Variance of an Averaged Ensemble
Consider an ensemble of $B$ estimators $hat{f}_1(x), dots, hat{f}_B(x)$, each having variance $sigma^2$ and positive pairwise correlation $rho = text{Corr}(hat{f}_j, hat{f}_k)$ for $j ne k$. The variance of the simple ensemble average $bar{f}(x) = frac{1}{B} sum_{b=1}^B hat{f}_b(x)$ evaluates analytically as:
$$text{Var}(bar{f}(x)) = text{Var}left( frac{1}{B} sum_{b=1}^B hat{f}_b(x) right) = frac{1}{B^2} left[ sum_{b=1}^B text{Var}(hat{f}_b) + sum_{j ne k} text{Cov}(hat{f}_j, hat{f}_k) right]$$
$$text{Var}(bar{f}(x)) = frac{1}{B^2} left[ B sigma^2 + B(B – 1) rho sigma^2 right] = rho sigma^2 + frac{1 – rho}{B} sigma^2$$
Examining the asymptotic limit as ensemble size $B to infty$:
$$lim_{B to infty} text{Var}(bar{f}(x)) = rho sigma^2$$
This equation exposes the fundamental mechanics of ensemble learning:
- The second term $frac{1 – rho}{B} sigma^2$ decays to zero simply by training more trees.
- However, the ensemble cannot reduce variance below the asymptotic floor $rho sigma^2$. If trees are identical ($rho = 1$), averaging yields zero variance reduction!
To maximize variance reduction, an algorithm must ruthlessly drive pairwise correlation $rho to 0$ without degrading individual tree accuracy.
2. Bootstrap Aggregation (Bagging)
To train $B$ different trees from a single dataset $S$ of size $n$, Breiman leveraged Bradley Efron’s 1979 Bootstrap: drawing $n$ samples uniformly at random with replacement from $S$.
For large $n$, the probability that a specific observation $x_i$ is not selected in a bootstrap sample of size $n$ is:
$$lim_{n to infty} left( 1 – frac{1}{n} right)^n = frac{1}{e} approx 0.368$$
Thus, each bootstrap dataset contains approximately $63.2%$ unique original training points, leaving $36.8%$ of the dataset unused. These unused samples are the Out-of-Bag (OOB) data. OOB samples act as a built-in cross-validation set: evaluating each training point exclusively on the subset of trees that never saw it produces an unbiased generalization estimate without requiring separate validation splits!
3. Random Forests: Breaking the Correlation Floor
While Bagging reduces variance, standard bagged trees remain substantially correlated ($rho approx 0.6$). If the dataset contains one overwhelmingly strong feature (e.g., income in credit risk), virtually every bagged tree will select that feature at the root node, producing structurally similar splits.
In 2001, Breiman introduced Random Forests, introducing an additional layer of stochasticity: Random Feature Subsampling. At every single split in every tree:
- Instead of searching across all $p$ features, the algorithm randomly samples a small subset of $m approx sqrt{p}$ features (for classification) or $m approx p/3$ (for regression).
- The split is selected exclusively from among this random subset of candidates.
By preventing dominant features from monopolizing root nodes, feature bagging forces individual trees to explore alternative predictive mechanisms, dramatically depressing pairwise correlation $rho$ (often from $0.6$ down to $0.1$). Because individual trees are grown deep without pruning (preserving low bias), the forest achieves monumental variance reduction without inflating bias.
4. Mathematical Properties of the Forest Horizon
Random Forests possess exceptional theoretical properties:
- Immunity to Overfitting via Scale: Adding more trees $B$ cannot cause overfitting! As $B to infty$, the Strong Law of Large Numbers guarantees that the forest error converges almost surely to an asymptotic limit:
$$lim_{B to infty} text{PE}^*_{text{forest}} = mathbb{P}_{X, Y}left( mathbb{P}_Theta(h(X, Theta) = Y) – max_{j ne Y} mathbb{P}_Theta(h(X, Theta) = j) < 0 right)$$
- Adaptive Nearest Neighbors: Lin and Jeon (2006) proved that Random Forests can be viewed as an adaptive nearest neighbor algorithm where the effective metric warps dynamically based on feature importance.
By synthesizing bootstrap resampling with stochastic feature projections, Random Forests formalized the principle that a collection of uncorrelated, high-variance weak estimators can unite into an unassailable predictor.
