Random Forests

In the previous module, we explored Bagging—the technique of training multiple models on bootstrap samples and aggregating their predictions to reduce variance. Bagging is powerful, but it has a subtle limitation: when the training data contains strongly predictive features, every tree in the ensemble tends to use those features at the top splits, making the trees structurally similar and their errors correlated.

The Random Subspace Method (RSM), also known as attribute bagging or feature bagging, provides an elegant solution. Instead of giving each learner access to all features, we randomly restrict each learner to a subset of the available features. This simple modification has profound consequences for ensemble diversity and predictive power.

To appreciate the random subspace method, we must first understand why pure bagging sometimes falls short. Consider a dataset with 100 features where 3 features are exceptionally predictive. When we build a bagged ensemble of decision trees:

1. Every tree examines all 100 features at each split
2. The same 3 dominant features consistently appear at the root and upper levels
3. Tree structures become highly similar despite different bootstrap samples
4. Prediction errors correlate because similar structures make similar mistakes

This phenomenon is sometimes called tree correlation or feature dominance, and it limits the variance reduction that bagging can achieve.

A Concrete Example:

Imagine predicting house prices with features including square_footage, location_score, num_bedrooms, and 97 other features. If square_footage and location_score alone explain 80% of variance:

• Every bagged tree will split on square_footage or location_score at the root
• The top structure of each tree looks nearly identical
• Bootstrap sampling only introduces variety through which data points appear
• The ensemble's "wisdom of crowds" benefit is severely limited

The random subspace method breaks this pattern by ensuring that some trees cannot use the dominant features, forcing them to find alternative predictive patterns.

The Random Subspace Method (RSM), introduced by Tin Kam Ho in 1998, constructs ensemble members by training each base learner on a randomly selected subset of the original feature space. The algorithm is remarkably simple:

Key Algorithmic Properties:

The classic random subspace method does not use bootstrap sampling—it randomizes features while using all training samples. Random Forests combine both bootstrap sampling (bagging) and feature subspace sampling, getting the benefits of both techniques.

The random subspace method can be understood through the lens of projection onto random subspaces of the original feature space. Let's formalize this mathematically.

Notation:

• Original feature space: $\mathbb{R}^p$ with $p$ features
• Subspace dimension: $m$ where $1 \leq m < p$
• Training data: $\mathbf{X} \in \mathbb{R}^{n \times p}$
• Feature selection: $S_t \subset {1, 2, \ldots, p}$ with $|S_t| = m$ for tree $t$

The Projection Operation:

For each ensemble member $t$, we define a projection matrix $\mathbf{P}_t \in \mathbb{R}^{m \times p}$ that selects the features in $S_t$. If $S_t = {j_1, j_2, \ldots, j_m}$, then:

$$\mathbf{P}t = \begin{bmatrix} \mathbf{e}{j_1}^T \ \mathbf{e}{j_2}^T \ \vdots \ \mathbf{e}{j_m}^T \end{bmatrix}$$

where $\mathbf{e}_j$ is the standard basis vector with 1 in position $j$ and 0 elsewhere.

The projected training data for learner $t$ is: $$\mathbf{X}_t = \mathbf{X} \mathbf{P}_t^T \in \mathbb{R}^{n \times m}$$

Diversity Through Random Projections:

The probability that two ensemble members share the exact same feature set is:

$$P(S_i = S_j) = \frac{1}{\binom{p}{m}}$$

For $p = 100$ and $m = 10$, this probability is approximately $5.9 \times 10^{-14}$—essentially zero. Even partial overlap has low probability:

$$P(|S_i \cap S_j| = k) = \frac{\binom{m}{k} \binom{p-m}{m-k}}{\binom{p}{m}}$$

This combinatorial analysis shows that random subspace selection naturally generates highly diverse feature sets, which translates to diverse decision boundaries and decorrelated predictions.

Expected Overlap Between Subspaces:

The expected number of shared features between two randomly selected subspaces is:

$$\mathbb{E}[|S_i \cap S_j|] = \frac{m^2}{p}$$

For example, with $p = 100$ features and $m = 10$ features per learner:

• Expected overlap: $\frac{100}{100} = 1$ feature
• Each pair of learners typically shares only 1 feature out of 10

This low expected overlap is the source of prediction diversity. With $m = \sqrt{p}$ (a common choice), the expected overlap is:

$$\mathbb{E}[|S_i \cap S_j|] = \frac{p}{p} = 1$$

Again, just one feature despite each learner having $\sqrt{p}$ features.

The subspace dimension $m$ is a critical hyperparameter that controls the bias-variance-diversity tradeoff:

Common Rules of Thumb:

The Bias-Variance-Diversity Tradeoff:

Let's denote:

• $\text{Bias}_m$ = bias of individual learners using $m$ features
• $\text{Var}_m$ = variance of individual learners
• $\rho_m$ = average correlation between learner predictions

As $m$ increases:

• $\text{Bias}_m$ decreases (more features → better individual fit)
• $\text{Var}_m$ increases (more features → higher variance)
• $\rho_m$ increases (more feature overlap → more correlated predictions)

The ensemble variance with $T$ learners is approximately:

$$\text{Var}_{\text{ensemble}} \approx \rho_m \cdot \text{Var}_m + \frac{1-\rho_m}{T} \cdot \text{Var}_m$$

The optimal $m$ balances these competing effects. Smaller $m$ increases individual bias but decreases $\rho_m$, allowing greater variance reduction through averaging. The $\sqrt{p}$ rule empirically balances these factors well for many classification tasks.

While both RSM and Bagging are ensemble diversification strategies, they operate on different axes:

The Key Insight: Combining Both

Random Forests achieve superior performance by combining both strategies:

1. Bootstrap Sampling (from Bagging): Creates diverse training sets
2. Feature Subspace Sampling (from RSM): Creates diverse feature views

This dual randomization multiplicatively increases diversity. Even if two trees receive similar bootstrap samples, they're forced to build different structures due to different feature access. Even if two trees have overlapping features, they see different data points.

The random subspace method has a beautiful geometric interpretation. Consider data in $\mathbb{R}^3$ projected onto different 2D planes:

• Projection 1 (features 1,2): Sees data from the "front view"
• Projection 2 (features 1,3): Sees data from the "top view"
• Projection 3 (features 2,3): Sees data from the "side view"

Each 2D classifier finds a decision boundary that works well in its projected view. Some class separations are clearly visible in one projection but hidden in another. By aggregating classifiers from multiple projections, the ensemble captures separations that no single projection fully reveals.

The Blessing of Dimensionality (Sometimes):

While high dimensionality typically causes problems (the "curse of dimensionality"), the random subspace method can turn high dimensionality into an advantage:

• More subspaces available: With $p = 1000$ features, there are $\binom{1000}{10} \approx 2.6 \times 10^{23}$ possible 10-dimensional subspaces
• High probability of diverse views: Nearly every ensemble member sees genuinely different data projections
• Robust feature discovery: Different subspaces may reveal different aspects of the underlying pattern

This is why Random Forests work remarkably well on high-dimensional data like genomics (thousands of genes) or text analysis (thousands of words)—there's an exponentially large space of diverse projections to sample from.

The Random Forest algorithm, introduced by Leo Breiman in 2001, extends the random subspace method in three key ways:

1. Feature Randomization at Every Split (Not Just Per Tree)

Classic RSM selects $m$ features once per tree, then builds the tree using only those features. Random Forests re-randomize feature selection at every internal node:

• At each split decision, sample $m_{try}$ features from the full set
• Find the best split among only those $m_{try}$ candidates
• Repeat at the next node with a fresh random sample

This per-split randomization creates far more diversity than per-tree randomization.

2. Combined with Bootstrap Sampling

Random Forests apply bagging in addition to feature randomization:

3. Typically Unpruned Trees

Unlike traditional decision trees (which risk overfitting), Random Forest trees are typically grown to maximum depth:

• Each tree overfits to its bootstrap sample + feature subset
• The overfitting is in different directions for different trees
• Aggregation averages out the individual overfitting

We've explored the random subspace method—a foundational technique that transforms ensemble learning by introducing feature-level diversity.

What's Next:

Now that we understand the random subspace method, the next page dives deeper into feature randomization in Random Forests—examining exactly how per-split sampling works, why $m_{try} = \sqrt{p}$ is recommended, and what happens when we vary this parameter.