Bagging

Why Does This Exist?

Average enough noisy guesses and the noise cancels. That's close to the only free thing in machine learning.

You are mapping a reservoir bed from 300 sonar soundings taken from a small boat, and you want depth anywhere on the surface. A deep decision tree does the job: carve the surface into blocks, predict the mean sounding in each. Take 300 different soundings and it draws visibly different blocks. Same water, same procedure, different map.

That instability has a name. Variance is how much your fitted model moves when the sample moves, with nothing about the truth changed. The full split of error into bias, variance, and noise lives in the bias-variance tradeoff. Bagging is the cheapest treatment found for variance, and it asks for no new data. This page covers resample, fit, and average, plus the free validation the leftovers give you. The sequel that breaks through bagging's ceiling is random forests. The sibling that attacks bias instead is boosting.

Think of It Like This

How It Actually Works

Draw, fit, average

Bootstrap aggregating, shortened to bagging. Draw $B$ samples from your $n$ rows, each also of size $n$, with replacement. Here $B$ means how many resamples you draw and $n$ means how many rows you started with. Fit one model per resample, alone. Average the $B$ predictions for numbers, or take the majority vote for classes. There is no step four.

With replacement is the part people skim, and it's the only reason this works. Draw $n$ rows without replacement from $n$ rows and you get the same rows back and $B$ identical models. With replacement a row can appear twice or never, so each model sees a slightly different sample. Bootstrap and resampling explains why sampling your own sample is legitimate.

Why variance falls, and where it stops

Average $B$ independent estimators that each have variance $\sigma^2$, where $\sigma^2$ means how much one model's prediction wobbles across samples, and you get $\sigma^2 / B$. Thirty models, a thirtieth of the wobble. If that held you could buy your way to zero.

It doesn't hold. Any two bootstrap samples come from the same rows and share most of them, so their models err together. Write $\rho$ for the correlation between two models' predictions, a number from 0 for independent to 1 for identical. The variance of the average is then

Push $B$ to infinity and the second term vanishes. The first stays: $\rho \sigma^2$ is a floor set by how alike your models are, and no count of them gets underneath. At $\rho = 0.6$ you can remove at most 40 percent of the variance, whatever you spend. That floor is why random forests exists: it goes after $\rho$, not $B$.

Notice what never appears: bias. Every member comes from the same procedure, so whatever it gets systematically wrong, all of them get wrong together and the average keeps it. Bagging is a variance tool and nothing else. It's enormous for deep trees and nearly nothing for a linear model.

Worked example

Six sonar soundings, depths in metres: row 1 is 12, row 2 is 15, row 3 is 10, row 4 is 18, row 5 is 14, row 6 is 16. We predict depth at one new spot with the sample mean. The mean is steady, so we use it here only to keep the arithmetic checkable. In practice you'd bag a deep tree, because means have little variance to remove.

Three draws, each of size six with replacement:

• Draw A takes rows [1, 1, 3, 4, 4, 6], depths [12, 12, 10, 18, 18, 16]. Sum 86, mean $86 / 6 \approx 14.33$. Rows 2 and 5 never appear, so they are out of bag for model A.
• Draw B takes rows [2, 3, 3, 3, 5, 6], depths [15, 10, 10, 10, 14, 16]. Sum 75, mean $75 / 6 = 12.50$. Rows 1 and 4 are out of bag for model B.
• Draw C takes rows [1, 2, 2, 4, 5, 5], depths [12, 15, 15, 18, 14, 14]. Sum 88, mean $88 / 6 \approx 14.67$. Rows 3 and 6 are out of bag for model C.

The bagged prediction is the mean of means:

Each draw missed two of six rows, about a third. That is the $e^{-1}$ figure showing up at small $n$: with six rows $(1 - 1/6)^6 \approx 0.335$, so about two rows sit out per draw.

The rows you missed

Each resample draws $n$ times from $n$ rows, so the chance a given row is never picked is $(1 - 1/n)^n$, which tends to $e^{-1} \approx 0.368$ as $n$ grows. A large resample holds about 63.2 percent of the rows and leaves 36.8 percent behind.

Rows left behind are out-of-bag for that model. It never saw them, so its prediction on them is genuinely held out. Every row is out of bag for roughly a third of the models. Average those predictions per row and score them, and you hold a validation estimate built from the same data, with nothing set aside and no extra fitting.

Code

The point is the check, not the formula: rebuild the three draws, watch the means land where the hand computation said, and count the leftovers.

1depths: list[float] = [12.0, 15.0, 10.0, 18.0, 14.0, 16.0]2draws: list[list[int]] = [[1, 1, 3, 4, 4, 6], [2, 3, 3, 3, 5, 6], [1, 2, 2, 4, 5, 5]]3
4
5def mean(xs: list[float]) -> float:6    return sum(xs) / len(xs)7
8
9means: list[float] = [mean([depths[i - 1] for i in d]) for d in draws]10oob: list[list[int]] = [[r for r in range(1, 7) if r not in d] for d in draws]11
12print([f"{m:.2f}" for m in means])  # -> ['14.33', '12.50', '14.67']13print(f"{sum(means) / len(means):.2f}")  # -> 13.8314print(oob)  # -> [[2, 5], [1, 4], [3, 6]]

The printout matches the hand computation: 14.33, 12.50, 14.67, bagged 13.83, two rows out per draw.

Watch Out For

The Quick Version

• Draw $B$ resamples of size $n$ with replacement, fit one model per resample, then average numbers or take the majority vote for classes.
• Averaging correlated models leaves $\rho \sigma^2 + (1 - \rho) \sigma^2 / B$. More models shrink only the second term, so $\rho \sigma^2$ is a floor.
• Bias passes through averaging untouched, so bag deep trees and skip linear models.
• A large resample keeps about 63.2 percent of rows and leaves 36.8 percent out of bag, because $(1 - 1/n)^n$ tends to $e^{-1}$.
• Out-of-bag rows give held-out predictions from models that never saw them, so averaging per row validates without setting data aside.
• Shared preprocessing and grouped rows lift correlation between members and remove the variance reduction without warning.

What to Read Next

• Decision Trees
• Bias–Variance Tradeoff
• Random Forests
• Boosting