Efficient extension to mixture techniques for prediction and decision trees

Fernando Pereira, Yoram Singer

Research output: Contribution to conferencePaper

5 Scopus citations

Abstract

We present a method for maintaining mixtures of prunings of a prediction or decision tree that extends the `node-based' prunings of [Bun90, WST95, HS95] to the larger class of edge-based prunings. The method includes an efficient 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 on-line framework of Freund and Schapire [FS95], 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)
Pages114-121
Number of pages8
DOIs
StatePublished - Jan 1 1997
EventProceedings of the 1997 10th Annual Conference on Computational Learning Theory - Nashville, TN, USA
Duration: Jul 6 1997Jul 9 1997

Other

OtherProceedings of the 1997 10th Annual Conference on Computational Learning Theory
CityNashville, TN, USA
Period7/6/977/9/97

All Science Journal Classification (ASJC) codes

  • Computational Mathematics

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

    Pereira, F., & Singer, Y. (1997). Efficient extension to mixture techniques for prediction and decision trees. 114-121. Paper presented at Proceedings of the 1997 10th Annual Conference on Computational Learning Theory, Nashville, TN, USA, . https://doi.org/10.1145/267460.267487