Efficient extension to mixture techniques for prediction and decision trees

Fernando C. Pereira, Yoram Singer

Research output: Contribution to journalArticlepeer-review

22 Scopus citations


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
Issue number3
StatePublished - 1999

All Science Journal Classification (ASJC) codes

  • Software
  • Artificial Intelligence


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

Cite this