Boosting, AdaBoost & Gradient Boosting: Learning From Your Mistakes, Sequentially

Imagine you're training a junior doctor. After each patient, instead of starting fresh,
you hand them a list of the exact patients they diagnosed incorrectly
and ask them to focus on those. The next rotation, they're better at those edge cases.
You keep doing this, iteration after iteration, each time targeting the current weaknesses.

After 200 iterations, you don't have a junior doctor anymore.
That's boosting — and it's the engine behind XGBoost.

01 — Sequential Correction vs Parallel Averaging

Day 11 showed how Random Forest builds trees in parallel — each tree independent, each seeing a random slice of data, all voting together at the end. Variance drops because uncorrelated errors cancel. Boosting is the philosophical opposite. Trees are built one at a time, each one seeing the same data but with its attention redirected toward the examples the previous trees got wrong.

02 — Weak Learners: Why Stumps Are the Building Block

Both AdaBoost and Gradient Boosting use weak learners — models that are only slightly better than random guessing. The most common weak learner is a decision stump: a decision tree with exactly one split (depth=1). It checks one feature against one threshold and makes one decision. That's it.

03 — AdaBoost: Weights Updating Step by Step

AdaBoost's mechanism is best understood through a worked example with real numbers. Let's trace 3 rounds on 8 training examples manually — watching exactly how the weights change after each mistake.

The worked example: 8 training examples, labels ±1, starting with equal weights of 1/8 = 0.125 each.

import numpy as np

# 8 training examples with labels +1 or -1
y_true = np.array([1, 1, 1, 1, -1, -1, -1, -1])

# Simulate 3 stumps' predictions (in practice, these come from training)
# Stump 1: misclassifies examples 5, 6, 7 (indices 4,5,6)
# Stump 2: misclassifies examples 1, 2, 3 (indices 0,1,2)
# Stump 3: misclassifies examples 3, 4 (indices 2,3)
stumps = [
    np.array([ 1,  1,  1,  1,  1,  1, -1, -1]),  # wrong on [4,5]
    np.array([-1, -1,  1,  1, -1, -1, -1, -1]),  # wrong on [0,1]
    np.array([ 1,  1, -1, -1, -1, -1, -1, -1]),  # wrong on [2,3]
]

weights = np.ones(8) / 8   # start: all examples equal, weight = 0.125
alphas  = []

print(f"{'Round':<6} {'ε (weighted err)':>17} {'α (model weight)':>17} {'Updated weights (top 4)'}")
print("-" * 75)

for t, stump_preds in enumerate(stumps, 1):
    correct = (stump_preds == y_true)
    epsilon = weights[~correct].sum()               # weighted error
    alpha   = 0.5 * np.log((1 - epsilon) / epsilon)  # model's vote weight
    alphas.append(alpha)

    # Update: wrong examples get heavier, correct get lighter
    weights *= np.exp(-alpha * y_true * stump_preds)
    weights /= weights.sum()                         # normalize to sum=1

    wrong_idx = np.where(~correct)[0]
    print(f"  {t:<4} {'wrong: '+str(wrong_idx.tolist()):<22} ε={epsilon:.3f}  α={alpha:.3f}   w={weights.round(3).tolist()}")

# Final prediction: weighted sum of all stumps
print(f"\nFinal alphas: {[round(a,3) for a in alphas]}")
final_scores = sum(a * p for a, p in zip(alphas, stumps))
final_preds  = np.sign(final_scores)
accuracy     = (final_preds == y_true).mean()
print(f"Final scores: {final_scores.round(3).tolist()}")
print(f"Final predictions: {final_preds.astype(int).tolist()}")
print(f"True labels:       {y_true.tolist()}")
print(f"Accuracy after 3 rounds: {accuracy:.0%}")

04 — Gradient Boosting: Gradient Descent in Prediction Space

Gradient Boosting is the deeper, more general idea. To understand it, you need to understand the distinction between two kinds of gradient descent — one you already know, one that's subtle and powerful.

This is why Gradient Boosting is so general: you can swap the loss function and the residuals change automatically. For regression (squared error), residuals = y − ŷ. For classification (log loss), the "pseudo-residuals" are the gradient of log-loss with respect to the current predictions. The algorithm is identical — only the residual formula changes.

05 — Gradient Boosting Residuals: Computed Step by Step

Here's the mechanism made concrete — watch each tree's residuals shrink as the ensemble improves:

import numpy as np

# Tiny regression problem: 6 examples, true values y
y     = np.array([2.5, 5.0, 1.0, 8.0, 3.5, 6.5])
eta   = 0.5   # learning rate

# Round 0: initialise with the mean — the dumbest baseline
F = np.full_like(y, y.mean())
print(f"Mean(y) = {y.mean():.2f}  — this is F₀, our starting prediction\n")

print(f"{'Round':<6} {'Tree predicts residuals':>26}  {'New prediction F':>20}  {'MSE':>7}")
print("-" * 72)

for t in range(1, 5):
    residuals = y - F           # what the current ensemble got wrong
    mse_before = (residuals**2).mean()

    # In practice a shallow tree fits residuals; here we simulate the tree's output
    # by using half the residual (tree captures part of the signal)
    tree_pred = residuals * 0.7  # realistic: tree fits ~70% of the residual pattern

    F = F + eta * tree_pred      # update prediction: add small correction
    mse_after = ((y - F)**2).mean()

    print(f"  {t:<4} residuals={residuals.round(2).tolist()}  F={F.round(2).tolist()}  MSE={mse_after:.3f}")

print(f"\nAfter 4 rounds, MSE dropped from {((y-y.mean())**2).mean():.3f} → {((y-F)**2).mean():.3f}")
print(f"Predictions: {F.round(2).tolist()}")
print(f"True values: {y.tolist()}")

06 — Learning Rate: Why Slow Learning Generalises Better

The learning rate η is the most important hyperparameter in boosting. It controls how much of each tree's correction to trust. Small η = tiny steps = requires many more trees = typically better test performance. This is counterintuitive — why would learning slower produce a better result?

07 — Full Code: AdaBoost vs GradientBoosting vs Random Forest

Three models, same dataset, same output format — so the numbers tell the story directly:

import numpy as np
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split, cross_val_score
from sklearn.tree import DecisionTreeClassifier
from sklearn.ensemble import (AdaBoostClassifier,
                                   GradientBoostingClassifier,
                                   RandomForestClassifier)

data = load_breast_cancer()
X, y = data.data, data.target
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.2, random_state=42)

# ── Baseline: single stump (what AdaBoost uses as its weak learner) ──────
stump = DecisionTreeClassifier(max_depth=1, random_state=42)
stump.fit(X_tr, y_tr)

# ── AdaBoost: 200 stumps, weighted vote ──────────────────────────────────
ada = AdaBoostClassifier(
    estimator=DecisionTreeClassifier(max_depth=1),  # depth-1 stumps
    n_estimators=200,
    learning_rate=0.5,
    random_state=42
)
ada.fit(X_tr, y_tr)

# ── GradientBoosting: shallow trees, small lr, subsample ─────────────────
gb = GradientBoostingClassifier(
    n_estimators=200,
    learning_rate=0.05,   # small steps → better generalisation
    max_depth=3,           # shallow trees, not stumps
    subsample=0.8,         # stochastic: 80% of data per tree
    random_state=42
)
gb.fit(X_tr, y_tr)

# ── RandomForest for comparison ───────────────────────────────────────────
rf = RandomForestClassifier(n_estimators=300, oob_score=True,
                             n_jobs=-1, random_state=42)
rf.fit(X_tr, y_tr)

# ── Compare all four ─────────────────────────────────────────────────────
models = [
    ("Single Stump     ", stump),
    ("AdaBoost (200)   ", ada),
    ("GradientBoosting ", gb),
    ("RandomForest     ", rf),
]

print(f"{'Model':<20} {'Train':>6} {'Test':>6} {'CV Mean':>8} {'CV Std':>7}")
print("-" * 55)
for name, model in models:
    cv = cross_val_score(model, X, y, cv=5)
    print(f"{name} {model.score(X_tr,y_tr):>6.3f} {model.score(X_te,y_te):>6.3f} {cv.mean():>8.3f} {cv.std():>7.3f}")

# ── GradBoost error curve: watch it drop monotonically ───────────────────
print(f"\n── GradientBoosting learning curve ──")
train_errors = [1 - s for s in gb.staged_score(X_tr, y_tr)]
test_errors  = [1 - s for s in gb.staged_score(X_te,  y_te)]
for t in [1, 5, 10, 25, 50, 100, 150, 199]:
    print(f"  Round {t:>3}: train_err={train_errors[t]:.4f}  test_err={test_errors[t]:.4f}")
best_round = int(np.argmin(test_errors))
print(f"  Best round: {best_round} (test_err={test_errors[best_round]:.4f})")

# ── Early stopping: how many trees do you actually need? ─────────────────
print(f"\n── Early Stopping (patience=10) ──")
best, wait, stopped = 1.0, 0, 200
for t, te in enumerate(test_errors, 1):
    if te < best - 1e-4: best, wait = te, 0
    else: wait += 1
    if wait == 10: stopped = t - 10; break
print(f"  Would stop at round {stopped} (best test_err={best:.4f})")
print(f"  Using {stopped} trees instead of 200 saves {(1-stopped/200):.0%} of training time")

08 — When to Choose Boosting Over Bagging

09 — A Thought to Sit With

10 — Coming Up Next

Day 13 — XGBoost & LightGBM. These aren't new algorithms — they're engineering masterpieces built on top of Gradient Boosting that run 10–100× faster, handle missing data automatically, and add built-in regularisation on the trees themselves. They're the workhorses of production ML and the most-used models in competitive data science. Now that you understand the foundation, seeing what was added and why will make complete sense.

11 — Go Deeper

▶ StatQuest: AdaBoost, Clearly Explained
YouTube · 22 min · The definitive visual walkthrough of AdaBoost's weighting mechanism. Watch after reading §03.

▶ StatQuest: Gradient Boost Part 1 (Regression)
YouTube · 15 min · Residual fitting explained visually from scratch — the companion video to §05.

▶ Greedy Function Approximation: A Gradient Boosting Machine — Friedman (2001)
The original paper by Jerome Friedman. Section 4 ("Steepest-Descent") is where "gradient descent in function space" is formalised. Surprisingly readable — the residuals-as-gradients idea becomes very clear in 3 pages.