Ensemble Learning

§ 01The ensemble idea

A single decision tree is a flawed oracle: deep enough to memorize the training set, shallow enough to miss the pattern. Ensemble learning works around that flaw by combining many imperfect learners into one strong learner. The key insight — sometimes called the wisdom-of-crowds theorem — is that if individual errors are not perfectly correlated, averaging cancels them out.

There are two dominant philosophies for building the crowd:

• Bagging parallel — train many models independently on different views of the data, then average. The goal is to reduce variance.
• Boosting sequential — train models one after another, each one focusing on the mistakes of the previous. The goal is to reduce bias.

§ 02Bias-variance recap

For a model f̂(x) trained on a dataset D, the expected squared error at a point x decomposes as:

• Bias how far the average prediction is from the truth. High when the model is too simple (underfitting).
• Variance how much predictions wobble across different training sets. High when the model is too flexible (overfitting).
• σ² irreducible noise — labelling noise in y. Nothing fixes this.

§ 03Bagging vs Boosting at a glance

§ 04The bagging procedure

Bagging — short for Bootstrap Aggregating — was introduced by Breiman in 1996. The recipe is three steps:

The bootstrap is the heart of the method. Sampling with replacement means each D_b contains some duplicates and is missing roughly 37% of the original points (the famous 1/e ≈ 0.368 probability that a given point is never picked in n draws from n items). Those out-of-bag points become a free validation set.

§ 05Bootstrap sampling — animated

Watch how a bootstrap sample is drawn from an original dataset of 10 points. Some points are picked multiple times; others are never picked (the out-of-bag set, shown faded).

For n = 10, the probability a particular point is excluded from one bag is (1 − 1/n)ⁿ ≈ 0.349. For large n it approaches 1/e ≈ 0.368. Those out-of-bag (OOB) points let you estimate test error with no separate validation set.

§ 06Bagging for regression — worked example

Suppose we want to predict house price from square footage. We bootstrap 5 samples from a training set of 8 houses and fit a small regression tree on each. For a new house at x = 1800 sq ft, the five trees give:

The bagged regression prediction is the simple average:

Notice the individual trees disagree by up to $45k. The average is more stable than any single tree. To quantify the gain, suppose each tree's error has variance σ² = 400 and the pairwise correlation between trees is ρ = 0.3. Then:

As B → ∞, the variance floors at ρσ². The correlation between trees is the bottleneck — which is precisely the problem Random Forest fixes (§08).

§ 07Bagging for classification — worked example

For classification we replace averaging with majority vote. Consider spam detection on one email x. We train B = 7 trees on bootstrap samples:

Votes: 5 spam vs 2 ham → bagged classifier predicts spam.

If we also want a probability, use soft voting — average the predicted class probabilities from each tree:

P(spam) = 0.64 → still spam, with calibrated confidence. Soft voting is generally preferred to hard voting because it preserves uncertainty information.

§ 08Random Forest — fixing the correlation problem

Plain bagged trees share most of their structure: every tree gets to pick from all features at every split, so they all latch onto the same dominant predictor. Their errors stay correlated, and the variance reduction stalls early.

Random Forest (Breiman, 2001) adds a second source of randomness:

This forces trees to use different features, decorrelating their predictions. Recall the bagging variance formula ρσ² + (1−ρ)σ²/B. Random Forest lowers ρ, so the asymptotic floor drops too.

Random Forest = Bagging + per-split feature subsampling. It is one of the most reliably strong baselines in tabular ML.

§ 09Why bagging reduces variance — the math

Let f̂_b(x) denote the prediction of the b-th bagged learner. The bagged predictor is f̂(x) = (1/B) Σ f̂_b(x). Its variance:

Two observations:

• If ρ = 0 (independent learners), variance falls as σ²/B — pure averaging.
• If ρ = 1 (identical learners), variance stays at σ² — bagging does nothing.

What about bias? Each bagged tree has roughly the same bias as a single tree trained on the full data (bootstraps are statistically similar to the original). So:

Bagging trades variance for nothing — it's free, provided you can afford the compute and your base learner has variance to spare. That's why deep, unpruned trees are the perfect base learner.

§ 10Bagging — advantages, disadvantages, when to use

§ 11The boosting procedure

Boosting also builds an ensemble, but the philosophy is the opposite of bagging: instead of training independent learners on different views of the data, boosting trains learners sequentially, each one trying to fix the previous one's mistakes.

The general recipe (additive modelling):

The base learners h_m are usually weak — typically decision stumps or depth-2/3 trees. Each is barely better than random; the magic is in their sum. η is a small learning rate (typically 0.01–0.1) that slows the descent and improves generalization.

Two flavours dominate:

• AdaBoost The original (Freund & Schapire, 1995). Re-weights data: misclassified points become heavier. Works for classification.
• Gradient Boosting Friedman (1999). Each new tree fits the negative gradient of the loss — i.e. the residuals. Works for any differentiable loss: regression, classification, ranking.

§ 12AdaBoost — animated

AdaBoost on a tiny 2-D dataset. At each round we (1) fit a stump that minimizes weighted error, (2) compute its weight α, (3) up-weight the misclassified points so the next stump pays them more attention.

§ 13AdaBoost classification — full numeric walkthrough

Let's do every number. Dataset: 5 points, labels in {−1, +1}:

Initialize uniform weights:

Round 1

Try every possible stump h(x) = sign(x − θ). The stump h₁(x) = +1 if x < 2.5 else −1 classifies points 1,2,3,4 correctly and misclassifies only point 5.

Point 5 — the one we got wrong — now carries half of the total weight. The next stump must deal with it.

Round 2

With these new weights, the best stump is h₂(x) = +1 if x > 4.5 else −1 (correctly classifies point 5 and points 3,4; misclassifies points 1,2).

Round 3

The best stump now is h₃(x) = +1 if 2.5 < x < 4.5 else −1… wait, that's not a single threshold. A proper stump tries every split. With these weights the best simple split is h₃(x) = −1 if x < 2.5 else +1 (correctly handles 3,4,5; wrong on 1,2 — but those have small weight). Let's pick an even better one: h₃(x) = −1 if 2.5 ≤ x ≤ 4.5 else +1 correctly classifies all 5. (For pure stumps we accept that exact zero error is rare — let's use the split that gives ε = 0.166.)

Final classifier

Each weak stump alone had ~20–25% error. Their weighted vote separates the data perfectly. That's boosting in action: a sum of weak learners is a strong learner.

§ 14Gradient Boosting for regression — full numeric walkthrough

Gradient boosting generalizes AdaBoost: instead of re-weighting points, we fit each new learner to the negative gradient of the loss with respect to the current prediction. For squared loss, the negative gradient is exactly the residual — making the procedure especially intuitive.

Dataset: predict y from x.

Use squared loss L = ½ (y − F)², learning rate η = 0.5, and stumps of depth 1.

Step 0 — initialize

The optimal constant under squared loss is the mean:

Step 1 — compute residuals, fit tree 1

Residuals r_i = y_i − F₀(x_i):

Fit a stump on (x, r⁽¹⁾). The best split (minimizing SSE) is at x < 3.5:

Update predictions

Total SSE: 4.37 (down from 10.0 at step 0).

Step 2 — new residuals, fit tree 2

Best split for these residuals is at x < 1.5:

Update F₂(x) = F₁(x) + 0.5 · h₂(x):

Total SSE: 2.26.

After 10 such rounds

Each tree shaves a bit more residual. The total prediction is the sum:

§ 15Gradient Boosting for classification

For binary classification with y ∈ {0, 1} we use the log-loss (cross-entropy):

We don't predict probabilities directly; we predict log-odds F(x) and convert with the sigmoid p = σ(F) = 1/(1+e^{−F}). The negative gradient is beautifully simple:

That's just the prediction error in probability space. So gradient-boosted classification is identical to regression — fit trees to y − p — but in log-odds space.

Numeric example

Dataset: 4 points, 2 positives, 2 negatives.

Step 0: initialize with log-odds of the empirical positive rate:

Step 1: residuals are r⁽¹⁾_i = y_i − p₀ = y_i − 0.5:

Fit a stump. Best split at x < 2.5: left leaf = −0.5, right leaf = +0.5.

With η = 1.0:

Step 2: new residuals = y − p₁:

Same split direction, smaller leaf values. After many rounds, F_M grows large positive on the right, large negative on the left, and p approaches 0 or 1 as appropriate.

The exact same algorithm — fit trees to residuals — works for classification because of the elegant fact that cross-entropy's gradient is just the probability error.

§ 16XGBoost / LightGBM / CatBoost — in a paragraph

Modern gradient boosting libraries are all gradient boosting at heart, with engineering refinements:

All three use the residual-fitting framework from §14 — they just compute splits faster, regularize cleverly, and handle edge cases the textbook version doesn't.

§ 17Why boosting reduces bias — the math

Each round of boosting solves:

By Taylor expansion around F_{m−1}:

Minimizing in h for fixed leaf values gives h* ≈ −g/H. The new tree fits the negative gradient — that's literal gradient descent in function space.

Each iteration takes the loss strictly downward (with small enough η). The training-set bias drops monotonically. If we ran for infinite rounds, training error would hit zero. But at some point, additional rounds start fitting noise — and test error rises. So boosting needs early stopping; bagging doesn't.

§ 18Boosting — advantages, disadvantages, when to use

§ 19Bias-variance side by side

§ 20When to use which

§ 21Who wins? — the empirical verdict

If you only get one answer, here it is:

Some numbers from the literature:

• Kaggle competitions: gradient boosting (XGBoost/LightGBM) wins 60–70% of tabular contests; random forests rarely top leaderboards but make solid stacking components.
• Grinsztajn et al. (NeurIPS 2022) — across 45 tabular benchmarks, GBDT outperformed neural nets and held a small but consistent edge over random forests on accuracy.
• Real-world deployment: random forests dominate where ML teams want a model that "just works" with minimal tuning — credit scoring, fraud baselines, healthcare risk models.

§ 22Reference — at a glance

Companion 06 of 06 · ensemble learning · bagging & bootstrap aggregating · boosting & gradient descent in function space · trade-offs & practical use.