Bagging: Bootstrap Resampling and the Variance It Removes

A decision tree grown on a finite sample is a high-variance object. Move a few rows, and a split that separated two classes cleanly may no longer be chosen; the entire subtree below it changes shape. Bagging attacks this directly: train many trees on perturbed copies of the training set and average their predictions, so that the perturbations cancel.

The mechanism is simple enough to state in a paragraph, but the arithmetic of when it works and how much it helps is where the subject lives. The gain is bounded by how correlated the individual predictors are, and bagged trees are correlated, because they all see nearly the same data.

What a bootstrap sample contains

A bootstrap sample of size $n$ is drawn from the $n$ training rows uniformly with replacement. Each row is included at least once with probability $1-(1-1/n)^n$, which converges to $1-e^{-1} \approx 0.632$ as $n$ grows. So roughly 63% of the distinct rows appear in any given sample, and the expected number of omitted rows is $n e^{-1} \approx 0.368n$. Rows that appear multiple times act as implicit weights, shifting split thresholds and leaf means toward them.

For a training set of 1,000 rows, a bootstrap sample contains about 632 distinct rows and about 368 duplicates beyond the first occurrence of each. That ratio is stable across $n$; a 10-row dataset behaves the same way, which is worth remembering when the dataset is small and the resamples overlap heavily.

A bagged ensemble fits $B$ such trees, each grown independently, and combines them. For regression the combination is the mean of the leaf values; for classification it is usually a vote, though averaging the leaf class frequencies is strictly better behaved, as discussed below. Nothing about the base learner needs to change. Bagging is a wrapper: it takes a procedure that fits one model and returns one fitted on each resample, so the only requirement is that the procedure be deterministic given its input.

Averaging correlated predictors

Suppose each tree has variance $\sigma^2$ and every pair of trees has correlation $\rho$. The variance of the average of $B$ trees is

$$ \rho\sigma^2 + \frac{1-\rho}{B}\sigma^2 $$

The second term vanishes as $B$ grows; the first does not. Increasing the number of trees from 10 to 1,000 can only shrink the ensemble’s variance toward $\rho\sigma^2$, so the quantity that matters is the correlation between members, not the count.

For plain bagging of trees, $\rho$ is not small. All trees are fitted to the same features with the same algorithm; on a dataset with one dominant predictor, most trees will split on that predictor at the root, and their predictions will agree on most of the input space. The variance reduction is real but limited, and it saturates quickly. Averaging has usually converged to within a negligible distance of its limit long before the member count reaches a few thousand, and probability estimates converge more slowly than hard votes because they depend on the spread of leaf frequencies rather than on the identity of the winning class.

This is also why the base learner matters. Bagging reduces variance, not bias: the average of $B$ trees has approximately the bias of one tree, since the expectation of an average equals the average of expectations. A procedure whose error is dominated by variance, such as a deep unpruned tree, benefits. A procedure whose error is dominated by bias, such as a stump or a strongly regularized linear model, does not. For linear regression with a fixed design, bagging is close to a no-op: the bootstrap perturbs the fit slightly, and averaging those perturbations returns something very near the original least-squares estimate.

import random

def bootstrap(rows, rng):
    n = len(rows)
    return [rows[rng.randrange(n)] for _ in range(n)]

def bagged_predict(models, x):
    return sum(m.predict(x) for m in models) / len(models)

The loop above draws indices rather than rows, which is the usual implementation detail: shuffling an index array and taking the first $n$ with replacement avoids copying large feature matrices per resample. Memory is $O(n)$ indices per tree if the trees are fitted one at a time, which is why most implementations expose a streaming or incremental interface.

Out-of-bag error as a by-product

Because each tree omits about 37% of the rows, those rows are an unseen test set for that tree. The out-of-bag estimate uses this: for each training row, collect the predictions of only the trees that did not see it, aggregate them, and compare with the true label. Every row has roughly $0.368B$ such trees, so with a few hundred members each row is scored by dozens of models.

The estimate is nearly free and correlates well with held-out error, but it is not the same thing, for two reasons. Each tree is trained on 63% of the distinct rows, so the ensemble that produces the OOB prediction is weaker than the ensemble eventually deployed on all data; the estimate is therefore mildly pessimistic. And the trees scoring a given row are a correlated subset, so the effective sample size behind the aggregate is smaller than the raw count of trees suggests, which makes the OOB error noisier than a cross-validation estimate at the same number of folds.

The bootstrap also gives a way to estimate a quantity that cross-validation cannot: the spread of the prediction across resamples. It is a rough confidence indicator, not a calibrated interval, and the probabilities produced by averaged trees are known to be poorly calibrated, with mass pushed toward zero and one because a vote can only land on the values a finite number of trees can produce.

Votes, averages, and ties

For classification, hard voting counts one vote per tree. Averaging the trees’ class probability estimates instead uses more information and produces better-ranked scores, which matters whenever the output is thresholded later or fed into a downstream cost calculation. The two disagree most when the ensemble is small and the trees are confident but split.

Ties are possible with an even number of trees and two classes. Implementations break them by class order or by the averaged probability, and the choice is invisible unless it is not: a tie broken toward the positive class on a balanced problem can shift a thresholded decision by a full vote. Using an odd number of members, or resolving on the averaged score, avoids the issue.

Averaging probabilities also exposes a distinction that matters for inference cost. A vote needs only the argmax per tree, so each tree can return a single integer; an averaged probability needs the full leaf distribution. If the trees are being evaluated in a latency-sensitive path, the lighter output is a real saving, and it is the reason some serving formats store only the winning class per leaf.

The costs that do not shrink

Bagging multiplies training cost by $B$ and model size by $B$. Inference cost is $B$ tree traversals, which can be parallelized across cores but not eliminated; a forest of 500 trees of depth 20 is 500 independent root-to-leaf walks per prediction. Training can be parallelized perfectly, since the trees never interact, which is why bagging scales across machines trivially and boosting does not.

Interpretability degrades in a specific way. A single tree can be read as a decision list, at least once it has been collapsed to a manageable size by cost-complexity pruning; an average of 500 trees cannot, and the usual substitute is a feature importance score, which measures association rather than decision structure. The importance measures computed from bagged ensembles carry their own biases, which is the subject of feature subsampling in random forests.

Finally, bagging interacts poorly with sample weights and with time-ordered data. Resampling with replacement destroys the weighting, and any structure in which row order carries information, such as a time series, is violated by a bootstrap that can place a future row in a tree’s training set. Block bootstraps exist for that case, but they change the variance calculation and are no longer the procedure described here.

The natural next step is to make the trees less correlated on purpose, which is what adding randomness to the split search does. Bagging supplies the resampling machinery; the forest supplies the decorrelation, and the combination is the subject of the rest of this cluster.