Ensemble Methods: Bagging and Boosting

In 1906, the statistician Francis Galton visited a livestock fair in Plymouth, England, where 787 people paid a coin to guess the weight of an ox. Almost every individual guess was wrong. But when Galton averaged all 787 guesses, the result was 1,197 pounds against a true weight of 1,198 pounds — an error of less than a tenth of a percent, far better than the best individual guess in the crowd. No single guesser was reliable, yet the crowd, as a collective, was almost exact. This is not a fluke of human psychology. It is a mathematical fact about how errors from independent, unbiased estimators cancel out when averaged — and it is the entire justification for why machine learning builds ensembles: systems that combine many mediocre models into one strong one. This chapter derives, precisely, the two dominant strategies for doing this — bagging and boosting — and shows exactly why each one works, with every number checked by hand.

Why a Single Model Isn't Enough: Bias and Variance

Every prediction error a model makes can be decomposed into two very different sources.

Bias is error from a model being too simple to capture the true pattern — a straight line trying to fit a curve. A high-bias model is wrong in a consistent, predictable direction no matter what training data it sees. Variance is error from a model being too sensitive to the specific training data it happened to see — a deep, unpruned decision tree memorises the quirks of one training set and would produce a wildly different tree if you retrained it on a slightly different sample of the same population. A high-variance model is unstable: it is not consistently wrong, but it is inconsistently right.

These two failure modes need opposite medicine. Bagging is built to fix variance. Boosting is built to fix bias. Confusing the two is the single most common conceptual error students make with ensembles, so hold onto this distinction — we will return to it explicitly.

Two Fundamentally Different Ways to Combine Models

Both bagging and boosting train many weak or moderately accurate models and combine their outputs. The difference is how the individual models are trained and how their votes are weighted.

• Bagging (Bootstrap AGGregatING) trains many models independently and in parallel, each on a different random resample of the training data. Every model gets an equal vote in the end. The models never communicate with each other during training.
• Boosting trains many models sequentially. Each new model is deliberately built to focus on the examples the previous models got wrong, and each model's final vote is weighted by how accurate it actually was. The models form a chain, each one correcting the last.

We now build each one from first principles, with real arithmetic.

Bagging: Bootstrap Aggregating

A bootstrap sample of a dataset with N rows is a new dataset of size N, drawn by sampling with replacement from the original — meaning the same row can be picked more than once, and some rows may not be picked at all. Bagging draws B independent bootstrap samples, trains one model (usually an unpruned decision tree) on each, and combines their outputs by majority vote (classification) or averaging (regression).

import numpy as np

# 8 students' hours studied this week
data = np.array([2, 3, 4, 6, 7, 8, 9, 10])
rng = np.random.default_rng(seed=42)

bootstrap_sample = rng.choice(data, size=len(data), replace=True)
print(list(bootstrap_sample))
# -> [2, 9, 8, 6, 6, 9, 2, 8]

Trace this by hand: the original 8 values are {2,3,4,6,7,8,9,10}, each appearing exactly once. The draw above contains 2 twice, 9 twice, 8 twice, and 6 twice — and the values 3, 4, 7, and 10 were never picked at all. A tree trained on this resample sees a dataset that overweights four students and has never heard of the other four. That is exactly the point: each of the B trees sees a different slice of reality, so their individual mistakes are not identical.

How much data does each bootstrap sample actually leave out?

The probability that one specific row is not chosen on a single draw is (1 - 1/N). Since the N draws are independent, the probability that a specific row is missed by all N draws is:

P(row never picked) = (1 - 1/N)^N

As N grows large, this converges to a famous limit:

lim  (1 - 1/N)^N  =  1/e  ≈ 0.368
N→∞

This follows directly from the standard definition e^(-x) = lim(n→∞) (1 - x/n)^n with x = 1. So for a reasonably large dataset, each bootstrap sample leaves out roughly 36.8% of the original rows on average — these are called out-of-bag (OOB) rows, and because each tree never trained on them, they act as a free, built-in validation set for that tree. This is why Random Forests can report an accuracy estimate without needing a separate held-out test split.

Why averaging actually reduces error: the correlation formula

Suppose each of B bagged trees is an unbiased predictor with the same variance σ^2, and every pair of trees has the same pairwise correlation ρ (they are correlated because every bootstrap sample is drawn from the same underlying dataset). We want the variance of the averaged prediction, T̄ = (1/B)·Σ (i=1 to B) Tᵢ.

Var(T̄) = Var( (1/B) Σ Tᵢ )
        = (1/B²) [ Σᵢ Var(Tᵢ) + Σᵢ≠ᴡ Cov(Tᵢ, Tᴡ) ]
        = (1/B²) [ B·σ² + B(B-1)·ρσ² ]
        = σ²/B + ρσ²·(B-1)/B

As B → ∞, the first term σ^2/B → 0, but the second term does not vanish — it approaches ρσ^2. This is the single most important fact about bagging: adding more trees drives the variance down toward ρσ^2, not toward zero. The residual variance is entirely set by how correlated the trees are with each other. This is precisely why Random Forests add a second trick beyond bagging: at every split, each tree is only allowed to consider a random subset of features (typically √p out of p features), which deliberately decorrelates the trees — lowering ρ further and squeezing out more variance reduction than bootstrap resampling alone can achieve.

Common misconception, corrected: many students assume bagging works because each bootstrap tree becomes a better model. It's the opposite — a tree trained on a bootstrap sample (with ~37% of rows missing and others duplicated) is typically a worse, higher-variance individual model than a tree trained on the full dataset. Bagging's power comes entirely from the cancellation of many independent, unbiased errors when averaged, exactly as in Galton's ox-weight crowd — not from making any single model smarter. This is also why bagging barely helps a low-variance model like linear regression, and helps enormously with high-variance models like deep decision trees.

Boosting: Learning From Your Own Mistakes

Boosting takes the opposite approach: instead of training independent models on random resamples, it trains a sequence of weak learners, where each new learner is explicitly trained to fix the errors of the ensemble built so far. We'll derive the classic algorithm, AdaBoost (Adaptive Boosting), step by step.

Start with N training examples, each given an equal weight wᵢ = 1/N. At each round t:

1. Train a weak learner hₜ (commonly a decision stump — a tree of depth 1) on the weighted data.
2. Compute its weighted error: εₜ = Σ (over i where hₜ(xᵢ) ≠ yᵢ) wᵢ — the total weight sitting on the examples it got wrong.
3. Compute its vote weight: αₜ = (1/2)·ln[(1 - εₜ)/εₜ].
4. Update every example's weight: multiply by e^(-αₜ) if hₜ got it right, and by e^(+αₜ) if it got it wrong; then renormalise so the weights sum to 1.

Step 3's formula for αₜ is not arbitrary — it falls straight out of calculus. AdaBoost is minimising the total weighted exponential loss of the ensemble. After normalising, a fraction (1 - εₜ) of the weight sits on correctly-classified points and a fraction εₜ sits on misclassified points, so the loss as a function of the new vote weight α is:

L(α) = (1 - ε_t)·e^(-α)  +  ε_t·e^(α)

Differentiate with respect to α and set the result to zero to find the minimum:

dL/dα = -(1 - ε_t)·e^(-α) + ε_t·e^(α) = 0
        ε_t·e^(α) = (1 - ε_t)·e^(-α)
        e^(2α) = (1 - ε_t) / ε_t
        α = (1/2)·ln[ (1 - ε_t) / ε_t ]

This confirms the formula and explains its shape: if εₜ = 0.5 (the stump is no better than a coin flip), αₜ = 0 — a useless model gets zero say in the final vote. If εₜ → 0 (a nearly perfect stump), αₜ → ∞ — an excellent model dominates the vote. And if εₜ > 0.5 (worse than random), αₜ turns negative, meaning the ensemble literally inverts that stump's prediction, which is still informative.

AdaBoost, Traced by Hand

Take 8 students. Feature x is hours studied this week; the true label is whether they passed a test. Six follow the obvious pattern; two — students 4 and 5 — studied a lot but still failed (perhaps they skipped every class), breaking the simple "more hours = pass" rule.

Round 1. Every student starts with weight wᵢ = 1/8 = 0.125. The best stump available is "if hours ≥ 5.5, predict Pass, else Fail." This correctly classifies students 1, 2, 3 (low hours, Fail) and 6, 7, 8 (high hours, Pass) — six students — but wrongly predicts Pass for students 4 and 5, who studied a lot yet failed.

ε₁ = weight on {4, 5} = 1/8 + 1/8 = 0.25
α₁ = 0.5 · ln((1 - 0.25)/0.25) = 0.5 · ln(3) ≈ 0.5493

Now update every weight. Correct students get multiplied by e^(-α₁) = 1/√3 ≈ 0.5774; the two wrong students get multiplied by e^(+α₁) = √3 ≈ 1.7321. Before normalising, the six correct students each sit at 0.125 × 0.5774 = 0.07217 and the two wrong ones at 0.125 × 1.7321 = 0.21651. These sum to 6(0.07217) + 2(0.21651) = 0.86603. Dividing every weight by this total to renormalise:

Students 1,2,3,6,7,8 (correct):  0.07217 / 0.86603 = 1/12 ≈ 0.0833 each
Students 4,5 (wrong):            0.21651 / 0.86603 = 1/4  = 0.25   each

Check: 6×(1/12) + 2×(1/4) = 0.5 + 0.5 = 1.0  ✓

Notice what just happened: the two students the stump got wrong now carry three times the weight of the six it got right (1/4 versus 1/12). Round 2's weak learner is trained on these weights, so it is under heavy pressure to get students 4 and 5 right, even at the cost of other students.

Round 2. A second stump, this time splitting on a different feature — assignments completed, z — with rule "if z ≥ 6, predict Pass, else Fail," correctly handles students 4 and 5 (both have low z, correctly predicted Fail) along with 2, 3, 6, 7, 8. It makes exactly one mistake: student 1, who happens to have z = 7 (high), so the stump predicts Pass — but student 1's true label is Fail. That single mistake sits entirely on a student with weight 1/12.

ε₂ = weight on {student 1} = 1/12 ≈ 0.0833
α₂ = 0.5 · ln((1 - 1/12)/(1/12)) = 0.5 · ln(11) ≈ 1.1989

This is the honest, weighted-error-driven reason round 2 earns a much louder vote than round 1: ε₂ ≈ 0.083 is genuinely lower than ε₁ = 0.25, because the round-2 stump got right precisely the two heavily-upweighted students that round 1 missed, at the cost of a single lightly-weighted student. Its vote weight, α₂ ≈ 1.199, is a little over twice α₁ ≈ 0.549 — a direct, mechanical consequence of the formula, not a coincidence.

The final ensemble vote

The combined classifier is H(x) = sign(α₁h₁(x) + α₂h₂(x)), using +1 for Pass and -1 for Fail. Check it on the two students who caused trouble:

Student 4:  h₁ = +1 (wrong),  h₂ = -1 (correct)
  vote = 0.5493·(+1) + 1.1989·(-1) = -0.6496  → Fail  ✓ CORRECT

Student 1:  h₁ = -1 (correct), h₂ = +1 (wrong)
  vote = 0.5493·(-1) + 1.1989·(+1) = +0.6496  → Pass  ✗ WRONG

The ensemble now correctly handles student 4 — the case round 1 alone got wrong — because round 2's confident, correct vote outweighs round 1's single incorrect vote. But it introduces a new error on student 1, who round 1 got right and round 2 got wrong. This is boosting working exactly as designed: it is a relentless error-correction process, not a magic trick that fixes everything at once. If training continued, student 1's weight would rise sharply for round 3, forcing the next stump to prioritise fixing that specific mistake.

A Visual Comparison

Bagging vs Boosting: Choosing the Right Tool

These two strategies solve different problems, so their trade-offs run in opposite directions.

• What each one fixes. Bagging averages away variance from unstable, high-variance base models (deep trees). It does very little for a model that is systematically biased, because averaging many equally-biased models just gives you the same bias. Boosting attacks bias directly, by repeatedly forcing new learners to correct the ensemble's remaining errors — it can turn a collection of learners barely better than a coin flip into a highly accurate ensemble.
• Parallelism. Bagging's B trees are fully independent, so they can be trained simultaneously on B different machines. Boosting is inherently sequential — round t cannot start until round t-1's weights are known — making it slower to train, though modern implementations like XGBoost and LightGBM use aggressive engineering (histogram binning, parallel split-finding within a single tree) to make each round fast even though the rounds themselves are sequential.
• Sensitivity to noisy labels and outliers. This is where boosting's biggest weakness shows up. Because misclassified points get their weight multiplied by e^(αₜ) every round, a single mislabelled training example can accumulate enormous weight over many rounds, dragging every subsequent weak learner toward fitting that one bad label. Bagging has no such mechanism — a mislabelled row simply appears in roughly 63% of bootstrap samples like any other row, with no runaway weight growth, making it noticeably more robust to noisy or corrupted data.
• Overfitting behaviour. A frequently-cited surprising empirical result (formally explained by Schapire, Freund, Bartlett, and Lee's 1998 "margin theory" of boosting) is that AdaBoost's test error often keeps falling even after its training error hits exactly zero, because later rounds keep increasing the confidence margin on already-correct points. This does not mean boosting is immune to overfitting — with enough rounds on noisy data, it can and does overfit, precisely because of the outlier-weight problem above.

Exam Relevance

Ensemble methods sit at the intersection of statistics and algorithms, which makes them a favourite testing ground across exams. For CBSE board and school-level AI electives, expect conceptual questions distinguishing bagging from boosting and identifying Random Forest as a bagging-family algorithm. For engineering entrance and GATE-style machine learning questions, the bias-variance decomposition, the AdaBoost weight-update arithmetic, and the αₜ derivation from exponential loss are exactly the kind of "derive, don't just recall" questions that separate rote answers from understood ones — the calculation you traced by hand above is a realistic worked-example format for such questions. If you can reproduce the round-1/round-2 table from scratch, including why α₂ came out larger than α₁, you understand the algorithm, not just its name.

Summary

• Ensembles combine many models because independent errors partially cancel when averaged — the same principle behind Galton's ox-weight crowd.
• Bagging trains B models independently and in parallel on bootstrap resamples (each leaving out ~36.8% of rows, by the limit (1 - 1/N)^N → 1/e), then averages/votes with equal weight. It reduces variance toward the floor ρσ^2 set by inter-tree correlation — which is exactly why Random Forest adds random feature subsampling to push ρ lower still.
• Boosting (AdaBoost) trains models sequentially, up-weighting misclassified examples after each round and giving each model a vote αₜ = (1/2)·ln[(1 - εₜ)/εₜ] proportional to its own weighted accuracy — a formula derived by minimising exponential loss, not asserted by fiat.
• Bagging targets variance and tolerates noisy labels well; boosting targets bias and is more powerful on clean data but vulnerable to runaway weight growth on mislabelled points.

Check Your Understanding

1. In the worked example, suppose a hypothetical round 3 stump achieves weighted error ε₃ = 0.05. Compute α₃ and compare it to α₂ ≈ 1.199. Which round now has the loudest vote, and does that match your intuition about what a low weighted error should earn?
2. A stump has weighted error ε = 0.5. Use the formula to show α = 0, and explain in one sentence, in terms of the exponential-loss derivation, why this is the correct behaviour rather than a special-cased rule.
3. You are choosing between bagging and boosting for a dataset you know contains a meaningful number of mislabelled rows (a common real-world situation, e.g. crowd-sourced labels). Which would you pick, and justify it using the weight-update mechanics of each method, not just a memorised rule of thumb.
4. Explain why increasing B (the number of bagged trees) beyond a few hundred rarely improves a Random Forest much further, using the variance formula σ^2/B + ρσ^2(B-1)/B rather than just saying "diminishing returns."

Think About It

Think about this: How would you explain ensemble methods: bagging and boosting to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Practice Exercises

Now it is time to practice! Complete these challenges to solidify your understanding:

• Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
• Exercise 2: Find a real-world example where ensemble methods: bagging and boosting is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
• Exercise 3: Create a mind-map connecting ensemble methods: bagging and boosting to at least 3 other topics you have studied.