Bagging: many copies of a model, averaged

Bagging is covered in section 8.2 of An Introduction to Statistical Learning. The method comes from Leo Breiman’s 1996 paper “Bagging Predictors”. The name is short for bootstrap aggregating.

The bias and variance post ended with a problem: a deep tree has almost no bias but huge variance. Its answer depends heavily on which data it happened to see. Bagging fixes that by averaging many trees.

The idea: ask a committee

If you ask one risk analyst how volatile next month will be, you get their answer, quirks and all. Ask twenty analysts who each learned from a slightly different few years of history, and take the average: their individual quirks partly cancel out, and what’s left is closer to the real pattern.

Bagging does this with models:

1. Make many bootstrap samples of the training data.
2. Train one model (usually a deep decision tree) on each.
3. Average their predictions. For classification, average their probabilities, or take a vote.

Step 1: the bootstrap sample

A bootstrap sample is drawn from the training data with replacement, and it has the same size as the original. Some rows get picked more than once, some not at all.

Eight training rows, numbered 1 to 8, and three bootstrap samples of them:

Each tree sees a different version of the history, so each tree comes out different.

How many rows does a bootstrap sample leave out? The chance that a given row is not picked in one draw is $1 - 1/n$. Over $n$ draws:

$$\left(1 - \frac{1}{n}\right)^n \;\longrightarrow\; \frac{1}{e} \approx 0.368 \quad \text{as } n \text{ grows}$$

So each tree never sees about 37% of the data, and uses about two-thirds of it (ISLP section 8.2.1, Murphy section 18.3). With 10,000 rows, I measured 36.7%. Those left-out rows are called out-of-bag rows, and they’re useful: each tree can be tested on the rows it never saw, which gives a free estimate of performance without a separate test set.

Step 3: why averaging reduces variance

An Introduction to Statistical Learning (section 8.2.1) starts from a simple fact: averaging $n$ independent numbers, each with variance $\risk{\sigma^2}$, gives an average with variance $\risk{\sigma^2} / n$. Bagged trees aren’t independent, though: they learn from overlapping data. If you average $B$ predictions that each have variance $\risk{\sigma^2}$, and every pair has correlation $\key{\rho}$, the average has variance:

ρ, how alike the trees' errors areσ², one tree's variance

$$\risk{\text{Var}}(\text{average}) = \key{\rho}\,\risk{\sigma^2} + \frac{1 - \key{\rho}}{B}\,\risk{\sigma^2}$$

Plain meaning: the second term shrinks as you add models. The first term doesn’t. If the models were completely independent ($\key{\rho} = 0$), averaging 100 of them would cut variance 100-fold. But trees trained on overlapping data make similar mistakes ($\key{\rho} > 0$), so variance falls towards a floor of $\key{\rho}\,\risk{\sigma^2}$ and stops. ISLP (section 8.2.2) says the same in words: averaging highly correlated quantities does not reduce variance as much as averaging uncorrelated ones. (It’s the same maths as the diversification floor in a portfolio of correlated assets.)

Where the formula comes from

The variance of a sum is the sum of every variance plus every covariance between pairs. $B$ models each have variance $\risk{\sigma^2}$, and each of the $B(B - 1)$ ordered pairs has covariance $\key{\rho}\,\risk{\sigma^2}$. Dividing the sum by $B$ divides its variance by $B^2$:

$$\begin{aligned} \text{Var}(\text{average}) &= \frac{1}{B^2}\left(B\,\risk{\sigma^2} + B(B - 1)\,\key{\rho}\,\risk{\sigma^2}\right) \\[10pt] &= \frac{\risk{\sigma^2}}{B} + \frac{B - 1}{B}\,\key{\rho}\,\risk{\sigma^2} \\[10pt] &= \key{\rho}\,\risk{\sigma^2} + \frac{1 - \key{\rho}}{B}\,\risk{\sigma^2} \end{aligned}$$

Measuring it

Same made-up problem as the bias and variance post: predict next month’s volatility from this month’s, on a curve I invented so the truth is known. Same method: 200 fresh training samples of 80 made-up months, measuring how much the predictions move between samples.

• Bias stays near zero. Averaging deep trees doesn’t make them too simple.
• Variance halves, from 8.9 to 4.2, most of it by the first 10 trees.
• Then it levels off. That’s the $\key{\rho}\,\risk{\sigma^2}$ floor. From these numbers, the trees’ predictions are correlated at roughly $\key{\rho} \approx 0.47$ (my estimate: $4.2 / 8.9$, ignoring the small leftover term).

On this small, simple problem, the best single tree from the bias and variance post (depth 3, error 11.8) still beats 100 bagged deep trees (13.2). Bagging removes variance. It doesn’t remove the need to choose a sensible model.

On the stress-month data

Now the classification problem from the decision trees post: will next month be a stress month? Scores are AUC on the 2,405 test rows of 2022 and 2023, one per ticker per trading day (0.5 is a coin flip, 1.0 is perfect):

This table says most of what there is to say about bagging:

• It helps a lot when the base model is unstable (high variance), like a fully grown tree.
• It helps less when the model is already stable. A depth-3 tree changes little between bootstrap samples, so there’s less noise to average away; it still gains about 0.02 of AUC here, because real market data is noisier than my toy curve.

And a warning about the out-of-bag estimate. From the training data alone, the bag of fully grown trees reported an AUC of $\key{0.907}$. Its real test score was 0.788. The estimate is far too rosy, and the reason is the data, not the method: two rows a day apart are computed from almost the same month of prices, so a row left out of a bootstrap sample has near-twins inside it, and “never seen” isn’t really true. On a time series, the only honest test is forward in time. The out-of-bag score is free and useful when rows are independent. Here it would have fooled me.

Three more experiments

On the regression version of the problem, predicting next month’s volatility as a number, the same ideas look like this.

How many trees. Fully grown trees, averaged, scored by RMSE (the typical size of a miss; lower is better) on the 2022 to 2023 rows:

The first twenty trees take a third off the error; the next eighty take nothing. That levelling off is the $\key{\rho}\,\risk{\sigma^2}$ floor from the formula above, measured.

Random splits. A tree that picks each cut point at random instead of searching for the best one is weaker alone and far cheaper to build: 5.9 milliseconds against 16.5 for a fully grown tree here. On this noisy target it is also, oddly, better once leaves hold a few rows (a test RMSE of 10.24 against 12.01 at ten rows per leaf), because the search was finding cuts that fit the training noise. Twenty bagged random trees scored 9.80 against 10.61 for twenty bagged searching trees. Randomness acts as regularisation (a brake that stops a model fitting noise), and it is the trade that random forests and “extra trees” (extremely randomised trees, which pick their cut points at random as here) are built on.

Bagging a stable model. Bag twenty linear regressions and you get the single regression’s answer back, to two decimal places. A straight line barely moves between resamples of the same data, so there is nothing to average away. Bagging helps unstable learners, deep trees above all, and does nothing for stable ones.

The code

All three ideas on made-up data, so it runs as pasted (pip install numpy scikit-learn): one bootstrap sample, deep trees bagged on the made-up volatility curve from the bias and variance post, and a straight line bagged for comparison. X_train holds this month’s volatility as a one-column table, y_train next month’s.

import numpy as np
from sklearn.ensemble import BaggingRegressor
from sklearn.linear_model import LinearRegression
from sklearn.metrics import root_mean_squared_error
from sklearn.tree import DecisionTreeRegressor

rng = np.random.default_rng(0)

# 1. One bootstrap sample: draw 8 rows, with replacement, from rows 1 to 8
rows = np.arange(1, 9)
sample = rng.choice(rows, size=8, replace=True)
print("drawn:", np.sort(sample), " left out:", np.setdiff1d(rows, sample))

n = 10_000                                            # the same on 10,000 rows
left_out = 1 - len(np.unique(rng.choice(n, size=n))) / n
print("share of rows left out:", round(left_out, 3))  # about 0.37

# 2. Bagging deep trees on a made-up curve (next month's volatility from this month's)
def true_curve(x):
    return 6 + 0.45 * x + 8 / (1 + np.exp(-(x - 25) / 3))

x_train = rng.uniform(5, 45, 300)
y_train = true_curve(x_train) + rng.normal(0, 3, 300)
x_test = rng.uniform(5, 45, 1000)
y_test = true_curve(x_test) + rng.normal(0, 3, 1000)
X_train, X_test = x_train.reshape(-1, 1), x_test.reshape(-1, 1)   # tables of one column

for B in (1, 10, 100):                                # how many trees are averaged
    bag = BaggingRegressor(DecisionTreeRegressor(), n_estimators=B, random_state=0)
    bag.fit(X_train, y_train)                         # each tree gets its own bootstrap sample
    print(f"{B:3} deep trees: test RMSE {root_mean_squared_error(y_test, bag.predict(X_test)):.2f}")

# 3. Bagging a stable model: twenty straight lines average back to one line
line = LinearRegression().fit(X_train, y_train)
bagged = BaggingRegressor(LinearRegression(), n_estimators=20, random_state=0).fit(X_train, y_train)
print("one line:", round(root_mean_squared_error(y_test, line.predict(X_test)), 2),
      " twenty bagged lines:", round(root_mean_squared_error(y_test, bagged.predict(X_test)), 2))

It prints one bootstrap sample (some rows several times, a few left out), then a left-out share of about 0.37. Then the averaging: one deep tree misses by about 4.7, ten trees by about 3.85, a hundred by about 3.8, the fast fall and then the floor from the table above. The noise added to y has a spread of 3, so 3 is the best any model can do. Last, the single line and twenty bagged lines score the same 3.37: nothing to average away.

The scripts behind the real numbers

The tables come from examples/bagging/bagging.py and, for the three experiments, from examples/machine-learning-in-ten-ideas/ten_ideas.py. The stress-month and regression numbers use the blog’s five tickers. To run it yourself, clone the examples repo: its README has a three-command Docker setup, or run uv run on it.

Summary

References

• James, Witten, Hastie, Tibshirani and Taylor, An Introduction to Statistical Learning, with Applications in Python (Springer, 2023), section 8.2.1: bagging and out-of-bag error, each tree using about two-thirds of the rows; section 8.2.2: why correlated trees cancel less
• Kevin P. Murphy, Probabilistic Machine Learning: An Introduction (MIT Press, 2022), section 18.3: bagging, and the 63% / 37% bootstrap split
• Hastie, Tibshirani and Friedman, The Elements of Statistical Learning (2nd ed., Springer, 2009), equation 15.1: the variance of an average of correlated trees, derived in the fold above
• Leo Breiman, “Bagging Predictors”, Machine Learning 24(2), 123–140, 1996
• scikit-learn: bagging meta-estimator