On updates that constrain the features' connections during learning

ABSTRACT

In many multiclass learning scenarios, the number of classes is relatively large (thousands,...), or the space and time efficiency of the learning system can be crucial. We investigate two online update techniques especially suited to such problems. These updates share a sparsity preservation capacity: they allow for constraining the number of prediction connections that each feature can make. We show that one method, exponential moving average, is solving a "discrete" regression problem for each feature, changing the weights in the direction of minimizing the quadratic loss. We design the other method to improve a hinge loss subject to constraints, for better accuracy. We empirically explore the methods, and compare performance to previous indexing techniques, developed with the same goals, as well as other online algorithms based on prototype learning. We observe that while the classification accuracies are very promising, improving over previous indexing techniques, the scalability benefits are preserved.

REFERENCES

• 1: Koby Crammer , Ofer Dekel , Joseph Keshet , Shai Shalev-Shwartz , Yoram Singer, Online Passive-Aggressive Algorithms, The Journal of Machine Learning Research, 7, p.551-585, 12/1/2006
• 2: Koby Crammer , Yoram Singer, A family of additive online algorithms for category ranking, The Journal of Machine Learning Research, 3, 3/1/2003
• 3: B. D. Davison and H. Hirsh. Predicting sequences of user actions. In AAAI-98/ICML'98 Workshop on Predicting the Future: AI Approaches to Time Series Analysis, 1998.
• 4: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 5: Susan Dumais , Hao Chen, Hierarchical classification of Web content, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.256-263, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345593]
• 6: B. S. Everitt. Cambridge Dictionary of Statistics. Cambridge University Press, 2nd edition edition, 2003.
• 7: D. A. Forsyth and J. Ponce. Computer Vision. Prentice Hall, 2003.
• 8: D. A. Forsyth and J. Ponce. Computer Vision. Prentice Hall, 2003.
• 9: C. Genest and J. V. Zidek. Combining probability distributions: A critique and an annotated bibliography. Statistical Science, 1(1):114--148, 1986.
• 10: T. Hastie, R. Tibshirani, and J. Friedman. The Elements of Statistical Learning. Springer-Verlag, 2001.
• 11: S. Sathiya Keerthi , Dennis DeCoste, A Modified Finite Newton Method for Fast Solution of Large Scale Linear SVMs, The Journal of Machine Learning Research, 6, p.341-361, 12/1/2005
• 12: 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]
• 13: Benjamin Korvemaker , Russell Greiner, Predicting UNIX Command Lines: Adjusting to User Patterns, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.230-235, July 30-August 03, 2000
• 14: K. Lang. Newsweeder: Learning to filter netnews. In Proceedings of the Twelfth International Conference on Machine Learning, pages 331--339, 1995.
• 15: David D. Lewis , Yiming Yang , Tony G. Rose , Fan Li, RCV1: A New Benchmark Collection for Text Categorization Research, The Journal of Machine Learning Research, 5, p.361-397, 12/1/2004
• 16: Tie-Yan Liu , Yiming Yang , Hao Wan , Hua-Jun Zeng , Zheng Chen , Wei-Ying Ma, Support vector machines classification with a very large-scale taxonomy, ACM SIGKDD Explorations Newsletter, v.7 n.1, p.36-43, June 2005 [doi>10.1145/1089815.1089821]
• 17: O. Madani. Exploring massive learning via a prediction system. In AAAI Fall Symposium Series: Computational Approaches to Representation Change During Learning and Development, 2007.
• 18: O. Madani and M. Connor. Large-scale many-class learning. In SIAM Conference on Data Mining (SDM), 2008.
• 19: O. Madani, W. Greiner, D. Kempe, and M. Salavatipour. Recall systems: Efficient learning and use of category indices. In AISTATS, 2007.
• 20: O. Madani and J. Huang. On updates that constrain the features? connections during learning. Technical report, SRI International, AI Center, 2008. In preparation.
• 21: C. Mesterharm. A multi-class linear learning algorithm related to Winnow. In NIPS, 2000.
• 22: J. Rennie, L. Shih, J. Teevan, and D. Karger. Tackling the poor assumption of Naive Bayes text classifiers. In ICML, 2003.
• 23: Ryan Rifkin , Aldebaro Klautau, In Defense of One-Vs-All Classification, The Journal of Machine Learning Research, 5, p.101-141, 12/1/2004
• 24: R. Rosenfeld. Two decades of statistical language modeling: Where do we go from here? IEEE, 88(8), 2000.
• 25: Fabrizio Sebastiani, Machine learning in automated text categorization, ACM Computing Surveys (CSUR), v.34 n.1, p.1-47, March 2002 [doi>10.1145/505282.505283]
• 26: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Connectionism and neural nets

General Terms:
Algorithms, Performance, Theory

Keywords:
index learning, many-class learning, multiclass learning, online learning, text categorization