Bagging and Boosting: Ensemble Intuition

No single model is perfect. A decision tree with the wrong depth misses the boundary. A linear model can't bend around nonlinear data. Ensemble methods don't solve these problems by building a better model — they build many imperfect models and combine them so their errors cancel.

Anchor dataset: 8-sample loan default dataset.

import numpy as np
import pandas as pd

# 8 samples: [income_$k, credit_score]
X = np.array([
    [25, 580], [32, 610], [45, 650], [60, 680],
    [70, 710], [80, 730], [90, 750], [110, 780]
])
y = np.array([1, 1, 1, 0, 0, 0, 0, 0])  # 1=default
# Class boundary near income≈55k

Why Single Learners Fail

A decision stump (depth=1 tree) on this data splits at income ≤ 55k → predict default, income > 55k → predict no_default. This correctly classifies 7 of 8 samples. The one mistake: sample 3 (income=60k, y=0) sits just over the threshold but is predicted as default.

Changing the training data slightly shifts the boundary and changes which samples are wrong. This sensitivity to small data changes is called high variance. Bagging directly addresses this.

A different failure mode: a model that's too simple to represent the true boundary — high bias. Boosting directly addresses this.

Bagging — Bootstrap AGGregating

Bagging creates diversity by training each model on a different random sample of the data. Each sample is drawn with replacement (bootstrap), so each model sees a slightly different view of the training set.

Step 1: Bootstrap Sampling

Draw n=8 samples WITH REPLACEMENT from the 8 training samples. Each bootstrap has ~63.2% unique samples; the rest are duplicates. The ~36.8% of samples not drawn are called out-of-bag (OOB) samples.

Each bootstrap produces a training set where some samples appear 2–3 times and others are absent. The duplicated samples get more influence over the model trained on that bootstrap.

Step 2: Train One Model Per Bootstrap

Train a decision stump (depth=1) on each bootstrap. Bootstrap 1 has [25,580] twice and [45,650] twice, so these low-income defaulters dominate the weighted split. Each tree learns a slightly different boundary because it saw a different data distribution.

Step 3: Aggregate Predictions

For x_new = [55k income, 670 credit score]:

Two trees predict default, one predicts no_default. Majority vote → default. The ensemble overrides the outlier tree.

OOB Error Estimation

Each sample is OOB for some trees but not others. Use those trees to estimate its class — no separate validation set needed:

• Sample 3 (income=60k, y=0): OOB for Bootstrap 1 only → Tree 1 predicted default (1) → wrong
• Sample 7 (income=110k, y=0): OOB for Bootstrap 1 only → Tree 1 predicted no_default (0) → correct

OOB accuracy from these 2 samples: 50%. This increases substantially with more trees (typically 50–200 trees give reliable OOB estimates). The OOB error approximates the leave-one-out cross-validation error — a free validation score without a dedicated validation split.

Why Bagging Reduces Variance

A single deep decision tree has high variance — small changes to training data produce very different trees. Bootstrap samples create T different "versions" of the training data → T different trees. When these trees disagree (as Tree 3 did above), the majority vote suppresses the outlier. Mathematically:

$\text{Var}\left(\frac{1}{T}{\sum }_{t=1}^T{h}_t(x)\right)=\rho \cdot {\sigma }^2+\frac{1-\rho }{T}\cdot {\sigma }^2$

Where $\rho$ is the average pairwise correlation between trees, ${\sigma }^2$ is the per-tree variance, and $T$ is the number of trees. As $T\to \infty$: $\text{Var}\to \rho {\sigma }^2$. Trees with lower correlation give bigger variance reductions — this is why Random Forest adds feature subsampling on top of bagging.

Boosting — Sequential Error Correction

Boosting is architecturally opposite to bagging. Instead of parallel independent models, boosting trains models sequentially — each model focuses on the errors the previous models made.

Step 1: Initialize Weights

All 8 samples start with equal weight: $w_i=1/n=1/8=0.125$.

Step 2: Train Weak Learner 1

A decision stump (depth=1, income ≤ 55k) — the same stump we started with. It correctly classifies 7 of 8 samples. Sample 3 (income=60k, y=0) is predicted as default but is actually no_default.

Weighted error rate: ${\epsilon }_1=w_3=0.125$ (only sample 3 is wrong, weight = 0.125).

Learner weight: ${\alpha }_1=\frac{1}{2}\ln \left(\frac{1-{\epsilon }_1}{{\epsilon }_1}\right)=\frac{1}{2}\ln \left(\frac{0.875}{0.125}\right)=\frac{1}{2}\ln (7)=0.973$

High ${\alpha }_1$ (close to 1) means this stump is trusted heavily — it was nearly perfect.

Step 3: Update Sample Weights

Upweight the misclassified sample (sample 3) so the next model is forced to get it right:

• Misclassified (sample 3): $w_3\leftarrow 0.125\times e^{0.973}=0.125\times 2.645=0.331$
• Correct (samples 0–2, 4–7): $w_i\leftarrow 0.125\times e^{-0.973}=0.125\times 0.378=0.047$

Normalize (sum = $7\times 0.047+1\times 0.331=0.329+0.331=0.660$):

Sample 3 now carries 50.1% of the total weight. Any stump that ignores sample 3 will have at least 50% weighted error — worse than random guessing.

Step 4: Train Weak Learner 2

The new stump must focus on classifying sample 3 correctly. The best split considering the new weights might be: credit_score ≤ 695 → no_default (sample 3 has credit=680), credit_score > 695 → default. This correctly labels sample 3 (no_default) at the cost of misclassifying high-credit defaulters with low weights.

Step 5: Final Prediction

$f(x)={\alpha }_1{h}_1(x)+{\alpha }_2{h}_2(x)+\dots +{\alpha }_T{h}_T(x)$

$\hat{y}=\text{sign}(f(x))$

Each stump contributes proportionally to its weight ${\alpha }_t$. The final model is a weighted combination of all stumps — a "strong learner" built from many "weak learners."

Bagging vs Boosting — When Each Wins

Ensemble Vocabulary

Test Your Understanding

1. The 63.2% unique sample rate for bootstrap is an asymptotic result: as $n\to \infty$, the probability that a specific sample is NOT drawn at least once is $(1-1/n{)}^n\to 1/e\approx 0.368$. For n=8 (our dataset), the exact probability that sample 0 is OOB is $(7/8{)}^8$. Compute this. Is it close to 36.8%?

2. In Step 3 of Boosting, we said sample 3 gets weight 0.501 after normalization. The 7 correct samples each get weight 0.071. Verify: $7\times 0.071+1\times 0.501=?$. Does it sum to 1? If there's a small discrepancy, where does it come from?

3. Bagging reduces variance but not bias. If the base learner is a depth-1 stump (already high bias), does bagging 100 stumps reduce the bias? Why or why not — and which method would you use instead?

4. Boosting can overfit: if you add a 100th stump that perfectly classifies all remaining noise, later stumps upweight noise samples and start memorizing them. What hyperparameter controls this in practice? What happens to training accuracy vs test accuracy as this hyperparameter increases?

5. The ensemble formula is $f(x)={\sum }_t{\alpha }_t{h}_t(x)$. Stump 1 has ${\alpha }_1=0.973$, stump 2 has ${\alpha }_2=0.641$. For a new sample where both stumps agree (both predict default=1), what is $f(x)$? What would $f(x)$ need to exceed for sign$(f(x))$ to predict default?