On the algorithmic implementation of multiclass kernel-based vector machines

ABSTRACT

In this paper we describe the algorithmic implementation of multiclass kernel-based vector machines. Our starting point is a generalized notion of the margin to multiclass problems. Using this notion we cast multiclass categorization problems as a constrained optimization problem with a quadratic objective function. Unlike most of previous approaches which typically decompose a multiclass problem into multiple independent binary classification tasks, our notion of margin yields a direct method for training multiclass predictors. By using the dual of the optimization problem we are able to incorporate kernels with a compact set of constraints and decompose the dual problem into multiple optimization problems of reduced size. We describe an efficient fixed-point algorithm for solving the reduced optimization problems and prove its convergence. We then discuss technical details that yield significant running time improvements for large datasets. Finally, we describe various experiments with our approach comparing it to previously studied kernel-based methods. Our experiments indicate that for multiclass problems we attain state-of-the-art accuracy.

REFERENCES

• 1: Erin L. Allwein , Robert E. Schapire , Yoram Singer, Reducing Multiclass to Binary: A Unifying Approach for Margin Classifiers, Proceedings of the Seventeenth International Conference on Machine Learning, p.9-16, June 29-July 02, 2000
• 2: Bernhard E. Boser , Isabelle M. Guyon , Vladimir N. Vapnik, A training algorithm for optimal margin classifiers, Proceedings of the fifth annual workshop on Computational learning theory, p.144-152, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130401]
• 3: Erin J. Bredensteiner , Kristin P. Bennett, Multicategory Classification by Support Vector Machines, Computational Optimization and Applications, v.12 n.1-3, p.53-79, Jan. 1999 [doi>10.1023/A:1008663629662]
• 4: L. M. Bregman. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Computational Mathematics and Mathematical Physics, 7: 200-217, 1967.
• 5: Leo Breiman, Jerome H. Friedman, Richard A. Olshen, and Charles J. Stone. Classification and Regression Trees. Wadsworth & Brooks, 1984.
• 6: 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]
• 7: Yair Al Censor , Stavros A. Zenios, Parallel Optimization: Theory, Algorithms and Applications, Oxford University Press, 1997
• 8: 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]
• 9: Corinna Cortes , Vladimir Vapnik, Support-Vector Networks, Machine Learning, v.20 n.3, p.273-297, Sept. 1995 [doi>10.1023/A:1022627411411]
• 10: Koby Crammer , Yoram Singer, On the Learnability and Design of Output Codes for Multiclass Problems, Proceedings of the Thirteenth Annual Conference on Computational Learning Theory, p.35-46, June 28-July 01, 2000
• 11: Koby Crammer , Yoram Singer, Ultraconservative Online Algorithms for Multiclass Problems, Proceedings of the 14th Annual Conference on Computational Learning Theory and and 5th European Conference on Computational Learning Theory, p.99-115, July 16-19, 2001
• 12: Nello Cristianini , John Shawe-Taylor, An introduction to support Vector Machines: and other kernel-based learning methods, Cambridge University Press, New York, NY, 1999
• 13: Dennis Decoste , Bernhard Schölkopf, Training Invariant Support Vector Machines, Machine Learning, v.46 n.1-3, p.161-190, 2002 [doi>10.1023/A:1012454411458]
• 14: Thomas G. Dietterich, An Experimental Comparison of Three Methods for Constructing Ensembles of Decision Trees: Bagging, Boosting, and Randomization, Machine Learning, v.40 n.2, p.139-157, Aug. 2000 [doi>10.1023/A:1007607513941]
• 15: Thomas G. Dietterich and Ghulum Bakiri. Solving multiclass learning problems via error-correcting output codes. Journal of Artificial Intelligence Research, 2: 263-286, January 1995.
• 16: Yoav Freund , Robert E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Journal of Computer and System Sciences, v.55 n.1, p.119-139, Aug. 1997 [doi>10.1006/jcss.1997.1504]
• 17: André Elisseeff , Hélène Paugam-Moisy, A New Multi-Class SVM Based on a Uniform Convergence Result, Proceedings of the IEEE-INNS-ENNS International Joint Conference on Neural Networks (IJCNN'00)-Volume 4, p.4183, July 24-27, 2000
• 18: Klaus-Uwe Höffgen , Hans Ulrich Simon, Robust trainability of single neurons, Proceedings of the fifth annual workshop on Computational learning theory, p.428-439, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130431]
• 19: Thorsten Joachims. Making large-scale support vector machine learning practical. In B. Schölkopf, C. Burges, and A. Smola, editors, Advances in Kernel Methods - Support Vector Learning. MIT Press, 1998.
• 20: S.S. Keerthi and E.G. Gilbert. Convergence of a generalized smo algorithm for svm classifier design. Technical Report CD-00-01, Control Division Dept. of Mechanical and Production Engineering National University of Singapore, 2000.
• 21: C.-J. Lin. Stopping criteria of decomposition methods for support vector machines: a theoretical justification. Technical report, Depratment of Computer Science and Information Engineering, National Taiwan University, May 2001.
• 22: 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
• 23: J.C. Platt, N. Cristianini, and J. Shawe-Taylor. Large margin DAGs for multiclass classification. In Advances in Neural Information Processing Systems 12, pages 547-553. MIT Press, 2000.
• 24: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 25: Robert E. Schapire , Yoram Singer, Improved Boosting Algorithms Using Confidence-rated Predictions, Machine Learning, v.37 n.3, p.297-336, Dec. 1999 [doi>10.1023/A:1007614523901]
• 26: B. Schölkopf. Support Vector Learning. PhD thesis, GMD First, 1997.
• 27: Bernhard Schölkopf , Christopher J. C. Burges , Alexander J. Smola, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 28: B. Schoelkopf , K. Sung , C. Burges , F. Girosi , P. Niyogi , T. Poggio , V. Vapnik, Comparing Support Vector Machines with Gaussian Kernels to Radial Basis Function Classifiers, Massachusetts Institute of Technology, Cambridge, MA, 1996
• 29: Vladimir N. Vapnik. Statistical Learning Theory. Wiley, 1998.
• 30: J. Weston and C. Watkins. Support vector machines for multi-class pattern recognition. In Proceedings of the Seventh European Symposium on Artificial Neural Networks, April 1999.