Machine Learning
Topic 18 · Supervised algorithms · ⏱ about 5 h

Ensembles: Random Forests & Boosting

Many weak or noisy models combined into one strong model.

Show:
In this topic
Beginner

Bagging & Random Forests

An ensemble combines many models into one, in the hope that the group will be more accurate than any of its members. The first and simplest family of ensembles is based on a technique called bagging, short for bootstrap aggregating.

trainingdatabootstrap 1tree 1bootstrap 2tree 2bootstrap 3tree 3average / votetrained independently, in parallel → reduces variance
Bagging: train many trees on bootstrap samples of the data, then average their predictions.

Bagging starts by creating many slightly different versions of the training set using bootstrap sampling. A bootstrap sample is made by drawing nn examples from the original nn at random, with replacement, so the same example can be drawn more than once and some examples are not drawn at all. Each bootstrap sample is therefore a little different from the others. A separate model is trained on each one, and their predictions are combined, by averaging for regression or by majority vote for classification.

Why does this help? Recall from the bias–variance topic that a high-variance model, such as a deep decision tree, changes a lot when its training data change. Each bagged model makes its own particular mistakes, driven by the quirks of its own bootstrap sample. When we average many such models, these individual mistakes partly cancel out, while the genuine pattern, which they all capture, remains. Bagging therefore mainly reduces variance.

A random forest is bagging applied to decision trees, plus one extra ingredient. When each tree is choosing a split, it is only allowed to consider a random subset of the features, typically about d\sqrt d of the dd features for classification. Without this, if one feature were very strong, almost every tree would split on it first and the trees would end up similar, so averaging them would gain little. Restricting the choice forces the trees to differ, and averaging different trees cancels more of their errors.

Bagging comes with a free bonus. Each bootstrap sample leaves out, on average, about 37% of the original examples, and these are called the out-of-bag examples for that tree. We can predict each training example using only the trees that never saw it, and compare those predictions with the true labels. The resulting out-of-bag error is an almost free estimate of how the forest will perform on new data, without setting aside a separate validation set.

Random forests are robust, need very little tuning, rarely overfit badly as more trees are added, and report feature importances. For these reasons they are an excellent first model to try on any table of data.

Interactive: this part runs in your browser.

Interactive. Bootstrap samples: drawing with replacement, and the 63% rule.
Beginner

Watch it: Ensembles: bagging (random forests) and boosting

A short narrated animation. Press ▶ Play, or step through it with ⏮ ⏭. Tick 🔊 narrate to hear each step.

Interactive: this part runs in your browser.

Beginner

Boosting

The second family of ensembles, boosting, takes almost the opposite approach to bagging. Instead of training many models independently and averaging them, boosting trains models one after another, and each new model is designed to fix the mistakes of the ensemble built so far.

tree 1residualstree 2residualstree 3F(x) = f₀ + η·tree₁ + η·tree₂ + η·tree₃ + …trained one after another, each fixing the last → reduces bias
Boosting: each new tree is trained on the errors (residuals) left by the trees before it, and the trees are added together.

The models used in boosting are deliberately weak learners: simple models, typically very shallow decision trees, that on their own are only a little better than guessing. Each has high bias, but by adding many of them together, each correcting what the previous ones got wrong, the ensemble gradually builds up a very accurate model. Boosting therefore mainly reduces bias.

There are two main versions. AdaBoost, the original boosting algorithm, keeps a weight for each training example. After each round, it increases the weights of the examples the latest model got wrong, so that the next model concentrates on these hard cases. The final prediction is a weighted vote, in which more accurate models get a bigger say.

Gradient boosting is more general and more widely used. It starts with a simple prediction, such as the average target value, and then repeatedly adds a small tree trained to predict the remaining errors of the current ensemble. For squared-error loss these errors are literally the residuals y−y^y - \hat y; for other losses, the tree is trained on the gradient of the loss, which is where the name comes from. Each new tree's predictions are multiplied by a small learning rate (often 0.05 to 0.1) before being added, so that the ensemble improves in many small, careful steps rather than a few large, overconfident ones.

Highly optimised gradient-boosting libraries, notably XGBoost, LightGBM and CatBoost, add regularisation, clever split-finding and support for missing values and categorical features. On tabular data (spreadsheet-like tables of features), they are very often the most accurate models available, and they dominate data-science competitions.

Boosting has more hyperparameters to tune than a random forest: the number of trees, the learning rate, the depth of each tree, and the fraction of rows and columns sampled for each tree. Unlike a random forest, boosting can overfit if too many trees are added, because each new tree keeps fitting the remaining errors, eventually including the noise. The standard safeguard is early stopping: monitor performance on a validation set and stop adding trees when it stops improving.

Interactive: this part runs in your browser.

Breakdown. A boosted prediction is the starting guess plus one small correction per tree.
Beginner

Bagging vs boosting at a glance

Bagging and boosting both combine many trees, but they do so in opposite ways and for opposite reasons, so it is worth comparing them directly.

In bagging and random forests, the trees are trained independently and in parallel, each on its own bootstrap sample. The individual trees are grown deep, so each one has low bias but high variance, and averaging them reduces that variance. Because each tree is trained independently, adding more trees almost never causes overfitting; it just costs more computation. Random forests need little tuning and work well with default settings.

In boosting, the trees are trained sequentially, each one depending on the errors of those before it. The individual trees are kept shallow, so each one has high bias but low variance, and adding them up step by step reduces that bias. Because each new tree specifically targets the remaining errors, too many trees can eventually overfit, so boosting needs early stopping and more careful tuning, but in return it often reaches higher accuracy.

Bagging / Random forestBoosting
How trees are trainedin parallel, independentlysequentially, each fixing the last
Individual treesdeep (low bias, high variance)shallow (high bias, low variance)
Mainly reducesvariancebias
Overfits as more trees are added?rarelyyes, without early stopping
Tuning effortlowhigher

A third approach, stacking, combines models of different kinds. Several diverse models, perhaps a random forest, a gradient-boosting model and a logistic regression, are trained first. Then a final "meta-model" is trained to combine their predictions, learning which models to trust in which situations. To avoid leakage, the meta-model must be trained on predictions that each base model made for examples it did not see during its own training, which is usually done with cross-validation.

Try it

Try it: bagging and boosting side by side

In bagging mode, add bootstrap trees and watch their jagged predictions average into a smooth curve. In boosting mode, add trees one at a time and watch each one chip away at the remaining residuals.

Interactive: this part runs in your browser.

Intermediate · Maths

Why bootstrap leaves out 37%, and why averaging helps

📐 Maths you'll need: m-prob · m-notation
💡 The idea in plain words

Each bootstrap sample leaves out about a third of the rows, which gives free test data for each tree. Averaging many trees helps only to the extent that their mistakes differ, which is why random forests deliberately make trees different. AdaBoost goes the other way: it trains models one after another, each paying extra attention to the examples the previous ones got wrong.

🔤 Symbols in this section
(1−1/n)n(1 - 1/n)^nchance a given row is never drawn
e−1≈0.368e^{-1}\approx 0.368its limit
mmfeatures considered per split
εt\varepsilon_tweighted error of learner t
αt\alpha_tvote weight of learner t
ht(x)∈{−1,+1}h_t(x)\in\{-1,+1\}prediction of weak learner t

This section explains two pieces of mathematics behind ensembles: where the famous 37% out-of-bag figure comes from, and how AdaBoost decides how much to trust each model and how to re-weight the examples.

The out-of-bag fraction. A bootstrap sample draws nn times, with replacement, from nn examples. On any single draw, a particular example is not picked with probability 1−1n1 - \frac1n. The draws are independent, so the probability that it is never picked in all nn draws is

(1−1n)n  →  n→∞    e−1≈0.368. \Big(1 - \frac1n\Big)^n \;\xrightarrow{\;n\to\infty\;}\; e^{-1} \approx 0.368.

The limit is a standard result from calculus, and the approximation is already very good for modest nn (for n=100n = 100 the value is 0.366). So each tree sees about 63.2% of the distinct examples, and the remaining 36.8% are its out-of-bag examples. If we predict each training example using only the trees for which it was out-of-bag, we get predictions from models that never saw it, which gives a nearly free estimate of test error.

How random forests reduce variance. From the bias–variance topic, averaging BB trees that each have variance σ2\sigma^2 and pairwise correlation ρ\rho gives a variance of ρσ2+1−ρBσ2\rho\sigma^2 + \frac{1-\rho}{B}\sigma^2. Adding trees removes the second term, but the first term, ρσ2\rho\sigma^2, remains. Random forests attack this floor by making the trees less correlated: each split considers only mm randomly chosen features out of dd. The defaults are m=dm = \sqrt d for classification and m=d/3m = d/3 (or sometimes dd) for regression. A smaller mm makes the trees more different, lowering ρ\rho, but it also makes each tree slightly weaker, so mm is a hyperparameter worth tuning.

AdaBoost. For a two-class problem with labels y∈{−1,+1}y\in\{-1, +1\}, AdaBoost runs as follows. Every example starts with the same weight. In round tt, a weak learner hth_t is trained on the weighted data, and its weighted error rate εt\varepsilon_t is computed. The learner then receives a voting weight

αt=12ln⁡1−εtεt. \alpha_t = \tfrac12\ln\frac{1-\varepsilon_t}{\varepsilon_t}.

This is large when εt\varepsilon_t is small (an accurate learner gets a big say), zero when εt=0.5\varepsilon_t = 0.5 (a learner no better than guessing gets no say), and it can't be computed for a perfect learner, which in practice never occurs with weak learners. Next, every example's weight is updated and the weights are rescaled to sum to 1:

wi←wi e−αtyiht(xi). w_i \leftarrow w_i\,e^{-\alpha_t y_i h_t(x_i)}.

If example ii was classified correctly, yiht(xi)=+1y_i h_t(x_i) = +1 and its weight is multiplied by e−αt<1e^{-\alpha_t} < 1, so it shrinks. If it was misclassified, yiht(xi)=−1y_i h_t(x_i) = -1 and its weight is multiplied by eαt>1e^{\alpha_t} > 1, so it grows, and the next learner will pay more attention to it. After TT rounds, the final classifier is a weighted vote,

F(x)=sign⁡(∑t=1Tαtht(x)). F(x) = \operatorname{sign}\Big(\sum_{t=1}^{T} \alpha_t h_t(x)\Big).

Although AdaBoost was originally designed by intuition, it was later shown to be exactly a step-by-step ("forward stagewise") minimisation of the exponential loss ∑ie−yiF(xi)\sum_i e^{-y_i F(x_i)}. That insight led directly to gradient boosting, which works with any loss.

Key takeaway. ~36.8% of rows are out-of-bag for each tree; forests reduce variance by decorrelating trees; AdaBoost re-weights mistakes and minimises exponential loss.
Advanced

Gradient boosting as gradient descent in function space, and XGBoost

📐 Maths you'll need: m-calculus · m-gradients · m-optim
💡 The idea in plain words

Gradient boosting is gradient descent, but instead of nudging weights, each step adds a small tree that nudges the predictions in the direction that reduces the loss most. For squared error, that direction is simply the residuals. XGBoost also uses the curvature (second derivative), like Newton's method, to decide each leaf's value and whether a split is worth it.

🔤 Symbols in this section
Fm(x)F_m(x)ensemble after m trees
rimr_{im}pseudo-residual: −∂L/∂F for example i
ν\nulearning rate (shrinkage)
gi, hig_i,\ h_ifirst and second derivatives of the loss
Gj, HjG_j,\ H_jsums of g and h in leaf j
wj∗w_j^*optimal leaf value
γ, λ\gamma,\ \lambdapenalty per leaf, L2 penalty on leaf values

Gradient boosting has an elegant mathematical interpretation: it is gradient descent, carried out not on a set of weights but on the model's predictions themselves. This section develops that idea and then shows how XGBoost refines it.

Gradient descent in function space. We want a function FF that minimises the total loss ∑iL(yi,F(xi))\sum_i L(y_i, F(x_i)). Think of the nn predictions on the training set, F(x1),…,F(xn)F(x_1), \dots, F(x_n), as the quantities we are allowed to adjust. Gradient descent would move each prediction a small step in the direction that reduces the loss most steeply, which is the negative of the loss's derivative with respect to that prediction. These negative derivatives are called pseudo-residuals:

rim=−∂L(yi,F(xi))∂F(xi)∣F=Fm−1. r_{im} = -\left.\frac{\partial L(y_i, F(x_i))}{\partial F(x_i)}\right|_{F = F_{m-1}} .

There is one catch: knowing the ideal adjustment at the training points doesn't tell us what to do for new inputs. So instead of adjusting the predictions directly, we fit a small regression tree hmh_m to the pseudo-residuals. The tree learns to produce those adjustments from the features, and therefore generalises to inputs it hasn't seen. We then add it to the model, scaled by the learning rate ν\nu:

Fm(x)=Fm−1(x)+ν hm(x). F_m(x) = F_{m-1}(x) + \nu\, h_m(x).

The choice of loss determines what the trees chase. For squared-error loss 12(y−F)2\tfrac12(y - F)^2, the pseudo-residual is y−Fy - F, literally the residual, so each tree predicts the current errors. For log-loss in classification, with p=σ(F)p = \sigma(F), the pseudo-residual is y−py - p. For absolute-error loss, it is sign⁡(y−F)\operatorname{sign}(y - F), which ignores the size of the errors and so makes the method robust to outliers. A small learning rate, together with training each tree on a random subsample of rows and columns (stochastic gradient boosting), acts as regularisation.

XGBoost's second-order refinement. XGBoost improves on this by using the curvature of the loss as well as its slope, much as Newton's method improves on gradient descent. For each example it computes the first derivative gig_i and the second derivative hih_i of the loss with respect to the current prediction. A second-order Taylor expansion then approximates how much the loss would change if a new tree added a value wjw_j to every example in leaf jj. Adding a penalty γ\gamma for each of the tree's TT leaves and an L2 penalty λ\lambda on the leaf values, the objective for one new tree becomes

Obj≈∑j=1T[Gjwj+12(Hj+λ)wj2]+γT, \text{Obj} \approx \sum_{j=1}^{T}\Big[G_j w_j + \tfrac12 (H_j + \lambda) w_j^2\Big] + \gamma T,

where GjG_j and HjH_j are the sums of gig_i and hih_i over the examples in leaf jj. Each leaf's term is a simple quadratic in wjw_j, and setting its derivative to zero gives the best leaf value:

wj∗=−GjHj+λ. w_j^* = -\frac{G_j}{H_j + \lambda}.

Substituting this back gives the best achievable objective for any tree structure, and from it a formula for how much a candidate split improves the objective:

Gain=12[GL2HL+λ+GR2HR+λ−(GL+GR)2HL+HR+λ]−γ. \text{Gain} = \tfrac12\left[\frac{G_L^2}{H_L+\lambda} + \frac{G_R^2}{H_R+\lambda} - \frac{(G_L+G_R)^2}{H_L+H_R+\lambda}\right] - \gamma.

The bracket compares the quality of the left and right children with the quality of the unsplit parent, and γ\gamma is the price of the extra leaf. A split is made only if its gain is positive, so γ\gamma acts as built-in pruning. LightGBM adds histogram-based split finding and grows trees "leaf-wise", always splitting the single most promising leaf, while CatBoost adds a careful treatment of categorical features that avoids target leakage.

Key takeaway. Each boosting tree fits the negative gradient of the loss; XGBoost's leaf value is −G/(H + λ) and a split is kept only if its gain beats γ.
Code

Code: gradient boosting from scratch, then the real libraries

Twenty lines of NumPy + a regression stump learner reproduce the core of gradient boosting for squared loss.

Python · gradient boosting from scratch (squared loss)
import numpy as np
from sklearn.tree import DecisionTreeRegressor

rng = np.random.default_rng(0)
X = rng.uniform(-3, 3, size=(400, 1))
y = np.sin(X[:, 0]) + 0.3 * rng.normal(size=400)
Xtr, ytr, Xte, yte = X[:300], y[:300], X[300:], y[300:]

class GradientBoostingScratch:
    def __init__(self, n_trees=200, lr=0.1, depth=2):
        self.n_trees, self.lr, self.depth = n_trees, lr, depth
    def fit(self, X, y):
        self.f0 = y.mean()                        # start from the best constant
        F = np.full(len(y), self.f0)
        self.trees = []
        for m in range(self.n_trees):
            residuals = y - F                     # = negative gradient of 1/2 (y - F)^2
            tree = DecisionTreeRegressor(max_depth=self.depth).fit(X, residuals)
            F += self.lr * tree.predict(X)
            self.trees.append(tree)
        return self
    def predict(self, X):
        return self.f0 + self.lr * sum(t.predict(X) for t in self.trees)

gb = GradientBoostingScratch().fit(Xtr, ytr)
print("scratch GB test MSE:", np.mean((gb.predict(Xte) - yte) ** 2).round(4))
Open in playground ↗
Python · scikit-learn forests and boosting
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.ensemble import (RandomForestClassifier, HistGradientBoostingClassifier,
                              AdaBoostClassifier)

X, y = load_breast_cancer(return_X_y=True)
Xtr, Xte, ytr, yte = train_test_split(X, y, stratify=y, random_state=0)

rf = RandomForestClassifier(n_estimators=500, max_features="sqrt",
                            oob_score=True, n_jobs=-1, random_state=0).fit(Xtr, ytr)
print("RF  OOB acc:", round(rf.oob_score_, 3), " test acc:", round(rf.score(Xte, yte), 3))

hgb = HistGradientBoostingClassifier(learning_rate=0.05, max_iter=1000,
                                     early_stopping=True, validation_fraction=0.15,
                                     n_iter_no_change=30, random_state=0).fit(Xtr, ytr)
print("HGB trees used:", hgb.n_iter_, " test acc:", round(hgb.score(Xte, yte), 3))

ada = AdaBoostClassifier(n_estimators=300, learning_rate=0.5, random_state=0).fit(Xtr, ytr)
print("AdaBoost test acc:", round(ada.score(Xte, yte), 3))

# XGBoost / LightGBM have the same fit/predict API, e.g.
#   from xgboost import XGBClassifier
#   XGBClassifier(n_estimators=2000, learning_rate=0.05, max_depth=4, subsample=0.8,
#                 colsample_bytree=0.8, reg_lambda=1.0, early_stopping_rounds=50)
#   .fit(Xtr, ytr, eval_set=[(Xval, yval)])
Open in playground ↗
Check yourself

Quiz

1. Random forests mainly reduce…

2. In gradient boosting, each new tree is trained on…

3. Out-of-bag error is…

4. The fraction of rows left out of a bootstrap sample tends to…

5. For log-loss, gradient boosting's pseudo-residuals are…

6. In XGBoost the optimal leaf weight is…

Go deeper

📚 Further reading

Trusted, mostly free sources: official documentation, well-known textbooks and courses. When you want to confirm or go deeper on anything here, start with these.

Ready