The idea: many weak rules, each one aimed at the last one's mistakes
A decision stump is a decision tree with one split: "+1 if x1 < 7, else −1". On its own it is a weak learner, only a bit better than guessing. AdaBoost (adaptive boosting) trains stumps one after another. Before each round it gives more weight to the points the earlier stumps got wrong, so the next stump has to care about them. At the end all stumps vote, and better stumps get a bigger say.
The canvas has 10 points with two features x1, x2: blue + points and orange − points. The circle size is the point's weight. Next Round runs one round step by step, 10 Rounds runs the rest quickly, and Predict ? lets the stumps vote on the new point ? = (6, 2). Nothing is random, so every run gives the same numbers.
Decision stumps and the weighted error
A stump picks one feature, one threshold and a direction: +1 on one side, −1 on the other. The page tries thresholds halfway between neighbouring values of x1 and of x2, both ways round, and keeps the stump with the lowest weighted error:
ε = the sum of the weights of the points the stump gets wrong.
In round 1 every weight is 1/10 = 0.100, so ε is just the share of mistakes. The best stump is "+1 if x1 < 7". It misses (5,1) and (4,2), two − points on the + side: ε = 0.100 + 0.100 = 0.200. (Demo: round 1)
The stump's say: α
Each stump gets a vote weight
α = ½ ln((1 − ε) / ε).
For ε = 0.2 that is ½ ln 4 = ln 2 = 0.69. A smaller error gives a larger α. At ε = 0.5 the stump is a coin flip and α = 0, so AdaBoost stops if no stump beats 0.5. Above 0.5, α is negative: the vote turns the stump around. Because the page tries both directions of every split, the best stump never has ε above 0.5.
Reweighting: mistakes get heavier
After the round, every weight is multiplied:
- a point the stump got wrong: × eα (× 2 in round 1);
- a point it got right: × e−α (× ½ in round 1).
The new weights add up to Z, and dividing by Z makes them sum to 1 again. In round 1, Z = 2 × 0.200 + 8 × 0.050 = 0.800, the two mistakes end at 0.250 each and the eight others at 0.0625.
The mistakes now hold exactly half of the weight (0.25 + 0.25 = 0.50). This is always so: after reweighting, the stump just used has weighted error 0.5, a coin flip. So the next stump can't be the same one; it must get some of those heavy points right. Round 2 picks "+1 if x1 < 3.5": it gets (5,1) and (4,2) right but misses three + points of weight 0.0625 each, ε = 0.188, α = 0.73. (Demo: round 2)
The weighted vote
The final classifier adds up the stumps, each times its α, and takes the sign:
H(x) = sign(F(x)), F(x) = α1h1(x) + α2h2(x) + …
The tint on the plot is the sign of F. After three rounds the stumps are "x1 < 7" (α = 0.69), "x1 < 3.5" (α = 0.73) and "x2 ≥ 3" (α = 0.85). Each one alone misses 2 or 3 of the 10 points; together they get all 10 right (Demo: three stumps). For the new point ? = (6, 2), stump 1 says +1, but F = +0.69 − 0.73 − 0.85 = −0.89, so the vote says −. The size of |F| is the margin: how sure the vote is. (Demo: the weighted vote)
| Round m | Stump: +1 if | ε | α | Z | Training error of the vote | Bound ∏Z |
|---|---|---|---|---|---|---|
| 1 | x1 < 7 | 0.200 | 0.69 | 0.800 | 2/10 | 0.800 |
| 2 | x1 < 3.5 | 0.188 | 0.73 | 0.781 | 3/10 | 0.624 |
| 3 | x2 ≥ 3 | 0.154 | 0.85 | 0.722 | 0/10 | 0.451 |
| 10 | x1 < 7 | 0.190 | 0.72 | 0.785 | 0/10 | 0.078 |
Training error and its bound
The training error of the vote is never more than the product of the Z's:
error ≤ Z1 · Z2 · … · ZM, with Zm = 2√(εm(1 − εm)).
Each Z is below 1 whenever ε < 0.5, so the bound falls every round, and it falls fast when the stumps are good. The error itself can go up for a round: after round 2 the vote is wrong on 3 points, one more than after round 1, because with two stumps the one with the larger α decides alone. By round 3 it is 0, and it stays 0 while the bound keeps falling to 0.078 after 10 rounds. (Demo: 10 rounds)
The bound comes from the loss AdaBoost is really minimising, the exponential loss Σ e−y·F(x). Each round is one greedy step on it: the stump and its α are the choice that lowers it most.
A wrong label grabs the weight
Pick 10 points + 1 wrong label: (3,8) is labelled − although it sits among the + points. No sensible stump gets it right, so it is a mistake round after round and its weight keeps being multiplied by eα. After 10 rounds it weighs 0.277, while no other point weighs more than 0.111. Later stumps such as "x2 ≥ 8.5" and "x2 < 7.5" exist only to chase it, and the training error keeps jumping between 0 and 1 of 11 points. (Demo: one wrong label) The exponential loss punishes a confident mistake very hard, so AdaBoost is sensitive to label noise and outliers. Limiting the number of rounds (checked on validation data) or a gentler loss, as in gradient boosting with the log-loss, helps.
AdaBoost and gradient boosting
| AdaBoost | Gradient boosting | |
|---|---|---|
| What the next learner sees | all points, with new weights | all points, with new targets (the residuals) |
| How it is added | × α from its weighted error | × a fixed learning rate ν |
| Loss | exponential | any differentiable loss |
| Typical learner | stumps | small trees |
Both reduce mainly bias: a stump is far too simple, and the sum of many stumps is not. See also Random Forest vs Gradient Boosting for residual boosting and bagging, Decision Tree Learning for how a full tree picks its splits, and the Perceptron for another weighted vote of features.
What the page leaves out
The page shows discrete AdaBoost for two classes with stumps on 10 integer points. Real AdaBoost runs hundreds of rounds and can use deeper trees. SAMME extends it to many classes, Real AdaBoost and LogitBoost use class probabilities, and scikit-learn adds a learning rate that shrinks each α. Resampling instead of reweighting, the margin theory of why test error often keeps falling after the training error hits 0, and the Viola–Jones face detector (AdaBoost over Haar features) are only mentioned here.