A1 · Supervised Machine Learning in Depth

Boosting: AdaBoost and Gradient Boosting

Boosting builds an ensemble sequentially, each new weak model focusing on the errors of the ensemble so far. AdaBoost re-weights training examples, increasing the weight of misclassified ones. Gradient boosting fits each new tree to the negative gradient of the loss (for squared error, the residuals) and adds it with a learning rate: Fₘ = Fₘ₋₁ + η·hₘ.

18 min Advanced Jump to the activity

What you need: The earlier topics of this module, and its prerequisites.

Definition

Can many weak learners, each fixing the last one's mistakes, become strong?

Boosting builds an ensemble sequentially, each new weak model focusing on the errors of the ensemble so far. AdaBoost re-weights training examples, increasing the weight of misclassified ones. Gradient boosting fits each new tree to the negative gradient of the loss (for squared error, the residuals) and adds it with a learning rate: Fₘ = Fₘ₋₁ + η·hₘ.

In simple words

The first small tree makes a rough guess. The second tree learns only what the first got wrong. The third fixes what's still wrong, and so on. A small learning rate means each tree only corrects a little, which needs more trees but generalises better.

Why it matters

Gradient boosting is the most successful method for tabular data in industry and competitions, behind fraud detection, credit scoring, ranking and demand forecasting.

Key terms

Boosting
Building models one after another, each focusing on the mistakes of the ensemble so far.
Weak learner
A simple model only slightly better than chance, such as a tree stump of depth 1.
AdaBoost
Reweights training rows so misclassified ones count more for the next learner.
Gradient boosting
Fits each new tree to the negative gradient of the loss, the residuals for squared error.
Learning rate (shrinkage)
A factor such as 0.05 that scales each tree's contribution, trading speed for accuracy.
Early stopping
Stopping when validation loss stops improving for a set number of rounds.

Explained in detail

Learning from mistakes, one model at a time

Bagging trains models independently and averages them to reduce variance; boosting trains them sequentially to reduce bias. AdaBoost, published by Yoav Freund and Robert Schapire in 1997, starts with equal weights on all rows, trains a stump, increases the weights of misclassified rows and trains the next stump on the reweighted data. Each stump gets a vote proportional to its accuracy, and the final prediction is the weighted vote. Gradient boosting, formalised by Jerome Friedman in 2001, generalises this to any differentiable loss. For house prices with squared error, the first model predicts the mean price; the next tree is fitted to the residuals, actual minus predicted; its predictions, multiplied by a learning rate such as 0.1, are added; and the process repeats hundreds of times.

A tiny worked example

Three houses cost 50, 60 and 90 lakh. The first prediction is the mean, 66.7 for all, leaving residuals of −16.7, −6.7 and 23.3. A stump splits the houses into the first two and the third, predicting −11.7 and 23.3 for those groups. With learning rate 0.5, predictions become 60.8, 60.8 and 78.3, and the new residuals, −10.8, −0.8 and 11.7, are smaller. Each round chips away at what is left. A small learning rate needs more trees but usually generalises better, so learning rate and number of trees are tuned together, with early stopping on a validation set deciding when to stop.

Bagging / random forestBoosting
TrainingParallel, independent modelsSequential, each fixing the last
Mainly reducesVarianceBias (and variance with shrinkage)
Base modelsDeep treesShallow trees, depth 3 to 8
Sensitivity to noise and tuningLowHigher; can overfit noisy labels

Gradient boosting is usually the most accurate family for tabular data and dominates data-science competitions. Its main risks are overfitting noisy labels and the need to tune several interacting hyperparameters. Scikit-learn's HistGradientBoostingClassifier bins features into histograms for speed, handles missing values natively and is a good default; the next topic covers XGBoost, LightGBM and CatBoost, which add further engineering for speed and accuracy.

AdaBoost found an early famous use in the Viola-Jones face detector of 2001, which combined thousands of simple features this way.

How it works

Bagging / random forestBoosting
Trees builtIndependently, in parallelSequentially
Each treeDeep, low bias, high varianceShallow, high bias
Mainly reducesVarianceBias
Overfits with more trees?RarelyYes: use early stopping

The maths

Additive model built stage by stage
Each tree fits the negative gradient (pseudo-residuals)
AdaBoost model weight
Weighted error of the m-th weak learner

In code

Gradient boosting from scratch on residuals for a regression curve, then AdaBoost and gradient boosting classifiers improving stage by stage.

boosting.py
import numpy as np
from sklearn.datasets import load_breast_cancer
from sklearn.ensemble import AdaBoostClassifier, GradientBoostingClassifier
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeRegressor

rng = np.random.default_rng(0)
x = np.sort(rng.uniform(0, 6, 200)).reshape(-1, 1)
y = np.sin(x).ravel() + rng.normal(scale=0.2, size=200)
prediction = np.full_like(y, y.mean())
for m in range(1, 51):
    residuals = y - prediction                                   # negative gradient of squared error
    stump = DecisionTreeRegressor(max_depth=2).fit(x, residuals)
    prediction += 0.1 * stump.predict(x)
    if m in (1, 10, 50):
        print(f"From scratch, {m:>2} trees: MSE {np.mean((y - prediction) ** 2):.3f}")

X, yc = load_breast_cancer(return_X_y=True)
X_tr, X_te, y_tr, y_te = train_test_split(X, yc, test_size=0.3, random_state=0)
ada = AdaBoostClassifier(n_estimators=200, random_state=0).fit(X_tr, y_tr)
gb = GradientBoostingClassifier(n_estimators=200, learning_rate=0.1, max_depth=2, random_state=0).fit(X_tr, y_tr)
print("AdaBoost test accuracy:", round(ada.score(X_te, y_te), 3))
staged = [np.mean(p == y_te) for p in gb.staged_predict(X_te)]
for m in (1, 10, 50, 200):
    print(f"Gradient boosting after {m:>3} trees: {staged[m - 1]:.3f}")

Output

From scratch,  1 trees: MSE 0.437
From scratch, 10 trees: MSE 0.119
From scratch, 50 trees: MSE 0.032
AdaBoost test accuracy: 0.988
Gradient boosting after   1 trees: 0.632
Gradient boosting after  10 trees: 0.930
Gradient boosting after  50 trees: 0.947
Gradient boosting after 200 trees: 0.971

Try it yourself

Boosting step by step

Put one round of gradient boosting for regression in order.

  1. 1Repeat with the new residuals
  2. 2Start with a constant prediction: the mean of y
  3. 3Compute residuals: true value minus current prediction
  4. 4Add the tree's output, scaled by the learning rate
  5. 5Fit a small tree to the residuals

Common mistakes

  • Using a large learning rate and many trees without early stopping.
  • Growing deep trees inside boosting; shallow trees (depth 2 to 6) work best.
  • Confusing boosting with bagging: boosting is sequential and can overfit.

Check yourself

Question 1

1. In gradient boosting with squared error, each tree fits…

Question 2

2. What does round two of AdaBoost focus on?

Question 3

3. A smaller learning rate usually needs…

Summary

  • Boosting adds weak models in sequence, each fixing earlier errors.
  • Gradient boosting fits the negative gradient: Fₘ = Fₘ₋₁ + η·hₘ.
  • Use shallow trees, a small learning rate and early stopping.

Read it. Now try it yourself.

Open the interactive activity

Finished reading?

Sources: scikit-learn: Gradient boosting · Friedman, Greedy Function Approximation (2001)