AdaBoost

What this chapter covers

Back in week 1 we built a decision stump: one feature, one threshold, a single straight cut. It's the weakest useful classifier there is, and on hard data it barely clears a coin flip. This chapter takes that same stump and does something that shouldn't work — it stacks a pile of them into one of the strongest classifiers of the pre-deep-learning era.

The trick is AdaBoost. It trains the stumps in sequence, and each new stump is told to care most about the points the previous ones got wrong. You do that by carrying a weight on every training point: fit a stump on the weighted data, give it a vote sized to how well it did, then crank up the weight on whatever it missed so the next stump leans that way. Repeat fifty times and a boundary no single line could ever draw emerges from a stack of lines.

We build the whole thing from scratch in NumPy — the weighted stump, the vote, the reweighting, the final tally — then let scikit-learn build the same ensemble and check the numbers land in the same place. And you get to watch it happen: one boosting round per frame, the hard points visibly swelling and pulling the next stump toward them while the ensemble boundary sharpens.

A bit of history

AdaBoost came out of a theoretical question that sounds like a riddle. In 1990 Robert Schapire asked whether a "weak" learner — one that only has to do slightly better than random guessing — could be boosted into a "strong" one that gets arbitrarily close to perfect. The surprising answer was yes, and it wasn't just a proof; it was a recipe.

Yoav Freund and Schapire turned that recipe into a practical algorithm in a 1995 conference paper, published in full as "A decision-theoretic generalization of on-line learning and an application to boosting" in 1997. They called it AdaBoost, short for adaptive boosting — adaptive because each round adapts to the last one's mistakes. It worked embarrassingly well, it was almost trivial to implement, and for a decade it was the thing you reached for when you wanted accuracy off the shelf. In 2003 the two of them won the Gödel Prize for it, which is roughly the theory world's way of saying this one mattered.

The weak learner in the original demos, and the one we use here, is the decision stump from week 1. That's the through-line worth holding onto: the humblest model in the course is the atom AdaBoost is built from.

The intuition

Here's the data we'll work on. Two classes, and they're arranged the one way a stump can't handle: concentric. One class sits in a blob at the center, the other wraps around it. There is no vertical or horizontal line you can draw that puts most of one class on one side and most of the other on the other — a single stump tops out around 67% here, barely better than guessing.

Now imagine training stumps in a row. The first one draws its best single line and gets a chunk of the plane right and a chunk wrong. Instead of throwing it away, we keep it, and we make a note: these points over here, the ones it missed, those matter more now. The second stump trains on that note — it's graded on the weighted data, so getting the flagged points right is worth more than getting the easy ones right, and it draws a different line to chase them. Its misses get flagged in turn. Keep going and you accumulate a committee of stumps, each an expert on a different slice of the hard cases, and each with a vote proportional to how trustworthy it was. The committee's weighted majority carves the ring that no member could carve alone.

That's the whole idea, and the reason it works is that every round is forced to work on the part of the problem the previous rounds found hardest. Nothing gets to coast on the easy points forever.

The math

Labels are in $\{-1, +1\}$ — not $\{0, 1\}$ — because that choice makes the whole update collapse into sign arithmetic. Each weak stump is a function $h_t$ that outputs $h_t(x) \in \{-1, +1\}$, and every training point $i$ carries a weight $w_i^{(t)}$ at round $t$, starting uniform at $w_i^{(1)} = 1/N$.

The stump for round $t$ is the one that minimizes the weighted error — the total weight sitting on the points it gets wrong:

Because the weights sum to one, $\varepsilon_t$ is a number between 0 and 1, and with uniform weights it's just the ordinary miss rate. From it we compute the stump's vote, $\alpha_t$:

Look at what that does. A stump with $\varepsilon_t = 0.5$ is a coin flip and gets $\alpha_t = 0$ — no say at all. A stump better than chance gets a positive vote that grows as its error shrinks; a perfect stump would get an infinite one. Then we reweight, pushing weight onto the points this stump missed:

The product $y_i \, h_t(x_i)$ is $+1$ when the stump is right and $-1$ when it's wrong, so correct points get multiplied by $e^{-\alpha_t}$ and shrink, wrong points by $e^{+\alpha_t}$ and grow. $Z_t$ is just the normalizer that keeps the weights summing to one. Finally, the ensemble predicts by a weighted vote of all $T$ stumps, and takes the sign:

Five formulas, and the last four are one line of code each. That's the whole algorithm.

What it's good at, what it isn't

AdaBoost's strength is that it turns a model you'd never ship on its own into one you might. Give it a weak learner that's only a little better than random and it will drive training error down fast, often to zero, and — this is the part that surprised people — test error tends to keep dropping even after training error hits the floor, because the margins keep widening. It has almost no knobs. There's the number of rounds and the choice of weak learner, and that's essentially it. No feature scaling, no distance metric, no kernel to pick.

The weakness is the flip side of the whole mechanism. AdaBoost chases its mistakes, and it can't tell a genuinely hard point from a mislabeled one or an outlier. A point that's just noise gets missed round after round, so its weight climbs and climbs, and eventually the ensemble is contorting itself to fit garbage. On clean data that relentlessness is a feature; on noisy data it's how AdaBoost overfits. You'll see a hint of it in this very chapter — our test accuracy peaks partway through and then sags as later rounds start fitting the split's quirks rather than its signal.

The data

The dataset is a make_gaussian_quantiles snapshot from scikit-learn: 200 points in two dimensions, split into two classes of 100 by how far they fall from the center of a Gaussian. Class A is the inner blob, class B the surrounding shell. It's the canonical AdaBoost demo for a reason — it's the simplest 2-D layout where a single axis-aligned cut is hopeless but a boosted stack is not. The scatter above is the whole of it; the CSV is committed under data/ and the README notes exactly how it was generated.

We split it 140 for training and 60 for test, seeded, and every number in this chapter comes from that split via data/results.json.

Build it, one function at a time

Seven small functions, no library. Same order I'd write them at a terminal: the weak learner first, then the pieces that turn a sequence of weak learners into a strong one.

Start with the stump. It's week 1's threshold classifier with two changes — the labels are $\{-1, +1\}$ now, and there's a polarity bit so the split can face either direction:

def stump_predict(X, stump):
    """A decision stump: one feature, one threshold, one direction.

    `polarity` +1 means predict +1 on the high side of the threshold, -1 on the
    low side; polarity -1 flips it. This is the week-1 threshold classifier with
    its labels moved to {-1, +1} and a direction bit so the split can point
    either way. Returns an (N,) array of ±1 predictions.
    """
    col = X[:, stump["feature"]]
    pred = np.ones(len(X))
    if stump["polarity"] == 1:
        pred[col < stump["threshold"]] = -1.0
    else:
        pred[col >= stump["threshold"]] = -1.0
    return pred

AdaBoost never scores a stump by plain accuracy; it scores it by weighted error, the total weight on the points it misses. With uniform weights that's the ordinary miss rate, but once the weights spread out it's what makes a stump care about the flagged points:

def weighted_error(y, pred, w):
    """The fraction of weight sitting on misclassified points.

    Not the raw miss rate — each mistake is counted by its sample weight w, so a
    point AdaBoost has flagged as hard costs more to get wrong. With uniform
    weights this is exactly the ordinary error rate.
    """
    return float(w[pred != y].sum())

Fitting a stump is the same brute-force search as week 1, now minimizing weighted error over every feature, every threshold between adjacent values, and both polarities. It returns the stump and its predictions so the loop doesn't have to recompute them:

def fit_stump(X, y, w):
    """Fit the stump with the smallest weighted error on weighted data.

    Brute force, the honest way: for every feature, try a threshold between each
    pair of adjacent sorted values and both polarities, and keep the combination
    that misclassifies the least weight. Returns the stump plus its weighted
    error and its prediction vector, which the boosting loop reuses.
    """
    best = {"error": np.inf, "stump": None, "pred": None}
    n_features = X.shape[1]
    for f in range(n_features):
        values = np.unique(X[:, f])
        thresholds = (values[:-1] + values[1:]) / 2.0        # midpoints
        for thr in thresholds:
            for polarity in (1, -1):
                stump = {"feature": f, "threshold": float(thr), "polarity": polarity}
                pred = stump_predict(X, stump)
                err = weighted_error(y, pred, w)
                if err < best["error"]:
                    best = {"error": err, "stump": stump, "pred": pred}
    return best["stump"], best["error"], best["pred"]

Once we have the stump's error, its vote falls straight out of the formula. The clamp is the only defensive line — it stops a perfect stump from producing an infinite $\alpha$:

def stump_vote(error, eps=1e-10):
    """How much say this stump gets in the final vote: alpha.

    A stump with low error earns a big positive alpha; a coin-flip stump
    (error 1/2) earns alpha 0 and is ignored. The eps clamp keeps a perfect
    stump (error 0) from blowing up to an infinite vote.
    """
    error = min(max(error, eps), 1 - eps)
    return 0.5 * np.log((1 - error) / error)

Then the reweighting, the heart of the whole thing. Correct points shrink, missed points grow, and we renormalize so the weights stay a distribution:

def reweight(w, alpha, y, pred):
    """Raise the weight on the points this stump missed, lower it on the hits.

    w <- w * exp(-alpha * y * pred): the product y*pred is +1 on a correct call
    and -1 on a wrong one, so correct points get multiplied by exp(-alpha) and
    wrong points by exp(+alpha). Renormalize so the weights stay a distribution
    that sums to one — that is what makes the next stump's weighted error a clean
    fraction.
    """
    w = w * np.exp(-alpha * y * pred)
    return w / w.sum()

Now assemble the loop. Uniform weights to start; each round fits a stump, votes it, records what happened, and reweights for the next round. I keep a full per-round history because the animation replays it frame by frame — the weights that pulled each stump, the stump itself, its error and vote, and the running accuracy:

def adaboost_fit(X, y, n_rounds, X_test=None, y_test=None):
    """The AdaBoost loop: fit a stump, score it, vote it, reweight, repeat.

    Start with uniform weights. Each round: fit the best weighted stump, read
    off its weighted error and its vote alpha, then reweight the points so the
    next round leans on the current mistakes. Returns the ensemble (a list of
    (alpha, stump) pairs) and a per-round history the chapter replays frame by
    frame — the weights going into the round, the stump it produced, its error
    and alpha, and running train/test accuracy.
    """
    n = len(X)
    w = np.full(n, 1.0 / n)                 # uniform to start
    ensemble, history = [], []
    for _ in range(n_rounds):
        stump, error, pred = fit_stump(X, y, w)
        alpha = stump_vote(error)
        history.append({
            "weights": w.copy(),            # the weights that pulled THIS stump
            "stump": stump,
            "error": error,
            "alpha": float(alpha),
        })
        ensemble.append((alpha, stump))
        history[-1]["train_acc"] = accuracy(ensemble, X, y)
        if X_test is not None:
            history[-1]["test_acc"] = accuracy(ensemble, X_test, y_test)
        w = reweight(w, alpha, y, pred)     # hard points swell for next round
    return ensemble, history

And the prediction: a weighted vote of every stump, then the sign. A trustworthy stump pulls hard, a weak one barely nudges the total:

def adaboost_predict(ensemble, X):
    """The final call: a weighted vote of every stump, then take the sign.

    Each stump votes ±1; its vote is scaled by its alpha. Sum the scaled votes
    and the sign is the prediction. A stump that was reliable pulls hard; a weak
    one barely nudges the total. Ties (a sum of exactly 0) fall to +1.
    """
    total = np.zeros(len(X))
    for alpha, stump in ensemble:
        total += alpha * stump_predict(X, stump)
    return np.where(total >= 0, 1.0, -1.0)

Watch it work

This is the algorithm running for real, one boosting round per frame. Read it in three places at once.

The dots are the training points, and their SIZE is their current weight — the weight that pulled this round's stump. In round one they're all the same size, because the weights start uniform. Watch what happens after: the points near the boundary of the ring, the ones stumps keep missing, swell round after round. That swelling is the algorithm's attention, made visible. The orange line is the newest stump, and you can see it drawn toward the fat points. The shaded grid behind everything is the ensemble's decision boundary using every stump so far — it starts as a single crude split and sharpens into the ring as the votes accumulate. The lower panel traces training and test error falling as rounds stack up.

Press play. Every frame is one real round; the caption names it, its stump's error $\varepsilon$, its vote $\alpha$, and the ensemble's accuracy. Reset and run it as many times as you like.

Two things are worth pausing on. First, notice that the individual stumps stay terrible — their errors hover near 0.4 the whole way, and their votes stay small. No single frame's line looks any smarter than week 1's. The intelligence isn't in any stump; it's in the accumulation. Second, watch the boundary in the shaded grid go from one flat cut to something that genuinely wraps the inner blob. That ring is built entirely out of horizontal and vertical lines, stacked and voted — which is exactly how a committee of weak, axis-aligned opinions turns into a curved one.

Now the same run taken all the way to fifty rounds, just the error curves. This is where AdaBoost's honest weakness shows up:

Training error slides steadily toward zero — that's boosting doing what it promises. Test error drops fast early, bottoms out around 0.10 near round 17, and then drifts back up. Those later rounds aren't finding signal anymore; they're spending their votes on the handful of points wedged in the class overlap, the ones no line can fix, and paying for it on held-out data. This is the overfitting that noise and outliers cause in AdaBoost, and it's why "more rounds" is not a free lunch.

The full implementation

The whole file the animation actually ran on, top to bottom — seven functions, no library:

"""AdaBoost (discrete AdaBoost / SAMME for two classes), built from scratch.

One decision stump is a weak learner: it barely beats a coin flip. AdaBoost
stacks many of them into a strong classifier by making each new stump focus on
the points the previous ones got wrong. It does that by carrying a weight on
every training point, fitting a stump that minimizes the WEIGHTED error, giving
that stump a vote proportional to how good it was, then raising the weight on
the points it missed so the next stump is pulled toward them.

Labels are in {-1, +1} throughout — that is what makes the weight update and the
final vote come out as clean sign arithmetic. Pure NumPy, no ML library here.

Every function below appears in the chapter one step at a time (the
`# region:` markers are what the book's include directives pull in).
"""

import numpy as np
import pandas as pd


# region: stump_predict
def stump_predict(X, stump):
    """A decision stump: one feature, one threshold, one direction.

    `polarity` +1 means predict +1 on the high side of the threshold, -1 on the
    low side; polarity -1 flips it. This is the week-1 threshold classifier with
    its labels moved to {-1, +1} and a direction bit so the split can point
    either way. Returns an (N,) array of ±1 predictions.
    """
    col = X[:, stump["feature"]]
    pred = np.ones(len(X))
    if stump["polarity"] == 1:
        pred[col < stump["threshold"]] = -1.0
    else:
        pred[col >= stump["threshold"]] = -1.0
    return pred
# endregion


# region: weighted_error
def weighted_error(y, pred, w):
    """The fraction of weight sitting on misclassified points.

    Not the raw miss rate — each mistake is counted by its sample weight w, so a
    point AdaBoost has flagged as hard costs more to get wrong. With uniform
    weights this is exactly the ordinary error rate.
    """
    return float(w[pred != y].sum())
# endregion


# region: fit_stump
def fit_stump(X, y, w):
    """Fit the stump with the smallest weighted error on weighted data.

    Brute force, the honest way: for every feature, try a threshold between each
    pair of adjacent sorted values and both polarities, and keep the combination
    that misclassifies the least weight. Returns the stump plus its weighted
    error and its prediction vector, which the boosting loop reuses.
    """
    best = {"error": np.inf, "stump": None, "pred": None}
    n_features = X.shape[1]
    for f in range(n_features):
        values = np.unique(X[:, f])
        thresholds = (values[:-1] + values[1:]) / 2.0        # midpoints
        for thr in thresholds:
            for polarity in (1, -1):
                stump = {"feature": f, "threshold": float(thr), "polarity": polarity}
                pred = stump_predict(X, stump)
                err = weighted_error(y, pred, w)
                if err < best["error"]:
                    best = {"error": err, "stump": stump, "pred": pred}
    return best["stump"], best["error"], best["pred"]
# endregion


# region: stump_vote
def stump_vote(error, eps=1e-10):
    """How much say this stump gets in the final vote: alpha.

    A stump with low error earns a big positive alpha; a coin-flip stump
    (error 1/2) earns alpha 0 and is ignored. The eps clamp keeps a perfect
    stump (error 0) from blowing up to an infinite vote.
    """
    error = min(max(error, eps), 1 - eps)
    return 0.5 * np.log((1 - error) / error)
# endregion


# region: reweight
def reweight(w, alpha, y, pred):
    """Raise the weight on the points this stump missed, lower it on the hits.

    w <- w * exp(-alpha * y * pred): the product y*pred is +1 on a correct call
    and -1 on a wrong one, so correct points get multiplied by exp(-alpha) and
    wrong points by exp(+alpha). Renormalize so the weights stay a distribution
    that sums to one — that is what makes the next stump's weighted error a clean
    fraction.
    """
    w = w * np.exp(-alpha * y * pred)
    return w / w.sum()
# endregion


# region: adaboost_fit
def adaboost_fit(X, y, n_rounds, X_test=None, y_test=None):
    """The AdaBoost loop: fit a stump, score it, vote it, reweight, repeat.

    Start with uniform weights. Each round: fit the best weighted stump, read
    off its weighted error and its vote alpha, then reweight the points so the
    next round leans on the current mistakes. Returns the ensemble (a list of
    (alpha, stump) pairs) and a per-round history the chapter replays frame by
    frame — the weights going into the round, the stump it produced, its error
    and alpha, and running train/test accuracy.
    """
    n = len(X)
    w = np.full(n, 1.0 / n)                 # uniform to start
    ensemble, history = [], []
    for _ in range(n_rounds):
        stump, error, pred = fit_stump(X, y, w)
        alpha = stump_vote(error)
        history.append({
            "weights": w.copy(),            # the weights that pulled THIS stump
            "stump": stump,
            "error": error,
            "alpha": float(alpha),
        })
        ensemble.append((alpha, stump))
        history[-1]["train_acc"] = accuracy(ensemble, X, y)
        if X_test is not None:
            history[-1]["test_acc"] = accuracy(ensemble, X_test, y_test)
        w = reweight(w, alpha, y, pred)     # hard points swell for next round
    return ensemble, history
# endregion


# region: adaboost_predict
def adaboost_predict(ensemble, X):
    """The final call: a weighted vote of every stump, then take the sign.

    Each stump votes ±1; its vote is scaled by its alpha. Sum the scaled votes
    and the sign is the prediction. A stump that was reliable pulls hard; a weak
    one barely nudges the total. Ties (a sum of exactly 0) fall to +1.
    """
    total = np.zeros(len(X))
    for alpha, stump in ensemble:
        total += alpha * stump_predict(X, stump)
    return np.where(total >= 0, 1.0, -1.0)
# endregion


def accuracy(ensemble, X, y):
    """Fraction the current ensemble gets right — used all through the loop."""
    return float((adaboost_predict(ensemble, X) == y).mean())


def load_data(path="../data/quantiles.csv"):
    """make_gaussian_quantiles snapshot: 200 2-D points, two concentric classes.

    Returns X as an (N, 2) float array and y in {-1, +1}. The raw CSV stores the
    label as {0, 1}; we remap 0 -> -1 so the boosting math stays sign-clean.
    """
    df = pd.read_csv(path)
    X = df[["x1", "x2"]].to_numpy(float)
    y = np.where(df["label"].to_numpy(int) == 1, 1.0, -1.0)
    return X, y

The library version

Nobody hand-rolls this in production. AdaBoost with decision stumps is one constructor in scikit-learn — the base estimator is a DecisionTreeClassifier capped at max_depth=1, which is exactly our stump:

def sk_adaboost(X_train, y_train, X_test, y_test, n_rounds):
    """Fit sklearn AdaBoost with depth-1 trees; return train/test accuracy.

    learning_rate=1.0 leaves the vote alpha unshrunk, so it lines up with our
    from-scratch alpha = 1/2 ln((1-eps)/eps). Also returns the fitted model so
    the traces can read its per-round staged accuracy.
    """
    clf = AdaBoostClassifier(
        estimator=DecisionTreeClassifier(max_depth=1),
        n_estimators=n_rounds,
        learning_rate=1.0,
        random_state=0,
    )
    clf.fit(X_train, y_train)
    train_acc = float(clf.score(X_train, y_train))
    test_acc = float(clf.score(X_test, y_test))
    return train_acc, test_acc, clf

Two differences from ours, both small. The library fits each stump by Gini impurity rather than by searching accuracy directly, so on any given round it may pick a slightly different split — but it's optimizing for the same thing, a good weighted cut, and it lands in the same neighborhood. And as of scikit-learn 1.6 the only algorithm is SAMME, the multi-class generalization of discrete AdaBoost; for our two classes it reduces to precisely the $\pm 1$ vote we derived. To compare how fast each version's error falls, the library hands us its accuracy after every successive round:

def sk_staged(clf, X, y):
    """sklearn's accuracy after each successive round, for the error curve.

    staged_score walks the ensemble one estimator at a time, so we get the same
    "accuracy vs number of rounds" trace we build from our own history — the
    honest way to compare how fast each version's error falls.
    """
    return [float(s) for s in clf.staged_score(X, y)]

Scratch versus library

Same 140/60 split, both trained for 50 rounds, scored on the held-out 60. Here's the face-off, with the lone stump thrown in so you can see what boosting bought:

The single stump scores 0.63 on the test set — barely above guessing, exactly the floor we expected from concentric classes. Our from-scratch AdaBoost lifts that to 0.88, and scikit-learn's reaches 0.92. Both boosted models hit the same 0.98 on training data; the gap between them on test is one split's worth of Gini-versus- accuracy difference in which threshold each round chose, not a difference in the algorithm. The headline is the jump from 0.63 to the high 0.80s and 0.90s: a weak learner stacked fifty deep, on data where one of it alone is useless. Every figure here is read from data/results.json, regenerated whenever the code changes, so the prose can't drift from what ran.

Takeaways

AdaBoost is the cleanest demonstration in the course of an idea that runs through all of modern ML: a strong model doesn't have to be a complicated model. It can be a swarm of dumb ones, aimed. The stump you'd never ship becomes, fifty copies deep and each pointed at the last one's mistakes, a classifier that draws boundaries none of them could. Understand this and you understand the engine inside every gradient-boosted model you'll ever run.

Reach for it when your weak learner is genuinely weak and your data is genuinely clean. That second condition is not optional. Because AdaBoost defines "hard" as "keeps getting missed," it can't distinguish a subtle case from a corrupted one, and it will happily pour its later rounds into fitting your outliers — you saw the test error turn back up while training error kept falling. If your labels are noisy, boosting will find the noise. In that setting a bagged ensemble like the random forest from last chapter, which averages instead of chases, is usually the safer bet.

And this is the bridge to what's next. AdaBoost reweights points; the reweighting is really a crude way of telling each new learner to fix the current errors. Gradient boosting makes that explicit — instead of nudging weights, each new learner is fit directly to the residual, the gradient of a loss you get to choose. Same core move, chase what's still wrong, but generalized from classification error to any differentiable objective. That generalization is what took boosting from a clever classifier to the workhorse behind XGBoost and every Kaggle leaderboard, and it's exactly where the next chapter goes.