module 07

Boosting: AdaBoost and Gradient Boosting

free pdf

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.

free pdf

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:

  1. Train a weak model on the weighted points.
  2. Measure its weighted error ε.
  3. Give it a vote: big if it was accurate, zero if it was no better than a coin. α = ½ ln((1 − ε)/ε)
  4. 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:

  1. Start with the average as the prediction.
  2. Compute what's left over: truth − prediction (the residuals).
  3. Fit a small tree to those leftovers.
  4. Add a small fraction of that tree to the prediction, and repeat.

each new tree fixes what's left over

train error 0.1875
0123456-10123xy
model so farstarting guess (average)
the model starts as a flat line at the average. each tree is small (two questions deep), so on its own it can only add a few steps. added one by one, each fitting the remaining error, they build the curve.

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.