Ensemble Methods: Bagging, Boosting, and Stacking

On the evening polling ends in a big Indian general election, no single exit-poll agency's number is trusted on its own. Axis My India might project one seat range, C-Voter another, Today's Chanakya a third — each survey has its own sampling quirks, its own blind spots in certain states, its own random noise from asking a few thousand voters instead of all 900 million. Television channels have learned to do something smarter than pick a favourite pollster: they average several agencies' projections into a "poll of polls." That combined number is, historically, closer to the actual result than most of the individual polls that went into it — not because averaging adds new information, but because it cancels out the part of each survey's error that is random and agency-specific, while the part of the error that every agency shares (a genuinely misleading pre-poll mood, for instance) survives the averaging.

That single idea — a well-chosen combination of imperfect predictors can be more accurate than any one of them — is the entire subject of this chapter. In machine learning it is called an ensemble method, and it is not a minor trick. Random forests, gradient boosting machines, and stacked model blends are, together, the most consistently winning approach in structured-data machine learning competitions, and they power a large share of the tabular-data models running in production today — credit scoring, fraud detection, ad ranking, demand forecasting. You are about to learn exactly why they work, with the algebra to back it up, not just the vocabulary.

Why Does Combining Predictors Ever Help? Bias and Variance

To see precisely what averaging buys you, split a model's prediction error into two separate failure modes. Bias is the error a model makes even with unlimited data, because its assumptions are too simple for the true pattern — a straight-line model trying to fit a curve will always miss, no matter how much data you feed it. Variance is how much a model's predictions swing if you retrained it on a different random sample from the same population — a model with high variance is unstable: change the training data slightly and it gives you a different answer.

A single, fully grown decision tree is a textbook high-variance, low-bias model. It can carve the feature space finely enough to fit almost any pattern (low bias), but change ten rows in the training set and the tree's early splits can flip entirely, cascading into a very different tree (high variance). This is exactly the exit-poll situation: each pollster's estimate is roughly unbiased (no systematic trick makes them all wrong in the same direction, most of the time) but individually noisy. Averaging many roughly-unbiased, noisy estimators cancels their independent noise while leaving their shared bias untouched. That single sentence is the entire justification for bagging, and its opposite — deliberately building a sequence of estimators that attacks the shared, systematic error term — is the justification for boosting. Stacking, the third family, does not reduce bias or variance by a fixed formula at all; it trains a model to discover the best way to combine estimators that may be strong in different regions of the data. All three are "ensembles"; each earns the name for a completely different mathematical reason, which is exactly what the rest of this chapter proves.

Bagging: Bootstrap Aggregating

Bagging — short for bootstrap aggregating — builds many copies of the same base learner (almost always a decision tree), each trained on a different random resample of the training data, then averages their predictions (regression) or takes a majority vote (classification). The randomness that makes each tree different comes from the bootstrap sample: given a training set of n rows, you draw n rows from it uniformly at random with replacement. Some rows get picked two or three times; others get skipped entirely.

How much of the original data does a typical bootstrap sample actually contain? This is worth deriving exactly, because the answer explains a genuinely useful side effect of bagging. Consider one specific training row, x. In a single random draw (one of the n draws that make up the bootstrap sample), the probability that x is not chosen is (1 − 1/n), since each draw picks uniformly among n rows. The n draws are independent of each other, so the probability that x is never chosen across all n draws is:

P(x never selected) = (1 − 1/n)ⁿ

This expression has a famous limit. As n grows large, (1 − 1/n)ⁿ approaches 1/e ≈ 0.3679 (a standard calculus limit — the same one that defines the number e itself). But notice how fast it gets there for realistic training-set sizes:

• n = 10: (0.9)¹⁰ = 0.3487
• n = 100: (0.99)¹⁰⁰ ≈ 0.3660
• n = 1000: (0.999)¹⁰⁰⁰ ≈ 0.3677
• n → ∞: limit = 1/e ≈ 0.3679

By n = 100 you are already within 0.2% of the limiting value. So for any dataset with more than a few hundred rows — which is essentially every real dataset — roughly 36.8% of the original rows are left out of any given bootstrap sample, and the remaining 63.2% appear at least once (some more than once). Those excluded rows are called out-of-bag (OOB) rows for that particular tree, and because that tree never saw them during training, they act as a free, built-in validation set — scikit-learn exposes this directly as oob_score_, so bagged ensembles can estimate their own test performance without setting aside a separate validation split.

How Much Does Averaging Actually Reduce Variance?

Now derive the payoff precisely. Suppose you train B trees, each an estimator with the same variance σ² (they're all trees of similar complexity fitted the same way), and suppose any two trees' predictions have correlation ρ with each other — they are not identical, but because they're all trained on overlapping bootstrap samples of the same underlying data, they are not independent either. Let the ensemble prediction be the plain average of the B trees:

Var(average) = Var( (1/B) Σᵢ f̂ᵢ(x) )

Expanding the variance of a sum using Var(ΣXᵢ) = ΣVar(Xᵢ) + Σᵢ≠ⱼ Cov(Xᵢ,Xⱼ), and dividing by B²:

Var(average) = (1/B²)[ B·σ² + B(B−1)·ρσ² ] = σ²/B + ((B−1)/B)·ρσ²

This is a genuinely important formula, and it says something that surprises most students meeting bagging for the first time: as B → ∞, the first term σ²/B shrinks to zero, but the second term does not — it converges to ρσ², a floor set entirely by how correlated your trees are, not by how many of them you build. Let's see this numerically with σ² = 1 and ρ = 0.2, a realistic correlation for trees bootstrap-sampled from the same data:

• B = 10: Var = 1/10 + (9/10)(0.2) = 0.100 + 0.180 = 0.280
• B = 100: Var = 1/100 + (99/100)(0.2) = 0.010 + 0.198 = 0.208
• B = 1000: Var = 1/1000 + (999/1000)(0.2) = 0.001 + 0.1998 = 0.2008
• B → ∞: Var → ρσ² = 0.200

Going from 10 trees to 100 trees buys you a real drop, from 0.280 down to 0.208. Going from 100 to 1000 — ten times the compute — buys you almost nothing, 0.208 down to 0.2008. Diminishing returns aren't a vague warning here; they fall directly out of the algebra. And this is precisely why Random Forest exists as a separate algorithm rather than "bagging, but with more trees."

Random Forests: Attacking ρ, Not Just B

Since the achievable variance floor is ρσ², the highest-leverage move is lowering ρ — making the trees less correlated with each other — not adding more of them. Random Forest does exactly this with one extra rule on top of plain bagging: at every split in every tree, instead of choosing the best split among all available features, it restricts the choice to a random subset of features (conventionally √p features out of p, for classification). This stops every tree from being dominated by the single strongest predictor — if one feature is overwhelmingly informative, ordinary bagged trees would all split on it near the root, making them highly correlated with each other despite being trained on different bootstrap samples. Forcing each split to ignore most features most of the time breaks that correlation, pushing ρ down and, by the formula above, pushing the achievable variance floor down with it.

from sklearn.ensemble import BaggingClassifier, RandomForestClassifier
from sklearn.tree import DecisionTreeClassifier

bag = BaggingClassifier(
    estimator=DecisionTreeClassifier(),
    n_estimators=200,
    bootstrap=True,
    random_state=42
)
bag.fit(X_train, y_train)

rf = RandomForestClassifier(
    n_estimators=200,
    max_features='sqrt',   # each split sees only a random subset of features -> lowers rho
    oob_score=True,
    random_state=42
)
rf.fit(X_train, y_train)
print(rf.oob_score_)  # accuracy estimated from each tree's ~36.8% held-out rows, no separate val set needed

BaggingClassifier with plain decision trees uses all features at every split, so its trees are more correlated; RandomForestClassifier's max_features='sqrt' is the one line of code implementing the ρ-lowering trick derived above. Both average many trees; only one of them systematically decorrelates them.

Boosting: Learning From Mistakes, Sequentially

Bagging trains B trees independently and in parallel — you could train all of them on B different machines simultaneously with zero coordination between them. Boosting does the opposite: it builds a sequence of typically very weak learners (often decision stumps — trees just one split deep, barely better than a coin flip) one at a time, where each new learner is deliberately trained to fix the mistakes of the ensemble built so far. Where bagging attacks variance by averaging independent noise, boosting attacks bias by directly targeting the errors a simple model class keeps making.

AdaBoost (Adaptive Boosting), the algorithm that established this idea, works by maintaining a weight Dₜ(i) on every training example i at round t — initially uniform, D₁(i) = 1/n for all i. After training weak learner hₜ (predicting +1 or −1) on the current weighted data, compute its weighted error:

errₜ = Σ_{i : hₜ(xᵢ) ≠ yᵢ} Dₜ(i)

— the total weight sitting on the examples it got wrong. This error determines how much say hₜ gets in the final vote, through:

αₜ = 0.5 · ln( (1 − errₜ) / errₜ )

Read what this formula does before using it. As errₜ approaches 0 (a nearly perfect weak learner), the ratio (1−errₜ)/errₜ blows up, so αₜ grows large — a highly accurate learner gets a loud vote. As errₜ approaches 0.5 (no better than guessing), the ratio approaches 1, ln(1) = 0, so αₜ → 0 — a useless learner is silenced, contributing nothing to the final decision. Here is that behaviour laid out numerically:

• errₜ = 0.10 → αₜ = 0.5·ln(9) = 0.5(2.1972) = 1.0986
• errₜ = 0.15 → αₜ = 0.5·ln(5.667) = 0.5(1.7346) = 0.8673
• errₜ = 0.30 → αₜ = 0.5·ln(2.333) = 0.5(0.8473) = 0.4236
• errₜ = 0.45 → αₜ = 0.5·ln(1.222) = 0.5(0.2007) = 0.1003
• errₜ = 0.50 → αₜ = 0.5·ln(1) = 0

Notice that if a weak learner were somehow worse than random (errₜ > 0.5), this formula gives a negative αₜ — which is exactly correct, not a bug: a systematically-wrong classifier becomes informative the moment you flip its votes, and a negative weight does precisely that. In practice, boosting implementations pick weak learners good enough to keep errₜ below 0.5, so this edge case is rarely hit deliberately.

After computing αₜ, every example's weight is updated so that misclassified examples get heavier and correctly classified ones get lighter, forcing the next weak learner to concentrate on the current ensemble's mistakes:

Dₜ₊₁(i) = Dₜ(i) · exp(−αₜ · yᵢ · hₜ(xᵢ)) / Zₜ

where Zₜ is a normalizing constant chosen so the new weights sum to 1, and yᵢ·hₜ(xᵢ) equals +1 when hₜ got example i right and −1 when it got it wrong.

A fully worked round. Take four training examples, all starting with equal weight D₁ = [0.25, 0.25, 0.25, 0.25]. Suppose the first weak learner misclassifies exactly one of them (example 3). Its weighted error is the weight sitting on that one wrong example: err₁ = 0.25. Then:

α₁ = 0.5·ln(0.75/0.25) = 0.5·ln(3) = 0.5(1.0986) = 0.5493

Since (1−err)/err = 3 exactly here, exp(α₁) = √3 = 1.7321 and exp(−α₁) = 1/√3 = 0.5774 — clean numbers, useful for checking your arithmetic. For each of the three correctly-classified examples, the new unnormalized weight is 0.25 × 0.5774 = 0.14434. For the one misclassified example, it's 0.25 × 1.7321 = 0.43303. Summing: Z₁ = 3(0.14434) + 0.43303 = 0.86604. Dividing every unnormalized weight by Z₁ gives the new, normalized weights:

• Three correctly-classified examples: 0.14434 / 0.86604 = 0.1667 each (= 1/6)
• The one misclassified example: 0.43303 / 0.86604 = 0.5000

Check: 3(0.1667) + 0.5000 = 0.5001 ≈ 1.0 ✓ (rounding). One wrong example, out of four, has just been handed half of the entire dataset's weight for the next round. That single example — the hard case — now dominates what the second weak learner is trained to get right. This is boosting's whole mechanism, made concrete: not a vague "focus on mistakes" slogan, but an exact reweighting you can compute by hand.

from sklearn.ensemble import AdaBoostClassifier
from sklearn.tree import DecisionTreeClassifier

ada = AdaBoostClassifier(
    estimator=DecisionTreeClassifier(max_depth=1),  # decision stumps: deliberately weak
    n_estimators=50,
    learning_rate=1.0,
    random_state=42
)
ada.fit(X_train, y_train)

Gradient Boosting: A More General Way to Correct Mistakes

AdaBoost corrects mistakes by reweighting misclassified data points. Gradient boosting generalizes the idea to work with any differentiable loss function by instead fitting each new tree to the ensemble's current error signal directly, treated as a regression target. Formally, build up the model additively — F₀(x) is a simple starting prediction (for squared-error loss, just the mean of y); at each round, fit a tree hₜ(x), then update Fₜ(x) = Fₜ₋₁(x) + ν · hₜ(x), where ν (typically 0.01–0.3) is a shrinkage rate that keeps any single tree from dominating the ensemble.

What does hₜ get trained to predict? For a general differentiable loss L(y, F), it is trained to predict the negative gradient of the loss with respect to the current prediction, −∂L(yᵢ, F)/∂F, evaluated at F = Fₜ₋₁(xᵢ) — these are called pseudo-residuals. This is a scoping point worth being exact about: for the special (but very common) case of squared-error loss on a regression target, L(y,F) = 0.5(y−F)², and the negative gradient works out to exactly rᵢ = yᵢ − Fₜ₋₁(xᵢ) — the plain arithmetic leftover error. That is why gradient boosting is usually introduced as "fit a tree to the residuals," and it is exactly true for squared-error regression, which is also scikit-learn's GradientBoostingRegressor default. But for other losses — log-loss for classification, for instance — the negative gradient is a different expression that only coincides with y−F in the squared-error special case. Do not walk away thinking "gradient boosting always fits y minus F"; it always fits the negative gradient of whichever loss you chose, and squared error is simply the one case where that negative gradient happens to equal the plain residual.

from sklearn.ensemble import GradientBoostingRegressor

gbr = GradientBoostingRegressor(
    n_estimators=100,
    learning_rate=0.1,   # this is the shrinkage rate, nu
    max_depth=3,
    random_state=42
)
gbr.fit(X_train, y_train)
preds = gbr.predict(X_test)

Stacking: A Model That Learns How to Combine Models

Bagging combines many copies of the same algorithm trained on resampled data. Boosting combines a sequence of the same weak-learner type trained on reweighted data. Stacking does something structurally different: it trains several genuinely different algorithms — say, logistic regression, a decision tree, and k-nearest neighbours — all on the same full training data, and then trains one more model, the meta-learner, whose job is to learn how to best combine the base learners' predictions. Where the exit-poll "average" is a fixed, equal-weight combination, a stacked meta-learner might learn something like "trust the decision tree more in states where turnout was unusually high, and trust logistic regression more elsewhere" — a combination rule discovered from data rather than assumed in advance.

There's a subtlety here that a careless implementation gets badly wrong: you cannot train the meta-learner on the base learners' predictions on the same rows those base learners were trained on. A decision tree or a k-NN model can memorize peculiarities of its own training rows; its predictions on those exact rows are unrealistically accurate compared to how it would do on unseen data. If the meta-learner is fed those overly-optimistic, memorized predictions, it will learn a combination rule that looks great in training and falls apart at test time — a textbook case of data leakage. The fix is to generate out-of-fold predictions: split the training data into k folds; for each fold, train the base learners on the other k−1 folds and predict only on the held-out fold. Stitching those held-out predictions back together across all k folds gives, for every training row, a base-learner prediction that row's own model never saw during its training — an honest signal for the meta-learner to learn from.

from sklearn.ensemble import StackingClassifier
from sklearn.linear_model import LogisticRegression
from sklearn.tree import DecisionTreeClassifier
from sklearn.neighbors import KNeighborsClassifier

stack = StackingClassifier(
    estimators=[
        ('lr', LogisticRegression(max_iter=1000)),
        ('dt', DecisionTreeClassifier(max_depth=4)),
        ('knn', KNeighborsClassifier(n_neighbors=7))
    ],
    final_estimator=LogisticRegression(),
    cv=5   # generates out-of-fold predictions for the meta-learner automatically
)
stack.fit(X_train, y_train)

The cv=5 argument is doing exactly the out-of-fold work described above — scikit-learn is not silently reusing training-set predictions; it is running 5-fold cross-validation internally purely to build honest inputs for final_estimator, then, separately, fitting each base learner once more on the full training set for use at prediction time.

Seeing the Three Families Side by Side

Common Misconception: "Bagging and Boosting Are Basically the Same Thing"

Because both families are usually taught back-to-back and both usually involve a pile of decision trees, students very reliably start treating "bagging" and "boosting" as two names for one idea — often compounding the mistake by assuming Random Forest, specifically, is a boosting algorithm. It is not, on either count, and the difference is not cosmetic. Bagging's trees are built independently and in parallel, each blind to what the others are doing, on differently-resampled versions of the same data; their errors are averaged away because the errors are largely uncorrelated, which is a statement about variance. Boosting's trees are built one after another, each one explicitly informed by and correcting the mistakes of every tree before it, on the same data but with reweighted emphasis; this is a statement about bias — a boosted ensemble can represent patterns that a single weak learner structurally cannot, no matter how much data you give it. A practical consequence follows directly: bagging is naturally resistant to overfitting as you add more trees (the variance-floor derivation above shows why more trees can only help or plateau, never actively hurt), whereas boosting, left with too many rounds and no shrinkage or early stopping, can and does overfit, because it keeps chasing ever-smaller residuals, including the residuals that are just noise in the training data. Random Forest belongs firmly in the bagging family; AdaBoost and gradient boosting belong firmly in the boosting family. Knowing which family an algorithm belongs to tells you, immediately, whether "add more estimators" is a safe knob to turn or one that needs to be tuned carefully against a validation set.

Where This Fits in Your Exams

Ensemble methods are not on the JEE Main/Advanced or BITSAT syllabus — both are Physics-Chemistry-Mathematics papers with no machine learning content, and no honest exam-mapping exists there. Where this topic is directly examinable is CBSE's own Artificial Intelligence curriculum, offered as a skill subject for Classes 9–10 (subject code 417) and as an elective for Classes 11–12 (subject code 843), where ensemble techniques and the underlying regression/classification ideas are explicit syllabus items. It is also core material in GATE's Data Science and Artificial Intelligence (DA) paper, whose Machine Learning section names "ensemble methods including bagging and boosting" outright as an examinable topic — so a rigorous grasp of this chapter's derivations is directly useful groundwork if you sit that paper after a CS/AI undergraduate degree. Beyond formal exams, this is precisely the reasoning skill tested in data-science hackathons and Kaggle-style competitions common in Indian engineering colleges' technical fests: knowing why a random forest, a gradient-boosted model, and a stacked blend behave differently — not just how to import them — is what separates a competitor who tunes intelligently from one guessing at hyperparameters.

Check Your Understanding

1. Using Var(average) = σ²/B + ((B−1)/B)ρσ², if trees were perfectly independent (ρ = 0) instead of ρ = 0.2, what would the variance approach as B → ∞, with σ² = 1? Answer: it would approach 0 — the ρσ² floor disappears entirely when trees are uncorrelated, which is the theoretical ideal Random Forest's feature-subsampling is chasing (though real trees from the same dataset can never be made fully independent).

2. A training set has 800 rows. Roughly how many rows are expected to be out-of-bag for any single bootstrap tree? Answer: about 0.368 × 800 ≈ 294 rows.

3. Compute α for a weak learner with weighted error 0.05. Answer: α = 0.5·ln(0.95/0.05) = 0.5·ln(19) = 0.5(2.9444) = 1.4722 — a much louder vote than any of the error rates worked through in this chapter, since 0.05 is a very accurate weak learner.

4. True or false: "Gradient boosting always literally fits a tree to y − F(x)." Answer: False. That equality holds exactly only for squared-error loss (the common regression case). For a general differentiable loss, each tree fits the negative gradient of that loss — the pseudo-residual — which coincides with the plain residual only in the squared-error special case.

5. Why must a StackingClassifier's base-learner predictions be generated out-of-fold rather than by predicting on the same rows the base learners were trained on? Answer: to avoid data leakage — base learners can partially memorize their own training rows, so predictions on those rows are unrealistically accurate; feeding that inflated signal to the meta-learner would teach it a combination rule that fails on genuinely unseen data.

Summary

An ensemble beats a single model only when you understand which failure mode it is attacking. Bagging trains many copies of the same learner independently on bootstrap resamples and averages them, attacking variance; the achievable improvement is capped at ρσ² regardless of how many trees you add, which is exactly why Random Forest's random feature subsampling — lowering ρ directly — matters more than raw tree count once you're past a few hundred estimators. Boosting trains a sequence of weak learners, each one reweighted (AdaBoost) or refit to a residual/pseudo-residual (gradient boosting) to correct the accumulated mistakes of everything trained before it, attacking bias, with a formula αₜ = 0.5·ln((1−errₜ)/errₜ) that automatically silences learners no better than a coin flip. Gradient boosting's "fit the residual" description is exactly correct for squared-error regression and only approximately correct — really, fit the negative gradient of whatever loss you chose — everywhere else. Stacking trains heterogeneous algorithms in parallel and lets a meta-learner discover how to combine them, provided that meta-learner is trained on honest, out-of-fold predictions rather than leaked, memorized ones. Three different mechanisms, three different guarantees — and, on the evidence of a decade of Kaggle leaderboards and production ranking systems, three of the most reliable tools available for turning a collection of merely decent models into one genuinely strong one.

Think About It

Think about this: How would you explain ensemble methods: bagging, boosting, and stacking 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.