AdaBoost

Why Does This Exist?

You run a belt that must pull hollow walnuts before packing. Each nut gets two cheap numbers: weight in grams and ring frequency when a paddle taps it. Hollow nuts skew lighter and higher, but shell thickness varies and the belt shakes, so one cut on either number lands near 70 percent correct. Neither cut ships, and you cannot buy a better sensor.

You need a way to turn two blunt rules into one sharp call. That is what boosting does: fit simple rules in sequence, each cleaning up after the last. AdaBoost was the first method that made the sequence work. It hands the next learner the same rows with new weights, heavier on the rows the run keeps missing.

This page covers that reweighting plus the vote that follows. The parent page on boosting sets the family against bagging. The sequel on gradient boosting keeps the loop and swaps the loss.

The one idea you need first is the weak learner. Here it is a stump: one threshold on one feature, the smallest decision tree you can draw. Its weighted error is the total weight on the rows it gets wrong, not a plain miss count. Everything below is arithmetic on those two objects.

Think of It Like This

How It Actually Works

Call row $i$ the pair $(x_{i}, y_{i})$. Here $x_{i}$ means the two sensor numbers for nut $i$ and $y_{i}$ means its label, written as $+1$ for hollow and $-1$ for sound. Give every row a weight $w_{i}$, with all $w_{i}$ summing to one, starting at $w_{i} = 1/n$ for $n$ rows. Call the one cut rule $h$, with $h(x_{i}) = +1$ or $-1$ for each nut. You fit $h$ to minimize weighted error, not plain accuracy.

The vote each stump earns

Score the stump by its weighted error $\varepsilon$, which means the total weight on the rows it gets wrong. Then give it its vote:

In plain words, $\alpha$ says how loudly this stump speaks in the final vote. At $\varepsilon = 0.5$ the fraction inside is one, its log is zero, so a coin flip stump gets $\alpha = 0$ and is ignored. As $\varepsilon$ falls toward zero, $\alpha$ climbs with no ceiling. Worse than a coin flip gives a negative $\alpha$, which flips that stump backward. You need each stump to beat a coin flip on its weighted data, or the round contributes nothing.

Why the mistakes always end up holding half

Push the weights toward the misses. Multiply every misclassified row by $e^{\alpha}$ and every correct row by $e^{-\alpha}$, then divide by $Z$, where $Z$ means the normalizer that brings the total back to one:

Check the signs. When the stump is right, $y_{i} h(x_{i}) = +1$ and the factor is $e^{-\alpha}$, a shrink. When it is wrong, the product is $-1$ and the factor is $e^{+\alpha}$, a grow. The math always lands the same way: after rescaling, the rows this stump missed hold exactly half the total weight. So the next stump faces a problem where the last round failures count as much as everything else combined. That is the whole trick. No sampling, no copies, just a distribution that tilts.

Worked example: ten nuts, three misses

Start with ten nuts, so each $w_{i} = 0.10$. Your first stump misses three of ten. Its weighted error is $\varepsilon = 0.30$, and its vote is $\alpha = 0.5 \times \ln(0.70/0.30) \approx 0.424$.

Grow the three misses: $0.10 \times e^{0.424} \approx 0.10 \times 1.528 \approx 0.1528$. Shrink the seven hits: $0.10 \times e^{-0.424} \approx 0.10 \times 0.655 \approx 0.0655$. The total is $3 \times 0.1528 + 7 \times 0.0655 \approx 0.9165$. Divide through by that total and each miss lands at $0.167$ while each hit lands at $0.071$. Add the three misses: $3 \times 0.167 = 0.50$. Half, as promised. Those are the numbers drawn in the diagram above, and the snippet below repeats them.

The loss view that led to gradient boosting

Write the running vote as $F(x)$, which means the $\alpha$ weighted sum of stumps so far. Call $yF(x)$ the margin: positive when the ensemble is right, large when it is confidently right. Years later the field showed AdaBoost had been doing gradient descent on one loss all along:

A borderline nut sits near zero margin and costs little. A confidently wrong nut sits at a large negative margin, and $e^{-yF}$ blows up there: margin $-1$ costs about $2.72$, margin $-3$ costs about $20.09$, margin $-5$ costs about $148.41$. That shape is the trade. It chases hard rows fast, and it cannot let go of a wrongly labelled row. Keep the loop but swap this loss for a gentler one and you have gradient boosting. That swap is what ships now. Read this page for the reweighting idea, then reach for the sequel when you build.

Code

The whole update on the ten nut round above. The point is the check: the vote, the two new weights, and the half total you can verify by hand.

1import numpy as np2
3
4def one_round(w: np.ndarray, wrong: np.ndarray) -> tuple[float, np.ndarray]:5    err = float(w[wrong].sum())  # weighted error, not a plain miss count6    alpha = 0.5 * np.log((1.0 - err) / err)  # this stump vote, rising as err falls7    w = w * np.exp(np.where(wrong, alpha, -alpha))  # misses up, hits down8    return alpha, w / w.sum()  # rescale so weights stay a distribution9
10
11missed = np.zeros(10, dtype=bool)12missed[[2, 5, 9]] = True  # first stump calls three of ten wrong13alpha, w = one_round(np.full(10, 0.1), missed)14print(f"vote {alpha:.3f} | miss {w[missed][0]:.3f} each | hit {w[~missed][0]:.3f} each | misses hold {w[missed].sum():.3f}")15# -> vote 0.424 | miss 0.167 each | hit 0.071 each | misses hold 0.500

Refit a stump on those weights, collect the next vote, repeat a few hundred times with shallow stumps, and classify a new nut by the sign of the vote weighted sum. When labels are clean that loop is hard to beat for its size. When they are not, read the first card below before you trust it.

Watch Out For

The Quick Version

• AdaBoost fits one cut stumps in sequence, with each stump trained on weights that emphasize the rows missed so far.
• Weighted error is the total weight on the rows a stump gets wrong, and its vote is alpha at half the log of correct weight over wrong weight.
• The update multiplies missed rows by exp of alpha and correct rows by exp of minus alpha, then rescales, which always leaves the misses holding half the total.
• The final call is the sign of the alpha weighted vote across stumps, with coin flip stumps ignored and worse stumps flipped.
• The loop is gradient descent on exponential loss, so one mislabelled row can capture the ensemble and modern work uses gentler losses instead.

What to Read Next

• Boosting
• Gradient Boosting
• Decision Trees