Skip to content
LearnMLByDoing
Free

2.4 Decision trees, random forests and gradient boosting

36 minProintermediateISLRHOMLESL

A decision tree carves the feature plane into rectangles one greedy cut at a time; averaging many decorrelated trees cancels their variance, and adding small trees fitted to residuals is gradient descent in function space.

01Greedy splits and impurity

A classification tree cuts the feature plane into axis-aligned rectangles and predicts the majority class inside each one. The floor holds 160 points from two interleaved moons, class 0 in cyan and class 1 in emerald. CART grows the tree greedily: at a node it tries every feature jj and every threshold tt, keeps the pair that makes the children purest, and repeats inside each child.

What does purest mean in numbers? Take a node of 8 points, 4 cyan and 4 emerald. Its Gini impurity is 1−(0.52+0.52)=0.51-(0.5^2+0.5^2)=0.5, the worst a two-class node can score. A cut that sends 3 cyan and 1 emerald left and 1 cyan and 3 emerald right gives each child 1−(0.752+0.252)=0.3751-(0.75^2+0.25^2)=0.375. Each child holds half the points, so the weighted impurity after the cut is 12(0.375)+12(0.375)=0.375\tfrac12(0.375)+\tfrac12(0.375)=0.375, and the cut buys an impurity decrease of 0.5−0.375=0.1250.5-0.375=0.125. A perfect cut (4 cyan left, 4 emerald right) would buy the full 0.5. CART scores every candidate cut this way and keeps the best.

X (training points)[,]320 values

A split is one feature index j and one threshold t. Candidate thresholds are the midpoints between consecutive sorted values, so the root has at most d(N − 1) = 318 candidates.

G(p)=1−∑kpk2,H(p)=−∑kpklog⁡2pk\tok{impurity}{G}(p)=1-\sum_{k}p_k^{2},\qquad H(p)=-\sum_k p_k\log_2 p_k
Gini impurity and entropy of a node whose class proportions are p. Both are 0 for a pure node and largest at an even mix.
The impurity decrease of a split, and why it is never negative1/4
  1. 1
    ΔG=G(p)−nLn G(pL)−nRn G(pR)\tok{gain}{\Delta G}=G(p)-\frac{n_L}{n}\,G(p_L)-\frac{n_R}{n}\,G(p_R)

    Each child counts in proportion to the samples it receives. Averaging the two child impurities without weights rewards splits that peel off one pure point.

Loading figure
The search the viewport only mimes, on the same 160 points. The best cut over both features is x2≤−0.257x_2\le-0.257 with ΔG=0.282\tok{gain}{\Delta G}=0.282; on x1x_1 the best is only 0.120. Switching the impurity here also switches the viewport's tree.

Before each wall rises, an amber outline sweeps across the node, first along x1x_1 and then along x2x_2: that is the exhaustive search. The wall then appears at the winning threshold and slices only its own region, and the two child tiles settle in its place. A tile's colour is its class mix (cyan, slate at 50/50, emerald). Each wall is taller the larger its (n/N) ΔG(n/N)\,\tok{gain}{\Delta G} (square-root scale), so the root wall dominates. Once the depth-3 tree is fully grown, the HUD shows 6 leaves, 93.1% training accuracy, 88.0% test accuracy and a weighted leaf impurity of 0.106.

Loading figure
The same tree as a diagram, growing in step with the viewport's walls. The root box reads n=160n=160 and G=0.500G=0.500; its left child holds 65 points, 62 of them emerald.

Grow the depth-3 tree with entropy instead of Gini.

An Introduction to Statistical Learning, James, Witten, Hastie & Tibshirani, Ch. 8.1

The Elements of Statistical Learning, Hastie, Tibshirani & Friedman, Ch. 9.2

02Depth, overfitting and variance

Depth is the capacity knob. The viewport now grows the tree to d=8\tok{depth}{d}=8. It stops at 20 leaves, where every leaf is pure: training accuracy reaches 100% and the weighted impurity reaches 0. On 600 fresh moons from the same generator, test accuracy falls from 88.0% at d=3d=3 to between 84.5% and 85.7% for every d≥5d\ge5.

Go to the other extreme: a tree of depth 1, a single split.

E[(y−f^(x))2]=σε2+Bias⁡2[f^(x)]+Var⁡[f^(x)]\mathbb{E}\big[(y-\hat f(x))^2\big]=\sigma_\varepsilon^2+\operatorname{Bias}^2\big[\hat f(x)\big]+\operatorname{Var}\big[\hat f(x)\big]
The bias-variance decomposition from lesson 2.3 (Bias, variance and regularisation). Deep trees have low bias and high variance; shallow trees the reverse.

Watch the late walls: they are short, because each moves only a handful of points, and they carve thin slivers around single cyan or emerald points that sit on the wrong side of the moons. Those slivers are noise being memorised. They are also unstable: the greedy choice at the root conditions every split below it, so a small change in the data can redraw the whole tree.

Loading figure
The depth-8 tree, cut at 4 levels (grey stubs count the leaves below). Once the tree is fully grown, the probe at (−0.40,−0.25)(-0.40, -0.25) sits near the moons' boundary: its path takes all 8 comparisons and ends in a leaf holding a single emerald point. Late splits like these each serve a handful of points.

The next two steps take the opposite routes out of this trade-off. Bagging keeps deep, low-bias trees and averages away their variance. Boosting keeps shallow, low-variance trees and adds them up to remove bias.

An Introduction to Statistical Learning, James, Witten, Hastie & Tibshirani, Ch. 8.1.1 (tree pruning)

Hands-On Machine Learning, Aurélien Géron, Ch. 6 (regularisation hyperparameters, instability)

03Bagging and random forests

Bagging draws BB bootstrap samples (N draws with replacement), grows a deep tree on each and averages them. A random forest also restricts each split to a random subset of mm of the dd features; here d=2d=2 and m=1m=1, so every node gets one randomly chosen feature. The viewport adds trees one at a time up to B=60B=60. The height of the stepped surface is the averaged class-1 probability, and class-1 points sit at height 1. The three newest trees are drawn as amber outlines around the leaves where each one votes class 1, at that leaf's height. A single tree is a hard, blocky staircase; their average is smooth.

fˉB(x)=1B∑b=1BTb(x)\tok{forest}{\bar f_B}(x)=\frac{1}{B}\sum_{b=1}^{B}T_b(x)
T_b is the tree grown on bootstrap sample b, here returning its leaf's class-1 proportion.

A number example first. Say each tree's prediction at some point has variance σ2=0.1\sigma^2=0.1, any two trees are correlated with ρ=0.3\rho=0.3, and the forest averages B=10B=10 trees. The derivation below gives the forest's variance as ρσ2+1−ρBσ2=0.03+0.007=0.037\rho\sigma^2+\tfrac{1-\rho}{B}\sigma^2=0.03+0.007=0.037, about a third of one tree's 0.1. With B=1000B=1000 trees it is 0.0301: the shared part ρσ2=0.03\rho\sigma^2=0.03 never averages away.

Variance of an average of correlated trees1/4
  1. 1
    Var⁡Tb(x)=σ2,Corr⁡(Tb(x),Tb′(x))=ρ(b≠b′)\operatorname{Var}T_b(x)=\sigma^2,\qquad \operatorname{Corr}\big(T_b(x),T_{b'}(x)\big)=\tok{rho}{\rho}\quad(b\ne b')

    The trees are identically distributed. They are correlated because all of them were grown from the same training set.

Estimated over 40 fresh draws of the moons with depth-8 trees, plain bagging gives ρ≈0.23\rho\approx0.23 and σ2≈0.084\sigma^2\approx0.084, so a 60-tree average has variance about 0.021. Drawing one random feature per split makes each tree noisier (σ2≈0.103\sigma^2\approx0.103) but much less correlated (ρ≈0.12\rho\approx0.12), and the 60-tree average drops to about 0.014. The viewport grows the forest from one tree. That first tree scores 82.3% on the test set, but averaged over all 60 trees a single forest tree scores 86.0%, about the same as the full depth-8 tree's 85.2%. Each tree alone is no better than the full tree; the 60-tree vote scores 90.5%.

Average shallow trees instead: the same 60-tree forest with depth 3.

in-bag counts[,]9,600 values

How often each point was drawn for each tree. A given point is left out with probability (1 − 1/N)^N ≈ e⁻¹ ≈ 0.368.

The Elements of Statistical Learning, Hastie, Tibshirani & Friedman, Ch. 15.2 and 15.3.1

An Introduction to Statistical Learning, James, Witten, Hastie & Tibshirani, Ch. 8.2.1 and 8.2.2

The rest of this lesson is in Pro

  • 04Boosting as gradient descent in function space
  • 05Shrinkage, stages and early stopping
  • 06Feature importance and the exam lens
  • Python challenge: Split, then boost
  • Knowledge check, 4 questions

Pro opens all 45 lessons, every graded Python challenge and the full 3D labs.

Compiling scene

The Python challenge and knowledge check for this lesson are part of Pro.

Questions learners ask

What is the difference between a random forest and gradient boosting?
Both combine many decision trees. A random forest grows deep trees independently on bootstrap samples with random feature subsets and averages them, which mainly reduces variance; it is hard to overfit by adding trees. Gradient boosting grows shallow trees one after another, each fitted to the residuals (the negative gradient of the loss) of the current ensemble and added with a small learning rate, which mainly reduces bias. Boosting is usually more accurate on tabular data but needs early stopping and more tuning.
Should I use Gini impurity or entropy for a decision tree?
In practice it rarely matters. Both are concave functions of the class proportions, zero for a pure node and largest for an even mix, and they rank candidate splits almost identically, so trees built with them differ only in a few deep splits. Gini is slightly cheaper because it needs no logarithm, which is why it is the default in common libraries. Depth, leaf size and ensembling matter far more than the choice of impurity.
Do decision trees and gradient boosting need feature scaling or missing-value imputation?
Feature scaling is not needed. A split compares one feature with a threshold, so any monotone rescaling of that feature produces the same tree. Imputation is optional for libraries such as XGBoost and LightGBM, which learn at each split which branch missing values should follow. Some implementations still require complete data, so check the library, and keep the imputation consistent between training and serving.

Next in Classical Machine Learning

2.5Support vector machines and the kernel trickMaximise the margin, then lift the data into a space where a plane can separate it, without ever computing that space.

Sources

  • An Introduction to Statistical Learning, James, Witten, Hastie & Tibshirani
  • Hands-On Machine Learning, Aurélien Géron
  • The Elements of Statistical Learning, Hastie, Tibshirani & Friedman