Trees: bagging, random forests and gradient boosting

A decision tree partitions the feature space into boxes and predicts a constant in each. Alone it is high variance and nearly useless; combined by bagging or boosting it becomes the strongest general-purpose method on tabular data, which is most of what quantitative research works with.

Proposition 2.1

How a tree is grown

At each node, search every feature and every threshold for the split that most reduces impurity — variance for regression, Gini or entropy for classification — then recurse. Grown without limit a tree fits the training data exactly, which is why depth, minimum leaf size or pruning is always applied.

Holds when

Splits are axis-aligned, so a diagonal boundary needs a staircase of them.
Trees are invariant to monotone transformations of a feature, so scaling and log transforms change nothing.
Interactions come free: a split below another split is a conditional effect.

Aspect	Bagging / random forest	Gradient boosting
Attacks	Variance	Bias
Base learners	Deep trees, fitted independently	Shallow trees, fitted sequentially
Each tree sees	A bootstrap sample and a feature subset	The residuals of everything so far
Parallelisable	Yes	No — inherently sequential
Overfits by	Barely, with more trees	Readily, with too many rounds
Main knobs	Number of trees, features per split	Learning rate, depth, number of rounds

Table 2.2 · Bagging against boosting. The overfitting row is the practical difference. Adding trees to a forest is safe; adding rounds to a boosted model is not, which is why early stopping on a validation set is mandatory there.

Figure 2.3 · Why a forest stops improving. Averaging

B

trees leaves

\rho\sigma^2 + (1-\rho)\sigma^2/B

. The second term vanishes and the first does not, so the floor is the correlation between the trees — which is exactly why a random forest samples features at each split, and why the hundredth tree buys almost nothing.

Why averaging decorrelated trees works. Averaging $n$ independent estimates cuts the variance by $n$ ; averaging $n$ perfectly correlated ones cuts it by nothing. Bagged trees fitted on bootstrap samples are already somewhat decorrelated, but they still tend to split on the same dominant feature first. Random forests add a second randomisation — considering only a subset of features at each split — precisely to force the trees apart. The entire innovation is decorrelation, and it is the same $\sqrt{n}$ diversification argument as a portfolio.

Trees: bagging, random forests and gradient boosting

After this lesson you should be able to

How a tree is grown

The rest of this lesson is in Premium