Ensemble Methods: Boosting and Bagging for Superior Performance

A Delhi Winter Morning, Eight Predictions

Every November, Delhi's Central Pollution Control Board (CPCB) publishes the next day's Air Quality Index on a fixed scale: 0–50 is Good, 51–100 Satisfactory, 101–200 Moderate, 201–300 Poor, 301–400 Very Poor, and 401–500 is Severe — the level at which schools shut and construction halts under the Graded Response Action Plan. Suppose you build one machine learning model to answer a single yes/no question: will tomorrow's AQI cross 400 and hit Severe? Your model looks at wind speed, stubble-burning satellite counts, temperature inversion strength, and traffic density, and it is right 68% of the time on days it hasn't seen before. Not bad. But is 68% the best you can do with the data you already have — or is it the ceiling of asking only one model?

Here is the surprising, provable answer: if you train several different, imperfect models on the same data and combine their opinions correctly, the combination can be reliably more accurate than your single best model — even though no new information was added. Real operational forecasting systems lean on exactly this idea. India's SAFAR (System of Air Quality and Weather Forecasting And Research), run by the Indian Institute of Tropical Meteorology under the Ministry of Earth Sciences, forecasts AQI for Delhi, Mumbai, Pune and Ahmedabad by weighing multiple model runs against each other rather than trusting a single simulation. This chapter makes precise why combining models works, when it works, and gives you the exact arithmetic — not hand-waving — behind the two dominant combination strategies used in every serious machine learning system today: bagging and boosting.

Two Ways an Ensemble Can Win: An Archery Analogy

Picture four archers shooting at a target, each releasing five arrows.

• Archer A's arrows cluster tightly in the upper-left corner, far from the bullseye. Every shot is consistent, but consistently wrong. This archer has high bias, low variance.
• Archer B's arrows are scattered all over the target — some near the bullseye, some at the edge — but their average position is close to the center. This archer has low bias, high variance.
• Archer C's arrows are scattered but centered nowhere near the bullseye: high bias and high variance.
• Archer D lands every arrow inside the bullseye ring: low bias and low variance — the goal, and rarely achievable in one shot.

A single decision tree grown to full depth behaves like Archer B: it can represent almost any pattern in the training data (low bias) but is wildly sensitive to which exact training points it saw (high variance) — change a handful of rows and the whole tree reshapes. A decision stump (a tree with one split) behaves like Archer A: stable across datasets, but too simple to capture real structure (high bias). Ensemble methods exist because these two failure modes have two different cures, and mixing up which cure you need is the single most common mistake students make.

Making "Error" Precise: The Bias-Variance Decomposition

To choose the right cure we first need to derive, not assert, what "error" is built from. Suppose the true relationship is y = f(x) + ε, where ε is irreducible noise with mean 0 and variance σ2ε (measurement error, unmodeled factors — nothing can remove it). You train a model ħD(x) on a random training set D drawn from the population. Because D is random, your fitted model itself is a random quantity; a different draw of Delhi's pollution data from a different winter would fit a slightly different tree. Define h̄(x) = ED[ħD(x)], the average prediction you'd get if you retrained on infinitely many different training sets.

Now expand the expected squared error at a fixed test point, averaging over both the randomness in the noise and the randomness in which training set you happened to draw:

E[(y - h(x))^2] = E[(f(x) + eps - h(x))^2]
                = E[(f(x) - h(x))^2] + E[eps^2] + 2*E[eps]*E[f(x) - h(x)]

The cross term vanishes because the noise ε is independent of the training set and has mean zero, so E[ε] = 0 kills it outright, leaving E[ε2] = σ2ε. For the remaining term, insert and subtract h̄(x):

E_D[(f(x) - h_D(x))^2]
  = E_D[( (f(x) - hbar(x)) + (hbar(x) - h_D(x)) )^2]
  = (f(x) - hbar(x))^2 + E_D[(hbar(x) - h_D(x))^2]
      + 2*(f(x) - hbar(x))*E_D[hbar(x) - h_D(x)]

The last cross term is zero too, because ED[h̄(x) − ħD(x)] = h̄(x) − h̄(x) = 0 by the very definition of h̄. What survives is the clean, three-term identity every ensemble method is built to exploit:

Expected Error = sigma_eps^2  +  Bias(x)^2  +  Variance(x)
where  Bias(x)     = hbar(x) - f(x)
       Variance(x) = E_D[(h_D(x) - hbar(x))^2]

Irreducible noise you cannot touch. Bias measures how wrong your model's average answer is — a structural limitation (too simple, wrong assumptions). Variance measures how much your model's answer swings from one training set to another — an instability limitation (too sensitive). Bagging is a variance cure. Boosting is primarily a bias cure. That single sentence is worth memorizing, because it tells you which tool to reach for.

Bagging: Bootstrap Aggregating

Leo Breiman introduced bagging in a 1996 paper in the journal Machine Learning. The idea: if a full-depth decision tree has high variance because it's overly sensitive to its exact training sample, train many such trees on many different samples and average their predictions. Since we usually have only one dataset, bagging manufactures "different" datasets by bootstrap sampling: draw n rows from your n-row dataset with replacement, so the same row can appear multiple times and roughly a third will be left out entirely.

How much is left out, exactly? The probability a specific row is not chosen in one of the n draws is (1 − 1/n); since draws are independent, the probability it's missed in all n draws is (1 − 1/n)n. For n = 8:

n = 8
p_left_out = (1 - 1/n)**n
print(round(p_left_out, 4))   # 0.3436

Trace it by hand: 0.8752 = 0.765625, squared again gives 0.7656252 = 0.58618..., squared once more gives 0.586182 = 0.34360... — that's 0.8758 by repeated squaring, confirming 0.3436. As n → ∞, this converges to 1/e ≈ 0.3679 (a classic limit: lim (1−1/n)n = e-1). So for large datasets, each bootstrap sample contains about 63.2% of the unique original rows; the remaining ~36.8%, called out-of-bag points, act as a free built-in validation set for that tree since it never saw them during training.

Now the payoff: why does averaging reduce variance, and by how much? Suppose you grow B trees, each individually with variance σ2, and suppose any two trees' predictions have correlation ρ (bootstrap samples overlap heavily, so trees are correlated, not independent). The bagged prediction is H(x) = (1/B) ∑ hb(x). Using Var(∑Xi) = ∑Var(Xi) + ∑i≠jCov(Xi,Xj):

Var(H) = (1/B^2) * [ sum_b Var(h_b) + sum_(b != b') Cov(h_b, h_b') ]
       = (1/B^2) * [ B*sigma^2 + B*(B-1)*rho*sigma^2 ]
       = sigma^2 / B  +  ((B-1)/B) * rho * sigma^2

As B → ∞, the first term vanishes and (B−1)/B → 1, so Var(H) → ρσ2. This is the single most important sentence in this section: no matter how many trees you add, bagged variance cannot fall below ρσ2. Adding trees only kills the σ2/B term; it does nothing to the correlation floor. If your trees are near-identical (ρ → 1), bagging barely helps at all — you're just averaging copies of the same noisy answer. This is exactly why bagging alone is a weaker tool than what comes next.

Random Forests: Attacking the Correlation Term Directly

Breiman's follow-up 2001 paper, Random Forests, asks: if the ceiling is ρσ2, why not lower ρ itself? At every split in every tree, instead of choosing the best split among all p features, a Random Forest restricts the choice to a random subset of features — conventionally √p features for classification. If two features are both strong predictors of Severe AQI (say, wind speed and stubble-fire count), forcing some splits to ignore one of them decorrelates the trees that emerge, actively pushing ρ down rather than just increasing B. This is why Random Forest reliably outperforms plain bagged trees on real data at the same B: bagging alone reduces the σ2/B term; Random Forest additionally attacks the ρσ2 floor.

Boosting: Fixing Bias by Learning From Mistakes, Sequentially

Bagging trains B trees independently and in parallel — each tree never learns from another tree's errors. Boosting does the opposite: it trains weak learners sequentially, and each new learner is deliberately built to focus on the examples the previous learners got wrong. This targets bias, not variance: a single decision stump is a poor model (high bias) precisely because it's forced to be simple, but a weighted sequence of stumps, each specializing in the previous ensemble's blind spots, can represent something none of them could alone.

The canonical algorithm is AdaBoost (Adaptive Boosting), introduced by Yoav Freund and Robert Schapire in a 1997 paper in the Journal of Computer and System Sciences. AdaBoost maintains a weight wi for every training point, starting uniform at wi = 1/n. At each round t: (1) train a weak classifier ht that minimizes the weighted error rate εt; (2) assign that classifier a vote strength αt; (3) increase the weight of every point it got wrong, decrease the weight of every point it got right, so the next weak learner is forced to pay attention to the current failures.

Deriving α: Why That Exact Formula and No Other

The formula for αt is never handed down as folklore here — it falls out of minimizing a specific loss function. AdaBoost's ensemble output is F(x) = ∑t αt ht(x), and the quantity it minimizes is the exponential loss L = ∑i exp(−yi F(xi)), where labels are ±1. Having already fixed Ft−1 and ht, we choose the scalar αt that minimizes the loss given the current point weights wi = exp(−yiFt−1(xi)). Split the sum by whether ht got point i right (yiht(xi)=1) or wrong (=−1), and write εt for the weighted fraction wrong:

J(alpha) = (1 - eps_t) * exp(-alpha)  +  eps_t * exp(alpha)

dJ/dalpha = -(1 - eps_t) * exp(-alpha) + eps_t * exp(alpha) = 0
        =>  eps_t * exp(alpha) = (1 - eps_t) * exp(-alpha)
        =>  exp(2*alpha) = (1 - eps_t) / eps_t
        =>  alpha_t = 0.5 * ln( (1 - eps_t) / eps_t )

Check the shape of this against intuition: if εt = 0.5 (a coin flip, worthless), αt = 0.5·ln(1) = 0 — a useless classifier gets zero vote, exactly as it should. If εt → 0, αt → +∞ — a near-perfect classifier dominates the vote. If εt > 0.5 (worse than random), αt goes negative, which correctly flips the classifier's vote. The formula isn't arbitrary; it is the unique minimizer of exponential loss at that step, and (with substitution back into J) the resulting round's total weight shrinks by a factor Zt = 2√(εt(1−εt)), which is <1 whenever εt ≠ 0.5 — a formal guarantee that weighted training error strictly decreases every single round the weak learner beats a coin flip.

Worked Example: Three Rounds of AdaBoost on Eight Points

Take eight points on a number line at x = 1, 2, ..., 8 with true labels y = +1, +1, +1, −1, −1, −1, +1, +1 — a block of three positives, a block of three negatives, then two more positives. No single threshold ("decision stump") can separate this pattern perfectly, since the positive class sits on both sides of the negative block. Watch how AdaBoost handles that.

Round 1. All eight weights start at 1/8 = 0.125. Checking every candidate threshold, the split x < 3.5 → +1, else −1 gets six of eight right, misclassifying only x=7 and x=8 (both true +1, predicted −1). Weighted error ε1 = 2/8 = 0.25, so α1 = 0.5·ln(0.75/0.25) = 0.5·ln 3 ≈ 0.5493.

import math
eps = 0.25
alpha = 0.5 * math.log((1 - eps) / eps)   # 0.5 * ln(3)
print(round(alpha, 4))   # 0.5493

Update weights: correct points get multiplied by exp(−α1) = 1/√3 ≈ 0.5774, wrong points by exp(+α1) = √3 ≈ 1.7321, then renormalize so all eight weights sum to 1 again. Carrying the exact fractions through: the six correct points (x=1–6) settle at weight 1/12 ≈ 0.0833 each, and the two wrong points (x=7,8) jump to 1/4 = 0.25 each — check: 6×(1/12) + 2×(1/4) = 0.5 + 0.5 = 1. ✓

w = [1/12]*6 + [1/4]*2
print(round(sum(w), 4))   # 1.0

Round 2. With x=7,8 now carrying a quarter of the total weight each, the search for the next best stump is dominated by getting them right. The threshold x < 6.5 → −1, else +1 (note: reversed polarity from round 1) correctly classifies x=4,5,6 (true −1) and x=7,8 (true +1), but now misclassifies x=1,2,3 (true +1, predicted −1). Their combined weight is 3 × 1/12 = 0.25, so ε2 = 0.25 again, and by the same arithmetic α2 = 0.5·ln 3 ≈ 0.5493. Updating weights the same way: x=1,2,3 (now wrong) rise to 1/6 ≈ 0.1667 each; x=7,8 (now consistently right across both rounds) fall to 1/6 ≈ 0.1667 each; x=4,5,6 (right in both rounds) fall further to 1/18 ≈ 0.0556 each. Check: 3(1/6) + 3(1/18) + 2(1/6) = 0.5 + 0.1667 + 0.3333 = 1. ✓

Round 3. Now x=1,2,3 and x=7,8 carry equal, elevated weight (1/6 each), while x=4,5,6 are nearly ignored (1/18 each). The best available stump is x < 7.5 → +1, else −1, which gets x=1,2,3,7 right but misclassifies x=4,5,6 (low weight each, contributing 3/18 = 1/6) and x=8 (weight 1/6) — a weighted error of ε3 = 1/6 + 1/6 = 1/3, giving α3 = 0.5·ln(2) ≈ 0.3466, smaller than the first two votes because this stump is a noticeably weaker classifier.

Final vote. The ensemble prediction is sign(α1h1(x) + α2h2(x) + α3h3(x)). Working through each point (the two 0.5493 votes plus the 0.3466 vote), seven of eight points land unambiguously on the correct side: x=1,2,3 score +0.3466 (correct), x=4,5,6 score −0.7520 (correct), x=7 scores +0.3466 (correct) — but x=8 scores −0.5493+0.5493−0.3466 = −0.3466, landing on the wrong side despite three rounds of correction. Seven of eight (87.5%) after three rounds, not eight of eight.

This is not a mistake in the algorithm — it's an honest and important lesson. AdaBoost's guarantee is that weighted training error strictly decreases each round (via the Zt < 1 shrinkage shown above), not that a fixed, small number of rounds reaches zero error. Real implementations run for 50 to 500+ rounds, or stop early based on validation performance, precisely because a stubborn point like x=8 here can require several more rounds before enough weak learners "gang up" correctly on it. Anyone who tells you boosting always converges in exactly as many rounds as you'd like is oversimplifying; convergence is monotonic, not instant.

Gradient Boosting: Replacing Weights With Residuals

AdaBoost re-weights misclassified points. A more general and now more widely used framework, Gradient Boosting, instead has each new weak learner directly predict the errors of the current ensemble. For squared-error regression, if Fm−1(x) is the ensemble's prediction after m−1 rounds, the negative gradient of the squared loss (y − F(x))2 with respect to F(x) is exactly the residual y − Fm−1(x). So round m simply fits a new tree hm to predict these residuals, and updates Fm(x) = Fm−1(x) + ν·hm(x), where ν (typically 0.01–0.3) is a shrinkage rate that prevents any single round from overcorrecting. Because this is framed as gradient descent in "function space," the same recipe generalizes to any differentiable loss — classification, ranking, quantile prediction — simply by swapping in a different gradient. XGBoost (Chen & Guestrin, KDD 2016) and LightGBM (Ke et al., NeurIPS 2017, Microsoft Research) are highly engineered implementations of exactly this idea, adding second-order (Hessian) information, regularization terms, and histogram-based split-finding for speed — they dominate structured-data competitions precisely because gradient boosting attacks bias so effectively when tuned with care.

A Common Misconception, Corrected

Students who've just seen the σ2/B + ((B−1)/B)ρσ2 formula often conclude: "so I should just train hundreds of bagged trees and my error keeps falling." It does not. The formula's own limit proves the opposite: variance floors at ρσ2 no matter how large B gets, because the covariance terms between correlated trees never disappear — only the 1/B term shrinks. This is precisely why plain bagging plateaus quickly while Random Forest, which actively drives ρ down through feature subsampling, keeps improving for longer. A second, related mix-up: students often treat "boosting" and "bagging" as two flavors of the same idea ("running many models"). They are not interchangeable and cannot be swapped freely: bagging trains independently and in parallel to fight variance; boosting trains sequentially and adaptively to fight bias. Using boosting on a dataset that's already overfitting (high variance, low bias) usually makes things worse, and using bagging on a dataset where your base model is too simple (high bias) barely moves the needle, because bagging was never designed to touch bias at all — look back at the decomposition: averaging identically-biased models leaves the bias term completely unchanged.

Where This Sits in Your Exams

GATE's Data Science and AI (DA) paper explicitly examines bagging, boosting, AdaBoost, and Random Forests as core syllabus topics, so the exact derivations above — the ρσ2 variance floor and the αt derivation from exponential loss — are directly examinable there. CBSE's Artificial Intelligence elective (Classes 9–12) introduces ensemble techniques like Random Forest at a conceptual level as part of its machine learning modules; the bias-variance framing here gives you the "why" that a conceptual-only treatment skips. IIT-JEE and BITSAT do not test machine learning directly — they are Physics/Chemistry/Mathematics examinations — but the logarithm manipulation, series limits ((1−1/n)n → 1/e), and calculus-based optimization you just did to derive αt are the same techniques tested in their calculus and algebra sections.

Active Recall

1. Without looking back, write the three terms of the bias-variance decomposition and state in one sentence what each term physically means.
2. A bagged ensemble has σ2 = 4 and ρ = 0.3. What is the lowest variance this ensemble can ever reach, regardless of how many trees you add? (Answer: ρσ2 = 1.2.)
3. A weak learner has weighted error ε = 0.1. Compute its AdaBoost vote weight α to three decimal places. (Answer: 0.5·ln(9) ≈ 1.099.)
4. In the eight-point worked example, explain in your own words why x = 8 is still misclassified after three rounds even though every individual round strictly reduced weighted training error.
5. True or false, with justification: "Since Random Forest is a type of bagging, adding more trees to a Random Forest will eventually drive its variance to zero." (False — it drives variance toward ρσ2, not zero; Random Forest lowers ρ compared to plain bagging, but doesn't eliminate it.)

Summary

Every prediction error splits into irreducible noise, bias, and variance — a result we derived, not assumed, by expanding the expected squared error around the average-over-datasets prediction h̄(x). Bagging fights variance by averaging independently-trained models on bootstrap resamples, but the variance of that average is provably bounded below by ρσ2, the correlation floor — which is exactly why Random Forest adds random feature subsampling to push ρ down rather than just growing more trees. Boosting fights bias by training weak learners sequentially, each one reweighted by the previous ensemble's mistakes; AdaBoost's vote weight αt = 0.5·ln((1−εt)/εt) is the exact minimizer of exponential loss, guaranteeing (via Zt = 2√(εt(1−εt)) < 1) that weighted training error strictly falls every round a weak learner beats a coin flip — though, as our eight-point example honestly showed, "strictly falls" is not the same promise as "reaches zero in three rounds." Gradient Boosting generalizes the same sequential idea by fitting each new learner directly to the current residuals, the foundation beneath XGBoost and LightGBM. Choosing between them is not a coin flip either: diagnose whether your base model suffers from bias or variance first, then reach for boosting or bagging accordingly.

Think About It

Think about this: How would you explain ensemble methods: boosting and bagging for superior performance 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: boosting and bagging for superior performance 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: boosting and bagging for superior performance to at least 3 other topics you have studied.