Ensembles: forests and boosting

The last lesson ended on a weakness: decision trees are unstable. Change a few training points and the first question can change, and every question below it with it. A deep tree also memorizes noise. This lesson turns both problems into a strength. Instead of trusting one tree, grow many and combine them. A combination of models is called an ensembleEnsembleA model made by combining the predictions of many models, for example by voting or adding them up. It works best when the members are good and make different mistakes.Open in glossary, and two ways of building one dominate: average many independent trees (bagging and random forests), or build trees one after another, each correcting the last (boosting).

Why a vote helps

Suppose each of 25 voters is right 70% of the time, and they make their mistakes independently. The majority is wrong only when at least 13 of the 25 are wrong at once, which happens less than 2% of the time. The vote is far more reliable than any voter.

The catch is the word independently. Twenty-five copies of the same tree make the same mistakes, and their vote is no better than one. An ensemble needs members that are each reasonably good and also different from each other.

Bagging: many trees from resampled data

Where do different trees come from, if there is only one training set? Leo Breiman’s answer, which he called baggingBaggingBootstrap aggregating: train many models, each on its own bootstrap sample of the data, and combine them by voting or averaging. It mainly reduces the variance of unstable models such as deep trees.Open in glossary (bootstrap aggregating, Machine Learning, 1996), is to fake new training sets by resampling. A bootstrapBootstrap sampleA sample of n points drawn with replacement from n points, so some appear more than once and about 37% are left out. Used to estimate uncertainty and to train varied models.Open in glossary sample, an idea from statistician Bradley Efron (1979), draws $n$ points from the $n$ training points with replacement: some points appear twice or more, and others not at all. Each tree trains on its own bootstrap sample, and the trees vote.

How many points does a bootstrap sample miss? Each draw misses a given point with probability $1 - 1/n$, so all $n$ draws miss it with probability $(1 - 1/n)^n$, which is about $1/e \approx 36.8\%$ for large $n$. So each tree never sees about a third of the points.

Random forests

Bootstrap samples overlap a lot, so bagged trees still tend to ask the same strong question first. A random forestRandom forestAn ensemble of decision trees, each trained on a bootstrap sample and allowed to choose only among a random subset of features at every split, combined by majority vote.Open in glossary (Breiman, Machine Learning, 2001) adds a second source of variety: at every split, the tree may choose only among a small random subset of the features. Breiman’s simplest version fixes the subset size $F$ in advance, and he tried values as small as $F = 1$. With only two features, as in the lab, that means each split looks at one feature chosen at random.

Random forests come with a free accuracy check. Each point was left out of roughly a third of the trees, so you can classify it using only those trees. The share of training points classified correctly this way is the out-of-bag estimate (its complement is the out-of-bag errorOut-of-bag errorAn estimate of a bagged ensemble's error on new data, computed by judging each training point only with the models whose bootstrap samples left it out. It needs no separate test set.Open in glossary), and it needs no separate test set.

import numpy as np
from math import comb

rng = np.random.default_rng(0)

# A bootstrap sample: n draws with replacement from n points.
n = 150
left_out = [n - len(np.unique(rng.integers(0, n, n))) for _ in range(2000)]
print(f"share left out of a bootstrap sample: {np.mean(left_out) / n:.3f}")
print(f"(1 - 1/n)^n = {(1 - 1 / n) ** n:.3f}, 1/e = {np.exp(-1):.3f}")

# Why voting helps: if each of k voters is right 70% of the time and they
# err independently, how often is the majority right?
for k in (1, 5, 25, 51):
    majority = sum(comb(k, r) * 0.7**r * 0.3**(k - r) for r in range(k // 2 + 1, k + 1))
    print(f"{k:3d} independent voters: majority right {majority:.3f}")

share left out of a bootstrap sample: 0.366
(1 - 1/n)^n = 0.367, 1/e = 0.368
  1 independent voters: majority right 0.700
  5 independent voters: majority right 0.837
 25 independent voters: majority right 0.983
 51 independent voters: majority right 0.999

On the Circle data with labels flipped at random 10% of the time, one fully grown tree gets 83.3% of the test points right. A forest of 100 such trees, each overfitting in its own way, gets 88.7%. The flipped points still pull individual trees, but each flipped point is missing from about a third of the bootstrap samples and outvoted in many others, so the vote smooths it away. After 15 trees, every training point has been left out at least once, and from then on the out-of-bag estimate stays within 2 points of the test accuracy, without ever touching the test points.

The voting arithmetic above assumed independent voters; real trees trained on overlapping data are correlated, so the gain is smaller than that calculation suggests. Breiman proved an upper bound on a forest’s error that rises with the correlation between the trees and falls as the individual trees get stronger, which is why random feature choices, by making the trees less alike, can help.

Boosting: trees that fix each other’s mistakes

Bagging grows its trees independently. BoostingBoostingBuilding an ensemble in sequence, where each new model concentrates on what the models before it got wrong, and the final prediction is a weighted combination of all of them.Open in glossary grows them in sequence, and each new model concentrates on what the earlier ones got wrong. The members are often deliberately weak, such as a decision stumpDecision stumpA decision tree with a single question and two leaves. Weak on its own, it is a common building block for boosting.Open in glossary: a tree with a single question.

AdaBoostAdaBoostA boosting method that keeps a weight on every training point, raises the weights of points the latest weak model got wrong, and gives each model a say based on its weighted error.Open in glossary, introduced by Yoav Freund and Robert Schapire in 1995 (expanded in 1997, later awarded the Gödel Prize), keeps a weight on every training point. Each round:

1. Train a stump that makes the fewest weighted mistakes. Its weighted error is $\varepsilon_t$.
2. Give it a say in the final vote, $\alpha_t = \tfrac{1}{2}\ln\tfrac{1 - \varepsilon_t}{\varepsilon_t}$. A stump with error near one half gets almost no say; a nearly perfect one gets a large say.
3. Reweight the points: multiply each weight by $e^{\alpha_t}$ if the stump got the point wrong and by $e^{-\alpha_t}$ if it got it right, then rescale so the weights sum to 1.

The final classifier is the sign of the weighted vote, $\operatorname{sign}\left(\sum_t \alpha_t h_t(x)\right)$, where each stump $h_t$ answers $+1$ for class B or $-1$ for class A.

import numpy as np

# Points on a line with labels +1 and -1. No single threshold separates them.
x = np.array([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
y = np.array([1, 1, -1, -1, 1, 1, 1, -1, -1, -1])

def best_stump(w):
    # Try every threshold and both directions; keep the lowest weighted error.
    best = (np.inf, None, None)
    for t in (x[:-1] + x[1:]) / 2:
        for sign in (1, -1):
            pred = np.where(x <= t, sign, -sign)
            err = w[pred != y].sum()
            if err < best[0]:
                best = (err, t, sign)
    return best

w = np.full(len(x), 1 / len(x))  # start with equal weights
score = np.zeros(len(x))
for t in range(1, 6):
    err, thr, sign = best_stump(w)
    alpha = 0.5 * np.log((1 - err) / err)  # the stump's say in the vote
    pred = np.where(x <= thr, sign, -sign)
    w = w * np.exp(-alpha * y * pred)      # raise weights of mistakes
    w = w / w.sum()
    score += alpha * pred
    right = np.mean(np.sign(score) == y)
    print(f"round {t}: x <= {thr} -> {sign:+d}, error {err:.3f}, "
          f"alpha {alpha:.3f}, combined accuracy {right:.0%}")

round 1: x <= 7.5 -> +1, error 0.200, alpha 0.693, combined accuracy 80%
round 2: x <= 2.5 -> +1, error 0.188, alpha 0.733, combined accuracy 70%
round 3: x <= 4.5 -> -1, error 0.192, alpha 0.718, combined accuracy 100%
round 4: x <= 7.5 -> +1, error 0.190, alpha 0.723, combined accuracy 100%
round 5: x <= 2.5 -> +1, error 0.191, alpha 0.721, combined accuracy 100%

The reweighting is precisely balanced: after each update, the stump that was just added has a weighted error of exactly one half on the new weights. It is useless on the new problem, so the next stump must find something different. On the noise-free Circle data, 16 stumps, each a single straight cut, together classify every training point correctly.

Two limits show up in the lab. A sum of stumps is a function of the first feature plus a function of the second, and no such sum can produce XOR’s checkerboard, so on XOR the test accuracy stays below 60% in all 200 rounds the lab runs. Boosting deeper trees, which can ask about both features in turn, can represent it. And AdaBoost chases noise: on Moons with 10% label noise, the flipped points, 12 of the 150 training points (8%), end up holding over 40% of all the weight. Breiman reported that random forests are more robust than AdaBoost when labels are noisy.

Gradient boosting: fitting what is still wrong

Gradient boosting, described by Jerome Friedman in 2001, generalizes the idea to any loss you can differentiate. The demo below does regression with squared error, where it is easiest to see. Start with the simplest model, a constant: the average of the targets. Then repeat:

1. Compute the residuals $r_i = y_i - F(x_i)$: what the current model $F$ still gets wrong.
2. Fit a small regression tree $h$ to the residuals.
3. Add a fraction of it: $F \leftarrow F + \nu\, h$, where $\nu$ is the learning rate.

Why “gradient”? For the loss $\tfrac{1}{2}(y - F)^2$, the derivative with respect to the prediction $F$ is $-(y - F)$, so the residual is exactly the negative gradient. Each round is a step of gradient descent, but instead of nudging a few weights, it nudges the whole function, using a tree to say which way to move. For other losses the tree fits the negative gradient of that loss instead of the plain residual. That is the essence of gradient boostingGradient boostingA boosting method that adds small trees one at a time, each fitted to the negative gradient of the loss (for squared error, the residuals), scaled by a learning rate.Open in glossary.

import numpy as np

x = np.array([0.05, 0.15, 0.25, 0.35, 0.45, 0.55, 0.65, 0.75, 0.85, 0.95])
y = np.array([0.4, 0.9, 1.1, 0.7, 0.2, -0.5, -0.9, -0.6, 0.1, 0.6])

def fit_stump(x, r):
    # The threshold whose two side means fit the residuals r best.
    best = (np.inf, None)
    for t in (x[:-1] + x[1:]) / 2:
        left, right = r[x <= t], r[x > t]
        sse = ((left - left.mean())**2).sum() + ((right - right.mean())**2).sum()
        if sse < best[0]:
            best = (sse, (t, left.mean(), right.mean()))
    return best[1]

learning_rate = 0.5
F = np.full(len(x), y.mean())  # start from the average
for m in range(1, 31):
    residuals = y - F               # the negative gradient of squared error / 2
    t, lo, hi = fit_stump(x, residuals)
    F += learning_rate * np.where(x <= t, lo, hi)
    if m in (1, 2, 5, 10, 30):
        print(f"after {m:2d} stumps: training MSE {np.mean((y - F)**2):.4f}")

after  1 stumps: training MSE 0.2447
after  2 stumps: training MSE 0.1907
after  5 stumps: training MSE 0.0937
after 10 stumps: training MSE 0.0444
after 30 stumps: training MSE 0.0068

Boosting can overfit. With stumps and a learning rate of 1, test error is lowest after 20 trees (0.124) and then creeps up as later stumps fit the noise in just 40 points. A smaller learning rate, which Friedman called shrinkage, takes smaller steps: at 0.1 the best test error comes after about 200 trees and is lower, 0.118. The number of rounds has to be chosen, usually by watching the error on held-out data and stopping early.

Tree ensembles remain strong on tables of data, where each column is a separate measurement. A 2022 benchmark of 45 datasets by Léo Grinsztajn, Edouard Oyallon, and Gaël Varoquaux found that tree-based models, gradient boosting and random forests among them, still outperformed deep learning on typical medium-sized tabular datasets (around 10,000 rows). Images, audio, and text are where neural networks dominate.