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

Proceedings of the AAAI Conference on Artificial Intelligence, 16

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 16

Learning

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 (Oates and Jensen 1997). Second, building trees with data in which the class label and the attributes are independent often results in large trees (Oates and Jensen 1998. 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 (Quinlan 1987). 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. Finally, we argue that several other common pruning techniques can be viewed within the same framework, thus explaining their pathological behavior as well.