TY - JOUR
T1 - Efficient extension to mixture techniques for prediction and decision trees
AU - Pereira, Fernando C.
AU - Singer, Yoram
PY - 1999
Y1 - 1999
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0032595782&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0032595782&partnerID=8YFLogxK
U2 - 10.1023/A:1007670818503
DO - 10.1023/A:1007670818503
M3 - Article
AN - SCOPUS:0032595782
SN - 0885-6125
VL - 36
SP - 183
EP - 199
JO - Machine Learning
JF - Machine Learning
IS - 3
ER -