Toward a Theoretical Understanding of Why and When Decision Tree Pruning Algorithms Fail

Tim Oates, David D. JensenAAAI 1999 · OpenReview

Abstract

Recent empirical studies revealed two surprising pathologies of several common decision tree pruning algorithms. First, tree size is often a linear function of training set size, even when additional tree structure yields no increase in accuracy. Second, building trees with data in which the class label and the attributes are independent often results in large trees. In both cases, the pruning algorithms fail to control tree growth as one would expect them to. We explore this behavior theoretically by constructing a statistical model of reduced error pruning. The model explains why and when the pathologies occur, and makes predictions about how to lessen their effects. The predictions are operationalized in a variant of reduced error pruning that is shown to control tree growth far better than the original algorithm.

Introduction: The Pathology of Uncontrolled Tree Growth

In machine learning, pruning is intended to act as a "sanity check," trimming branches that capture noise rather than real patterns. However, empirical evidence has identified a persistent pathology: as training data increases, pruned trees often continue to grow linearly in size, even when accuracy remains stagnant. In extreme cases—such as datasets where attributes and labels are entirely independent (pure noise)—standard algorithms like Reduced Error Pruning (REP), Error-Based Pruning (EBP), and Minimum Description Length (MDL) fail to produce the expected single-node leaf, instead generating massive, complex structures.

Observed linear growth of tree size relative to training set size for MDL, EBP, and REP pruning algorithms on random data.

This paper bridges the gap between these empirical observations and theory by constructing a statistical model of the pruning process to understand why these algorithms "leak" excess structure.

Modeling the Pruning Decision

The analysis focuses on Reduced Error Pruning (REP) due to its algorithmic simplicity. In standard REP, a tree is built on a training set and then trimmed using a separate pruning set. For any internal node, the algorithm compares the number of errors the subtree makes on the pruning set ($r_T$) against the errors a single leaf would make ($r_L$). If $r_T \geq r_L$, the subtree is pruned.

Statistical model of the pruning decision, comparing subtree errors (centered at $\mu_T$) against leaf errors ($r_L$).

By treating these error counts as random variables, the authors model the pruning decision as a Bernoulli trial. This reveals a critical "pruning trap": while the probability of pruning a node is initially high, the act of pruning its children changes the statistical properties of the remaining subtree. Once children are pruned, the subtree's error rate becomes statistically identical to the leaf's error rate, turning the subsequent pruning decision into a coin flip or worse. This explains why a fixed percentage of "noise" branches will always pass the pruning test by sheer statistical chance, leading to linear growth.

Breaking Dependencies with Independent Pruning

The failure of pruning is not due to a lack of data, but a lack of independent data. Reusing the same pruning set for every node in the tree introduces statistical dependencies that allow noise to bypass the pruning phase. To address this, the authors propose a variant of REP where each pruning decision is made using a fresh, independent sample of data (or a randomly sampled subset). This ensures that the noise captured during the tree-growing phase does not systematically bias the pruning phase.

Experimental Results

The authors validated their model and the new sampling-based algorithm using both artificial noise datasets and 19 real-world benchmarks from the UCI repository.

  • Controlling Noise: On the structureless "rand" dataset (pure noise), standard REP produced trees with hundreds of nodes. The independent-sampling variant correctly reduced the tree to a single node.
  • Efficiency on Real Data: In 16 out of 19 real-world cases, the sampling-based variant (using 50% subsets) produced significantly smaller trees.
  • Accuracy Preservation: In 18 of those 19 cases, there was no significant loss in accuracy, confirming that the pruned structure was indeed redundant noise. The only exception was the tic-tac-toe dataset, which is noise-free and requires complex structure to represent its parity-like rules.

Conclusion

The linear growth of decision trees on noisy data is a fundamental consequence of how standard pruning algorithms handle statistical dependencies. By introducing independence through data sampling, it is possible to maintain the accuracy of decision trees while drastically reducing their complexity. Future work will involve generalizing this statistical model to other methods like EBP and MDL and exploring more data-efficient ways to maintain independence in small-sample scenarios.

Summary updated

Abstract

Recent empirical studies revealed two surprising pathologies of several common decision tree pruning algorithms. First, tree size is often a linear function of training set size, even when additional tree structure yields no increase in accuracy. Second, building trees with data in which the class label and the attributes are independent often results in large trees. In both cases, the pruning algorithms fail to control tree growth as one would expect them to. We explore thiS behavior theoretically by constructing a statistical model of reduced error pruning. The model explains why and when the pathologies occur, and makes predictions about how to lessen their effects. The predictions are operationalized in a variant of reduced error pruning that is shown to control tree growth far better than the original algorithm.
BibTeX
@inproceedings{oates1999toward,
  author = {Tim Oates and David D. Jensen},
  title = {{Toward a Theoretical Understanding of Why and When Decision Tree Pruning Algorithms Fail}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
  url = {https://openreview.net/forum?id=HkN1jAldbH},
}
Figure