Training linear SVMs in linear time

ABSTRACT

Linear Support Vector Machines (SVMs) have become one of the most prominent machine learning techniques for high-dimensional sparse data commonly encountered in applications like text classification, word-sense disambiguation, and drug design. These applications involve a large number of examples n as well as a large number of features N, while each example has only s << N non-zero features. This paper presents a Cutting Plane Algorithm for training linear SVMs that provably has training time 0(s,n) for classification problems and o(sn log (n))for ordinal regression problems. The algorithm is based on an alternative, but equivalent formulation of the SVM optimization problem. Empirically, the Cutting-Plane Algorithm is several orders of magnitude faster than decomposition methods like svm light for large datasets.

REFERENCES

• 1: Rich Caruana , Thorsten Joachims , Lars Backstrom, KDD-Cup 2004: results and analysis, ACM SIGKDD Explorations Newsletter, v.6 n.2, December 2004 [doi>10.1145/1046456.1046470]
• 2: C.-C. Chang and C.-J. Lin. LIBSVM: a library for support vector machines, 2001. Software available at http://www.csie.ntu.edu.tw/ cjlin/libsvm.
• 3: Ronan Collobert , Samy Bengio, SVMTorch: support vector machines for large-scale regression problems, The Journal of Machine Learning Research, 1, p.143-160, 9/1/2001 [doi>10.1162/15324430152733142]
• 4: J. Díez, J. del Coz, and A. Bahamonde. A support vector method for ranking minimizing the number of swapped pairs. Technical report, Artificial Intelligence Centre, Universidad de Oviedo at Gijón, 2006.
• 5: Susan Dumais , John Platt , David Heckerman , Mehran Sahami, Inductive learning algorithms and representations for text categorization, Proceedings of the seventh international conference on Information and knowledge management, p.148-155, November 02-07, 1998, Bethesda, Maryland, United States [doi>10.1145/288627.288651]
• 6: Michael C. Ferris , Todd S. Munson, Interior-Point Methods for Massive Support Vector Machines, SIAM Journal on Optimization, v.13 n.3, p.783-804, 2002 [doi>10.1137/S1052623400374379]
• 7: Glenn Fung , Olvi L. Mangasarian, Proximal support vector machine classifiers, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.77-86, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502527]
• 8: R. Herbrich, T. Graepel, and K. Obermayer. Large margin rank boundaries for ordinal regression. In Advances in Large Margin Classifiers, pages 115--132. MIT Press, Cambridge, MA, 2000.
• 9: Don Hush , Clint Scovel, Polynomial-Time Decomposition Algorithms for Support Vector Machines, Machine Learning, v.51 n.1, p.51-71, April 2003 [doi>10.1023/A:1021877911972]
• 10: Thorsten Joachims, Text Categorization with Suport Vector Machines: Learning with Many Relevant Features, Proceedings of the 10th European Conference on Machine Learning, p.137-142, April 21-23, 1998
• 11: Thorsten Joachims, Making large-scale support vector machine learning practical, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 12: Thorsten Joachims, Optimizing search engines using clickthrough data, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775067]
• 13: T. Joachims. Learning to align sequences: A maximum-margin approach. online manuscript, August 2003.
• 14: Thorsten Joachims, A support vector method for multivariate performance measures, Proceedings of the 22nd international conference on Machine learning, p.377-384, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102399]
• 15: 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, 9/1/2005
• 16: J. Kelley. The cutting-plane method for solving convex programs. Journal of the Society for Industrial Applied Mathematics, 8:703--712, 1960.
• 17: 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
• 18: O. L. Mangasarian , David R. Musicant, Lagrangian support vector machines, The Journal of Machine Learning Research, 1, p.161-177, 9/1/2001 [doi>10.1162/15324430152748218]
• 19: John C. Platt, Fast training of support vector machines using sequential minimal optimization, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 20: A. Rakotomamonjy. Svms and area under roc curve. Technical report, PSI-INSA de Rouen, 2004.
• 21: B. Schölkopf and A. J. Smola. Learning with Kernels. The MIT Press, Cambridge, MA, 2002.
• 22: Bernhard Schölkopf , Alex J. Smola , Robert C. Williamson , Peter L. Bartlett, New Support Vector Algorithms, Neural Computation, v.12 n.5, p.1207-1245, May 2000 [doi>10.1162/089976600300015565]
• 23: Ivor W. Tsang , James T. Kwok , Pak-Ming Cheung, Core Vector Machines: Fast SVM Training on Very Large Data Sets, The Journal of Machine Learning Research, 6, p.363-392, 9/1/2005
• 24: 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, 9/1/2005

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
ROC-area, large-scale problems, ordinal regression, support vector machines (SVM), training algorithms