Boosting: AdaBoost to gradient boosting

The big idea

A random forest is a committee of independent experts voting at once. Boosting is a relay of specialists, each one studying only what the team before it still gets wrong. The first student answers the exam and gets a few questions wrong. The second student spends all their time on those questions. The third focuses on what the first two together still miss. Combined, they cover the whole exam.

BoostingAn ensemble method that trains models sequentially, each one concentrating on the errors left by the ensemble so far, and adds them together. builds a strong model out of many weak ones, typically shallow trees that alone are barely better than guessing. Where bagging reduces variance by averaging deep, wobbly trees, boosting reduces bias by adding small, stable ones. Its modern form, gradient boosting, is the most accurate off-the-shelf model for most tables of numbers and categories.

How it works

Step 1: AdaBoost, the original idea

AdaBoostAdaptive Boosting: trains weak classifiers in sequence, increasing the weight of misclassified examples after each round, and combines them with a weighted vote. (1995) gives every training example a weight, initially equal. It trains a stumpA decision tree with a single split: one question, two leaves. The classic weak learner in boosting., then increases the weights of the examples it got wrong and decreases the rest. The next stump, trained on the reweighted data, is forced to care about the hard cases. At the end, each stump votes with a weight based on its accuracy. In the code below, one stump scores 0.707; AdaBoost with 200 stumps scores 0.823 on the same data.

Step 2: Gradient boosting fits residuals

For regression with squared error the idea is even simpler. Start with a constant prediction F0, the mean of y. Then repeat:

1. Compute residualsThe difference between the true target and the current prediction, y minus F(x). r = y - F(x) for every training example.
2. Fit a small tree h to predict r from x.
3. Update F(x) = F(x) + nu h(x), where nu is the learning rate.

Each tree literally learns the error the ensemble still makes. Worked example: a house is worth 300k and F0 predicts the mean, 250k. The residual is 50k. Tree 1 predicts 40k for houses like it; with nu = 0.1 the new prediction is 250 + 4 = 254k, and the residual is now 46k for tree 2 to work on.

Step 3: Why "gradient"

For squared error loss L = 0.5 (y - F)^2, the negative gradient with respect to the prediction F is exactly y - F, the residual. So "fit a tree to the residuals and take a small step" is gradient descent ( Gradient descent, the engine of ML ), except the step is taken in function space: instead of nudging parameters, each round nudges the predictions in the direction that lowers the loss. For any other differentiable loss, such as log loss for classification, you fit each tree to that loss's pseudo-residualsThe negative gradient of the loss with respect to the current predictions; for squared error it equals the ordinary residual. instead. AdaBoost turns out to be the same recipe with an exponential loss.

Step 4: Learning rate and number of trees work together

A small learning rate means each tree corrects only a little, so you need more trees, but the ensemble generalizes better: many small steps average out the noise in each individual tree. This trade-off is called shrinkageScaling each new tree's contribution by a learning rate below 1, which needs more trees but usually generalizes better..

Unlike a random forest, boosting can overfit by adding trees: it keeps fitting residuals until it fits the noise. The fix is early stoppingMonitoring validation error during training and stopping when it stops improving, keeping the best number of rounds.: hold out validation data and stop adding trees when its error stops improving ( XGBoost, LightGBM and CatBoost in practice shows this in the libraries).

Step 5: Keep each tree small

Boosting trees are shallow: depth 3 to 8, or a limit on leaves. A depth-d tree can capture interactions among up to d features. Stumps (depth 1) give an additive model with no interactions. Deeper trees fit faster but overfit sooner.

Try it

Try this:

1. At learning rate 0.3, step rounds from 0 to 10. Watch each new stump split where the residuals are largest, and the residual bars shrink.
2. Set the learning rate to 1 and rounds to 150. Does the violet line chase individual points? Compare the training MSE with the noise variance of about 0.12.
3. Set the learning rate to 0.05. How many rounds do you need before the fit looks like the green curve?

Going deeper

Code: boosting from scratch, then the libraries

import numpy as np
from sklearn.ensemble import AdaBoostClassifier, GradientBoostingRegressor, RandomForestClassifier, HistGradientBoostingClassifier
from sklearn.datasets import make_classification
from sklearn.model_selection import cross_val_score, train_test_split
from sklearn.tree import DecisionTreeRegressor, DecisionTreeClassifier

rng = np.random.default_rng(0)
x = np.sort(rng.uniform(0, 6, 300))[:, None]
y = np.sin(x[:, 0]) * 2 + 0.3 * x[:, 0] + rng.normal(0, 0.4, 300)
xtr, xte, ytr, yte = train_test_split(x, y, test_size=0.5, random_state=0)

# Gradient boosting for squared error, from scratch: each tree fits the current residuals
def boost(lr, rounds):
    pred_tr = np.full(len(ytr), ytr.mean())
    pred_te = np.full(len(yte), ytr.mean())
    hist = {}
    for m in range(1, rounds + 1):
        resid = ytr - pred_tr                      # negative gradient of 0.5 * (y - f)^2
        t = DecisionTreeRegressor(max_depth=2).fit(xtr, resid)
        pred_tr += lr * t.predict(xtr)
        pred_te += lr * t.predict(xte)
        hist[m] = (np.mean((ytr - pred_tr) ** 2), np.mean((yte - pred_te) ** 2))
    return hist

print("round   lr=1.0 train/test    lr=0.1 train/test")
h1, h2 = boost(1.0, 300), boost(0.1, 300)
for m in [1, 5, 20, 100, 300]:
    print(f"{m:>5}   {h1[m][0]:.3f} / {h1[m][1]:.3f}      {h2[m][0]:.3f} / {h2[m][1]:.3f}")
print(f"best test MSE: lr=1.0 {min(v[1] for v in h1.values()):.3f} at round {min(h1, key=lambda k: h1[k][1])}, "
      f"lr=0.1 {min(v[1] for v in h2.values()):.3f} at round {min(h2, key=lambda k: h2[k][1])}")

# The library version agrees with the hand-written loop
g = GradientBoostingRegressor(n_estimators=100, learning_rate=0.1, max_depth=2, random_state=0).fit(xtr, ytr)
print(f"sklearn GradientBoostingRegressor, 100 trees: test MSE {np.mean((yte - g.predict(xte)) ** 2):.3f}")

# Tabular classification: a stump, AdaBoost on stumps, a random forest and histogram gradient boosting
X, Y = make_classification(n_samples=1500, n_features=20, n_informative=8, flip_y=0.05, random_state=1)
for name, m in [("one stump", DecisionTreeClassifier(max_depth=1)),
                ("AdaBoost, 200 stumps", AdaBoostClassifier(n_estimators=200, random_state=0)),
                ("random forest, 100", RandomForestClassifier(n_estimators=100, random_state=0)),
                ("hist gradient boosting", HistGradientBoostingClassifier(random_state=0))]:
    print(f"{name:<24} 5-fold accuracy {cross_val_score(m, X, Y, cv=5).mean():.3f}")

round   lr=1.0 train/test    lr=0.1 train/test
    1   0.252 / 0.366      0.951 / 1.083
    5   0.132 / 0.246      0.539 / 0.669
   20   0.053 / 0.270      0.148 / 0.268
  100   0.001 / 0.316      0.066 / 0.223
  300   0.000 / 0.319      0.028 / 0.252
best test MSE: lr=1.0 0.226 at round 9, lr=0.1 0.219 at round 51
sklearn GradientBoostingRegressor, 100 trees: test MSE 0.223
one stump                5-fold accuracy 0.707
AdaBoost, 200 stumps     5-fold accuracy 0.823
random forest, 100       5-fold accuracy 0.892
hist gradient boosting   5-fold accuracy 0.891

The hand-written loop is ten lines, and at 100 trees with learning rate 0.1 it gets a test MSE of 0.223, the same as scikit-learn's GradientBoostingRegressor with the same settings. Note the training error: with learning rate 1.0 it reaches 0.000 by round 300 while test error rises to 0.319.

On the 20-feature classification task, histogram gradient boosting scores 0.891 and a random forest 0.892: on clean synthetic data the two tie. On real tabular data with messy features, interactions and many irrelevant columns, well-tuned gradient boosting more often comes out ahead, which is why it dominates competitions and production tabular models. Measure it on your own data instead of assuming.

Why boosted trees do so well on tables

• Trees handle mixed scales, skewed distributions, missing values and thresholds without preprocessing.
• Shallow trees added in sequence capture interactions between a few features at a time, which matches how tabular signal often looks.
• Shrinkage, row and column subsampling and early stopping give strong regularization that is easy to tune.

Stochastic gradient boosting

Training each tree on a random subsample of rows (often 50 to 80 percent) and columns adds bagging-style variance reduction to boosting and speeds training. All the major libraries support it.

Trade-offs

Common mistakes

• Using many deep trees in boosting as you would in a forest; boosting wants shallow trees.
• Fixing the number of trees without early stopping, then overfitting.
• Raising the learning rate to train faster and losing accuracy; lower it and add trees instead.
• Tuning the number of rounds on the test set.
• Running AdaBoost on data with noisy labels, where it keeps upweighting the mislabelled points.

In the wild

Gradient boosted trees are the workhorse for ranking, click prediction, fraud scoring, credit risk and forecasting features in industry, usually through XGBoost, LightGBM or CatBoost, covered in the next lesson. Search engines long used boosted trees for learning to rank ( Learning to rank ), and on platforms that host data science competitions, winning solutions for tabular problems very often include a gradient boosting model.

Check yourself

Recap