Bagging and the Bootstrap: Variance Reduction by Averaging

Ask one student to estimate the number of beans in a jar and you get a noisy guess. Ask a hundred students and average their guesses, and you usually get remarkably close. This "wisdom of crowds" works when the guesses are diverse and their errors partially cancel. Bagging — bootstrap aggregating, introduced by Leo Breiman in 1996 — applies this idea to machine-learning models.

The bootstrap#

The bootstrap (Efron, 1979) creates new datasets by sampling $n$ examples with replacement from the original $n$. Each bootstrap sample:

• has the same size as the original;
• contains some examples multiple times and omits others.

The probability that a given example is not chosen in $n$ draws is

So each bootstrap sample contains about 63.2% of the unique original examples; the remaining ~36.8% are out-of-bag (OOB).

Statisticians use the bootstrap to estimate the sampling variability of any statistic — confidence intervals for a median, an F1 score, or a regression coefficient — without distributional formulas.

Bagging#

1. Draw $B$ bootstrap samples.
2. Train a model $\hat{f}_b$ on each.
3. Aggregate: average for regression, majority vote (or averaged probabilities) for classification:

Why bagging reduces variance#

Suppose each model's prediction at $\mathbf{x}$ has variance $\sigma^2$, and any two have correlation $\rho$. The variance of their average is

• As $B \to \infty$, the second term vanishes, leaving $\rho\sigma^2$.
• If models were independent ($\rho = 0$), variance would fall to zero.
• Because all models see overlapping data, $\rho > 0$, so the benefit is limited by correlation.

Bagging leaves bias roughly unchanged (each model has similar bias). Therefore it helps most for low-bias, high-variance learners such as deep decision trees, and helps little for stable learners like linear regression or k-NN with large $k$.

Out-of-bag evaluation#

Each example is OOB for roughly 37% of the models. Predict each example using only the models that did not see it, and compare with its label. The resulting OOB error is an almost unbiased estimate of test error — obtained for free, without a separate validation set or cross-validation.

import numpy as np
from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
from sklearn.ensemble import BaggingClassifier

X, y = make_classification(n_samples=2000, n_features=20, n_informative=8,
                           flip_y=0.05, random_state=0)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3, random_state=0)

tree = DecisionTreeClassifier(random_state=0).fit(X_tr, y_tr)
print("single deep tree test acc:", round(tree.score(X_te, y_te), 3))

for B in [1, 10, 50, 200]:
    bag = BaggingClassifier(DecisionTreeClassifier(), n_estimators=B, oob_score=B > 1,
                            random_state=0, n_jobs=-1).fit(X_tr, y_tr)
    oob = f"  OOB acc: {bag.oob_score_:.3f}" if B > 1 else ""
    print(f"bagging B={B:>3}: test acc {bag.score(X_te, y_te):.3f}{oob}")

Test accuracy climbs as $B$ increases and then plateaus; the OOB estimate tracks it closely.

Bagging from scratch#

from collections import Counter

def bagging_fit(X, y, B=50, seed=0):
    rng = np.random.default_rng(seed)
    models = []
    for _ in range(B):
        idx = rng.integers(0, len(X), len(X))          # sample with replacement
        models.append(DecisionTreeClassifier().fit(X[idx], y[idx]))
    return models

def bagging_predict(models, X):
    votes = np.stack([m.predict(X) for m in models])   # (B, n)
    return np.array([Counter(col).most_common(1)[0][0] for col in votes.T])

models = bagging_fit(X_tr, y_tr)
print("from-scratch bagging acc:", (bagging_predict(models, X_te) == y_te).mean().round(3))

Practical notes#

• More estimators never hurt accuracy (unlike boosting, bagging does not overfit by adding models); they only cost computation. Stop when OOB error plateaus.
• Training is embarrassingly parallel — each model is independent.
• Variants: pasting (sampling without replacement), random subspaces (sampling features), and random patches (both).
• Bagging reduces the interpretability of a single tree; use permutation importance or SHAP to explain the ensemble.

Bagging in deep learning#

Training several networks with different random seeds and averaging them — a deep ensemble — is one of the most reliable ways to improve accuracy and uncertainty estimates in deep learning. Even without bootstrap resampling, random initialisation and data order provide enough diversity.