Tree pruning (cost complexity)
Grow a tree far too big on purpose, then cut it back. Every leaf is charged a fee α; a branch is kept only if it reduces the error by more than its fee. Choose the fee on validation data.
Question type: not a model: a way to control a tree’s size (regression or classification).
Week: 4.
Book: ISLP 8.1.1, “Tree pruning” (p335–337, Algorithm 8.1).
Techniques on this page: grow-then-prune, the penalised score \(\text{RSS} + \alpha|T|\), weakest-link pruning, choosing \(\alpha\) on a validation set, sklearn’s ccp_alpha.
The problem it solves
A fully grown regression tree memorises its training data. Stopping early (“only split if it helps a lot”) sounds sensible but is short-sighted: a dull split can open the door to a great one later.
So grow big, then prune. But a big tree has millions of subtrees, too many to test one by one. Cost-complexity pruning boils them down to a short, nested list, one per value of a single dial \(\alpha\), and then you only need to pick the dial. It’s the tree version of ridge regression’s \(\lambda\).
Words you’ll hear
| Word | Plain meaning |
|---|---|
| \(T_0\) | the big tree you grow first |
| subtree | \(T_0\) with some branches cut off (their points merged back into one leaf) |
| \(\lvert T\rvert\) | number of leaves |
| \(\alpha\) | the fee per leaf (the tuning dial) |
| weakest link | the branch that saves the least error per leaf: cut first |
ccp_alpha |
sklearn’s name for \(\alpha\), on a per-data-point scale |
Technique 1: the penalised score
Problem it solves: comparing trees of different sizes fairly.
\[C_\alpha(T) = \underbrace{\text{RSS}(T)}_{\text{how badly it fits}} + \underbrace{\alpha\,|T|}_{\text{fee for its size}}\]
For each \(\alpha\), keep the subtree with the smallest \(C_\alpha\). \(\alpha = 0\): the full tree. Bigger \(\alpha\): smaller trees. Huge \(\alpha\): just the root.
Worked example. The subtrees of the regression tree example:
| leaves | 1 | 2 | 3 | 4 | 6 |
|---|---|---|---|---|---|
| RSS | 73.5 | 13.33 | 5.17 | 1.0 | 0 |
| \(C_5\) | 78.5 | 23.33 | 20.17 | 21.0 | 30.0 |
With \(\alpha = 5\) the 3-leaf tree wins. The 4th leaf only saves \(5.17 - 1.0 = 4.17\), less than its fee of 5.
Technique 2: weakest-link pruning (the nested sequence)
Problem it solves: finding all the \(T_\alpha\) without searching.
Each split survives while its saving exceeds \(\alpha\). In the example the savings are 0.5 (the last tiny splits), 4.17, 8.17 and 60.17, so as \(\alpha\) rises past each value one more split disappears: 6 leaves → 4 → 3 → 2 → 1. The trees are nested: each is a pruned version of the one before. (For a branch with several leaves, the saving counted is its RSS drop per leaf removed.)
Technique 3: choose \(\alpha\) on a validation set
Problem it solves: the training RSS always prefers the biggest tree.
- Grow \(T_0\) on the training data.
- Get the sequence of \(\alpha\) values where the subtree changes.
- Score each subtree on the validation set; take the best \(\hat\alpha\).
- Refit with \(\hat\alpha\) (the lab uses train + validation) and report the test error once.
Plot validation error against \(\alpha\) and you get the usual U: too small, overfitting; too big, underfitting. ISLP uses K-fold cross-validation for step 3; same idea.
sklearn’s \(\alpha\) is per data point. cost_complexity_pruning_path and ccp_alpha use the training MSE (RSS\(/n\)), not the RSS. So sklearn’s \(\alpha\) = the slides’ \(\alpha\) / \(n\). In the example (\(n = 6\)), the savings 4.17 and 8.17 show up as 0.69 and 1.36. The path can also list the same \(\alpha\) several times in a row, when several branches tie.
Lab plot typo: the pruning cell calls plt.xlabel twice; the second should be plt.ylabel('error').
What to read in the book
| Section | Read? | Why |
|---|---|---|
| 8.1.1 “Tree pruning” (p335–337) | Read | Eq. 8.4, Algorithm 8.1, Figs 8.4–8.5 |
| Algorithm 8.1 step 3 (K-fold CV) | Read, but note | The slides and lab use one validation set instead |
Practice prompt
I'm studying CS5100 Data Analysis (textbook ISLP, section 8.1.1, tree pruning). I want practice questions on COST-COMPLEXITY PRUNING, done by hand:
- given a list of subtrees with (number of leaves, training RSS), find the subtree that minimises RSS + alpha * leaves for several alphas
- the alpha at which one subtree starts to beat a bigger one (the saving per leaf)
- why the subtrees form a nested sequence (weakest-link pruning)
- why alpha must be chosen on validation data, and what the validation-error-vs-alpha curve looks like
- converting between sklearn's ccp_alpha (MSE scale) and the RSS-scale alpha
- comparing pruning with stopping early, and with ridge regression's lambda
Please:
1. Use plain, everyday language and explain any technical term in one short sentence.
2. Give me ONE question at a time, easy first, then harder, with friendly numbers.
3. Wait for my answer, then mark it and show the full working step by step.
4. If I get it wrong, explain the mistake and give me a similar question.
5. Every 5 questions, summarise my strengths and what to practise.