Why remove a rule that fits training data?
A tree can fit the training cases by splitting until a leaf describes only one or two observations. Such a rule may capture a real pattern, but it may also encode accidental labels. The earlier decision-tree unit showed how to grow and compile a tree; it deliberately left pruning separate. Here we study one precise way to decide which branches to remove.
Definition 28.1.1
(Stored training labels and the three data sets)
Set aside labeled validation cases before growing the tree. Train the tree using the training cases only; route each training case through it and store at every node its training-label majority. For a binary tie choose label . If a node has no training cases, use a declared training-only fallback, such as its parent's stored label. These labels remain fixed during pruning. They are not recalculated from validation labels. Keep a third, untouched test set for the final evaluation, with splitting appropriate to how observations were collected; related people or later time periods may require group or time-based separation.
The procedure and its exact guarantee
Definition 28.1.2
(Postorder reduced-error pruning)
Write for the current finite tree and for its validation set. Process internal nodes in a fixed postorder: descendants before their parent, with a fixed child order. At node , replace its current subtree by a leaf labeled with the stored training majority at , but only if this replacement does not increase the number of mistakes on . Accept equality, preferring the smaller tree. Otherwise retain the current subtree. Later decisions at ancestors use the already modified descendants. The root is considered last; if an ancestor is pruned, all its descendants disappear. This is one pass with a specified tie convention, not a claim that every variant of pruning uses the same rule.
Definition 28.1.3
(Local error counts)
Let be the validation cases that reach in the current tree. Define as their errors under the current subtree and as their errors under the candidate leaf. Counts, rather than proportions, make the empty case clear: if is empty both are zero, so the stated tie rule prunes the subtree. This simplifies an unsupported branch; it does not show that the leaf predicts well there.
Theorem 28.1.4
(What each accepted replacement guarantees)
For a fixed finite validation set and deterministic routing, the stated procedure terminates and the final number of validation mistakes is no greater than that of the original tree. Each accepted replacement reduces the number of nodes. Among all trees obtainable by replacing original subtrees with their stored-label leaves, the final tree has minimum validation error and, among minimizers, the fewest nodes. This does not guarantee improved population accuracy.
Proof
(Local change equals the difference of two counts)
Replacing the subtree at changes no predictions for cases outside . Thus the change in the total error count is exactly . The algorithm accepts only when this difference is nonpositive. Every accepted replacement removes at least one node, and the fixed finite postorder considers only finitely many nodes. Hence it terminates and successive accepted changes cannot increase validation error. For the stronger claim, use induction from the leaves upward. At a node, every allowed pruning either replaces its whole subtree by the stored-label leaf or retains the node and independently prunes each child. Validation error for retained children is additive, since each case follows one child. By induction each processed child has minimum error; among equal-error choices it has fewest nodes. Comparing that retained tree with the candidate leaf therefore gives minimum error at the node, and accepting a tie gives the smallest minimizing tree. Apply this at the root. This is an in-sample selection statement about , not a probability statement about future cases.
Proof X-ray
The cancellation behind the comparison
Only cases reaching the chosen node can change prediction. All other error terms cancel, so comparing the two local error counts gives the exact change in the full validation objective. The comparison remains valid when some descendants have already been pruned.
Worked trace: improvement, tie and rejection
Worked example 28.1.5
(Improvement, tie and rejection)
The root tests . At , node tests and predicts for , for . At , node tests and predicts for , for . The stored training majorities are at , at , and at the root. For example, training label counts of at and at give those three majorities. Below, each list consists of validation labels for cases following that path; the feature values determine the path.
| Path | Validation labels | Initial prediction | Initial mistakes |
|---|---|---|---|
The initial tree makes mistakes among cases. Visit first. Its current subtree makes mistakes; leaf makes , one for each validation label . Replace : total error falls to . Next visit . Its subtree makes mistakes, and leaf also makes , one for each label . The tie rule replaces ; total error stays . Finally, the current root subtree has error . A root leaf would misclassify the two ones on the left and the three ones on the right, giving . Reject that replacement. The final tree tests only , predicting on the left and on the right; its validation error is .
Concept lensAlgorithmic
Pruning as a bottom-up minimum
Let be the fewest validation errors at the cases reaching over all prunings of the subtree at . Then over the children , and of a leaf is its own error count. In the trace, , and , the final error found above.
Worked example 28.1.6
(Comparing an ancestor with its modified descendants)
Let a root have a left and a right subtree, each reached by six validation cases. Currently the left subtree makes errors and the right subtree makes . The stored-label leaves would make and errors respectively, and a root leaf would make . Postorder: the left subtree is replaced because , and the right is retained because . The current subtree at the root now makes errors, so a root leaf with errors is rejected and the final error is . Comparing the root leaf with the stale original total would instead give a tie, prune the root, and end with error , no better than the starting tree and worse than the correct .
Worked example 28.1.7
(The tie convention changes the tree, not the validation error)
Return to the trace above, and suppose the tie were resolved the other way, so that a replacement is accepted only when it strictly lowers the validation error. Node is still replaced, since . At the leaf and the subtree both make errors, so is now retained. The root leaf still makes and is rejected. The final tree has total error , the same as under the stated rule, but it keeps the test of and has two more nodes (a retained node with two leaves instead of one leaf). The accepted-tie convention therefore selects the smallest tree among those with minimum validation error.
Common mistake
(Choosing a replacement label from validation cases)
The replacement leaf must carry the stored training majority. If its label were chosen from the validation labels at , then would be the smallest count that any single label can achieve on those cases, which biases the comparison toward pruning and uses the validation labels twice. In the trace above, the right-hand validation data contain three ones and two zeros; that coincidence does not authorize choosing a leaf label from validation. A different validation set could produce a different pruning decision even though the trained tree is unchanged.
Leakage and selection overfitting
Counterexample mode
A perfect selected score need not predict the future
Suppose is a unique identifier and is an independent fair coin. A sufficiently flexible tree can memorize the labels of the cases used to grow it and obtain zero training error, while its prediction for a fresh independent coin is correct with probability only . If those same labeled cases are called the validation set, pruning decisions and their score reuse training information. The zero score says nothing about a gain over chance on new cases.
Even a truly separate validation set is used repeatedly here: each pruning decision depends on its labels. Trying many trees, tie policies or hyperparameters on that same set can adapt the whole procedure to its noise. Validation error is therefore not an independent final performance estimate. Freeze all choices first, then evaluate once on untouched representative test cases; a single small test set still has sampling uncertainty. If training is repeated after selection, specify the refitting procedure in advance and evaluate the resulting refitted model on data that were not used for selection or fitting.
Common mistake
(Quoting the selected validation error as performance)
In the trace the pruned tree has validation error . That number was produced by comparing counts on the very labels that drove each pruning decision, so it is not an independent estimate of future error. A fresh test set, used once after all choices are frozen, is required.
Practice
Quick check
(At node , the current subtree makes errors on the validation cases reaching it. A training-majority leaf makes errors there. The whole tree currently makes validation errors. What happens, and what is the new total?)
Solution · Answer
Accept the replacement: . Outside the number of mistakes is unchanged, so the new total is .
Quick check
(A node has no validation cases. Under the algorithm above, is it pruned? Does that imply its replacement has zero population error?)
Solution · Answer
Yes: both local error counts are zero and equality is accepted. There is no evidence about future error from an empty validation subset; zero observed errors among zero observations gives no accuracy guarantee.
Exercise 28.1.8
(A tree has a root with left and right subtrees. Current validation errors are respectively and . Training-majority leaves would make and errors, respectively; a root training-majority leaf would make errors in total. Perform the postorder decisions with ties pruned, and state the final error. Why must the root comparison use the modified children?)
Core
Solution(3)
- 1
Decide the left subtree
The current error is and the leaf error is . The tie rule replaces the left subtree.
- 2
Decide the right subtree
The current error is and the leaf error is , and , so the right subtree is replaced.
- 3
Decide the root with modified children
The tree now makes errors, and the root leaf also makes , so the tie rule replaces the root; the final error is . The comparison must use the modified children because the root's candidate is measured against the tree actually in hand. Using the original child errors would compare the stale value with ; it happens to accept the root here, but that is not the procedure.
Quick check
(Someone grows a tree on all labeled examples, then randomly divides those same examples into purported training and validation subsets before pruning. Identify the leakage and propose a valid three-way workflow.)
Solution · Answer
The tree's splits and leaves were already fitted using labels later called validation labels; the validation set is not independent of tree growth. Split observations first, grow and label the tree on training data, prune and select using validation data, then freeze the procedure and evaluate on a separately held-out test set. The split must also respect relevant groups or time ordering.