Bagging

Bootstrap aggregating, Breiman's method of averaging a model over resampled copies of the data. Why the average of a method over training sets can only lower squared error, derived, and how the bootstrap imitates it; a seeded experiment on Friedman's problem measuring which methods bagging helps (fully grown and shallow trees) and which it leaves unchanged (least squares, nearest neighbors); how many bootstrap samples are enough; why bagging can make a poor classifier worse; and bagging in scikit-learn.

Sixty points are drawn from a sine curve with noise, and a regression tree is grown on them until every leaf holds a single point. The tree passes through every point and jumps between them: it follows the noise as faithfully as the curve. Now draw 200 bootstrap samples from the same 60 points, grow a tree on each, and average the 200 trees. The average still bends toward the points, but the jumps are smaller and the curve is closer to the truth. Repeating the whole experiment on 200 fresh sets of 60 points measures the improvement: the expected squared error of the single tree's predictions is 0.1836, and of the average 0.1348, against a noise variance of 0.09 that no method can remove. The gain is all in variance, which falls from 0.0931 to 0.0441, while the squared bias stays near zero for both (0.0005 and 0.0007).

Sixty noisy points from sin(2πx) (dashed). Left: a fully grown regression tree interpolates the points, noise included. Right: five trees grown on bootstrap samples of the same points (thin) and the average of 200 such trees (thick), which follows the curve more closely.
Sixty noisy points from sin(2πx) (dashed). Left: a fully grown regression tree interpolates the points, noise included. Right: five trees grown on bootstrap samples of the same points (thin) and the average of 200 such trees (thick), which follows the curve more closely.

This is bagging, short for bootstrap aggregating, introduced by Breiman (1996). It is the simplest of the ensemble methods surveyed in Introduction to Ensemble Models, and the first half of a random forest. Its abstract states the condition for it to work: "The vital element is the instability of the prediction method." This article explains why averaging over bootstrap samples helps, measures which methods it helps, and shows where it fails.

The method

Given a training set of $n$ cases and a method for fitting a model, bagging takes three steps:

  1. Draw $B$ bootstrap samples: each is $n$ cases drawn at random with replacement from the training set, so some cases appear several times and others not at all.
  2. Fit the model to each sample, giving $B$ fitted models $\hat{f}^{*1}, \dots, \hat{f}^{*B}$.
  3. Predict with their average, $\hat{f}_{\text{bag}}(x) = \frac{1}{B}\sum_{b=1}^{B} \hat{f}^{*b}(x)$, for a numerical outcome, or with a vote among their predicted classes for a categorical one.

Each bootstrap sample contains about 63.2% of the distinct training cases, and each case is left out of about 36.8% of the samples, out of bag. Random Forests derives these proportions and shows how the out-of-bag cases give a bagged model a built-in estimate of its own error, the out-of-bag error, without a separate test set. Everything said there about out-of-bag error applies to any bagged model.

Why averaging over training sets helps

Breiman (1996, §4) explains bagging with an idealized version of it. A fitted model $\hat{f}(x)$ depends on the training set $\mathcal{L}$ it was fitted to, and $\mathcal{L}$ is random. Imagine fitting the same method to every possible training set of size $n$ from the population and averaging the results:

$$f_{\text{ag}}(x) = \mathbb{E}_{\mathcal{L}}\bigl[\hat{f}(x)\bigr].$$

This is the aggregated predictor. It cannot be computed, since it needs unlimited fresh data, but it can be compared with the single model. Fix $x$ and let $Y$ be a new outcome there, independent of $\mathcal{L}$. Adding and subtracting $f_{\text{ag}}(x)$,

$$\mathbb{E}\bigl[(Y - \hat{f}(x))^2\bigr] = \mathbb{E}\bigl[(Y - f_{\text{ag}}(x))^2\bigr] + 2\,\mathbb{E}\bigl[(Y - f_{\text{ag}}(x))(f_{\text{ag}}(x) - \hat{f}(x))\bigr] + \mathbb{E}\bigl[(f_{\text{ag}}(x) - \hat{f}(x))^2\bigr].$$

In the middle term, $Y$ is independent of $\mathcal{L}$ and $f_{\text{ag}}(x)$ is a constant, so the expectation factors into $\mathbb{E}[Y - f_{\text{ag}}(x)] \cdot \mathbb{E}[f_{\text{ag}}(x) - \hat{f}(x)]$, and the second factor is zero by the definition of $f_{\text{ag}}$. So

$$\mathbb{E}\bigl[(Y - \hat{f}(x))^2\bigr] = \mathbb{E}\bigl[(Y - f_{\text{ag}}(x))^2\bigr] + \operatorname{Var}_{\mathcal{L}}\bigl(\hat{f}(x)\bigr) \;\ge\; \mathbb{E}\bigl[(Y - f_{\text{ag}}(x))^2\bigr].$$

The aggregated predictor never has larger expected squared error than the single model, and the improvement is exactly the variance of the single model's prediction over training sets (Breiman, 1996, §4; Hastie, Tibshirani and Friedman, 2009, eq. 8.52). In the language of The Bias-Variance Tradeoff, aggregation keeps the bias, since $f_{\text{ag}}$ is by definition the average prediction, and removes the variance. A method whose fitted model barely changes from one training set to another has little variance to remove, and $f_{\text{ag}}$ is close to $\hat{f}$. A method whose fitted model changes a lot, an unstable method, has much to gain.

Bagging approximates $f_{\text{ag}}$ by replacing fresh training sets from the population, which are not available, with bootstrap samples from the training set, which are. The bootstrap treats the training set as a stand-in for the population (see The Bootstrap Method), and the bagged prediction is a Monte Carlo estimate of the average of $\hat{f}$ over all possible bootstrap samples (Hastie et al., 2009, §8.7). The approximation is imperfect in two ways. The bootstrap samples all come from one training set, so they vary less than fresh training sets would, and the bagged model keeps the part of the variance that comes from which training set was drawn: this is the correlation between trees that Random Forests measures. And each bootstrap sample contains only about 63% of the distinct cases, so each member is fitted to effectively less data than the original model, which can raise the bias slightly. The inequality is exact for $f_{\text{ag}}$, not for bagging, so for bagging it is a reason to expect improvement rather than a guarantee.

Which methods bagging helps

Breiman (1996), citing his earlier study of instability, singled out classification and regression trees, neural networks and subset selection in linear regression as unstable, and nearest-neighbor methods as stable. The difference can be measured. Friedman's (1991) first test problem, which Breiman used to evaluate bagging, has ten inputs uniform on $[0, 1]$ and the outcome

$$y = 10 \sin(\pi x_1 x_2) + 20 (x_3 - 0.5)^2 + 10 x_4 + 5 x_5 + \varepsilon, \qquad \varepsilon \sim N(0, 1),$$

so the noise variance is 1 and inputs 6 to 10 are irrelevant. One hundred training sets of 200 cases were drawn (seed 2024), and four methods were fitted to each, alone and bagged with $B = 50$: least squares on all ten inputs, 10-nearest-neighbor regression, a regression tree limited to depth 2 (four leaves), and a fully grown regression tree. Because the true function is known, each method's expected test error at 500 fixed test points splits into squared bias, variance and the noise variance of 1, as in The Bias-Variance Tradeoff.

Method Squared bias Variance Test MSE Change
least squares alone 5.03 0.43 6.46
bagged 5.02 0.44 6.46 0.0%
10-nearest neighbors alone 7.21 1.59 9.80
bagged 7.30 1.33 9.63 −1.8%
depth-2 tree alone 9.21 5.20 15.41
bagged 8.90 1.52 11.43 −25.8%
fully grown tree alone 3.32 9.07 13.39
bagged 3.76 1.44 6.20 −53.7%
Friedman's problem, 100 training sets of 200 cases: squared bias (blue) and variance (orange) for four methods, alone and bagged with 50 bootstrap samples (hatched). Bagging removes most of the variance of both trees and leaves least squares and nearest neighbors almost unchanged. The bias of each method is untouched or nearly so.
Friedman's problem, 100 training sets of 200 cases: squared bias (blue) and variance (orange) for four methods, alone and bagged with 50 bootstrap samples (hatched). Bagging removes most of the variance of both trees and leaves least squares and nearest neighbors almost unchanged. The bias of each method is untouched or nearly so.

Least squares is unchanged. Its bagged and unbagged predictions differ by 0.072 on average, against a spread of predictions with standard deviation 4.13, and their correlation is 0.9998. The reason is that a least-squares fit is a linear function of the outcomes: refitting it to resampled data and averaging reproduces, approximately, the original fit. Hastie et al. (2009, §8.7) state the general principle: the bagged estimate differs from the original "only when the latter is a nonlinear or adaptive function of the data." Least squares on a fixed set of inputs is neither. Breiman (1996, §4) adds that for a stable method the bagged model can be slightly worse than the original, because it averages over the bootstrap's imitation of the population rather than the population itself, and in his subset-selection experiments bagging made the most stable regressions, those using many of the variables, worse rather than better. Here the difference is too small to see. The linear model's error is almost all bias, because a linear function cannot represent the sine and the quadratic term, and no amount of averaging linear functions produces a curve.

Nearest neighbors are nearly unchanged. A 10-nearest-neighbor prediction averages ten outcomes, and resampling changes which ten only at the margins. Its variance falls by a sixth, from 1.59 to 1.33, but its error is dominated by bias.

Trees are transformed. The fully grown tree has the lowest bias of the four methods and the highest variance, and bagging cuts its variance from 9.07 to 1.44, more than halving its test error, from 13.39 to 6.20. Breiman (1996, Table 3) reported a similar reduction on the same problem, from 11.4 to 6.2, a decrease of 46%; his single tree was pruned by cross-validation, which lowers its variance, so the starting point is better than this unpruned tree's. The bagged tree's squared bias rises slightly, from 3.32 to 3.76, the cost of fitting each member to a bootstrap sample with fewer distinct cases.

The depth-2 tree is the case to look at closely. It has only four leaves and high bias, and a simple model is easy to assume stable, yet on this problem, with 200 training cases, bagging removes more than two thirds of its variance (5.20 to 1.52). A shallow tree is unstable in a different way from a deep one. Its few splits are chosen by searching over all inputs and thresholds, and when two candidate splits are nearly as good, a small change in the data switches the choice and moves the whole prediction surface. Instability is a property of how a method responds to its data, not of how complex the fitted model looks; how much a shallow tree gains from bagging will vary with the problem and the sample size, and this experiment measures one case. Bagging cannot help with the depth-2 tree's bias, though: even bagged, its error (11.43) is nearly twice that of the bagged full tree.

The pattern matches Breiman's account and the inequality above. Bagging is worth applying to methods with low bias and high variance, and that is why it is almost always applied to deep, unpruned trees. The base models of a bagged ensemble should be flexible, not simple: simplicity reduces variance, which is the one thing bagging already supplies.

How many bootstrap samples

The bagged prediction is an average of $B$ random members, and its error falls as $B$ grows, quickly at first. For the fully grown tree on Friedman's problem, averaging the first $B$ of the 50 bootstrap trees gives these expected test errors:

Trees $B$ 1 2 5 10 25 50
Test MSE 15.45 10.81 7.93 7.01 6.40 6.20

A single bootstrap tree (15.45) is worse than the tree grown on the full training set (13.39), since it sees fewer distinct cases. Two already beat it, ten capture most of the gain, and the improvement from 25 to 50 trees is small. Breiman (1996) used 50 bootstrap samples for classification and 25 for regression, and found on one classification problem that the error rate barely changed beyond 25: "More than 25 bootstrap replicates is love's labor lost." More classes, he suggested, call for more samples. As Random Forests explains, adding members to an average does not cause overfitting, so the only cost of a large $B$ is computation, and the out-of-bag error shows when the error has settled.

Bagging classifiers

For classification, the members' predictions are combined by majority vote, or, when the members give class probabilities, by averaging the probabilities and choosing the most probable class. Breiman (1996, §6.1) found that the two gave virtually identical misclassification rates in every classification example he tried, and, on simulated data where the true probabilities are known, that bagged probability estimates were more accurate than a single tree's. scikit-learn's BaggingClassifier averages probabilities when the base model provides them and votes otherwise.

The inequality behind bagging is for squared error, and it does not carry over to misclassification error. Hastie et al. (2009, §8.7) give a stark example. Suppose the true class is 1 everywhere, and a classifier, depending on its training set, predicts 1 everywhere with probability 0.4 and 0 everywhere with probability 0.6. Its error rate is 0.6. A majority vote of independent copies of it predicts 0 more and more often: the vote of 11 copies has error 0.7535, of 101 copies 0.9791, and the aggregated classifier, the vote of infinitely many, is always wrong. Averaging made a bad classifier worse. Breiman (1996, §4) gives the general account. At a given input, ask whether a classifier, over training sets, predicts the most probable class more often than any other class. Where it does, the aggregated classifier always predicts that class, which is the best possible prediction there; where it does not, aggregation makes the classifier consistently wrong. Aggregation, he concluded, can turn good classifiers into nearly optimal ones and poor ones into worse ones. His summary: "Bagging unstable classifiers usually improves them. Bagging stable classifiers is not a good idea." This is the majority vote calculation again, where voters better than chance improve with numbers and voters worse than chance get worse.

Stable classifiers barely move. On the breast cancer data (Wolberg, Mangasarian, Street and Street, 1993), with 10-fold cross-validation (the folds of Random Forests) and 100 bootstrap samples:

Classifier Accuracy alone Bagged Same prediction
logistic regression 0.977 0.974 565 of 569
5-nearest neighbors 0.965 0.967 568 of 569
1-nearest neighbor 0.953 0.956 567 of 569

Bagged and unbagged predictions differ on at most 4 of the 569 tumors, and the accuracy moves by 0.003 at most, within the noise of the estimate. Breiman (1996, §6.3) found bagged and unbagged nearest-neighbor classifiers to have identical error rates on six datasets and explained why: a bagged 1-nearest-neighbor classifier can change its prediction for a case only if the case's nearest training neighbor is missing from at least half the bootstrap samples, while each training case appears in about 63% of them. A fully grown classification tree, by contrast, goes from a cross-validated accuracy of 0.923 to 0.961 when bagged on the same data (Random Forests).

Strengths and costs

Bagging is easy to apply: Breiman (1996) described it as a loop that sends bootstrap samples to an existing method and an average at the end. It needs no change to the method, it has essentially one setting, $B$, that is safe to make large, and its members can be fitted in parallel, since none depends on another. With the out-of-bag error it also comes with its own estimate of accuracy.

It improves only what it can average away. It reduces variance and does nothing for bias, so it cannot rescue a method that is systematically wrong, as the linear model and the shallow tree on Friedman's problem show; for that, the members must be combined in a way that corrects each other's errors, which is the idea of Boosting. When one input dominates, the bootstrap trees are alike and their average keeps much of their shared variance; a random forest lowers that floor by also randomizing the inputs considered at each split. And, like any ensemble, a bagged model loses the readability of its members: Breiman's conclusion was that with trees, "What one loses ... is a simple and interpretable structure. What one gains is increased accuracy."

In Python

import numpy as np
from sklearn.ensemble import BaggingRegressor
from sklearn.tree import DecisionTreeRegressor

rng = np.random.default_rng(2024)
X = rng.random((200, 10))
y = (10 * np.sin(np.pi * X[:, 0] * X[:, 1]) + 20 * (X[:, 2] - 0.5) ** 2
     + 10 * X[:, 3] + 5 * X[:, 4] + rng.normal(0, 1, 200))

bag = BaggingRegressor(DecisionTreeRegressor(), n_estimators=50,
                       oob_score=True, random_state=0, n_jobs=-1)
bag.fit(X, y)
print(bag.oob_score_)        # out-of-bag R squared

BaggingRegressor and BaggingClassifier take any scikit-learn model as estimator (a decision tree by default) and fit n_estimators copies (default 10, usually too few). max_samples sets the size of each sample and max_features the fraction of inputs each member sees; both default to 1.0, meaning all cases and all inputs. Setting bootstrap=False samples cases without replacement, and drawing a fraction of the inputs for each member gives the random subspace method; the documentation lists the papers behind these variants. n_jobs=-1 fits the members on all processor cores. For trees, RandomForestRegressor and RandomForestClassifier with max_features=None are bagging, and with smaller max_features they are random forests. The numbers in this article are computed by tools/experiments/data-science/bagging.py in the site's repository.

References

  • Breiman, L. (1996). Bagging predictors. Machine Learning, 24(2), 123–140. Quotations, section and table numbers follow the technical report version (No. 421, Department of Statistics, University of California, Berkeley, September 1994). record · 3 pages
  • Friedman, J. H. (1991). Multivariate adaptive regression splines. The Annals of Statistics, 19(1), 1–67. record · 4 pages
  • Hastie, T., Tibshirani, R., and Friedman, J. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2nd ed.). Springer. record · 23 pages
  • Wolberg, W., Mangasarian, O., Street, N., and Street, W. (1993). Breast Cancer Wisconsin (Diagnostic) [Data set]. UCI Machine Learning Repository. https://doi.org/10.24432/C5DW2B record · 14 pages