Why a Deep Tree Can Fit Too Closely
A classification tree predicts a class by following a case through a sequence of splits to a terminal node, or leaf. A shallow tree groups many cases into a few leaves. A deeper tree makes more splits, creating smaller groups. Those smaller groups can match the labels in the training data very closely, including patterns that arose by chance and will not recur in new data.
The key distinction is between performance on the data used to grow a tree and performance on cases that were not used to fit it. Training error describes the first. Validation error provides an estimate of the second, subject to sampling variability. A lower training error is expected as a tree is refined; it is not, by itself, evidence that the tree will classify new cases more accurately.
For a data set with \(n\) cases, let \(I_j=1\) if case \(j\) is misclassified and \(I_j=0\) otherwise. Its empirical classification error rate is
Use this calculation separately for training and validation cases. If sample sizes differ, compare rates rather than raw error counts. Validation results are informative only insofar as the validation cases represent the population on which predictions will be used; with a small validation set, a few cases can change the measured rate substantially.
Why Training Error Cannot Increase When a Leaf Is Split
Assume a binary classification tree predicts the majority class in each leaf, with a fixed rule for ties. Consider a leaf containing \(n_0\) cases of class 0 and \(n_1\) cases of class 1. The minimum number of training errors attainable by assigning one class label to the whole leaf is \(\min(n_0,n_1)\).
Now split the leaf into two children, with counts \(n_{0L},n_{1L}\) and \(n_{0R},n_{1R}\). Majority-class predictions give a combined child error count of \(\min(n_{0L},n_{1L})+\min(n_{0R},n_{1R})\). To see why this cannot exceed the parent error count, assign the parent’s majority class to both children. This would produce exactly the parent’s number of errors across the two children. Each child’s majority-class prediction has errors no greater than this alternative assignment. Therefore,
because \(n_0=n_{0L}+n_{0R}\) and \(n_1=n_{1L}+n_{1R}\). Repeating the argument at later splits shows that training classification error cannot increase as leaves are refined under these assumptions. It may stay the same or decrease. This result concerns training error; it gives no corresponding guarantee about validation error.
Worked Example: Training Error Falls While Validation Error Rises
A hypothetical claims-screening study grows a sequence of nested binary classification trees for “review” and “no review.” At each leaf, the predicted label is the training majority class. The table gives the numbers of misclassified cases at four successive depths. Calculate both error rates at each depth and identify where validation performance is best.
| Tree depth | Training errors (out of 20) | Validation errors (out of 10) |
|---|---|---|
| 0 (root only) | 8 | 4 |
| 1 | 6 | 3 |
| 2 | 3 | 5 |
| 3 | 2 | 6 |
Method. Divide each error count by the corresponding sample size; do not compare the counts directly because the training and validation denominators differ.
At depth 0, the training rate is \(8/20=0.40\), or 40%, and the validation rate is \(4/10=0.40\), or 40%.
At depth 1, the training rate is \(6/20=0.30\), or 30%, and the validation rate is \(3/10=0.30\), or 30%.
At depth 2, the training rate is \(3/20=0.15\), or 15%, and the validation rate is \(5/10=0.50\), or 50%.
At depth 3, the training rate is \(2/20=0.10\), or 10%, and the validation rate is \(6/10=0.60\), or 60%.
The validation error is lowest at depth 1. From depth 1 to depth 3, training error falls from 30% to 10%, while validation error rises from 30% to 60%. The depth-3 tree fits its training cases more closely, but these results do not support the claim that it predicts better on unseen cases. The validation sample has only 10 cases, so its measured rate is also sensitive to individual outcomes.
Check. The depth-3 rates use the same denominators as at the other depths: \(2/20=10\%\) for training and \(6/10=60\%\) for validation. A larger validation percentage is not a contradiction of the nonincreasing-training-error result; the result applies only to training cases.
Repeated Splits Can Isolate Training Cases
A split can separate cases according to a predictor value or category. Further splits can divide the resulting groups again. If the available predictors happen to distinguish individual training cases, a sufficiently deep tree can form leaves containing one case each. Each such leaf is pure by construction and has zero training classification error. But a predictor pattern that uniquely identifies a training case may not identify future cases in a useful way.
Even without one-case leaves, repeated splitting can produce very small groups. A leaf containing one class-1 case and no class-0 cases predicts class 1 correctly on that training case. The same split rule may send a new case down that branch even though its label differs. More branches therefore create opportunities both to capture real structure and to fit accidental details; training fit alone cannot distinguish the two.
Worked Example: A Pure Training Fit Does Not Ensure Validation Accuracy
In a hypothetical equipment-inspection data set, a parent leaf contains 12 training cases: 9 labeled “routine” (C) and 3 labeled “inspect” (D). The tree uses two successive splits that divide these cases into the following leaves. On a separate validation set of 20 cases, the root-only tree misclassifies 6 cases, the one-split tree misclassifies 7, and the two-split tree misclassifies 10. Calculate the training error at each stage, compare validation rates, and interpret the result.
Root only. The leaf predicts C, the majority class. It misclassifies the 3 D cases, so the training error is \(3/12=0.25\), or 25%. The validation error is \(6/20=0.30\), or 30%.
After the first split. The two leaves contain \(7\) C and \(1\) D, then \(2\) C and \(2\) D. The first leaf predicts C and makes 1 error. The second leaf is tied; under the stated fixed tie rule, suppose it predicts C and makes 2 errors. Total training errors are \(1+2=3\), giving \(3/12=25\%\). Validation error is \(7/20=35\%\).
After the second split. The first branch is divided into leaves containing \(7\) C and \(0\) D, and \(0\) C and \(1\) D. The second branch is divided into leaves containing \(2\) C and \(0\) D, and \(0\) C and \(2\) D. Each leaf is pure, so training errors are \(0+0+0+0=0\), and the training error rate is \(0/12=0\%\). Validation error is \(10/20=50\%\).
The deeper tree has reduced training error from 25% to 0%, but validation error has risen from 30% at the root to 50%. The first split did not reduce the training error in this example: its leaves still make three errors in total. The second split makes the training leaves pure, yet the validation results get worse. This is a concrete illustration of how a tree can isolate observed cases without improving predictions for new ones.
Common mistake avoided. Calling the two-split tree “perfect” because it has 0% training error confuses fit to the training sample with performance on unseen cases. Its validation error is 50%, not 0%.
Reading Training and Validation Results Carefully
A typical sign of overfitting is that training error continues to fall as tree depth increases while validation error stops falling or begins to rise. The gap between the two can also grow. This pattern is evidence that added complexity is fitting aspects of the training sample that do not carry over to the validation sample. It is not proof that every added split is useless: a split can reveal a real relationship and improve validation performance, as can happen at a modest depth.
Validation error is an estimate, not a guaranteed measure of future performance. In particular, the rate changes in increments of \(1/n\) when one case changes classification. For a validation set of 10 cases, one case represents \(1/10=10\) percentage points. For a set of 100 cases, one case represents \(1/100=1\) percentage point. A small validation set can therefore make two tree depths appear meaningfully different when the difference is driven by very few cases.
Worked Example: Interpreting a Small Validation Set
A hypothetical fraud-screening study compares four nested tree depths. Each tree is evaluated on 50 training cases and 8 validation cases. Training error counts are 16, 10, 7, and 3; validation error counts at the corresponding depths are 3, 2, 2, and 3. Calculate the rates, identify the validation minimum, and quantify the effect of one validation case.
The training rates are \(16/50=0.32\), \(10/50=0.20\), \(7/50=0.14\), and \(3/50=0.06\), or 32%, 20%, 14%, and 6%.
The validation rates are \(3/8=0.375\), \(2/8=0.25\), \(2/8=0.25\), and \(3/8=0.375\), or 37.5%, 25%, 25%, and 37.5%. The minimum validation error is tied between the second and third tree depths at 25%.
At the deepest tree, the generalization gap is \(37.5\%-6\%=31.5\) percentage points. One validation case changes the error rate by \(1/8=12.5\) percentage points. Thus, a difference of 12.5 points between neighboring depths may reflect the classification of only one case, and the observed tie at 25% does not establish that the tied trees have identical future performance.
Check. The training rates decline at every listed depth, while validation error first falls and then rises. The calculations show why both sample sizes and the direction of the two error curves matter.
Common Exam Traps
- Equating zero training error with zero prediction error. A tree can classify every training case correctly and still misclassify many unseen cases. Report which data set each rate describes.
- Comparing raw counts with different denominators. Six errors among 20 cases is 30%, while four among 10 cases is 40%. The smaller count does not mean the smaller rate.
- Assuming every split reduces training error strictly. A split may leave the total error unchanged, as in the first split in the second worked example. Refinement guarantees nonincrease under majority-class predictions, not a strict decrease at every step.
- Treating a validation rate as exact. A held-out sample gives an estimate. Especially with few cases, one changed classification can noticeably alter the percentage.
- Assuming deeper always means worse validation performance. A useful split can improve validation error. The warning is that training error alone cannot tell whether added depth has improved generalization.
Check Your Understanding
For each problem, distinguish training fit from validation performance and show the relevant rate calculation.
- A root leaf contains 9 cases of class A and 5 of class B. A split creates leaves with counts \(5A,1B\) and \(4A,4B\). Using a tie rule that predicts A, calculate the root and split training errors and decide whether the split strictly improves training error. (Answer: Root \(5/14=35.71\%\); split \((1+4)/14=5/14=35.71\%\), so it does not strictly improve.)
- A tree evaluated at two depths has 30 training cases, with 12 errors at the shallower depth and 7 at the deeper depth. On 16 validation cases, the corresponding error counts are 5 and 7. Calculate both pairs of rates and describe the pattern. (Answer: Training \(40.00\%\) then \(23.33\%\); validation \(31.25\%\) then \(43.75\%\). Training error falls while validation error rises.)
- A leaf contains 8 cases of class 0 and 3 of class 1. A split produces one leaf with \(6\) class-0 cases and no class-1 cases, and another with \(2\) class-0 and \(3\) class-1 cases. Calculate the error counts before and after the split. (Answer: Before, 3 errors; after, 2 errors in the second leaf, so training error falls from \(3/11\) to \(2/11\).)
- Two tree depths have validation errors of 6 and 9 among the same 24 cases. Calculate the rates and the difference in percentage points. (Answer: \(6/24=25.00\%\) and \(9/24=37.50\%\); the second rate is 12.50 percentage points higher.)
- A shallow tree has 4 training errors among 25 cases and 3 validation errors among 10 cases. A deeper tree has 1 training error among 25 and 5 validation errors among 10. Calculate the generalization gap for each and state which tree has the lower validation error. (Answer: Shallow gap \(30\%-16\%=14\) percentage points; deep gap \(50\%-4\%=46\) percentage points. The shallow tree has lower validation error.)