Learning a two-stage SVM/CRF sequence classifier

ABSTRACT

Learning a sequence classifier means learning to predict a sequence of output tags based on a set of input data items. For example, recognizing that a handwritten word is "cat", based on three images of handwritten letters and on general knowledge of English letter combinations, is a sequence classification task. This paper describes a new two-stage approach to learning a sequence classifier that is (i) highly accurate, (ii) scalable, and (iii) easy to use in data mining applications. The two-stage approach combines support vector machines (SVMs) and conditional random fields (CRFs). It is (i) highly accurate because it benefits from the maximum-margin nature of SVMs and also from the ability of CRFs to model correlations between neighboring output tags. It is (ii) scalable because the input to each SVM is a small training set, and the input to the CRF has a small number of features, namely the SVM outputs. It is (iii) easy to use because it combines existing published software in a straightforward way. In detailed experiments on the task of recognizing handwritten words, we show that the two-stage approach is more accurate, or faster and more scalable, or both, than leading other methods for learning sequence classifiers, including max-margin Markov networks (M3Ns) and standard CRFs.

REFERENCES

• 1: L. Bottou. CRFSGD software, 2008. Available at http://leon.bottou.org/projects/sgd.
• 2: Christopher J. C. Burges, A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, v.2 n.2, p.121-167, June 1998 [doi>10.1023/A:1009715923555]
• 3: C.-C. Chang and C.-J. Lin. LIBSVM: a library for support vector machines, 2007. Available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.
• 4: Koby Crammer , Yoram Singer, On the algorithmic implementation of multiclass kernel-based vector machines, The Journal of Machine Learning Research, 2, 3/1/2002
• 5: Vojtěch Franc , Bogdan Savchynskyy, Discriminative Learning of Max-Sum Classifiers, The Journal of Machine Learning Research, 9, p.67-104, 6/1/2008
• 6: Tommi Jaakkola , Mark Diekhans , David Haussler, Using the Fisher Kernel Method to Detect Remote Protein Homologies, Proceedings of the Seventh International Conference on Intelligent Systems for Molecular Biology, p.149-158, August 06-10, 1999
• 7: T. Joachims. SVM^light Support Vector Machine, 2004. Available at http://svmlight.joachims.org.
• 8: T. Joachims. SVM-hmm sequence tagging with structural support vector machines, 2008. Version 3.03 available at http://www.cs.cornell.edu/People-/tj/svm_light/svm_hmm.html.
• 9: Robert Howard Kassel, A comparison of approaches to on-line handwritten character recognition, Massachusetts Institute of Technology, Cambridge, MA, 1996
• 10: S. S. Keerthi and S. Sundararajan. CRF versus SVM-Struct for sequence labeling. Technical report, Yahoo Research, 2007.
• 11: John D. Lafferty , Andrew McCallum , Fernando C. N. Pereira, Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data, Proceedings of the Eighteenth International Conference on Machine Learning, p.282-289, June 28-July 01, 2001
• 12: L. Liao and W. S. Noble. Combining pairwise sequence similarity and support vector machines for detecting remote protein evolutionary and structural relationships. Journal of Computational Biology, 10(6):857--868, 2003.
• 13: Nam Nguyen , Yunsong Guo, Comparisons of sequence labeling algorithms and extensions, Proceedings of the 24th international conference on Machine learning, p.681-688, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273582]
• 14: J. Nocedal and S. J. Wright. Limited memory BFGS. In Numerical Optimization, pages 222--247. Springer, 1999.
• 15: F. Perez-Cruz, Z. Ghahramani, and M. Pontil. Conditional graphical models. In Predicting Structured Data, pages 265--282. MIT Press, Cambridge, MA, USA, 2006.
• 16: B. Taskar, C. Guestrin, and D. Koller. Max-margin Markov networks. In S. Thrun, L. K. Saul, and B. Schölkopf, editors, NIPS. MIT Press, 2003.
• 17: Ben Taskar , Simon Lacoste-Julien , Michael I. Jordan, Structured Prediction, Dual Extragradient and Bregman Projections, The Journal of Machine Learning Research, 7, p.1627-1653, 12/1/2006
• 18: Ioannis Tsochantaridis , Thorsten Joachims , Thomas Hofmann , Yasemin Altun, Large Margin Methods for Structured and Interdependent Output Variables, The Journal of Machine Learning Research, 6, p.1453-1484, 12/1/2005
• 19: S. V. N. Vishwanathan , Nicol N. Schraudolph , Mark W. Schmidt , Kevin P. Murphy, Accelerated training of conditional random fields with stochastic gradient methods, Proceedings of the 23rd international conference on Machine learning, p.969-976, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143966]
• 20: R. Yan. MATLABArsenal: A Matlab package for classification algorithms, 2006. Carnegie Mellon University, School of Computer Science.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms

Keywords:
conditional random fields, sequence learning, support vector machines