Learning prediction suffix trees with Winnow

ABSTRACT

Prediction suffix trees (PSTs) are a popular tool for modeling sequences and have been successfully applied in many domains such as compression and language modeling. In this work we adapt the well studied Winnow algorithm to the task of learning PSTs. The proposed algorithm automatically grows the tree, so that it provably remains competitive with any fixed PST determined in hindsight. At the same time we prove that the depth of the tree grows only logarithmically with the number of mistakes made by the algorithm. Finally, we empirically demonstrate its effectiveness in two different tasks.

REFERENCES

• 1: Avrim Blum, Empirical Support for Winnow and Weighted-MajorityAlgorithms: Results on a Calendar Scheduling Domain, Machine Learning, v.26 n.1, p.5-23, Jan. 1997 [doi>10.1023/A:1007335615132]
• 2: Buhlmann, P., & Wyner, A. (1999). Variable length Markov chains. Annals of Statistics, 27, 480--513.
• 3: Koby Crammer , Yoram Singer, On the algorithmic implementation of multiclass kernel-based vector machines, The Journal of Machine Learning Research, 2, 3/1/2002
• 4: Dekel, O., Shalev-Shwartz, S., & Singer, Y. (2004). The power of selective memory: Self-bounded learning of prediction suffix trees. Neural Information Processing Systems, 17, 345--352.
• 5: David P. Helmbold , Robert E. Schapire, Predicting Nearly As Well As the Best Pruning of a Decision Tree, Machine Learning, v.27 n.1, p.51-68, April 1997 [doi>10.1023/A:1007396710653]
• 6: Michael J. Kearns , Yishay Mansour, A Fast, Bottom-Up Decision Tree Pruning Algorithm with Near-Optimal Generalization, Proceedings of the Fifteenth International Conference on Machine Learning, p.269-277, July 24-27, 1998
• 7: Jyrki Kivinen , Manfred K. Warmuth, Exponentiated gradient versus gradient descent for linear predictors, Information and Computation, v.132 n.1, p.1-63, Jan. 10, 1997 [doi>10.1006/inco.1996.2612]
• 8: N. Littlestone, Mistake bounds and logarithmic linear-threshold learning algorithms, University of California at Santa Cruz, Santa Cruz, CA, 1990
• 9: Marden, M. (1966). Geometry of Polynomials. AMS.
• 10: Fernando C. Pereira , Yoram Singer, An Efficient Extension to Mixture Techniques for Prediction and Decision Trees, Machine Learning, v.36 n.3, p.183-199, Sept. 1999 [doi>10.1023/A:1007670818503]
• 11: Dana Ron , Yoram Singer , Naftali Tishby, The power of amnesia: learning probabilistic automata with variable memory length, Machine Learning, v.25 n.2-3, p.117-149, Nov./Dec. 1996 [doi>10.1007/BF00114008]
• 12: Rosenblatt, F. (1958). The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review, 65, 386--408.
• 13: Shalev-Shwartz, S. (2007). Online learning: Theory, algorithms, and applications. Doctoral dissertation, The Hebrew University of Jerusalem.
• 14: Willems, F., Shtarkov, Y., & Tjalkens, T. (1995). The context-tree weighting method: basic properties. IEEE Transactions on Information Theory, 41, 653--664.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory