Adapting two-class support vector classification methods to many class problems

ABSTRACT

A geometric construction is presented which is shown to be an effective tool for understanding and implementing multi-category support vector classification. It is demonstrated how this construction can be used to extend many other existing two-class kernel-based classification methodologies in a straightforward way while still preserving attractive properties of individual algorithms. Reducing training times through incorporating the results of pairwise classification is also discussed and experimental results presented.

REFERENCES

• 1: Erin L. Allwein , Robert E. Schapire , Yoram Singer, Reducing multiclass to binary: a unifying approach for margin classifiers, The Journal of Machine Learning Research, 1, p.113-141, 9/1/2001
• 2: Blake, C. L., & Merz, C. J. (1998). UCI repository of machine learning databases. http://www.ics.uci.edu/~mlearn/MLRepository.html.
• 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: Dietterich, T., & Bakiri, G. (1995). Solving multiclass learning problems via error-correcting output codes. Journal of Artificial Intelligence Research, 2, 263--286.
• 5: Fung, G., & Mangasarian, O. L. (2001a). Multicategory proximal support vector machine classifiers (Technical Report 01--06). Data Mining Institute.
• 6: 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]
• 7: Johannes Fürnkranz, Round robin classification, The Journal of Machine Learning Research, 2, p.721-747, 3/1/2002
• 8: Ralf Herbrich , Thore Graepel , Colin Campbell, Bayes point machines, The Journal of Machine Learning Research, 1, p.245-279, 9/1/2001
• 9: Hill, S. I., & Doucet, A. (2005). A framework for kernel-based multi-category classification (Technical Report CUED/F-INFENG/TR.508). University of Engineering, Cambridge University.
• 10: Hsu, C.-W., & Lin, C.-J. (2002a). A comparison of methods for multi-class support vector machines. IEEE Transactions on Neural Networks, 13, 415--425.
• 11: Chih-Wei Hsu , Chih-Jen Lin, A Simple Decomposition Method for Support Vector Machines, Machine Learning, v.46 n.1-3, p.291-314, 2002 [doi>10.1023/A:1012427100071]
• 12: S. S. Keerthi , S. K. Shevade , C. Bhattacharyya , K. R. K. Murthy, Improvements to Platt's SMO Algorithm for SVM Classifier Design, Neural Computation, v.13 n.3, p.637-649, March 2001 [doi>10.1162/089976601300014493]
• 13: Ulrich H.-G. Kreßel, Pairwise classification and support vector machines, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 14: Lee, Y., Lin, Y., & Wahba, G. (2004). Multicategory support vector machines, theory, and application to the classification of microarray data and satellite radiance data. Journal of the American Statistical Association, 99, 659--672.
• 15: O. L. Mangasarian , David R. Musicant, Lagrangian support vector machines, The Journal of Machine Learning Research, 1, p.161-177, 9/1/2001
• 16: Ryan Rifkin , Aldebaro Klautau, In Defense of One-Vs-All Classification, The Journal of Machine Learning Research, 5, p.101-141, 12/1/2004
• 17: Schölkopf, B., & Smola, A. J. (2002). Learning with kernels. MIT Press.
• 18: Tony Van Gestel , Johan A. K. Suykens , Bart Baesens , Stijn Viaene , Jan Vanthienen , Guido Dedene , Bart De Moor , Joos Vandewalle, Benchmarking Least Squares Support Vector Machine Classifiers, Machine Learning, v.54 n.1, p.5-32, January 2004 [doi>10.1023/B:MACH.0000008082.80494.e0]
• 19: T. Van Gestel , J. A. K. Suykens , G. Lanckriet , A. Lambrechts , B. De Moor , J. Vandewalle, Multiclass LS-SVMs: Moderated Outputs and Coding-Decoding Schemes, Neural Processing Letters, v.15 n.1, p.45-58, February 2002 [doi>10.1023/A:1013815310229]
• 20: Vapnik, V. N. (1998). Statistical learning theory. Wiley.
• 21: Weston, J. A. E., & Watkins, C. (1999). Support vector machines for multi-class pattern recognition. Proceedings of the 7th European Symposium On Artificial Neural Networks.