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.

A loop of four boxes: 1. weights w, all 1/N at the start; 2. fit a stump with the lowest weighted error epsilon; 3. its say alpha = one half ln of (1 minus epsilon) over epsilon; 4. reweight: mistakes times e to the alpha, correct points times e to the minus alpha, divide by Z; then back to 1. Each round adds alpha times h to the vote H(x) = sign of the sum of alpha times h(x)
One round of AdaBoost: weights → stump → α → new weights. Each round adds one weighted stump to the vote.

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 − ε) / ε).

Curve of alpha against epsilon from 0 to 1. It is large and positive near epsilon 0, passes 0.85 at epsilon 0.154 and 0.69 at epsilon 0.2, crosses zero at epsilon 0.5, and is negative above 0.5, for example minus 0.69 at epsilon 0.8
A stump with a small error gets a big say; a stump at ε = 0.5 is a coin flip and gets α = 0.

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.

Two copies of the 10 points with the stump line x1 = 7. Before: all circles the same size, weight 0.1, and the two orange points (5,1) and (4,2) on the plus side are ringed in red. After: those two circles are large (weight 0.25) and the other eight are small (0.0625)
Round 1: the two mistakes go from 0.1 to 0.25, the eight correct points from 0.1 to 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 mStump: +1 ifεαZTraining error of the voteBound ∏Z
1x1 < 70.2000.690.8002/100.800
2x1 < 3.50.1880.730.7813/100.624
3x2 ≥ 30.1540.850.7220/100.451
10x1 < 70.1900.720.7850/100.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

AdaBoostGradient boosting
What the next learner seesall points, with new weightsall points, with new targets (the residuals)
How it is added× α from its weighted error× a fixed learning rate ν
Lossexponentialany differentiable loss
Typical learnerstumpssmall 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.

On the mind map

Open the Machine Learning mind mapMachine LearningLearning setup: what feedback, how to scoreLearning setupLinear models: weighted sum w·x + bLinear modelsOther classic models: trees, margins, neighboursOther classic modelsUnsupervised: find structure without labelsUnsupervisedTraining: loss, gradient, small stepTrainingNeural networks: layers of σ(W·a + b)Neural networksArchitectures: how layers share informationArchitecturesLanguage models: predict the next tokenLanguage modelsLLM speed and tuning: cheaper to run, safer to useLLM speed and tuningRetrieval and agents: give the model data and toolsRetrieval and agentsK-nearest neighborsK-nearest neighborsmajority vote of the K closestDigit template matchingDigit template matchingnearest average digit winsNaive BayesNaive Bayeswords independent, sum log-probabilitiesDecision treeDecision treesplit on the biggest information gainRandom forest vs boostingRandom forest vs boostingforest: average; boosting: fit residualsAdaBoostReweight mistakes, vote with αOpen the Machine Learning mind mapMachine Learningtrees, margins, neighboursOther classic modelsK-nearest neighborsK-nearest neighborsmajority vote of the K closestDigit template matchingDigit template matchingnearest average digit winsNaive BayesNaive Bayeswords independent, sum log-probabilitiesDecision treeDecision treesplit on the biggest information gainRandom forest vs boostingRandom forest vs boostingforest: average; boosting: fit residualsAdaBoostReweight mistakes, vote with α
This page on the Machine Learning mind map · 77 pages in 10 branches · open it to see the whole map and test yourself in recall mode.