Predicting Nearly As Well As the Best Pruning of a Decision Tree

David P. Helmbold, Robert E. Schapire

Research output: Contribution to journalArticle

79 Scopus citations

Abstract

Many algorithms for inferring a decision tree from data involve a two-phase process: First, a very large decision tree is grown which typically ends up "over-fitting" the data. To reduce over-fitting, in the second phase, the tree is pruned using one of a number of available methods. The final tree is then output and used for classification on test data. In this paper, we suggest an alternative approach to the pruning phase. Using a given unpruned decision tree, we present a new method of making predictions on test data, and we prove that our algorithm's performance will not be "much worse" (in a precise technical sense) than the predictions made by the best reasonably small pruning of the given decision tree. Thus, our procedure is guaranteed to be competitive (in terms of the quality of its predictions) with any pruning algorithm. We prove that our procedure is very efficient and highly robust. Our method can be viewed as a synthesis of two previously studied techniques. First, we apply Cesa-Bianchi et al.'s (1993) results on predicting using "expert advice" (where we view each pruning as an "expert") to obtain an algorithm that has provably low prediction loss, but that is computationally infeasible. Next, we generalize and apply a method developed by Buntine (1990, 1992) and Willems, Shtarkov and Tjalkens (1993, 1995) to derive a very efficient implementation of this procedure.

Original languageEnglish (US)
Pages (from-to)51-68
Number of pages18
JournalMachine Learning
Volume27
Issue number1
DOIs
StatePublished - Jan 1 1997
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Artificial Intelligence

Keywords

  • Decision trees
  • On-line learning
  • Prediction
  • Pruning

Fingerprint Dive into the research topics of 'Predicting Nearly As Well As the Best Pruning of a Decision Tree'. Together they form a unique fingerprint.

  • Cite this