Ensembles: Random Forests & Boosting
Many weak or noisy models combined into one strong model.
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.
Bagging starts by creating many slightly different versions of the training set using bootstrap sampling. A bootstrap sample is made by drawing examples from the original 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 of the 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.
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.
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.
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 ; 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.
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 forest | Boosting | |
|---|---|---|
| How trees are trained | in parallel, independently | sequentially, each fixing the last |
| Individual trees | deep (low bias, high variance) | shallow (high bias, low variance) |
| Mainly reduces | variance | bias |
| Overfits as more trees are added? | rarely | yes, without early stopping |
| Tuning effort | low | higher |
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: 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.
Why bootstrap leaves out 37%, and why averaging helps
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
| chance a given row is never drawn | |
| its limit | |
| features considered per split | |
| weighted error of learner t | |
| vote weight of learner t | |
| 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 times, with replacement, from examples. On any single draw, a particular example is not picked with probability . The draws are independent, so the probability that it is never picked in all draws is
The limit is a standard result from calculus, and the approximation is already very good for modest (for 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 trees that each have variance and pairwise correlation gives a variance of . Adding trees removes the second term, but the first term, , remains. Random forests attack this floor by making the trees less correlated: each split considers only randomly chosen features out of . The defaults are for classification and (or sometimes ) for regression. A smaller makes the trees more different, lowering , but it also makes each tree slightly weaker, so is a hyperparameter worth tuning.
AdaBoost. For a two-class problem with labels , AdaBoost runs as follows. Every example starts with the same weight. In round , a weak learner is trained on the weighted data, and its weighted error rate is computed. The learner then receives a voting weight
This is large when is small (an accurate learner gets a big say), zero when (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:
If example was classified correctly, and its weight is multiplied by , so it shrinks. If it was misclassified, and its weight is multiplied by , so it grows, and the next learner will pay more attention to it. After rounds, the final classifier is a weighted vote,
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 . That insight led directly to gradient boosting, which works with any loss.
Gradient boosting as gradient descent in function space, and XGBoost
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
| ensemble after m trees | |
| pseudo-residual: −∂L/∂F for example i | |
| learning rate (shrinkage) | |
| first and second derivatives of the loss | |
| sums of g and h in leaf j | |
| optimal leaf value | |
| penalty 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 that minimises the total loss . Think of the predictions on the training set, , 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:
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 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 :
The choice of loss determines what the trees chase. For squared-error loss , the pseudo-residual is , literally the residual, so each tree predicts the current errors. For log-loss in classification, with , the pseudo-residual is . For absolute-error loss, it is , 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 and the second derivative 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 to every example in leaf . Adding a penalty for each of the tree's leaves and an L2 penalty on the leaf values, the objective for one new tree becomes
where and are the sums of and over the examples in leaf . Each leaf's term is a simple quadratic in , and setting its derivative to zero gives the best leaf value:
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:
The bracket compares the quality of the left and right children with the quality of the unsplit parent, and is the price of the extra leaf. A split is made only if its gain is positive, so 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.
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.
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))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)])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…
📚 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.
- scikit-learn: Ensembles ↗ Official guide
- An Introduction to Statistical Learning (free book) ↗ James, Witten, Hastie, Tibshirani (Python edition available)