Abstract
In decision tree induction, "overfitting avoidance" via pruning is often treated as a universal statistical necessity. This paper argues that such techniques are actually a form of bias toward simpler models. Using a controlled synthetic environment and real-world benchmarks, we demonstrate that when training data is sparse relative to the complexity of the underlying target function, pruning can systematically decrease predictive accuracy.
Introduction
During the early 1990s, pruning techniques like those found in CART and C4.5 were considered essential for ensuring the generalization of decision trees. The prevailing wisdom suggested that overfitting was a fundamental trap to be avoided. Cullen Schaffer challenges this dogma, positing that overfitting avoidance is not a statistical requirement but a specific bias—a preference for simpler models. This bias is only beneficial if it aligns with the domain's characteristics. This study specifically investigates the "sparse data" problem: the performance of pruning when training examples are few or the underlying relationship is highly complex.
Methods
The study compares two primary induction strategies:
- Cross-Validated Pruning (CV): A cost-complexity pruning method using 10-fold cross-validation to determine optimal tree size.
- No Pruning (NP): A strategy that grows the tree until it perfectly fits the training data.
To systematically explore the interaction between data abundance and model complexity, a Poisson Generator was employed. This tool creates a 1D environment where classes alternate along a line, with the number of boundaries (cutpoints) determined by a Poisson process with parameter $\lambda$.
By varying the number of training instances ($n$), the complexity ($\lambda$), and the classification noise ($e$), the author mapped the regions where each strategy excels. Validation was also performed on several UCI datasets, including Heart Disease, Letter Recognition, and Mushroom data.
Results and Key Insights
The core finding is that the effectiveness of pruning depends heavily on the "abundance" of data. In scenarios with high sparsity—where the target function is complex but data points are scarce—pruning often "smooths over" genuine patterns, mistaking them for noise.
As shown in the experimental grids, there is a clear "crossover" point. In the upper-right regions of the grids (low $n$, high $\lambda$), the unpruned strategy (NP) consistently outperformed CV. This effect is most pronounced when noise is low. For instance, on the noise-free Mushroom dataset, NP was superior across all tested training set sizes. Pruning only became advantageous once artificial noise was introduced.
Real-world data confirmed these trends. In the Letter Recognition task, unpruned trees were superior even with 1,000 training cases, illustrating that "sparsity" is relative to the complexity of the problem (e.g., the variety of fonts and characters).
Discussion
Schaffer concludes that pruning is an a priori prejudice in favor of smaller trees rather than an inherently superior statistical tool. The justification for pruning is primarily the presence of noise; without it, or when data is sparse, the bias toward simplicity can be harmful.
A significant limitation is the lack of a formal metric to determine exactly when a dataset is "too sparse" for pruning. Furthermore, the training data alone cannot signal its own sparsity; practitioners must rely on external domain knowledge to estimate the complexity of the target relationship before deciding whether to apply overfitting avoidance techniques.
Summary updated