Why Compare the Trees Case by Case?
A maximal classification tree can divide the feature space into many terminal nodes, each with its own estimated class proportions and predicted label. Pruning replaces a subtree with a single terminal node. That replacement can change which label is predicted for observations in the affected region, even though observations outside that region keep their previous predictions.
To compare the two trees correctly, keep three things distinct: the training counts that determine a leaf’s class proportions and predicted label; the training errors made by those predictions; and the validation observations used to assess performance on data not used to fit the tree. In particular, a validation leaf’s observed class proportions do not determine the prediction of a fitted tree.
When a subtree is collapsed, its new node receives all the training observations that were in its descendant leaves. Its positive and negative counts are the sums of the corresponding counts across those leaves. Thus, the collapsed node is not assigned the average of the descendant leaves’ predictions. It is assigned a prediction from the combined training counts.
Why the Training Error Can Increase
For a node that predicts the majority class, the number of training errors is the count in the minority class. If the node predicts positive, its errors are \(n_-\); if it predicts negative, its errors are \(n_+\). Consequently, its minimum attainable error count using one class label for everyone in the node is \(\min(n_+,n_-)\).
Before collapsing a subtree, each descendant leaf can use its own label. The subtree’s training errors are therefore the sum of the minority counts in its leaves. After collapsing, one label must cover the combined region, so the error count is the minority count among the combined totals. These quantities need not be equal: the collapsed node can have more training errors because its single label cannot preserve all the descendant leaves’ classifications.
This calculation follows directly from the majority rule. In a leaf, predicting positive misclassifies every negative observation, while predicting negative misclassifies every positive observation. Choosing the more numerous class makes the other class—the smaller count—the error count. After pruning, counts add because the descendant leaves partition the observations in the region, so the same argument applies to the combined counts.
Worked Example: Tracking a Collapse and an Unchanged Leaf
A fitted binary tree has a two-leaf subtree, called region A, and one other terminal leaf, C. The positive class is the class of interest. Training counts in the two leaves of A are: leaf A1 has 9 positive and 3 negative observations; leaf A2 has 2 positive and 8 negative observations. Leaf C has 2 positive and 6 negative observations. A validation set has, respectively, A1: 5 positive and 2 negative; A2: 2 positive and 4 negative; and C: 1 positive and 4 negative. Compare the maximal tree with the tree that collapses A. State the method and a common mistake to avoid.
Method: calculate each training label from its own training counts, then apply those fixed labels to the validation counts. In A1 the positive proportion is \(9/(9+3)=9/12=0.75\), so the leaf predicts positive and makes 3 training errors. In A2 it is \(2/(2+8)=2/10=0.20\), so the leaf predicts negative and makes 2 training errors. Thus region A contributes \(3+2=5\) training errors before pruning.
After collapsing A, its training counts are \(9+2=11\) positive and \(3+8=11\) negative. The positive proportion is \(11/22=0.50\). The counts tie, so the stated tie-breaker makes the collapsed node predict negative. It makes 11 training errors. Leaf C still predicts negative because it has 6 negative and 2 positive observations, and it contributes 2 errors. Total training errors are therefore \(5+2=7\) before pruning and \(11+2=13\) after pruning.
For validation, the maximal tree predicts positive in A1, where it makes 2 errors, and negative in A2, where it makes 2 errors. Leaf C predicts negative and makes 1 error. Its total is \(2+2+1=5\) errors among \(7+6+5=18\) validation observations, or \(5/18=0.2778\). After collapse, the negative prediction for A applies to all 13 validation observations in A. There are \(5+2=7\) positive and \(2+4=6\) negative observations there, so the collapsed node makes 7 errors. Adding C’s 1 error gives \(8/18=0.4444\).
Check: C is unchanged in both trees, and its 2 training errors and 1 validation error are counted once in each total. The common mistake is to retain the descendant leaves’ different predictions after they have been replaced by one node; the collapsed node has only one label.
Validation Error Must Be Counted in Every Leaf
For a fixed fitted tree, validation error is computed by routing each validation observation to a terminal node and comparing that node’s training-based predicted label with the observation’s known class. The error count for a leaf is the number of validation cases whose actual class differs from that leaf’s prediction. When comparing a maximal tree with a collapsed subtree, add the errors from every affected leaf before pruning, and compare that sum with the errors in the collapsed region after pruning.
Worked Example: Counting Both Descendant Leaves on Validation Data
A maximal tree has two leaves in region B. Training counts are 5 positive and 2 negative in B1, and 1 positive and 6 negative in B2. The validation set contains 2 positive and 6 negative observations in B1, and 5 positive and 1 negative observation in B2. Compare validation errors before and after collapsing B. The tie-breaker is negative. Name the method and the common error-counting trap.
Method: retain the labels fitted from training counts, then count validation mismatches leaf by leaf. B1 predicts positive because \(5>2\). Its validation cases include 6 negatives, so B1 makes 6 validation errors. B2 predicts negative because \(6>1\). Its validation cases include 5 positives, so B2 makes 5 errors. The maximal tree therefore makes \(6+5=11\) errors among \(2+6+5+1=14\) validation observations:
For the collapsed node, add the training counts: \(5+1=6\) positive and \(2+6=8\) negative. It predicts negative. The validation counts in the combined region are \(2+5=7\) positive and \(6+1=7\) negative. Since the fitted collapsed node predicts negative, it misclassifies all 7 positive validation cases. The collapsed tree’s validation error is \(7/14=0.5000\).
Check: The maximal tree’s numerator must include errors from both leaves. Counting only the 6 negative validation cases in B1 would omit B2’s 5 positive cases, incorrectly giving \(6/14\). The correct comparison is maximal \(11/14=0.7857\), collapsed \(7/14=0.5000\). Validation results can favor the collapsed tree even though its training error is higher: its training errors in B are \(2+1=3\) before collapse and \(6\) afterward.
Keep Unchanged Regions in the Overall Totals
A pruning step changes predictions only within the subtree being replaced. If the reported error is for the entire tree, errors from all unaffected terminal nodes must still be included. This is a separate bookkeeping step from combining the descendant leaves in the pruned region.
Worked Example: Including the Unchanged Leaf in Both Counts
A maximal tree has two leaves in region D and an unchanged leaf E. D1 contains 7 positive and 3 negative training observations; D2 contains 2 positive and 8 negative observations. E contains 5 positive and 3 negative observations. In validation data, D1 has 4 positive and 2 negative cases, D2 has 2 positive and 3 negative cases, and E has 3 positive and 2 negative cases. Compare the total training and validation errors before and after collapsing D. Use negative to break a tie.
Method: calculate the affected region and unchanged leaf separately, then add their errors. D1 predicts positive and has 3 training errors. D2 predicts negative and has 2 training errors. E predicts positive and has 3 training errors. Before pruning, the total is \(3+2+3=8\).
The combined training counts in D are \(7+2=9\) positive and \(3+8=11\) negative, so the collapsed node predicts negative and makes 9 errors. E remains positive and makes 3 errors. After pruning, total training errors are \(9+3=12\). The affected-region error changes from 5 to 9; the unchanged leaf’s 3 errors are included on both sides.
On validation data, D1 predicts positive and makes 2 errors; D2 predicts negative and makes 2 errors; E predicts positive and makes 2 errors. The maximal tree therefore makes \(2+2+2=6\) errors among \(6+5+5=16\) validation cases, or \(6/16=0.3750\). In the collapsed region D, validation counts combine to \(4+2=6\) positive and \(2+3=5\) negative. The collapsed node predicts negative from its training counts, so it makes 6 validation errors. E still makes 2, for \(6+2=8\) errors, or \(8/16=0.5000\).
Check: The full-tree training error before pruning is \(3+2+3=8\), not \(3+3=6\), because D2 contributes 2 errors. After collapse, D has 9 errors and E has 3, giving \(9+3=12\), not 13. The full validation totals likewise include E exactly once.
Interpreting the Comparison
A clean comparison records, for each version of the tree, its terminal-node labels, training error count, validation error count, and the relevant denominator. When a leaf’s class proportions are needed, report them from training counts. For example, a leaf with 7 positive and 3 negative training cases has positive proportion \(7/10=0.70\) and predicts positive; that prediction does not change merely because its validation cases have a different class balance.
| Quantity | Before collapsing | After collapsing |
|---|---|---|
| Class counts in the affected region | Kept separately for each descendant leaf | Added across all descendant leaves |
| Predicted label | May differ across leaves | One label from the combined training counts |
| Training errors | Sum of errors in descendant leaves | Minority count in the combined region |
| Validation errors | Sum of validation mismatches in descendant leaves | Mismatches against the collapsed node’s training-based label |
| Unaffected leaves | Included in the whole-tree total | Still included, with the same predictions |
A lower validation error is evidence that one tree performed better on that particular validation set, not a guarantee that it will perform better on every future sample. Conversely, an increase in training error after pruning is not an arithmetic defect: one label is replacing the separate labels that the descendant leaves could use. The comparison is useful because it makes the tradeoff visible without confusing tree structure, class proportions, or evaluation data.
Check Your Understanding
For each problem, use the stated tie rule and distinguish training counts from validation counts.
- A two-leaf subtree has training counts of 8 positive and 2 negative in the first leaf, and 3 positive and 7 negative in the second. Find the predictions and training errors before collapse, then the combined prediction and error after collapse. (Answer: Before: positive and negative, \(2+3=5\) errors. After: positive, \(9\) errors.)
- A validation set has 6 positive and 4 negative cases in a leaf that predicts positive, and 5 positive and 3 negative cases in a leaf that predicts negative. Find the maximal-tree error rate. If the collapsed node predicts positive, find its error rate. (Answer: Maximal \(4+5=9\) errors out of 18, \(9/18=0.5000\); collapsed \(7/18=0.3889\).)
- Two leaves have training counts of 4 positive and 1 negative, and 1 positive and 4 negative. The tie-breaker is negative. What are the leaf predictions and errors, the combined positive proportion, and the collapsed-node error count? (Answer: Leaf predictions positive and negative, with \(1+1=2\) errors; combined positive proportion \(5/10=0.50\); collapsed prediction negative with 5 errors.)
- A two-leaf subtree has validation counts of 4 positive and 3 negative in a leaf that predicts positive, and 2 positive and 5 negative in a leaf that predicts negative. An unchanged leaf predicts negative and has 1 positive and 4 negative validation cases. The collapsed subtree predicts negative. Find whole-tree validation errors before and after collapse, and the rates. (Answer: Before \(3+2+1=6\) errors out of 19, \(6/19=0.3158\); after \(6+1=7\) errors out of 19, \(7/19=0.3684\).)