Random Forests

A single unpruned decision tree possesses low bias but notoriously high variance ($\text{Var}(T(\mathbf{x})) = \sigma^2$). Because greedy splitting algorithms recursively partition feature space until terminal leaf nodes achieve near-zero impurity, the resulting decision boundary draws narrow axis-aligned stair-steps around noisy outliers. While training error drops to zero, held-out test error surges to $0.33$ as new query points fall into isolated overfitted islands.

Trees That Disagree

To tame single-tree variance, Breiman's bagging procedure draws $B$ bootstrap samples of size $N$ from the original training dataset with replacement. Mathematically, the probability that any individual observation is excluded from a single bootstrap draw approaches $\lim_{N \to \infty} (1 - 1/N)^N = 1/e \approx 0.368$. Approximately $63.2\%$ of unique rows appear in-bag (with duplicate copies), while the remaining $36.8\%$ form an Out-Of-Bag (OOB) partition that serves as an internal validation benchmark without requiring a held-out test split.

Votes Fix Errors

When classifying a new query vector $\mathbf{x}^*$, the ensemble collects individual predictions across all $B$ trees and takes the plurality vote:

$\hat{C}_{\text{RF}}(\mathbf{x}^*) = \arg\max_{k} \sum_{b=1}^B \mathbb{I}(\hat{C}_b(\mathbf{x}^*) = k)$

If Tree 3 memorized a noisy training artifact and casts a rogue vote for Class 0, independent peer trees evaluating the same instance vote for Class 1. By a 3-to-2 majority tally, the ensemble suppresses the localized error and preserves correct global classification.

Hide Some Features

Bootstrap aggregation alone fails when one dominant predictor exists: every tree greedily places that dominant feature at its root split, producing strongly correlated trees ($\rho \approx 0.95$). Random Forests overcome this correlation bottleneck by forcing each split candidate to consider only a random feature subspace of size $m \approx \lfloor \sqrt{p} \rfloor$ (e.g., $m=2$ out of $p=5$). Masking the dominant feature forces alternative trees to split on secondary attributes ($x_2, x_4, x_5$), decorrelating the ensemble down to $\rho \approx 0.25$.

Error Falls Together

The variance of an average of $B$ identically distributed random estimators with pairwise correlation $\rho$ and individual variance $\sigma^2$ obeys:

$\text{Var}(\bar{T}) = \rho \sigma^2 + \frac{1 - \rho}{B}\sigma^2$

As $B \to \infty$, the sample variance term $\frac{1-\rho}{B}\sigma^2$ vanishes, driving overall variance down to the irreducible correlation floor $\rho \sigma^2$. Averaging 200 decorrelated trees replaces jagged axis-aligned steps with a smooth continuous probability contour, cutting test classification error from $0.33$ to $0.08$ (a $76\%$ variance reduction).

Grow Enough Trees

Tracking Out-Of-Bag (OOB) generalization error against ensemble size $B$ demonstrates steep initial returns: error drops precipitously from $0.33$ at $B=1$ down to $0.13$ at $B=50$ and reaches an elbow near $B=200$ with an OOB error floor of $0.080$. Unlike gradient boosting or deep neural networks, Random Forests do not overfit as $B \to \infty$; the error curve plateaus asymptotically. Growing beyond $200$ trees burns CPU cycles with negligible statistical dividend ($\Delta < 0.001$).

Where It Breaks

The Random Forest architecture encounters two fundamental theoretical limitations:

1. Feature Redundancy and Correlation Collapse: If predictors are heavily confounded or multi-collinear, trees cannot decorrelate ($\rho \to 1$). When every tree constructs identical flawed partitions, they vote unanimously for the wrong label ($4\text{–}0$), completely defeating the variance-reduction benefits of voting.
2. Inability to Extrapolate: Because decision trees assign constant leaf values, an ensemble cannot forecast trends outside the bounding box of observed training data ($[x_{\min}, x_{\max}]$). Queries in outer domains receive flat, clipped constant predictions rather than tracking genuine physical trends.

The Quick Version

• Single tree dilemma: Deep trees achieve zero training error but suffer high variance ($0.33$ test error) through outlier memorization.
• Bootstrap sampling: Drawing with replacement reserves roughly $36.8\%$ of data as out-of-bag validation rows while ensuring training diversity.
• Majority voting: Combining individual votes suppresses rogue errors whenever the majority of independent trees holds the correct consensus.
• Random feature subspaces: Selecting $m \approx \sqrt{p}$ features per split prevents strong variables from creating identical, correlated trees.
• Variance formula: Averaging $B$ trees eliminates the $\frac{1-\rho}{B}\sigma^2$ term, cutting error to the correlation floor $\rho \sigma^2$ ($0.08$).
• Sizing $B$: Out-of-bag error plateaus near $B=200$; adding further trees costs compute without risking overfitting.
• Failure boundaries: High feature correlation ($\rho \to 1$) destroys voting diversity, and step-constant leaves cannot extrapolate beyond training extremes.