Tree pruning
A tree's flexibility is its number of leaves. Grow it big, then cut it back by charging a fee α per leaf: each leaf must pay for itself by lowering the RSS by more than α. Choose α on validation data.
2025 Q1 asked: “Discuss the flexibility of decision trees in terms of the number of terminal nodes. Give a technique to mitigate overfitting.” The answer is this stage.
Book: what to read for this stage
ISLP 8.1.1 Tree pruning (eq. 8.4, Algorithm 8.1, Figs 8.4 and 8.5): read. ISLP chooses \(\alpha\) by K-fold cross-validation; the slides and the lab use a single validation set. Same idea.
1. Flexibility = number of leaves
A tree with \(|T|\) terminal nodes (leaves) is a piecewise-constant function with \(|T|\) pieces. More leaves:
- smaller boxes, so the tree can follow finer detail: lower bias, lower training error;
- fewer training points per leaf, so each leaf’s average is noisier and the tree changes a lot with the data: higher variance.
At one point per leaf the training error is 0 and the tree has memorised the noise. Test error is U-shaped in \(|T|\).
Stopping early (only split if the RSS drops by more than a threshold) is short-sighted: a weak split can be followed by a very good one (stage 14’s 8 A / 2 B example). Better: grow a large tree \(T_0\), then prune it back to a subtree.
What happens to a regression tree’s bias and variance as its number of terminal nodes grows?
More leaves = more flexible. Same trade-off as every other knob in the course.
2. Cost-complexity pruning
For a tuning parameter \(\alpha \ge 0\), score each subtree \(T\) of \(T_0\) by
\[C_\alpha(T) = \sum_{m=1}^{|T|}\sum_{i \in R_m}(y_i - \hat y_{R_m})^2 + \alpha|T|:\]
training RSS plus a fee of \(\alpha\) per leaf. \(T_\alpha\) is the subtree with the smallest \(C_\alpha\).
- \(\alpha = 0\): no fee, so the full tree \(T_0\) wins.
- Larger \(\alpha\): leaves get expensive, the best subtree shrinks.
- Very large \(\alpha\): just the root (predict the overall mean).
It is the same idea as ridge regression: fit plus a penalty on complexity, with a dial chosen on validation data.
Worked example (stage 13’s tree). Nested subtrees: 1 leaf RSS 73.5; 2 leaves 13.33; 3 leaves 5.17; 4 leaves 1.0; 6 leaves 0.
With \(\alpha = 5\): \(C = 78.5,\ 23.33,\ \mathbf{20.17},\ 21.0,\ 30.0\). The 3-leaf tree wins. The 4th leaf only saves \(5.17 - 1.0 = 4.17 < 5\), so it doesn’t pay for itself.
3. Weakest-link pruning and the algorithm
As \(\alpha\) rises, splits disappear in order of how little they save: a split survives while its RSS saving exceeds \(\alpha\). So the best subtrees form a nested sequence (6, 4, 3, 2, 1 leaves above, with splits pruned at \(\alpha = 0.5, 4.17, 8.17, 60.17\)). This is weakest-link pruning. (For a whole branch, the saving per leaf removed is what’s compared.)
The algorithm (ISLP Algorithm 8.1, slide 34):
- Grow a large tree \(T_0\) on the training data.
- Compute the nested sequence \(T_\alpha\) and the \(\alpha\) values where it changes.
- Pick the \(\alpha\) with the lowest validation error.
- Refit with that \(\alpha\) (the lab uses training + validation) and report the test error once.
sklearn’s scale: ccp_alpha uses the training MSE (RSS/\(n\)), so sklearn’s \(\alpha\) = the slides’ \(\alpha\) / \(n\). With \(n = 6\) the thresholds above appear as 0.083, 0.69, 1.36, 10.03. tree.cost_complexity_pruning_path(X, y) lists them.
Subtrees \((|T|, \mathrm{RSS})\): \((1, 100), (2, 40), (3, 30), (5, 26)\). Above what \(\alpha\) does the 2-leaf tree beat the 3-leaf tree?
The third leaf saves \(40 - 30 = 10\), so once \(\alpha > 10\) it’s not worth its fee.
sklearn reports ccp_alpha = 2.5 for a tree trained on 200 points. What is this \(\alpha\) on the slides’ RSS scale?
\(2.5 \times 200 = 500\).
Stage test
(5 marks, exam format 3; 2025 Q1.) Discuss the flexibility of decision trees in terms of the number of terminal nodes, and give a technique to mitigate overfitting.
A tree with more terminal nodes divides the input space into more, smaller regions, so it can represent more complicated functions: it is more flexible. Its bias and training error fall (with one training point per leaf the training error is zero), but each leaf’s prediction is based on fewer points, so the variance rises and the tree starts fitting the noise in the training data: overfitting, with the test error rising again. To mitigate this, use cost-complexity pruning: grow a large tree \(T_0\), then for a penalty \(\alpha \ge 0\) choose the subtree \(T\) minimising \(\sum_m\sum_{i \in R_m}(y_i - \hat y_{R_m})^2 + \alpha|T|\). With \(\alpha = 0\) this is the full tree; increasing \(\alpha\) removes the weakest splits first and gives smaller trees. Choose \(\alpha\) by the error on a validation set (or by cross-validation) and report the test error of the pruned tree. (Alternatives: a maximum depth or minimum leaf size; averaging many trees, as in bagging and random forests.)
With \(\alpha = 0\), which subtree minimises \(C_\alpha(T)\)?
With no fee per leaf, only the training RSS counts, and the full tree has the lowest.
Why is \(\alpha\) chosen on a validation set rather than the training set?
Only unseen data can show when extra leaves start fitting noise.
Tick every true statement about cost-complexity pruning.
Pruning only removes splits; the weakest link goes first.