An efficient extension to mixture techniques for prediction and decision trees
Fernando M. B. Pereira, Yoram Singer · 1997
We present a method for maintaining mixtures of prunings of a prediction or decision tree that extends the "node-based" prunings of (BunSO, 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 edgebased 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.kmlission to make digital/hard copies ofnll or pan ofthin material tjr pefWNd Or ChlSSmOnl Use is granted without I& provided that the cop& are not made or dktrihukd for profit or commercial advantage, the copy.right notice, the title oflhe puhlicnrion and its date appear, nod notice is given that copyright is by pemkGon of the AChI.Inc.To copy otherwise, to republish.10 poti on servers or IO redistribute to lists.requires specific pemlissioo .uidlorfee COLT 97 Nashville, Tennesee.