Boosting

In the last lesson, random forests took a crowd of deep, low-bias, high-variance trees, grew each on a different bootstrap sample, and averaged them to cancel variance. Every tree was trained independently and in parallel. Boosting turns that idea inside out.

Boosting trains learners one at a time, and each new learner is trained to fix the errors the ensemble has made so far. The learners are deliberately weak: shallow trees, often a single split ("stumps"). No single one is good. But when you add them up, biased and slow at first, the committee sharpens into a model that is often the strongest thing you can run on tabular data.

This lesson builds the two boosting algorithms every engineer is expected to know. AdaBoost reweights the data toward the points it keeps getting wrong. Gradient boosting fits each new learner to the leftover error directly, which turns out to be gradient descent, run not on the weights of one model but in the space of functions itself.

The one idea: sequential, focused on mistakes

Here is the whole of boosting in one loop:

The two algorithms differ only in how they define "the mistakes" and how they focus the next learner on them. AdaBoost puts more weight on misclassified points. Gradient boosting fits the next learner to the residual error as a regression target. Everything else, the sequential loop and the additive final model, is shared.

Bagging vs boosting: variance vs bias

Both bagging and boosting are ensembles of trees, but they attack opposite halves of the error. Recall the decomposition from the bias-variance lesson:

The logic is symmetric. Bagging starts from learners that are already accurate but jittery (a deep tree changes a lot when the data shifts), and averaging many of them cancels that jitter, so it drives variance down. Boosting starts from learners that are stable but too simple to capture the pattern (a stump is nearly the same on any sample, but very wrong), and stacking many of them, each aimed at the current error, drives bias down.

AdaBoost: reweight the mistakes, then vote by confidence

AdaBoost (Adaptive Boosting) is the original boosting algorithm that made the idea practical. It works on classification, with labels written as $y_i \in \{-1, +1\}$ so that "correct" means the prediction and the label have the same sign.

Every training point carries a weight $w_i$, its say in the loss. All points start equal:

Each round t does three things.

1. Train a weak learner on the weighted data

Fit a stump $h_t$ that minimises the weighted error, so points with big weights matter most. Its weighted error rate is the total weight it gets wrong:

Since the weights sum to 1, $\varepsilon_t$ is between 0 and 1. A useless coin-flip learner sits at $\varepsilon_t = 0.5$.

2. Score the learner: how much should it count?

Give the learner a weight $\alpha_t$ in the final vote based on how much better than chance it is:

Read this formula. It is the heart of AdaBoost:

• A great learner ($\varepsilon_t \to 0$) gets $\alpha_t \to +\infty$: it dominates the vote.
• A coin flip ($\varepsilon_t = 0.5$) gets $\alpha_t = 0$: it is ignored, because $\ln(1) = 0$.
• A learner worse than chance ($\varepsilon_t > 0.5$) gets $\alpha_t < 0$: AdaBoost flips it and uses it backwards.

3. Reweight the data toward what this learner missed

Multiply up the weight of every point the learner got wrong, so the next round is forced to attend to them, then renormalise so the weights are a distribution again:

Correctly classified points multiply by $e^0 = 1$ and are left alone (they shrink only relative to the others after renormalising). Misclassified points multiply by $e^{\alpha_t} > 1$ and grow. The bigger $\alpha_t$ is, the harder the next learner is pushed onto today's mistakes.

The final model: a weighted majority vote

After T rounds, classify a new point by the sign of the confidence-weighted sum of the weak learners:

Each stump votes $\pm 1$, and its vote is scaled by how trustworthy it earned the right to be. Watch the whole loop run. Each round, the misclassified points swell, the stump line shifts to chase them, and the ensemble training error falls.

Gradient boosting: fit the residuals

AdaBoost's reweighting trick is elegant but specific to classification with that exponential loss. Gradient boosting generalises it to any differentiable loss with one clean idea: instead of reweighting points, fit each new learner directly to the error left over.

Build the model additively. Start from a constant $F_0$ (for squared error, the mean of $y$), then add one weak learner at a time:

Here $\nu$ (nu) is the learning rate, a small number like 0.1 that shrinks each step. The only question is what $h_m$ should learn. The answer: the negative gradient of the loss with respect to the current predictions.

That looks abstract until you plug in squared-error loss $L = \tfrac{1}{2}(y - F)^2$. Its derivative with respect to the prediction $F$ is:

The negative gradient is exactly the residual, the part of $y$ the current model still misses. So for regression with squared loss, gradient boosting is beautifully concrete:

Watch it happen. The top panel shows the staircase prediction creeping toward the target curve. The bottom panel shows the residuals shrinking, with the next stump (dashed) fitting whatever error is left. Slide the learning rate and see how smaller steps need more rounds but move more carefully.

Why this is "gradient descent in function space"

Ordinary gradient descent nudges a parameter vector downhill: $w \leftarrow w - \eta \, \partial L / \partial w$. Gradient boosting does the same thing, but the object being optimised is the whole function $F$, and each step moves $F$ in the direction of the negative gradient by adding a new learner that points that way. The learning rate $\nu$ plays the exact role $\eta$ plays below: the size of each downhill step.

Same picture, one level up. Below, a ball rolls down a loss surface by repeatedly stepping against the gradient. In gradient boosting, the "ball" is the ensemble's prediction, and each weak learner is one step down that same slope, fitting the residual because the residual is where the slope points.

Learning rate and shrinkage

Why not add each learner at full strength ($\nu = 1$)? Because a smaller $\nu$ (shrinkage) makes the model take many small, cautious steps instead of a few greedy ones. Each step corrects less, so no single stump can overreact to noise, and the ensemble generalises better. The trade-off is fixed:

In practice you set a small $\nu$ (0.05 to 0.1), then use as many rounds as a validation set will let you before it starts overfitting. Learning rate and number of rounds are tuned together.

Code: run both, watch the error fall

Time to make it real. First, fit both boosters on a real dataset and compare their accuracy to a single stump. AdaBoostClassifier and GradientBoostingClassifier both live in scikit-learn, which auto-loads in the Pyodide worker.

Now the payoff plot. Every booster can replay its prediction after each round with staged_predict (and gradient boosting also exposes staged_decision_function). Plot the test error round by round and you can literally watch bias fall as learners accumulate, and, if you push it, watch overfitting begin.

Finally, gradient boosting stripped to its skeleton: no scikit-learn, just NumPy fitting stumps to residuals. This is the entire algorithm for squared-error regression in about fifteen lines. Run it and watch the training error drop each round as the residuals shrink.

Push these. In the first playground, raise noise on the moons and watch every model's accuracy sag toward the noise floor. In the last one, set nu = 1.0 and see it lurch, or nu = 0.05 and watch it crawl but converge more smoothly. Break it, then fix it.

Recap

Interview readiness