module 07
Boosting: AdaBoost and Gradient Boosting
A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting
Yoav Freund & Robert E. Schapire
Introduces AdaBoost: train weak models one after another, and after each one give more weight to the examples it got wrong, so the next model focuses on them. Many weak models end up as one strong one, and the paper proves the training error falls fast.
Greedy Function Approximation: A Gradient Boosting Machine
Jerome H. Friedman
Treats boosting as gradient descent: each new tree is trained to fix the current model's errors in the direction that lowers the loss fastest. Because of that, the same recipe works for any loss, including ones that ignore outliers.
forests vs boosting
A random forest grows many strong trees side by side and averages them. Boosting adds many weak models one after another, each fixing what the team so far still gets wrong. A single one-question tree can only draw one straight line. A few hundred boosted ones can draw a circle.
adaboost: focus on the mistakes
Start with every training point weighted equally. Then, in each round:
- Train a weak model on the weighted points.
- Measure its weighted error
ε. - Give it a vote: big if it was accurate, zero if it was no better than a coin.
α = ½ ln((1 − ε)/ε) - Increase the weight of the points it got wrong and decrease the rest.
The final answer is the weighted vote of all the models. Because the mistakes get heavier every round, each new model concentrates on the hard cases near the boundary.
Freund and Schapire proved that if every weak model beats a coin by even a little, the training error falls exponentially fast.
gradient boosting: fit what's left over
Friedman saw boosting as gradient descent, but instead of adjusting weights it adjusts predictions. For squared error the recipe is simple:
- Start with the average as the prediction.
- Compute what's left over:
truth − prediction(the residuals). - Fit a small tree to those leftovers.
- Add a small fraction of that tree to the prediction, and repeat.
each new tree fixes what's left over
For other losses, "what's left over" becomes the direction that lowers the loss fastest, and the same recipe works:
| loss | what each tree fits | value in each leaf |
|---|---|---|
| squared error | truth − prediction |
the average |
| absolute error | just the sign: +1 or −1 |
the median |
| huber | leftovers, capped at a limit | a median-based value |
| log loss (classification) | truth − probability |
one Newton step |
With absolute error, a point that's 8 away pulls no harder than one that's 0.01 away, so wild labels can't drag the model around.
Shrinkage. Adding only a small fraction (the learning rate) of each tree means more trees are needed, but the model overfits much more slowly.
how the code works
| idea | in boosting.py |
|---|---|
| weighted weak model | DecisionTree(max_depth=1).fit(X, t, sample_weight=w) |
| vote and reweighting | alpha = …, w = w * exp(-alpha * t * pred) |
| the training-error guarantee | AdaBoost.training_error_bound() |
| what each tree fits, per loss | GradientBoosting._pseudo_residuals |
| the value in each leaf | _leaf_value |
| learning rate, random subsets | learning_rate, subsample |
| prediction after each tree | staged_decision_function |
what the demo checks
Run uv run python examples/07_boosting.py.
- One-question trees turn into a circle: 0.713 → 0.917 accuracy.
- At every round, AdaBoost's training error stays below its guarantee (0.050 vs 0.224 at round 200).
- Points near the true boundary are 21% of the data but end up with 60% of the weight.
- With 5% wild labels, squared error is ruined (error 1.63). Absolute error gets 0.009 and huber 0.007, as long as each leaf holds at least 10 points. With one-point leaves, a tree can give a wild point its own leaf and fit it exactly, whatever the loss.
- A big learning rate with deep trees overfits almost immediately. A small learning rate keeps improving for a hundred trees.
when it goes wrong
- Too many rounds with a big learning rate: test error turns around while training error keeps falling. Watch it and stop early.
- Label noise with AdaBoost: wrong labels keep getting heavier, and the model bends to fit them.
- Tiny leaves: they undo the protection of robust losses.