Ensemble Methods
1 Introduction
Throughout this text, we have encountered a fundamental tension in machine learning related to the tradeoff between bias and variance. Models with high capacity can fit complex patterns in the training data, but they are also prone to memorizing noise and idiosyncrasies, resulting in poor generalization to new data. On the other hand, models that are too simple may fail to capture important patterns in the data, resulting in high bias—the model’s predictions are systematically wrong. This tradeoff is highlighted in Idea #2 from the introduction.
Ensemble methods provide an elegant approach to navigating this tradeoff. The core idea is that “many heads are better than one”: why not have multiple models “vote” on the prediction? By combining multiple models, ensemble methods can achieve better performance than any individual model in the ensemble. The key insight is that different models tend to make different mistakes, and by aggregating their predictions, we can reduce the impact of any individual model’s errors. This principle is at the heart of ensemble learning and has been instrumental in many practical machine learning successes.
In this chapter, we explore one of the most fundamental ensemble techniques: bootstrap aggregation, commonly known as bagging. We will develop the theoretical foundation for why bagging works, examining its effect on the bias-variance decomposition.
One of the most successful applications of bagging is in decision trees. Thus, we will also study the random forest. Random forest is one of the most widely used machine learning algorithms.
2 The Intuition Behind Bagging
Recall from the bias-variance decomposition that a model’s expected error decomposes into squared bias, variance, and irreducible Bayes error. High-variance models (like deep decision trees and polynomial regressors with high degrees) are highly sensitive to the particular training data they see. Resampling of the training set leads to large changes in predictions, causing the model to overfit to training data idiosyncrasies.
High-variance polynomial predictor
As you can see from Figure 1, for a high-variance model, although each model (trained on a different training set) has predictions that vary significantly from each other, the average of their predictions tends to be close to the “best” possible prediction.
Thus, the core idea behind ensemble methods is to train several different high-variance models, and combine their predictions together: e.g., by averaging the predictions (in a regression problem) or having the models “vote” on the prediction (in a classification problem).
To understand why this might work, consider a thought experiment. Keeping with the theme from the bias-variance section, we will continue to use a regression setting. Suppose we could somehow sample many independent training datasets from the true data distribution. We could train a separate model on each dataset and then, when making a prediction on a test example, we could average the predictions of all these models. Intuitively, this averaging should help: if some models predict too high and others predict too low, the average should be closer to the true value than any individual prediction.
Ensemble averaging
3 The Mathematics of Model Averaging
Intuitively, averaging models trained from multiple datasets should be “better”, i.e., it should reduce expected error. We can verify this intuition theoretically by analyzing how averaging predictions affects the bias, variance, and Bayes error compared to using a single model trained on one training set. As shown in the figure above, suppose we have \(M\) independent training datasets \(\mathcal{D}_1, \mathcal{D}_2, \ldots, \mathcal{D}_M\), and we train a model on each one using the same learning algorithm \(\mathcal{A}\) (red arrow above). Let \(f_m(\mathbf{x})\) be the prediction from the \(m\)-th model at input \(\mathbf{x}\). We average these predictions to get the ensemble prediction \(f_{\text{ens}}(\mathbf{x}) = \frac{1}{M} \sum_{m=1}^M f_m(\mathbf{x})\).
Here, we use \(\mathcal{D}\) to denote a generic training dataset drawn from the data distribution \(p_\mathcal{D}\). We will use the notation \(\mathbb{E}_\mathcal{D}\) to mean expectation over all possible training datasets (i.e., \(\mathbb{E}_{\mathcal{D}_1,\mathcal{D}_2,\dots}\))
What happens to the bias, variance, and Bayes error of \(f_{\text{ens}}(\mathbf{x})\) compared to any individual \(f_m(\mathbf{x})\)?
First, the Bayes error remains unchanged. This is because the Bayes error \(\mathbb{E}_{\mathbf{x},t}[(\bar{y}(\mathbf{x}) - t)^2]\) is a property of the data generating distribution itself, measuring the inherent noise in the problem.
Second, the bias also remains unchanged. That is, \[\begin{align*} \mathbb{E}_{\mathbf{x}}\!\left[ \big(\bar{f}(\mathbf{x}) - \bar{y}(\mathbf{x})\big)^2\right] = \mathbb{E}_{\mathbf{x}}\!\left[ \big(\bar{f}_{\text{ens}}(\mathbf{x}) - \bar{y}(\mathbf{x})\big)^2\right], \end{align*}\] where \(\bar{f}_{\text{ens}}(\mathbf{x}) = \mathbb{E}_\mathcal{D}[f_{\text{ens}}(\mathbf{x})]\) is the expected ensemble predictor (taking expectation over all \(M\) training datasets). To show this equality, we can show that \(\bar{f}_{\text{ens}}(\mathbf{x}) = \bar{f}(\mathbf{x})\) for all \(\mathbf{x}\). Recall that \(\bar{f}(\mathbf{x}) = \mathbb{E}_\mathcal{D}[f_\mathcal{D}(\mathbf{x})]\) where \(f_\mathcal{D}\) is a model trained on training dataset \(\mathcal{D}\) using algorithm \(\mathcal{A}\), and \(\bar{y}(\mathbf{x}) = \mathbb{E}_t[t \mid \mathbf{x}]\) is the optimal predictor that minimizes the expected loss. To see that \(\bar{f}_{\text{ens}}(\mathbf{x}) = \bar{f}(\mathbf{x})\), consider the expected ensemble predictor for a fixed test input \(\mathbf{x}\). Taking expectation over the training datasets: \[\begin{align*} \bar{f}_{\text{ens}}(\mathbf{x}) = \mathbb{E}_\mathcal{D}[f_{\text{ens}}(\mathbf{x})] &= \mathbb{E}_\mathcal{D} \left[ \frac{1}{M} \sum_{m=1}^M f_m(\mathbf{x}) \right] \\ &= \frac{1}{M} \sum_{m=1}^M \mathbb{E}_\mathcal{D}[f_m(\mathbf{x})] \\ &= \mathbb{E}_\mathcal{D}[f_\mathcal{D}(\mathbf{x})] \\ &= \bar{f}(\mathbf{x}). \end{align*}\] Since this holds for all \(\mathbf{x}\), we have \(\bar{f}_{\text{ens}}(\mathbf{x}) = \bar{f}(\mathbf{x})\) for all \(\mathbf{x}\), so the bias is unchanged.
The variance, however, is reduced. When we average over \(M\) independent random variables, the variance of the average is \(\frac{1}{M}\) times the variance of any individual variable. More precisely, for a fixed test input \(\mathbf{x}\):
\[\begin{align*} \mathbb{E}_\mathcal{D}\left[ \left(f_{\text{ens}}(\mathbf{x}) - \bar{f}(\mathbf{x})\right)^2 \right] &= \mathbb{E}_\mathcal{D}\left[ \left(\frac{1}{M} \sum_{m=1}^M f_m(\mathbf{x}) - \bar{f}(\mathbf{x})\right)^2 \right] \\ &= \frac{1}{M^2} \sum_{m=1}^M \mathbb{E}_\mathcal{D}\left[ \left(f_m(\mathbf{x}) - \bar{f}(\mathbf{x})\right)^2 \right] \\ &= \frac{1}{M} \mathbb{E}_\mathcal{D}\left[ \left(f_\mathcal{D}(\mathbf{x}) - \bar{f}(\mathbf{x})\right)^2 \right] \end{align*}\]
where the second equality holds because the different training datasets are independent and identically distributed. Taking the expectation over \(\mathbf{x}\) as well, we find that the variance component of the expected test error is reduced by a factor of \(M\).
This is a remarkable result: by averaging the predictions of multiple models trained on independent datasets, we can reduce the variance component of the expected test error by a factor of \(M\), the number of models, without affecting other sources of error.
Unfortunately, in practice, we have only a single finite training set. Drawing many independent training sets from the true data distribution would require repeating expensive data collection processes. Moreover, training multiple models on multiple independent datasets would be extremely wasteful of data. Why train separate models when we could train a single model on the union of all \(M\) datasets?
4 Bootstrap Aggregation
The bootstrap provides an elegant solution to this problem. Instead of drawing new training datasets from the true distribution, we draw them from the empirical distribution defined by our training data. That is, we take our single training set with \(n\) examples and create \(M\) new datasets, each of size \(n\), by sampling with replacement from the original training set. This process is called bootstrap sampling, and the resulting ensemble method is called bootstrap aggregation, or bagging for short.
Definition: Bootstrap aggregation, or bagging, is an ensemble method that trains multiple models on bootstrap samples \(\mathcal{D}_m\) (random samples with replacement) of the training data \(\mathcal{D}\) and combines their predictions by averaging (for regression) or majority voting (for classification).
This strategy is justified because as the size of the training set grows, the empirical distribution converges to the true distribution. In the limit as \(n \to \infty\), sampling from the empirical distribution is equivalent to sampling from the true distribution. In practice, with finite datasets, bootstrap sampling provides a reasonable approximation.
The procedure for bagging is straightforward. Given a training set \(\mathcal{D}\) with \(n\) examples, we generate \(M\) bootstrap samples. Each bootstrap sample \(\mathcal{D}_m\) is created by randomly selecting \(n\) examples from \(\mathcal{D}\) with replacement. Because we sample with replacement, some examples from \(\mathcal{D}\) appear multiple times in a bootstrap sample, while others do not appear at all—and that’s okay!
Bootstrap sampling
As before, we then train \(M\) models, one on each bootstrap sample. Also as before, when making a prediction on a new test example, we combine the predictions from all \(M\) models. For regression problems, we simply average the predictions. For classification problems, we can either average the predicted probabilities and then threshold, or we can take a majority vote.
The goal of bagging is to reduce variance without increasing bias, while being data efficient. Thus, each individual model in the ensemble may have high variance, but by averaging their predictions, we smooth out the variance. This is somewhat analogous to the wisdom of crowds: even if individual opinions are noisy, the average opinion is often more reliable.
Definition: A learning method is data efficient if it can make effective use of available training data without requiring additional data collection. A data-efficient method extracts more useful information from the same amount of training data, effectively increasing the information content we can learn from the training examples.
5 The Effect of Correlation
In practice, the variance reduction achieved by bagging is not as dramatic as the idealized theory suggests. The reason is that the bootstrap samples are not truly independent. They are all drawn from the same finite training set, and they overlap substantially. This overlap induces correlation between the models in the ensemble.
To understand why this matters, we need to examine where the independence assumption was used in the idealized variance calculation. When we expand the squared error and take expectations, we get:
\[\begin{align*} &\quad\mathbb{E}_\mathcal{D}\left[ \left(\sum_{m=1}^M (f_m(\mathbf{x}) - \bar{f}(\mathbf{x}))\right)^2 \right] \\ &= \mathbb{E}_\mathcal{D}\left[ \sum_{m=1}^M (f_m(\mathbf{x}) - \bar{f}(\mathbf{x}))^2 + 2\sum_{m<m^\prime} (f_m(\mathbf{x}) - \bar{f}(\mathbf{x}))(f_{m^\prime}(\mathbf{x}) - \bar{f}(\mathbf{x})) \right] \\ &= \sum_{m=1}^M \mathbb{E}_\mathcal{D}\left[ (f_m(\mathbf{x}) - \bar{f}(\mathbf{x}))^2 \right] + 2\sum_{m<m^\prime} \mathbb{E}_\mathcal{D}\left[ (f_m(\mathbf{x}) - \bar{f}(\mathbf{x}))(f_{m^\prime}(\mathbf{x}) - \bar{f}(\mathbf{x})) \right] \end{align*}\]
The independence assumption is used in the next step: for \(m \neq m^\prime\), because \(f_m(\mathbf{x})\) and \(f_{m^\prime}(\mathbf{x})\) are independent (since they are trained on independent datasets), we can factor the expectation of their product:
\[\begin{align*} \mathbb{E}_\mathcal{D}[(f_m(\mathbf{x}) - \bar{f}(\mathbf{x}))(f_{m^\prime}(\mathbf{x}) - \bar{f}(\mathbf{x}))] &= \mathbb{E}_\mathcal{D}[f_m(\mathbf{x}) - \bar{f}(\mathbf{x})] \cdot \mathbb{E}_\mathcal{D}[f_{m^\prime}(\mathbf{x}) - \bar{f}(\mathbf{x})] \\ &= 0 \cdot 0 = 0 \end{align*}\]
This factorization only holds when \(f_m\) and \(f_{m^\prime}\) are independent. Since \(\mathbb{E}_\mathcal{D}[f_m(\mathbf{x}) - \bar{f}(\mathbf{x})] = 0\) for all \(m\), all the cross-terms vanish, leaving only the diagonal terms. When we divide by \(M^2\) to get the variance of the ensemble average, this gives us the \(\frac{1}{M}\) factor reduction.
However, when the training datasets are correlated (as with bootstrap samples), the cross-terms are no longer zero. If the predictions have variance \(\sigma^2\) and pairwise correlation \(\rho\), then the variance of the average is \(\frac{1}{M}(1-\rho)\sigma^2 + \rho\sigma^2\). When \(\rho = 0\) (models are uncorrelated), we recover the full \(\frac{1}{M}\) factor reduction in variance. When \(\rho = 1\) (models are perfectly correlated), there is no reduction in variance at all.
This observation leads to an interesting and somewhat counterintuitive strategy: if correlation (due to sharing training data) is limiting the effectiveness of bagging, we can reduce the correlation by making the models more different. This can mean using different learning algorithms in the ensemble (e.g., different choices of hyperparameters or initial settings), or injecting additional randomness into the learning process.
6 Random Forest
Random forest is a concrete example of this strategy, applied to decision trees.
Definition: A random forest is a bagged ensemble of decision trees where, when constructing each node of each decision tree, we randomly select a subset of features and only consider splits on those features.
This additional randomness makes individual trees more different from each other, even if similar data is used to train the trees. Effectively, this randomness decorrelates the trees and improves the variance reduction compared to standard bagging.
The additional randomness in the random forest comes at a small cost: each individual tree might be slightly worse because it considers fewer features. However, the reduction in correlation more than compensates for this, and the ensemble as a whole performs better. This is another manifestation of the ensemble principle: by having diverse models that make different mistakes, the ensemble can correct for individual errors.
Random forest has become one of the most popular and successful machine learning algorithms in practice. It has several advantages: it requires minimal hyperparameter tuning, it can handle mixed data types (numeric and categorical), it naturally handles feature interactions, and it can provide feature importance scores. Perhaps most importantly, it is remarkably robust and often produces good results out of the box.
7 Bagging in Practice
While bagging is a powerful technique in theory, there are several practical considerations to keep in mind. Bagging works best when the base learner is unstable, as the variance reduction benefit is most pronounced for high-variance models. Decision trees, neural networks, and nearest neighbor methods benefit substantially from bagging because small changes in the training data lead to large changes in their predictions.
The number of bootstrap samples \(M\) is a hyperparameter that can be tuned. Generally, more models lead to better performance, but with diminishing returns. Increasing \(M\) from 10 to 100 might provide a noticeable improvement, but increasing from 100 to 1000 might not.
However, there is an important tradeoff to consider: bagging increases both training and prediction time because we must train and evaluate all \(M\) models and aggregate their predictions. The computational cost scales linearly with \(M\) for both training and inference. This tradeoff between accuracy and computational cost (both training time and prediction latency) can be critical in applications where real-time predictions are required or computational resources are limited. While parallelization can help since the models can be trained and evaluated independently, the fundamental cost of processing multiple models remains. In applications where prediction latency is critical, this increased cost may be prohibitive, and one must carefully balance the accuracy gains from bagging against the computational overhead.
When tuning hyperparameters for ensemble models, it is crucial to optimize for the entire ensemble’s performance, not the performance of individual models. This is because the goal of ensemble methods is to combine multiple models to achieve better overall performance, even if individual models might be slightly worse. For example, if tuning the depth of decision trees in a random forest, one should evaluate the ensemble’s validation error, not the validation error of individual trees. A hyperparameter setting that produces slightly worse individual models but better ensemble performance (due to reduced correlation or better diversity) is preferable to a setting that optimizes individual model performance at the expense of ensemble diversity.
Finally, bagging assumes that all models should be weighted equally. This is reasonable when the models are statistically equivalent, but if some models are known to be more reliable than others, it may be beneficial to use a weighted average. In practice, the unweighted average works well in most cases.
8 Other Ensemble Methods
While bagging is one of the most fundamental ensemble methods, there are many other approaches to combining models. Boosting trains models sequentially, where each new model focuses on examples that previous models found difficult. Stacking uses a meta-learner to learn how to best combine the predictions from different base models. Mixture of experts divides the input space into regions and trains specialized models for each region, with a gating network that decides which expert to use for each input. Each of these methods has different strengths and is suited to different scenarios, but they all share the core principle of combining multiple models to achieve better performance than any individual model.
9 Summary
Ensemble methods, particularly bagging, provide a principled way to improve model performance by reducing variance. By averaging the predictions of multiple models trained on resampled versions of the data, we can smooth out the variance without affecting the bias. The bootstrap sampling procedure makes this approach practical, even with finite datasets. Random forest, an important instantiation of the bagging idea, has proven to be one of the most effective machine learning algorithms in practice. By combining bagging with feature subsampling to reduce correlation between trees, random forest achieves excellent performance with minimal tuning.
The method combines several key ideas in machine learning: the idea of averaging models in an ensemble is conceived by analyzing the tradeoffs involved between bias and variance (part of Fundamental Idea #2). This approach required considering data as a probabilistic phenomenon (Fundamental Idea #5), and using probabilistic approaches like resampling from the same dataset. The probabilistic approach helped us identify the correlation between individual models in an ensemble as a problem. The solution to decorrelating individual models was to use randomness as a tool, not just as an obstacle.
Thus, the success of bagging highlights a broader lesson in machine learning, that diversity among models can be beneficial. By having models that make different mistakes, an ensemble can compensate for individual errors and achieve better generalization. This principle extends beyond bagging to other ensemble methods such as boosting and stacking, which use more sophisticated strategies for combining models.
Nevertheless, bagging and random forest are not panaceas. They work best with high variance base learners and do not help with high bias. The increased computation cost presents another tradeoff that cannot be solved by observing model accuracy alone. As in Fundamental Idea #3: Model Evaluation is Empirical, determining when and how to use ensembles is a decision to be made with empirical evidence for the particular task at hand, while keeping in mind how harms and benefits are distributed among various people.