2.4 Decision trees, random forests and gradient boosting
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 and every threshold , 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 , 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 . Each child holds half the points, so the weighted impurity after the cut is , and the cut buys an impurity decrease of . 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.
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.
- 1
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.
Before each wall rises, an amber outline sweeps across the node, first along and then along : 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 (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.
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 . 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 to between 84.5% and 85.7% for every .
Go to the other extreme: a tree of depth 1, a single split.
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.
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 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 of the features; here and , so every node gets one randomly chosen feature. The viewport adds trees one at a time up to . 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.
A number example first. Say each tree's prediction at some point has variance , any two trees are correlated with , and the forest averages trees. The derivation below gives the forest's variance as , about a third of one tree's 0.1. With trees it is 0.0301: the shared part never averages away.
- 1
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 and , so a 60-tree average has variance about 0.021. Drawing one random feature per split makes each tree noisier () but much less correlated (), 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.
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.
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