Bagging and Random Forests: Reducing Variance

In our previous lesson, we explored the inner workings of decision trees, focusing on how they recursively partition data to create interpretable, rule-based models. While their transparency is a major strength, we concluded by noting their primary weakness: a tendency to overfit the training data. A single, deep decision tree often has high variance, meaning small perturbations in the training set can lead to a drastically different model structure.

Today, we will address this very problem by introducing ensemble methods, a powerful class of algorithms that combine multiple models to achieve superior performance. Our focus will be on deriving the principle of Bootstrap Aggregating (Bagging) and understanding how its most famous implementation, the Random Forest, leverages this principle to build robust models by reducing the variance of individual trees.

The Core Idea: Reducing Variance by Averaging

Before diving into the algorithm, let's establish the statistical foundation. The high variance of a deep decision tree means that its predictions can be unstable. If we could train many different trees on slightly different datasets drawn from the true underlying data distribution and then average their predictions, the errors of the individual trees would tend to cancel each other out, resulting in a more stable, lower-variance prediction.

This is the central tenet of bagging. The improvement is not just heuristic; it has a firm mathematical basis in the bias-variance decomposition.

Consider a set of $B$ estimators $f_1(x),f_2(x),...,f_B(x)$. If these estimators are independent and identically distributed (i.i.d.) with variance $\text{Var}(f_b(x))={\sigma }^2$, the variance of their average, $\bar{f}(x)=\frac{1}{B}{\sum }_{b=1}^B{f}_b(x)$, is:

By averaging, we reduce the variance by a factor of $B$. However, in machine learning, we cannot easily generate truly independent models because they are all trained on subsets of the same finite dataset. This means our models will be correlated. If we assume each estimator has variance ${\sigma }^2$ and the average pairwise correlation between any two estimators is $\rho$, the variance of the average becomes:

This equation is crucial. It tells us that as we add more estimators ($B\to \infty$), the second term vanishes, but the variance does not go to zero. It is fundamentally limited by the first term, $\rho {\sigma }^2$, which is governed by the correlation between the models. To effectively reduce variance, we must not only average many models but also ensure they are as decorrelated as possible.

Bootstrap Aggregating (Bagging)

The challenge is how to create these multiple models from a single training set. Bagging solves this with a clever statistical technique called bootstrapping. A bootstrap sample is created by drawing data points from the original training set with replacement. This process is repeated $B$ times to create $B$ new datasets, each the same size as the original.

The video "MIT: Machine Learning 6.036, Lecture 12" provides an excellent visual explanation of this process.

The full Bagging algorithm is as follows:

1. Bootstrap: Generate $B$ bootstrap samples from the original training dataset. Due to sampling with replacement, some data points will appear multiple times in a given sample, while others will be absent.
2. Train: Fit a model (e.g., a fully grown, unpruned decision tree) independently on each of the $B$ bootstrap samples.
3. Aggregate: For a new data point, make a prediction with each of the $B$ models.
   • For regression, the final prediction is the average of the $B$ individual predictions.
   • For classification, the final prediction is determined by a majority vote among the $B$ models.

This process is visualized in the "Bagging" diagram below.

From Bagging to Random Forests

While bagging decision trees is effective, it still suffers from one limitation: the trees can be highly correlated. If the dataset has one or a few very strong predictive features, these features will be selected as the top splits in most of the bootstrapped trees. This leads to a high value of $\rho$ in our variance equation, limiting the overall variance reduction.

The Random Forest algorithm, proposed by Leo Breiman, introduces a simple yet brilliant modification to decorrelate the trees.

At each split within each tree, the algorithm randomly selects a subset of $m$ features from the total of $d$ available features ($m<d$). It then finds the best possible split, but only among that random subset of $m$ features.

This deliberate restriction prevents individual trees from all latching onto the same dominant features. By forcing some trees to rely on other, perhaps less powerful predictors, the overall structure of the trees becomes more diverse. This directly reduces the correlation $\rho$ between the trees.

The following reading from the paper "Bootstrap Aggregating and Random Forest" provides the mathematical context for how both bagging and the feature randomization of Random Forests contribute to reducing variance.

A Deeper Theoretical Insight: Can Random Forests Reduce Bias?

The classical and dominant understanding, as we have just established, is that Random Forests improve over single trees primarily through variance reduction. The averaging process does not systematically change the expected prediction, so the bias remains roughly the same as that of an individual tree.

However, more recent theoretical work has challenged this simple narrative. A fascinating paper published in JMLR argues that under certain conditions, the feature randomization in Random Forests can also reduce bias. This occurs on datasets with what the authors call "hidden patterns."

Imagine a scenario where the true data-generating process depends on two features, X1 and X2. X1 has a strong, obvious linear effect on the outcome. X2 has a weaker but highly non-linear effect that is only active in a narrow range of its values. A greedy decision tree (and thus, a Bagging ensemble) will almost always split on X1 first, as it provides the largest immediate reduction in error. By the time the tree is deep enough to consider splitting on X2, the data has been partitioned so much by X1 that the subtle pattern in X2 is obscured and can no longer be learned effectively. The model is therefore biased against finding the true underlying function.

Random Forests, by sometimes forcing a tree to consider a split on X2 early on (when X1 is not in the random subset of features), can uncover this "hidden pattern." This ability to better capture the true data-generating function results in a reduction of model bias.

This insight is a testament to the depth of seemingly simple algorithms and aligns with your goal of building a robust theoretical foundation. While variance reduction remains the primary and most general explanation for the success of Random Forests, understanding their potential for bias reduction offers a more complete picture.

A Practical Advantage: Out-of-Bag Error

The bootstrapping process provides another powerful, "free" benefit: a robust way to estimate the model's generalization error without needing a separate validation set. This is known as the out-of-bag (OOB) error.

For each tree in the forest, about one-third of the original data points were not included in its bootstrap training sample. These are the "out-of-bag" points for that tree. To calculate the OOB error for a single data point $x_i$, we can make a prediction for it using only the trees for which $x_i$ was out-of-bag. The OOB error is the average error over all such predictions across all data points. This provides an unbiased estimate of the test error, which you get for free during the training process.

The following video provides an exceptionally clear explanation of this concept.

Conclusion

In this lesson, we have moved from the high-variance world of single decision trees to the robust and powerful domain of ensemble learning. We derived the core principles of Bagging and Random Forests, grounded in the mathematics of the bias-variance tradeoff.

Here are the essential takeaways:

• The Bagging Principle: Averaging the predictions of multiple models trained on bootstrap samples of the data reduces the variance of the final prediction.
• Variance of Correlated Models: The effectiveness of averaging is limited by the correlation ($\rho$) between the models, as described by the variance formula $\rho {\sigma }^2+\frac{1-\rho }{B}{\sigma }^2$.
• Random Forests' Key Innovation: Random Forests improve upon Bagging by introducing random feature selection at each split. This decorrelates the trees (reduces $\rho$), allowing for a more significant reduction in overall model variance.
• Bias Reduction: While primarily a variance-reduction technique, Random Forests can also reduce bias in scenarios with "hidden patterns" that greedy tree-building might otherwise miss.
• Out-of-Bag Error: Bagging provides a "free" and unbiased estimate of the test error by using the data points left out of each bootstrap sample for validation.

So far, we have focused on an ensemble method that builds models in parallel to reduce variance. In our next lesson, we will explore a fundamentally different ensemble strategy called Boosting. Boosting builds models sequentially, where each new model focuses on correcting the errors of the previous ones. This approach primarily targets reducing bias, offering a complementary strategy to the methods we've learned today.