4. Ensemble Methods: Bagging

Bagging (Bootstrap AGGregatING), introduced by Breiman (1994), is a parallel ensemble method that reduces variance by training multiple models on different bootstrap samples of the training data and aggregating their predictions.

Bootstrap Sampling

Given training set D of size N, create B bootstrap samples each of size N by sampling with replacement. On average, each bootstrap sample contains ~63.2% unique instances; ~36.8% are left out (out-of-bag instances). This follows from: P[not sampled] = (1 - 1/N)^N -> 1/e ~ 0.368.

Bagging Algorithm

1. For b = 1 to B:

a. Draw bootstrap sample D_b from D (with replacement, size N) b. Train base learner h_b on D_b

2. Classification: Final prediction = majority vote of {h_1,...,h_B}
3. Regression: Final prediction = average of {h_1(x),...,h_B(x)}

Why Bagging Reduces Variance

If each base learner has variance sigma^2 and pairwise correlation rho: Var(ensemble) = rho sigma^2 + ((1 - rho) / B) sigma^2

As B -> infinity, variance converges to rho * sigma^2. Lower correlation between models means greater variance reduction.

Out-of-Bag (OOB) Error

Since each model is trained on ~63.2% of data, the remaining ~36.8% serves as a built-in validation set. OOB error provides an unbiased estimate of generalization error — no separate validation set is needed.

Bagging vs Boosting

Common Pitfalls

• Bagging does NOT reduce bias — a biased model remains biased after bagging
• Too few estimators leaves residual variance
• Highly correlated base learners severely limit the variance reduction benefit

Exam-Ready Summary

• Bagging = bootstrap sampling + parallel training + aggregation
• OOB error approximates cross-validation and is computed for free
• Variance reduces proportionally to 1/B when models are uncorrelated
• Works best with unstable learners (small data change -> large model change)
• Decision trees are ideal base learners: low bias when deep, reduced variance via bagging