Decision Trees and Their Ensembles: Bagging, Random Forests and Boosting

The models so far in this series were formulas: a line, a sigmoid, a Gaussian density. A decision tree is a set of questions instead: is the player’s experience below 4.5 years? If not, did he get more than 117 hits last year? Each answer leads to the next question, and the last one gives a prediction. Trees are easy to explain to anyone, they handle categorical inputs and interactions without extra work, and on their own they predict rather poorly. Grown by the hundreds and combined, they become some of the most accurate methods there are.

This post builds trees from scratch (the CART algorithm of Breiman et al., 1984), prunes them by cross-validation, measures how unstable they are, and then compares bagging, random forests and boosting on a standard benchmark. Every number comes from code written for this post, and the lab runs the same algorithm in the browser.

1. A Tree Is a Partition

A regression tree divides the space of the predictors into non-overlapping regions $R_{1}, \dots, R_{J}$ , and predicts, for every observation in region $R_{j}$ , the mean of the training responses that fall there. On simulated data modelled on a classic example (log salary of 260 baseball players by years in the league and hits last year, where experience matters first and hits only for experienced players):

The tree is drawn upside down: the root at the top, internal nodes where the space is split, leaves (terminal nodes) at the bottom. The three regions are

R_{1} = {years < 4.5}, R_{2} = {years \geq 4.5, hits < 117.5}, R_{3} = {years \geq 4.5, hits \geq 117.5} .

The interpretation reads off the tree: experience is the most important factor; for inexperienced players, hits play little role; for experienced ones, more hits mean a higher salary. A linear regression could not say “hits matter only after 4.5 years” without an explicit interaction term; the tree finds it on its own.

Two properties of the regions are fixed by how they are built:

They are rectangles, aligned with the axes. Each split asks about one predictor and one threshold, so every boundary is parallel to an axis. A boundary along a diagonal can only be approximated by a staircase of many splits (§5). Trees with oblique splits on combinations of predictors exist (Breiman et al., 1984, ch. 5; Murthy et al., 1994), but standard CART does not grow them.
Every observation in a region gets the same prediction. A tree is a step function: it over-simplifies smooth relationships, which is one reason single trees predict poorly.

2. Growing a Tree: Recursive Binary Splitting

The goal is the partition with the smallest residual sum of squares,

RSS = j = 1 \sum J i \in R_{j} \sum (y_{i} - \overset{y}{^}_{R_{j}})^{2},

where $\overset{y}{^}_{R_{j}}$ is the mean response in region $R_{j}$ . Searching all partitions is impossible, so CART builds the tree top-down and greedily:

For every predictor $X_{j}$ and every cut point $s$ , consider splitting the data into ${X_{j} < s}$ and ${X_{j} \geq s}$ , and pick the pair $(j, s)$ that reduces the RSS most. (Only cut points between neighbouring observed values need to be checked; CART uses the midpoints.)
Repeat within each of the two new regions, and so on.
Stop when a node would have fewer than a minimum number of observations (often 5), or when no split reduces the RSS.

“Greedy” means each split is the best one at that moment, with no look-ahead: a split that is useless now but would enable an excellent split later is never chosen for that reason.

On the salary-like data, a tree of depth 2 found the true splits, years at 4.5 and, among experienced players, hits at 117.5. It also split the inexperienced players at 87.5 hits (means 5.23 and 4.98), a split that the generating function does not have: it fits noise. Deeper trees find more of those.

Categorical predictors need no dummy variables: a split sends some categories left and the rest right. With $q$ categories there are $2^{q - 1} - 1$ such splits, but for regression and two-class problems, sorting the categories by their mean response reduces the search to $q - 1$ (Breiman et al., 1984).

3. Pruning: Grow Large, Then Cut Back

A tree grown until every leaf holds one observation fits its training data perfectly and has high variance. Stopping early, whenever the next split gains little, is short-sighted, for the greedy reason above. The standard approach grows a large tree first and then prunes it.

Cost-complexity (weakest-link) pruning (Breiman et al., 1984) considers, for a tuning parameter $α \geq 0$ , the subtree $T$ of the large tree that minimises

m = 1 \sum ∣ T ∣ i : x_{i} \in R_{m} \sum (y_{i} - \overset{y}{^}_{R_{m}})^{2} + α ∣ T ∣,

where $∣ T ∣$ is the number of leaves. $α = 0$ keeps the full tree; as $α$ grows, the split that buys the least RSS reduction per extra leaf is removed first, giving a nested sequence of subtrees. $α$ is chosen by cross-validation: repeat the growing and pruning on each set of training folds, compute the validation error along the sequence, and pick the $α$ with the smallest average.

On 200 points of a smooth two-dimensional function (noise variance 0.16), the full tree had 200 leaves and the pruning path 177 subtrees:

Leaves	Training · 10-fold CV MSE	Test MSE
1	2.019 · 2.096	1.700
8	0.523 · 0.832	0.689
32	0.122 · 0.489	0.414
36 (chosen by CV)	– · 0.463	0.416
200 (full tree)	0.000 · –	0.415

Here pruning did not lower the test error: the function is smooth and needs many leaves, and the subtree chosen by CV is as accurate as the full tree, with a sixth of the leaves. That is a real gain in interpretability and size, and a reminder that pruning is a tool against variance, whose benefit depends on how much of it there is.

4. Classification Trees and Impurity

For a categorical outcome, a leaf predicts its most common class, and the RSS is replaced by a measure of how mixed a node is. With $\overset{p}{^}_{mk}$ the share of class $k$ in node $m$ :

Measure	Formula	Notes
Misclassification error	$1 - max_{k} \overset{p}{^}_{mk}$	what the tree is finally judged by
Gini index	$\sum_{k} \overset{p}{^}_{mk} (1 - \overset{p}{^}_{mk})$	small when one class dominates
Entropy (cross-entropy)	$- \sum_{k} \overset{p}{^}_{mk} lo g_{2} \overset{p}{^}_{mk}$	behaves much like the Gini index

Why not grow the tree with the misclassification error itself? Because it is not sensitive enough. A classic example (Hastie et al., 2009, §9.2.3): a node with 400 observations of each class, and two candidate splits.

Split of 400 / 400	Misclassification · Gini	Entropy (bits)
A: (300, 100) and (100, 300)	0.250 · 0.375	0.811
B: (200, 400) and (200, 0)	0.250 · 0.333	0.689

The misclassification error cannot tell them apart; the Gini index and entropy prefer B, which creates a pure node that needs no further splitting. Because they are strictly concave, they reward purity, and they are the usual choice for growing, while the misclassification error is often used for pruning when prediction accuracy is the goal.

5. Trees versus Linear Models, and Their Weaknesses

Which is better depends on the shape of the truth. 50 training sets of 200 points each, a pruned tree against linear regression:

True relationship	Pruned tree, test MSE	Linear regression, test MSE
Linear: $1 + 2 x_{1} - 1.5 x_{2}$	0.420	0.162 (noise 0.160)
An axis-aligned box: 2.5 if $x_{1} > 0.3$ and $x_{2} < - 0.2$	0.209	0.682

A linear relationship is a diagonal surface, which the tree can only approximate with a staircase; an axis-aligned box is exactly what a tree builds. Beyond accuracy, two weaknesses matter:

Trees are unstable. Small changes in the data can change the whole tree. Refitting a single split (a “stump”) to 200 bootstrap resamples of the same 200 points: the root split used $x_{2}$ in 88% of them and $x_{1}$ in 12%, with thresholds ranging over almost the whole range of each variable ( $x_{2}$ from −1.41 to 1.28). The lab’s “bootstrap resample” button shows the same on the salary data. A model whose structure changes with every resample cannot be read too literally, however readable it looks.

Single trees predict poorly. On the benchmark of §6, a pruned tree had a test MSE of 10.2, worse than a plain linear regression (7.4), although the true function is far from linear.

Both weaknesses are variance, and averaging is the classic cure for variance.

6. Ensembles: Many Trees

Bagging

Bagging (bootstrap aggregation; Breiman, 1996) grows a deep, unpruned tree on each of $B$ bootstrap resamples of the training data and averages their predictions (or takes a majority vote for classes):

\hat{f}_{bag} (x) = \frac{1}{B} b = 1 \sum B \hat{f}^{* b} (x) .

Each deep tree has low bias and high variance; averaging $B$ of them keeps the bias and reduces the variance, the way averaging $B$ noisy measurements reduces their noise. Adding trees cannot make a bagged model overfit; it only converges.

A free error estimate comes with it. Each resample leaves out about 37% of the observations (Cross-Validation and the Bootstrap); predicting each observation only with the trees that did not see it gives the out-of-bag (OOB) error, a cross-validation-like estimate without any extra fitting.

Random forests

The bagged trees are correlated: if one predictor is strong, nearly every tree splits on it first, and averaging correlated trees removes less variance. A random forest (Breiman, 2001) lets each split consider only a random subset of $m$ of the $p$ predictors (typically $m \approx p$ for classification, $p /3$ for regression), which decorrelates the trees. With $m = p$ it is bagging.

Boosting

Boosting works the other way round. Instead of averaging independent deep trees, it grows small trees one after another, each fitted to what the current model still gets wrong, and adds a shrunken version of each. For regression with squared error (Friedman, 2001):

Start with $\hat{f} (x) = \overset{y}{ˉ}$ and residuals $r_{i} = y_{i} - \overset{y}{ˉ}$ .
For $b = 1, \dots, B$ : fit a tree with $d$ splits to the residuals; update $\hat{f} (x) \leftarrow \hat{f} (x) + λ \hat{f}^{b} (x)$ and $r_{i} \leftarrow r_{i} - λ \hat{f}^{b} (x_{i})$ .

The learning rate $λ$ (e.g. 0.01–0.1) makes boosting learn slowly on purpose: each tree only nudges the fit, and many small corrections in different directions give a better model than a few large ones. Boosting mainly reduces bias, and unlike bagging it can overfit as trees are added, so $B$ is tuned (by cross-validation), together with $λ$ and the tree depth $d$ .

On a benchmark

Friedman’s first benchmark function (Friedman, 1991) has 10 inputs, uniform on [0, 1], of which only 5 matter:

y = 10 sin (π x_{1} x_{2}) + 20 (x_{3} - 0.5)^{2} + 10 x_{4} + 5 x_{5} + ε, ε \sim N (0, 1) .

300 training points, test MSE on 5,000 new ones (the noise variance, 1, is the floor):

Method	Test MSE	Notes
Linear regression	7.42
One tree, pruned by 5-fold CV (20 leaves)	10.24	worse than linear
Bagging, 300 trees	5.15	out-of-bag estimate 5.21
Random forest, $m = 3$ , 300 trees	5.19	no gain over bagging here
Boosting, depth 2, $λ = 0.1$ , 1,000 trees	3.07	best
Boosting, depth 2, $λ = 1$	7.28	too fast: overfits after ~10 trees
Boosting, depth 2, $λ = 0.01$ , 2,000 trees	3.18	slower, nearly as good
Boosting, stumps, $λ = 0.1$	3.55 at 200 trees, 3.91 at 2,000	overfits with more trees

Three observations:

Averaging works. Bagging halved the single tree’s error, and the out-of-bag error tracked the test error closely without a test set.
Random forests are not always better than bagging. Their advantage comes from decorrelating trees dominated by a few strong, correlated predictors; with 10 independent inputs, the trees were not correlated enough for it to matter.
Slow learning wins. Boosting with small trees and a small learning rate was best by a wide margin. With $λ = 1$ it overfitted almost at once; with stumps, which cannot represent the $x_{1} x_{2}$ interaction, it overfitted slowly after 200 trees.

The price of ensembles is interpretability: a forest of 300 trees has no picture to draw. Variable importance measures (the total RSS or Gini reduction from splits on each predictor, or the loss in accuracy when a predictor’s values are permuted; Breiman, 2001) recover part of it, with known biases toward predictors with many possible split points (Strobl et al., 2007).

7. Common Claims, Checked

Claim	Verdict
”R₂ = {years < 4.5, hits < 117.5}.”	R₂ is the experienced players with few hits: years ≥ 4.5 and hits < 117.5. The tree first separates years < 4.5 (R₁).
”RSS = Σⱼ Σᵢ (yᵢ − ŷ_Rⱼ).”	The deviations are squared: Σⱼ Σᵢ∈Rⱼ (yᵢ − ŷ_Rⱼ)². Without the square they sum to zero in every region.
”The regions can have any shape; rectangles are chosen for simplicity.”	Recursive binary splitting on one predictor at a time can only produce axis-aligned rectangles. A linear relationship needed a staircase and lost to linear regression (0.420 vs. 0.162).
”The classification error rate is a good splitting criterion.”	It is too insensitive: two splits with error 0.25 each got Gini 0.375 and 0.333; only Gini and entropy reward the pure node.
”Pruning always improves the test error.”	It reduces variance; here the CV-pruned tree (36 leaves) matched the full tree (0.416 vs. 0.415) with a sixth of the leaves. The gain depends on how much variance there is.
”A tree shows which variables matter.”	For one sample. Over 200 bootstrap resamples, the root split moved between x₂ (88%) and x₁ (12%) and across almost the whole range.
”Trees capture non-linearity, so they beat linear models.”	A pruned tree (10.2) lost to linear regression (7.4) on a non-linear benchmark; single trees have high variance.
”Boosting achieves faster learning.”	Boosting learns slowly on purpose: λ = 0.1 reached 3.07, while λ = 1 overfitted at 7.28. It fits trees in sequence to residuals and mainly reduces bias.
”More trees never hurt.”	True for bagging and random forests, which only converge. Boosting can overfit: stumps went from 3.55 at 200 trees to 3.91 at 2,000.
”Random forests always beat bagging.”	Only when the trees are correlated; with 10 independent inputs, 5.19 vs. 5.15.
”Bagging needs a separate validation set.”	The out-of-bag error (5.21) estimated the test error (5.15) from the unused 37% of each resample.

Summary

Idea	In one line
Tree	Axis-aligned rectangles, each predicting its training mean (or majority class)
Growing	Greedy, top-down recursive binary splitting by RSS, Gini or entropy
Pruning	Cost-complexity α chosen by CV; shrinks the tree, error gain depends on the variance
Strengths	Readable, interactions and categories for free
Weaknesses	Unstable, staircase boundaries, mediocre accuracy alone
Bagging	Average deep trees on bootstrap resamples; OOB error for free
Random forest	Bagging with m of p predictors per split, to decorrelate
Boosting	Small trees in sequence on residuals, shrunk by λ; tune B, λ, depth

Next: Unsupervised Learning: Principal Components and k-Means Clustering: structure without labels, on the crime rates of 50 states and on simulations where k-means succeeds and fails.

The experiments: trees.py (numpy 2.1, seeded), which implements CART, cost-complexity pruning, bagging, random forests and gradient boosting. The lab grows and prunes trees in the browser with the same rules; on the post’s data its trees are identical to the numpy version (same splits, thresholds and leaf means at depth 2; the same full tree of 200 leaves and the same pruning sequence of 177 subtrees). The ensemble curves are the numpy results.

References

Trees

Breiman, L., Friedman, J. H., Olshen, R. A., & Stone, C. J. (1984). Classification and Regression Trees. Wadsworth.
Quinlan, J. R. (1986). Induction of decision trees. Machine Learning, 1(1).
Murthy, S. K., Kasif, S., & Salzberg, S. (1994). A system for induction of oblique decision trees. Journal of Artificial Intelligence Research, 2.

Ensembles

Breiman, L. (1996). Bagging predictors. Machine Learning, 24(2).
Breiman, L. (2001). Random forests. Machine Learning, 45(1).
Freund, Y., & Schapire, R. E. (1997). A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1).
Friedman, J. H. (2001). Greedy function approximation: A gradient boosting machine. Annals of Statistics, 29(5).
Friedman, J. H. (1991). Multivariate adaptive regression splines. Annals of Statistics, 19(1).
Strobl, C., Boulesteix, A.-L., Zeileis, A., & Hothorn, T. (2007). Bias in random forest variable importance measures. BMC Bioinformatics, 8.

Textbooks

James, G., Witten, D., Hastie, T., & Tibshirani, R. (2021). An Introduction to Statistical Learning (2nd ed.). Springer.
Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning (2nd ed.). Springer.

Notes

Explorer