Efficient extension to mixture techniques for prediction and decision trees

Fernando C. Pereira, Yoram Singer

Research output: Contribution to journalArticle

19 Scopus citations

Abstract

We present an efficient method for maintaining mixtures of prunings of a prediction or decision tree that extends the previous methods for `node-based' prunings to the larger class of edge-based prunings. The method includes an online weight-allocation algorithm that can be used for prediction, compression and classification. Although the set of edge-based prunings of a given tree is much larger than that of node-based prunings, our algorithm has similar space and time complexity to that of previous mixture algorithms for trees. Using the general online framework of Freund and Schapire (1997), we prove that our algorithm maintains correctly the mixture weights for edge-based prunings with any bounded loss function. We also give a similar algorithm for the logarithmic loss function with a corresponding weight-allocation algorithm. Finally, we describe experiments comparing node-based and edge-based mixture models for estimating the probability of the next word in English text, which show the advantages of edge-based models.

Original languageEnglish (US)
Pages (from-to)183-199
Number of pages17
JournalMachine Learning
Volume36
Issue number3
DOIs
StatePublished - Jan 1 1999
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Efficient extension to mixture techniques for prediction and decision trees'. Together they form a unique fingerprint.

  • Cite this