Bagging and the Bootstrap

A learning algorithm is unstable if small changes to the training set produce large changes in the fitted function — full decision trees, nearest-neighbor classifiers with small $k$, and neural networks trained near interpolation are classic examples. Instability is exactly high variance in the The Bias–Variance Tradeoff sense: across many hypothetical training sets drawn from the same distribution, the fitted models disagree wildly with each other even though each is roughly unbiased. The bootstrap is a resampling procedure, introduced by Bradley Efron in 1979, for approximating the sampling distribution of a statistic without knowing the true underlying distribution. Given a dataset $D = \{(x_1, y_1), \dots, (x_n, y_n)\}$, a bootstrap sample $D^{*}$ is formed by drawing $n$ points with replacement from $D$. Because sampling is with replacement, $D^*$ typically contains duplicates of some original points and omits others entirely. Repeating this many times generates many "pseudo-datasets," each a plausible stand-in for what a fresh sample from the true distribution might look like — the empirical distribution of $D$ substitutes for the unknown true distribution.

Bagging applies the bootstrap to model averaging rather than to estimating a statistic's sampling variance. Draw $B$ bootstrap samples $D_1^*, \dots, D_B^*$, fit the base learner (e.g., an unpruned decision tree) on each to get $\hat f_1, \dots, \hat f_B$, and combine them: average the outputs for regression, or take a majority vote for classification. The combined predictor

is what gets deployed. Crucially, bagging changes nothing about the base learning algorithm — it is a meta-algorithm (an ensemble method) that wraps around any base learner, and it is most useful precisely when that base learner is unstable and roughly unbiased.

The mechanism has two independent phases: generating the bootstrap ensemble, then aggregating predictions. There is no coordination between the $B$ training runs — each one is completely independent, which is what makes bagging trivially parallelizable.

Step 1 — Resample. For each $b = 1, \dots, B$, draw $n$ indices uniformly at random with replacement from $\{1, \dots, n\}$, forming $D_b^*$.

Step 2 — Fit. Train the base learner (unchanged, no modification to its algorithm) on $D_b^*$ to obtain $\hat f_b$.

Step 3 — Track out-of-bag points. Record which original training points did not appear in $D_b^*$ — these are the out-of-bag (OOB) points for tree $b$, and they will later serve as a free validation set for that tree.

Step 4 — Aggregate. For a new input $x$: average $\hat f_b(x)$ across all $b$ (regression) or take the plurality vote of the $B$ predicted classes (classification); soft-voting by averaging predicted class probabilities is a common, often better-calibrated, alternative. ``` function BAGGING-TRAIN(D, B, BaseLearner):

# D: training set of n examples (x_i, y_i) n = size(D) models = [] oob_membership = array of size B, each an empty set # indices left out per model for b = 1 to B: sample_indices = [] for i = 1 to n: j = uniform_random_integer(1, n) # draw WITH replacement sample_indices.append(j) D_b_star = { D[j] for j in sample_indices } f_b = BaseLearner.fit(D_b_star) models.append(f_b) in_bag = set(sample_indices) oob_membership[b] = { i in 1..n : i not in in_bag } return models, oob_membership

function BAGGING-PREDICT(models, x, task): predictions = [ f_b(x) for f_b in models ] if task == "regression": return mean(predictions) else: # classification return majority_vote(predictions)

function OOB-ERROR(D, models, oob_membership):

# Estimate test error without a held-out set total_error = 0 counted = 0 for i = 1 to n: voters = [ f_b for b in 1..B if i in oob_membership[b] ] if voters is empty: continue # rare for small n or small B pred_i = aggregate(voters, D[i].x) # average or vote, using ONLY trees

# that never saw point i total_error += loss(pred_i, D[i].y) counted += 1 return total_error / counted ``` Two implementation details matter. First, the number of trees $B$ is not a bias-inducing hyperparameter in the way tree depth is: increasing $B$ never increases variance of the ensemble (it decreases it, subject to diminishing returns) and does not cause overfitting in the classical sense, so $B$ is typically set as large as computational budget allows, then checked for a plateau in OOB error. Second, sampling with replacement from $n$ items into a sample of size $n$ is standard, but variants exist (e.g., subsampling without replacement, "pasting") — the with-replacement choice is specifically what makes the 63.2% figure below hold and what enables the OOB estimate.

Time complexity. If the base learner takes $T(n)$ time to train on $n$ examples (e.g., $T(n) = O(n \log n \cdot d)$ for a decision tree with $d$ features, using presorted feature splitting), then training the full bagging ensemble costs

This is embarrassingly parallel: the $B$ fits share no state, so with $P$ processors the wall-clock time is $O(B \cdot T(n) / P)$. Prediction for a single query costs $O(B \cdot T_{\text{predict}})$, where $T_{\text{predict}}$ is the base learner's per-query cost (e.g., $O(\text{depth})$ for a tree) — again trivially parallelizable, and in practice a constant-factor overhead compared to a single model.

Space complexity. Storing the ensemble requires $O(B \cdot S(n))$ where $S(n)$ is one model's size; for trees this is proportional to the number of leaves, typically $O(n)$ in the worst case for fully grown trees, so $O(Bn)$ total. This is the real cost of bagging: you trade memory and inference-time compute for variance reduction.

Why averaging reduces variance — the derivation. Let $\hat f_1, \dots, \hat f_B$ be i.i.d. (approximately, since bootstrap samples overlap but let's first idealize as independent) predictors, each with variance $\sigma^2$ at a fixed point $x$, and pairwise correlation $\rho$ between any two of them (induced by sharing the same original dataset $D$). The variance of their average is

With each term $\text{Var}(\hat f_b(x)) = \sigma^2$ and $\text{Cov}(\hat f_b, \hat f_{b'}) = \rho \sigma^2$ for $b \ne b'$, and $B(B-1)$ such cross terms:

As $B \to \infty$, this converges to $\rho \sigma^2$ — not zero. This is the central honest fact about bagging: variance reduction saturates. If the base models were perfectly independent ($\rho = 0$), variance would shrink like $\sigma^2/B$, vanishing as $B$ grows. But bootstrap samples are drawn from the same underlying dataset $D$, so $\rho > 0$ inevitably — the models are correlated because they share overlapping data. Bagging's benefit is exactly $(1-\rho)$ of the naive $1/B$ reduction; the residual floor $\rho\sigma^2$ is the irreducible cost of shared training data. (This is precisely the gap that Random Forests attack directly, by injecting extra randomness — random feature subsets at each split — specifically to lower $\rho$ further.)

Bias is (almost) unchanged. Since $\hat f_{\text{bag}}(x) = \frac{1}{B}\sum_b \hat f_b(x)$ and expectation is linear,

for any single $b$ (by the identical-distribution assumption over bootstrap draws). So the bias of the ensemble equals the bias of a single base model trained on a bootstrap resample, which is close to (though not exactly) the bias of a model trained on the original $n$-sized dataset, since each resample is itself a sample of size $n$ from the empirical distribution. Bagging therefore leaves bias essentially untouched while attacking variance — it helps most when the base learner already has low bias (is flexible enough to fit the true signal) but high variance (is unstable). Applying bagging to a high-bias, low-variance learner (e.g., linear regression with few features) yields little benefit, since there is little variance left to remove and the averaging cannot fix systematic bias.

Why $\approx 63.2\%$ unique points. The probability a specific point $i$ is never chosen in $n$ draws with replacement from $n$ items is

So each bootstrap sample contains, in expectation, about $1 - e^{-1} \approx 63.2\%$ of the distinct original points (with repeats making up the rest to size $n$), and about 36.8% of points are held out — exactly the pool used for the OOB estimate. This convergence is fast: even at $n=20$, $(1-1/20)^{20} \approx 0.358$, already close to the limit.

Honest tradeoffs.

• Bagging trades interpretability for stability: a single decision tree can be visualized and explained; an ensemble of hundreds cannot.
• It trades compute and memory for accuracy: $B\times$ the training time and storage.
• It does not help stable, high-bias learners; it can occasionally hurt them slightly due to added noise from resampling.
• It does not remove bias, so if the base learner underfits, bagging will not fix that — only variance shrinks.

Consider a toy 1-D regression problem: true function $y = \sin(x) + \varepsilon$ with $\varepsilon \sim \mathcal{N}(0, 0.3^2)$, and $n = 8$ training points. We fit single-split regression stumps (extremely shallow, unstable trees) at $x = 2$ and bag $B = 5$ of them, tracking bootstrap composition explicitly. Original indices: $1,2,3,4,5,6,7,8$ with $x$-values $0.5, 1.0, 1.8, 2.3, 3.1, 4.0, 4.8, 5.5$.

Two things to notice immediately, both consequences of the math above. First, each sample retains $6$ out of $8$ unique points — $75\%$, higher than the asymptotic $63.2\%$ because $n=8$ is small (finite-sample effect: $(1-1/8)^8 \approx 0.343$, so expected unique fraction is $1-0.343 \approx 65.7\%$, and our small sample of 5 draws shows natural variation around that). Second, every index is OOB for at least one of the five models — for instance, point 2 is OOB in samples 1, 3, and 4, so its OOB prediction averages exactly those three trees' outputs on $x=1.0$, none of which were trained using point 2. Now suppose each stump's predicted value at query $x=2.5$ (near the middle of the range) comes out as:

A single stump (say $\hat f_1$ alone) would report $0.42$ — but a fresh bootstrap draw could easily have produced $\hat f_3$'s $0.35$ or $\hat f_2$'s $0.61$: that spread (roughly $0.35$ to $0.61$) is the variance we are trying to tame. The bagged prediction is the mean:

This value sits centrally among the five stumps' predictions, and — critically — the variance of this averaged estimate across hypothetical resamples of the whole procedure is smaller than the variance of any single stump's prediction, precisely by the factor derived above ($\rho + (1-\rho)/B$ rather than $1$). With only $B=5$ correlated trees the reduction is modest; growing $B$ into the hundreds (as done in practice) pushes this down toward the correlation floor $\rho\sigma^2$.

Bagging is rarely used in its pure textbook form as "bag many unpruned trees" in production today — it has largely been superseded by Random Forests, which is bagging plus deliberate decorrelation via random feature subsets at each split, giving a strictly better variance-reduction floor. But the bagging principle itself — resample, refit, average — is embedded throughout modern machine learning infrastructure:

• Random Forests (scikit-learn's `RandomForestClassifier`/`Regressor`, R's `randomForest`, Spark MLlib) directly generalize bagging and remain a default baseline for tabular data in industry, from credit scoring to genomics.
• Bagged ensembles for uncertainty estimation: the spread of bootstrap models' predictions is used as a practical (if imperfect) proxy for predictive uncertainty, in fields from ecology to epidemiology.
• Statistical inference via the bootstrap (the resampling half of this article, without the aggregation) underlies confidence interval estimation across nearly every applied statistics package, independent of machine learning.
• Bagging as a building block for <a class="wiki-link" href="/wiki/cs-ml-stacking" data-track="wiki_article.body.wiki_link">Stacking and Model Blending</a>: many stacked ensembles use bagged base learners as one "family" of predictors feeding into a meta-learner, since bagging supplies diverse, low-correlation predictions cheaply.
• Distributed computing frameworks exploit bagging's embarrassingly-parallel structure directly — each bootstrap fit is an independent map task, with aggregation as a cheap reduce, making it a natural fit for Spark, Dask, and multi-GPU training pipelines.
• Kaggle-style competition pipelines routinely bag identical model architectures with different random seeds/resamples purely to squeeze out variance reduction on the leaderboard, even outside formal Random Forest implementations.

Ask the tutor: How does adding random feature selection at each split (as in Random Forests) provably lower the correlation ρ between bagged trees, and how much further does variance actually drop in practice?