Bagging is an ensemble method that uses randomly
sampled subsets of a dataset as training sets for its
base learners. Aggregating the predictions
delivered by the base learners, by a majority vote in
classification or by averaging in regression, yields
the prediction of the ensemble method. A
random forest is the instance of bagging whose
base learners learn decision trees.
On twenty-four days of 2020, twelve from
winter and twelve from summer, the weather station Krems an der
Donau recorded a minimum and a maximum temperature. Predicting
the maximum temperature $\truelabel$ of a day from its minimum
temperature $\feature$ is a regression problem, and a
decision tree solves it by splitting the feature axis
at a threshold and predicting the mean label on each side.
Fig. 1 shows what happens when two
decision trees are each learned from five of those days
chosen at random: they place their threshold at $5.4$ and $9.2$
degrees Celsius, and their predictions differ by up to
$22$ degrees Celsius. This spread hints at a lack of
stability of the base learner: it is too sensitive to
the specific choice of training set, which in turn implies poor
generalization.
B-nofitBagging is an ensemble technique that suppresses this instability. Bagging
executes its base learners in parallel, in contrast to boosting,
which runs its base learners sequentially. The name is short for bootstrap aggregating.
Figure 1: Twenty-four days of 2020 at Krems an der Donau, twelve
from winter and twelve from summer, with the minimum
temperature of a day as feature and its maximum
temperature as label. Two decision trees of depth
one, each learned from five of the days chosen at random, are
drawn in the style of the days they were trained on: the solid
black step curve with the filled circles, the dashed gray step
curve with the filled squares. The remaining days are the
small gray dots. The two trees place their threshold at
different temperatures and predict different levels on either
side of it. Data generated by pythondemos/bagging.py
Bagging uses randomly sampled subsets of a dataset as training sets for its
base learners. Given the original training set
$\dataset$, it generates perturbed copies
$\widetilde{\dataset}^{(1)},\,\ldots,\,
\widetilde{\dataset}^{(\numlearners)}$
(typically via bootstrap sampling) and trains one
base learner on each, producing hypotheses
$\learntlocalhypothesis{1},\,\ldots,\,
\learntlocalhypothesis{\numlearners}$.
The final hypothesis aggregates these by majority vote
for classification (i.e., the class predicted by the most
base learners) or averaging for regression, a task
whose label space is $\reals$ (see
Fig. 2). Bagging methods differ in their
choice of base learner. A random forest, for example,
is the instance of bagging whose base learners learn
decision trees; it randomizes the features as
well as the data points.
Figure 2: Example of bagging in which three base learners use perturbations
$\widetilde{\dataset}^{(1)},\,\ldots,\,\widetilde{\dataset}^{(3)}$ of
the original training set $\dataset$ to learn the hypotheses
$\learntlocalhypothesis{1},\,\ldots,\,\learntlocalhypothesis{3}$. The final
hypothesis is obtained by aggregating these individual hypotheses
via some aggregation rule $\phi_{\rm agg}$. One aggregation rule for
regression problems is the average of the individual
predictions
Bagging reduces the variance of the machine learning (ML) method used
for the base learners
(Hastie et al., 2009, Sect. 8.7): each
base learner sees a different resample, so their
prediction errors are only partly correlated. In an
idealized setting of bagging with $\numlearners$
base learners that deliver uncorrelated predictions,
each with variance $\sigma^{2}$, the averaged
prediction has variance $\sigma^{2}/\numlearners$.
In general the predictions are correlated. For
$\numlearners$ identically distributed predictions, each
with variance $\sigma^{2}$ and with pairwise
correlation $\rho$, the averaged prediction has
variance
\[
\rho \sigma^{2}
+ \frac{1-\rho}{\numlearners}\, \sigma^{2}
\text{.}
\]
The second term vanishes as $\numlearners$ grows, while the
first does not: the correlation between the
base learners sets a lower bound $\rho \sigma^{2}$ that no
number of base learners brings down
(Hastie et al., 2009, Eq. (15.1)).
Fig. 3 shows, in a small numerical
experiment, the estimated variance of the average of
$\numlearners$ bagged decision trees against the value
this identity predicts from an estimated $\sigma^{2}$ and
$\rho$.
B-overlapThe predictions of the base learners are
independent only if the overall training set is assumed fixed
and given. If the training set itself is also modeled as a
random variable (RV), the predictions of the base learners are
no longer independent. Every base learner is grown from a
resample of the same $\samplesize$ data points: a resample
holds any one of them with probability about
$1 - 1/e \approx 63.2\%$
(Hastie et al., 2009, Eq. (7.55)), two resamples
therefore share about $(1-1/e)^{2} \approx 40\%$, and all of
them share the same empirical distribution.
B-rhoBagging reduces only the variance of an ML method,
not its bias. Indeed, for the regression setting,
the average and each of its members have the same expectation,
so averaging leaves the bias of a member unchanged.
Figure 3: The variance of the average of $\numlearners$
bagged decision trees (filled circles), against the
value the identity predicts from a $\sigma^{2}$ and a
$\rho$ estimated on separate training sets (dashed
curve). The two agree to within $5\%$ at every
$\numlearners$, and both approach the lower bound $\rho \sigma^{2}$
rather than zero. Data
generated by pythondemos/bagging.py
Averaging also yields stability: the learned
hypothesis depends only weakly on any single
data point of the training set. Consider any ML method with predictions in
$[0,1]$ whose base learners are each trained on a share $p$
of the $\samplesize$ data points, drawn without
replacement, and whose predictions are averaged over all
such subsamples. Then, removing a single data point from
the training set changes the prediction at a test
point by more than $\varepsilon$ for at most a
$\delta$-fraction of the removed data points, for every
pair $(\varepsilon, \delta)$ with
$\delta \varepsilon^{2} \geq
\frac{1}{4(\samplesize-1)} \cdot \frac{p}{1-p}$
(Soloff et al., 2024, Thm. 8). This guarantee holds for every
training set and requires nothing of the base learner
beyond the bounded predictions — the stability is
created by the averaging itself.
A random forest applies bagging to decision trees
and, in addition, lets each split choose only among a small
random subset of the features. The random choice reduces
the correlation between the learned decision trees,
and a lower correlation means a smaller variance of
their average (Breiman, 2001;
Hastie et al., 2009, Eq. (15.1)).
Hastie et al. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer Science+Business Media. doi.org/10.1007/978-0-387-84858-7
