Decision Trees & Ensembles
Splits, bagging, random forests and boosting.
A single deep decision tree is a nearly unbiased but high-variance estimator. Hundreds of them, averaged or added up cleverly, are among the most accurate predictors known for tabular data. Averaging removes variance as long as the trees disagree; boosting removes bias as long as each weak learner beats chance. This lesson makes both statements precise, from the variance of an average to AdaBoost's exponential bound and the second-order trees of XGBoost.
What you’ll learn
- Explain CART's impurity criteria and cost-complexity pruning, and why optimal trees are intractable and greedy trees myopic.
- Derive the variance of an average of correlated predictors, and use it to explain bagging and random forests, including Breiman's strength–correlation bound.
- Prove AdaBoost's training-error bound , and interpret AdaBoost as stagewise minimization of the exponential loss.
- Derive gradient boosting as functional gradient descent, and XGBoost's second-order leaf weights and split gain.
Trees: impurity, pruning and greedy myopia
CART (Breiman, Friedman, Olshen & Stone, 1984) grows a binary tree of axis-aligned splits, each chosen to maximize the decrease of an impurity of the class proportions (Gini for CART, entropy for ID3 and C4.5; see Supervised Learning), and predicts with each leaf's majority class or mean. Why impurities, rather than the error rate itself?
Trees are grown deep and then pruned. Cost-complexity pruning minimizes over the subtrees of the grown tree. For each there is a unique smallest minimizer, and as grows these subtrees are nested: they are found by repeatedly collapsing the "weakest link", the internal node whose removal increases least per leaf removed (Breiman et al., 1984). The value of is chosen by cross-validation. Optimal trees are NP-hard to find (Hyafil & Rivest, 1976), although mixed-integer and dynamic-programming methods now solve small depths exactly (for example Bertsimas & Dunn, 2017).
Bagging: the variance of an average
Let be identically distributed predictions at a point, each with variance and pairwise correlation . The variance of their average has diagonal and off-diagonal covariance terms:
Simplify:
As the second term vanishes but the first does not: averaging removes only the uncorrelated part of the variance, and leaves the bias untouched, because the average has the same mean as each member. To gain, make the members as uncorrelated as possible without making them much worse (the bias–variance trade-off again).
For squared loss, the average is never worse than a typical member. The ambiguity decomposition (Krogh & Vedelsby, 1995) shows the ensemble's error is the members' average error minus their spread:
Bagging (bootstrap aggregation; Breiman, 1996) manufactures diverse members from a single dataset: train each tree on a bootstrap sample of points drawn with replacement, then average or vote. A point is left out of a given bootstrap sample with probability , so each tree sees about 63.2% of the distinct points, and each point is out of bag for about a third of the trees. Predicting each point with only those trees gives the out-of-bag error, an almost free substitute for cross-validation. Bagging helps unstable, low-bias learners such as deep trees; it does little for stable ones such as linear models or k-NN with a large .
Ten trees each have prediction variance at a point, with pairwise correlation 0.3. What is the variance of their average, as a fraction of ?
Show the answer
0.37
. With 500 trees it would be 0.3014: beyond a few hundred trees the correlation term dominates, so lowering is worth more than adding trees. That is exactly what random forests do.
Random forests
Bagged trees are correlated because the same strong features win the top splits in almost every bootstrap sample. Random forests (Breiman, 2001) decorrelate them: at each split only a random subset of of the features is eligible, typically for classification and for regression, and the trees are grown deep without pruning.
function RANDOM-FOREST(D with n examples and p features, B trees, m features per split):
for b = 1 to B:
D_b ← n examples drawn from D with replacement # bootstrap sample
T_b ← GROW-TREE(D_b), each split searching only m randomly chosen features,
growing until the leaves are (nearly) pure
return x ↦ majority vote (or average) of T_1(x), …, T_B(x)
# out-of-bag error: predict each example with the trees whose D_b missed itA smaller lowers the correlation between trees but raises each tree's bias and variance. It is the forest's main tuning knob; forests are notably robust to their other settings.
The bound is loose, but it names the trade-off: strong individual trees ( large) that disagree ( small). Theory caught up slowly. Simplified "purely random" forests are consistent (Biau, Devroye & Lugosi, 2008), and Breiman's original algorithm was proved consistent for additive regression models (Scornet, Biau & Vert, 2015). Forests also yield feature importances, though impurity-based importances favor features with many possible split points (Strobl, Boulesteix, Zeileis & Hothorn, 2007) and permutation importances can mislead when features are correlated, and honest forests estimate heterogeneous causal effects with valid confidence intervals (Wager & Athey, 2018).
AdaBoost and the exponential bound
Boosting answers a question of Kearns and Valiant: can learners that are only slightly better than chance be combined into an arbitrarily accurate one? Schapire (1990) proved that they can, and AdaBoost (Freund & Schapire, 1997) made it practical. It reweights the training points so that each new weak learner concentrates on the examples its predecessors got wrong, then combines them in a weighted vote, an ensemble built sequentially.
function ADABOOST((x_1, y_1), …, (x_n, y_n) with y_i ∈ {−1, +1}, rounds T):
D_1(i) ← 1/n for every i
for t = 1 to T:
h_t ← weak learner trained with weights D_t # e.g. a decision stump
ε_t ← Σ_i D_t(i) · 1{h_t(x_i) ≠ y_i} # weighted error, < 1/2
α_t ← ½ · ln((1 − ε_t) / ε_t)
D_{t+1}(i) ← D_t(i) · exp(−α_t · y_i · h_t(x_i)) / Z_t # Z_t normalizes
return H(x) = sign(Σ_t α_t · h_t(x))Misclassified points have their weight multiplied by , correct ones by . After the update, has weighted error exactly under , so the next learner must find something new.
Unroll the weight updates. With , the final weights are
A mistake means , so . Average over and use :
Each normalizer is , and AdaBoost's is exactly its minimizer:
Finally, with gives the exponential form:
Every weak learner has weighted error 0.4, an edge of . How many rounds does the bound need to guarantee a training error below 1%?
Show the answer
231
requires , so 231 rounds. The product form is slightly tighter: 226 rounds. With training points, rounds push the bound below , so the training error is then exactly zero.
Why does it work so well? Friedman, Hastie and Tibshirani (2000) showed that AdaBoost is forward stagewise additive modeling with the exponential loss : minimizing over and gives exactly AdaBoost's and , and the population minimizer is half the log-odds, . Test error often keeps falling after the training error reaches zero, which margin theory explains through the growing margins of the training points (Schapire, Freund, Bartlett & Lee, 1998). The exponential loss is also AdaBoost's weakness: it puts enormous weight on mislabeled points, and random label noise defeats every convex potential booster (Long & Servedio, 2010).
Gradient boosting and XGBoost
Minimize over additive models made of trees. At stage , compute the pseudo-residuals, the negative gradient of the loss with respect to the current predictions:
Fit a regression tree with leaves to the pairs by least squares, the tree closest to a gradient step, then set each leaf's value by a line search on the true loss:
Take a shrunken step. Shrinkage , typically 0.01 to 0.1 with correspondingly more trees, generalizes better, and fitting each stage on a random subsample adds variance reduction (stochastic gradient boosting; Friedman, 2002):
Each loss gives its own residuals: squared loss gives ordinary residuals, absolute loss their signs, and log loss with gives . The exponential loss essentially recovers AdaBoost.
At round , add a tree with leaves and leaf weights , penalized by . Expand the loss to second order around the current predictions, with and its first and second derivatives:
Group the examples by leaf, with and . Each leaf contributes a one-dimensional quadratic:
Minimize each quadratic. The optimal weights are Newton steps damped by , and the optimal value scores the tree's structure:
So splitting a leaf into a left and a right part is worth the following, and the tree is grown greedily by this gain:
The systems contributions mattered as much: approximate split finding with a weighted quantile sketch, sparsity-aware splits that learn a default direction for missing values, cache-aware column blocks and out-of-core computation. LightGBM (Ke et al., 2017) added histogram-based splits and gradient-based subsampling, and CatBoost (Prokhorenkova et al., 2018) introduced ordered boosting to avoid target leakage from categorical features.
Key takeaways
- Strictly concave impurities (entropy, Gini) make every split's gain non-negative and reward purer children; trees are grown greedily and pruned by cost-complexity, and they are myopic and unstable.
- An average of predictors with variance and correlation has variance : bagging averages bootstrap trees, and random forests lower with random feature subsets.
- AdaBoost's training error is at most ; it is stagewise minimization of the exponential loss, powerful but sensitive to label noise.
- Gradient boosting fits each tree to the negative functional gradient; XGBoost's second-order expansion gives leaf weights and an exact split gain.
- As of the mid-2020s, boosted trees remain the default for tabular data, while why interpolating ensembles generalize is still only partly understood.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
A forest averages infinitely many trees, each with prediction variance and pairwise correlation . What is the variance of the average?
- 0
Show the answer
B.
. Only the uncorrelated part averages away, which is why random forests decorrelate their trees instead of merely adding more of them.
A weak learner has weighted error exactly . What weight does AdaBoost give it, and what happens if ?
- ; with error 0.7 the weight is negative, which turns the learner into one with error 0.3
- ; a learner with error 0.7 is rejected
- ; a learner with error 0.7 gets weight 1.4
- : it is the most informative learner
Show the answer
A. ; with error 0.7 the weight is negative, which turns the learner into one with error 0.3
is 0 at : a coin flip carries no information. At 0.7 it is , and has error 0.3, so the learner is used in reverse. What matters is the edge , which enters the bound squared.
Why does a random forest restrict each split to a random subset of the features?
- To speed up training, at a small cost in accuracy
- To make each individual tree more accurate
- To decorrelate the trees, which lowers the variance floor of their average
- To keep the trees shallow
Show the answer
C. To decorrelate the trees, which lowers the variance floor of their average
In plain bagging, the same strong features win the top splits of almost every tree, so the trees and their errors are highly correlated. Restricting the candidates forces different trees to use different features, which lowers by more than it weakens each tree: the trade-off in Breiman's bound .
In XGBoost, a leaf has gradient sum and Hessian sum , with . What is its optimal weight?
- 1.5
- −1
- 3
- 1
Show the answer
D. 1
: the Newton step , damped by the penalty. The leaf then lowers the objective by , before the leaf cost is subtracted.
Further reading
- L. Breiman, "Random forests," Machine Learning 45, 5–32 (2001).
- Y. Freund & R. E. Schapire, "A decision-theoretic generalization of on-line learning and an application to boosting," Journal of Computer and System Sciences 55(1), 119–139 (1997).
- J. H. Friedman, "Greedy function approximation: a gradient boosting machine," Annals of Statistics 29(5), 1189–1232 (2001).
- T. Chen & C. Guestrin, "XGBoost: a scalable tree boosting system," Proceedings of KDD (2016).
- T. Hastie, R. Tibshirani & J. Friedman, The Elements of Statistical Learning, 2nd ed. (Springer, 2009), chapters 9, 10, 15 and 16.