Simple Algorithm
Artificial Intelligence · Deep Layer · 28 min

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 ∏t2εt(1−εt)≤exp⁡(−2∑tγt2)\prod_t2\sqrt{\varepsilon_t(1-\varepsilon_t)}\le\exp(-2\sum_t\gamma_t^2), 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 II 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 Rα(T)=R(T)+α ∣leaves(T)∣R_\alpha(T)=R(T)+\alpha\,\abs{\mathrm{leaves}(T)} over the subtrees TT of the grown tree. For each α\alpha there is a unique smallest minimizer, and as α\alpha grows these subtrees are nested: they are found by repeatedly collapsing the "weakest link", the internal node whose removal increases RR least per leaf removed (Breiman et al., 1984). The value of α\alpha 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

DerivationThe variance of an average
  1. Var⁡(1B∑b=1Bfb)=1B2[Bσ2+B(B−1) ρ σ2]\Var\Big(\frac1B\sum_{b=1}^Bf_b\Big)=\frac1{B^2}\Big[B\sigma^2+B(B-1)\,\rho\,\sigma^2\Big]

    Let f1,…,fBf_1,\dots,f_B be identically distributed predictions at a point, each with variance σ2\sigma^2 and pairwise correlation ρ\rho. The variance of their average has BB diagonal and B(B−1)B(B-1) off-diagonal covariance terms:

  2. =ρ σ2+1−ρB σ2=\rho\,\sigma^2+\frac{1-\rho}{B}\,\sigma^2

    Simplify:

  3. lim⁡B→∞Var⁡(1B∑bfb)=ρ σ2\lim_{B\to\infty}\Var\Big(\frac1B\sum_bf_b\Big)=\rho\,\sigma^2

    As B→∞B\to\infty 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).

  4. (y−fˉ)2=1B∑b(y−fb)2−1B∑b(fb−fˉ)2\big(y-\bar f\big)^2=\frac1B\sum_b\big(y-f_b\big)^2-\frac1B\sum_b\big(f_b-\bar f\big)^2

    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 nn points drawn with replacement, then average or vote. A point is left out of a given bootstrap sample with probability (1−1/n)n→e−1≈0.368(1-1/n)^n\to e^{-1}\approx0.368, 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 kk.

Predict before you look

Ten trees each have prediction variance σ2\sigma^2 at a point, with pairwise correlation 0.3. What is the variance of their average, as a fraction of σ2\sigma^2?

Show the answer

0.37

ρ+(1−ρ)/B=0.3+0.7/10=0.37\rho+(1-\rho)/B=0.3+0.7/10=0.37. With 500 trees it would be 0.3014: beyond a few hundred trees the correlation term dominates, so lowering ρ\rho 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 mm of the pp features is eligible, typically m=⌊p⌋m=\lfloor\sqrt p\rfloor for classification and ⌊p/3⌋\lfloor p/3\rfloor for regression, and the trees are grown deep without pruning.

text
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 it

A smaller mm 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 (ss large) that disagree (ρˉ\bar\rho 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.

text
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 eαte^{\alpha_t}, correct ones by e−αte^{-\alpha_t}. After the update, hth_t has weighted error exactly 12\frac12 under Dt+1D_{t+1}, so the next learner must find something new.

DerivationProof
  1. DT+1(i)=exp⁡(−yif(xi))n∏tZtD_{T+1}(i)=\frac{\exp\big(-y_if(\mathbf x_i)\big)}{n\prod_tZ_t}

    Unroll the weight updates. With f(x)=∑tαtht(x)f(\mathbf x)=\sum_t\alpha_th_t(\mathbf x), the final weights are

  2. 1n∑i1{H(xi)≠yi}≤1n∑ie−yif(xi)=∏tZt\frac1n\sum_i\mathbf 1\{H(\mathbf x_i)\ne y_i\}\le\frac1n\sum_ie^{-y_if(\mathbf x_i)}=\prod_tZ_t

    A mistake means yif(xi)≤0y_if(\mathbf x_i)\le0, so 1{H(xi)≠yi}≤exp⁡(−yif(xi))\mathbf 1\{H(\mathbf x_i)\ne y_i\}\le\exp(-y_if(\mathbf x_i)). Average over ii and use ∑iDT+1(i)=1\sum_iD_{T+1}(i)=1:

  3. Zt=2εt(1−εt)=1−4γt2atαt=12ln⁡1−εtεtZ_t=2\sqrt{\varepsilon_t(1-\varepsilon_t)}=\sqrt{1-4\gamma_t^2}\quad\text{at}\quad\alpha_t=\tfrac12\ln\frac{1-\varepsilon_t}{\varepsilon_t}

    Each normalizer is Zt=(1−εt)e−αt+εteαtZ_t=(1-\varepsilon_t)e^{-\alpha_t}+\varepsilon_te^{\alpha_t}, and AdaBoost's αt\alpha_t is exactly its minimizer:

  4. ∏t1−4γt2≤∏te−2γt2=exp⁡(−2∑tγt2)\prod_t\sqrt{1-4\gamma_t^2}\le\prod_te^{-2\gamma_t^2}=\exp\Big(-2\sum_t\gamma_t^2\Big)

    Finally, 1+x≤ex1+x\le e^x with x=−4γt2x=-4\gamma_t^2 gives the exponential form:

Predict before you look

Every weak learner has weighted error 0.4, an edge of γ=0.1\gamma=0.1. How many rounds does the bound exp⁡(−2∑tγt2)\exp(-2\sum_t\gamma_t^2) need to guarantee a training error below 1%?

Show the answer

231

exp⁡(−2Tγ2)<0.01\exp(-2T\gamma^2)<0.01 requires T>ln⁡100/(2×0.01)≈230.3T>\ln100/(2\times0.01)\approx230.3, so 231 rounds. The product form (1−4γ2)T/2=0.96T/2(1-4\gamma^2)^{T/2}=0.96^{T/2} is slightly tighter: 226 rounds. With n=1,000n=1{,}000 training points, T>ln⁡1000/0.02≈346T>\ln1000/0.02\approx346 rounds push the bound below 1/n1/n, 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 e−yfe^{-yf}: minimizing ∑ie−yi(ft−1(xi)+αh(xi))\sum_ie^{-y_i(f_{t-1}(\mathbf x_i)+\alpha h(\mathbf x_i))} over hh and α\alpha gives exactly AdaBoost's hth_t and αt\alpha_t, and the population minimizer is half the log-odds, f∗=12log⁡η1−ηf^*=\frac12\log\frac\eta{1-\eta}. 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

DerivationGradient boosting as functional gradient descent (Friedman, 2001)
  1. rim=−∂ℓ(yi,F)∂F∣F=Fm−1(xi)r_{im}=-\frac{\partial\ell(y_i,F)}{\partial F}\Big|_{F=F_{m-1}(\mathbf x_i)}

    Minimize ∑iℓ(yi,F(xi))\sum_i\ell(y_i,F(\mathbf x_i)) over additive models F=∑mνhmF=\sum_m\nu h_m made of trees. At stage mm, compute the pseudo-residuals, the negative gradient of the loss with respect to the current predictions:

  2. γjm=arg min⁡γ∑xi∈Rjmℓ(yi,Fm−1(xi)+γ)\gamma_{jm}=\argmin_\gamma\sum_{\mathbf x_i\in R_{jm}}\ell\big(y_i,F_{m-1}(\mathbf x_i)+\gamma\big)

    Fit a regression tree with leaves RjmR_{jm} to the pairs (xi,rim)(\mathbf x_i,r_{im}) by least squares, the tree closest to a gradient step, then set each leaf's value by a line search on the true loss:

  3. Fm(x)=Fm−1(x)+ν∑jγjm 1{x∈Rjm}F_m(\mathbf x)=F_{m-1}(\mathbf x)+\nu\sum_j\gamma_{jm}\,\mathbf 1\{\mathbf x\in R_{jm}\}

    Take a shrunken step. Shrinkage ν∈(0,1]\nu\in(0,1], 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):

  4. ri=yi−F(xi),ri=sign⁡(yi−F(xi)),ri=yi−σ(F(xi))r_i=y_i-F(\mathbf x_i),\qquad r_i=\sign\big(y_i-F(\mathbf x_i)\big),\qquad r_i=y_i-\sigma\big(F(\mathbf x_i)\big)

    Each loss gives its own residuals: squared loss 12(y−F)2\frac12(y-F)^2 gives ordinary residuals, absolute loss their signs, and log loss with p=σ(F)p=\sigma(F) gives y−py-p. The exponential loss essentially recovers AdaBoost.

DerivationXGBoost’s second-order trees (Chen & Guestrin, 2016)
  1. L(t)≈∑i[gift(xi)+12hift(xi)2]+γT+12λ∑jwj2\mathcal L^{(t)}\approx\sum_i\Big[g_if_t(\mathbf x_i)+\tfrac12h_if_t(\mathbf x_i)^2\Big]+\gamma T+\tfrac12\lambda\sum_jw_j^2

    At round tt, add a tree ftf_t with TT leaves and leaf weights w\mathbf w, penalized by Ω(ft)=γT+12λ∥w∥2\Omega(f_t)=\gamma T+\frac12\lambda\norm{\mathbf w}^2. Expand the loss to second order around the current predictions, with gig_i and hih_i its first and second derivatives:

  2. L(t)≈∑j=1T[Gjwj+12(Hj+λ) wj2]+γT\mathcal L^{(t)}\approx\sum_{j=1}^T\Big[G_jw_j+\tfrac12(H_j+\lambda)\,w_j^2\Big]+\gamma T

    Group the examples by leaf, with Gj=∑i∈IjgiG_j=\sum_{i\in I_j}g_i and Hj=∑i∈IjhiH_j=\sum_{i\in I_j}h_i. Each leaf contributes a one-dimensional quadratic:

  3. wj∗=−GjHj+λ,L(t)∗=−12∑j=1TGj2Hj+λ+γTw_j^*=-\frac{G_j}{H_j+\lambda},\qquad\mathcal L^{(t)*}=-\frac12\sum_{j=1}^T\frac{G_j^2}{H_j+\lambda}+\gamma T

    Minimize each quadratic. The optimal weights are Newton steps damped by λ\lambda, and the optimal value scores the tree's structure:

  4. Gain=12[GL2HL+λ+GR2HR+λ−(GL+GR)2HL+HR+λ]−γ\mathrm{Gain}=\frac12\Big[\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}\Big]-\gamma

    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 BB predictors with variance σ2\sigma^2 and correlation ρ\rho has variance ρσ2+(1−ρ)σ2/B\rho\sigma^2+(1-\rho)\sigma^2/B: bagging averages bootstrap trees, and random forests lower ρ\rho with random feature subsets.
  • AdaBoost's training error is at most ∏t2εt(1−εt)≤exp⁡(−2∑tγt2)\prod_t2\sqrt{\varepsilon_t(1-\varepsilon_t)}\le\exp(-2\sum_t\gamma_t^2); 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 −Gj/(Hj+λ)-G_j/(H_j+\lambda) 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.

Question 1

A forest averages infinitely many trees, each with prediction variance σ2\sigma^2 and pairwise correlation ρ=0.4\rho=0.4. What is the variance of the average?

  1. 0
  2. 0.4σ20.4\sigma^2
  3. σ2/0.4\sigma^2/0.4
  4. 0.6σ20.6\sigma^2
Show the answer

B. 0.4σ20.4\sigma^2

ρσ2+(1−ρ)σ2/B→ρσ2=0.4σ2\rho\sigma^2+(1-\rho)\sigma^2/B\to\rho\sigma^2=0.4\sigma^2. Only the uncorrelated part averages away, which is why random forests decorrelate their trees instead of merely adding more of them.

Question 2

A weak learner has weighted error exactly εt=0.5\varepsilon_t=0.5. What weight does AdaBoost give it, and what happens if εt=0.7\varepsilon_t=0.7?

  1. αt=0\alpha_t=0; with error 0.7 the weight is negative, which turns the learner into one with error 0.3
  2. αt=0.5\alpha_t=0.5; a learner with error 0.7 is rejected
  3. αt=1\alpha_t=1; a learner with error 0.7 gets weight 1.4
  4. αt=∞\alpha_t=\infty: it is the most informative learner
Show the answer

A. αt=0\alpha_t=0; with error 0.7 the weight is negative, which turns the learner into one with error 0.3

αt=12ln⁡1−εtεt\alpha_t=\frac12\ln\frac{1-\varepsilon_t}{\varepsilon_t} is 0 at εt=12\varepsilon_t=\frac12: a coin flip carries no information. At 0.7 it is 12ln⁡0.30.7<0\frac12\ln\frac{0.3}{0.7}<0, and −ht-h_t has error 0.3, so the learner is used in reverse. What matters is the edge ∣γt∣\abs{\gamma_t}, which enters the bound squared.

Question 3

Why does a random forest restrict each split to a random subset of the features?

  1. To speed up training, at a small cost in accuracy
  2. To make each individual tree more accurate
  3. To decorrelate the trees, which lowers the variance floor ρσ2\rho\sigma^2 of their average
  4. To keep the trees shallow
Show the answer

C. To decorrelate the trees, which lowers the variance floor ρσ2\rho\sigma^2 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 ρ\rho by more than it weakens each tree: the trade-off in Breiman's bound ρˉ(1−s2)/s2\bar\rho(1-s^2)/s^2.

Question 4

In XGBoost, a leaf has gradient sum G=−6G=-6 and Hessian sum H=4H=4, with λ=2\lambda=2. What is its optimal weight?

  1. 1.5
  2. −1
  3. 3
  4. 1
Show the answer

D. 1

w∗=−G/(H+λ)=6/6=1w^*=-G/(H+\lambda)=6/6=1: the Newton step −G/H=1.5-G/H=1.5, damped by the ℓ2\ell_2 penalty. The leaf then lowers the objective by 12G2/(H+λ)=3\frac12G^2/(H+\lambda)=3, before the leaf cost γ\gamma 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.