Multiclass core vector machine

ABSTRACT

Even though several techniques have been proposed in the literature for achieving multiclass classification using Support Vector Machine(SVM), the scalability aspect of these approaches to handle large data sets still needs much of exploration. Core Vector Machine(CVM) is a technique for scaling up a two class SVM to handle large data sets. In this paper we propose a Multiclass Core Vector Machine(MCVM). Here we formulate the multiclass SVM problem as a Quadratic Programming(QP) problem defining an SVM with vector valued output. This QP problem is then solved using the CVM technique to achieve scalability to handle large data sets. Experiments done with several large synthetic and real world data sets show that the proposed MCVM technique gives good generalization performance as that of SVM at a much lesser computational expense. Further, it is observed that MCVM scales well with the size of the data set.

REFERENCES

• 1: Fabio Aiolli , Alessandro Sperduti, Multiclass Classification with Multi-Prototype Support Vector Machines, The Journal of Machine Learning Research, 6, p.817-850, 12/1/2005
• 2: Bǎdoiu, M., & Clarkson, K. L. (2002). Optimal core sets for balls. In DIMACS workshop on Computational Geometry.
• 3: Chang, C.-C., & Lin, C.-J. (2001). LIB-SVM: A library for Support Vector Machines. http://www.csie.ntu.edu.tw/~cjlin/libsvm, 2001.
• 4: R. Fletcher, Practical methods of optimization; (2nd ed.), Wiley-Interscience, New York, NY, 1987
• 5: Hsu, C.-W., & Lin, C.-J. (2002). A Comparison of Multiclass Support Vector Machines. IEEE Transactions on Neral Networks, 13, 415--425.
• 6: Piyush Kumar , Joseph S. B. Mitchell , E. Alper Yildirim, Approximate minimum enclosing balls in high dimensions using core-sets, Journal of Experimental Algorithmics (JEA), 8, 2003 [doi>10.1145/996546.996548]
• 7: Bernhard Schölkopf , John C. Platt , John C. Shawe-Taylor , Alex J. Smola , Robert C. Williamson, Estimating the Support of a High-Dimensional Distribution, Neural Computation, v.13 n.7, p.1443-1471, July 2001 [doi>10.1162/089976601750264965]
• 8: Alex J. Smola , Bernhard Schökopf, Sparse Greedy Matrix Approximation for Machine Learning, Proceedings of the Seventeenth International Conference on Machine Learning, p.911-918, June 29-July 02, 2000
• 9: K. P. Soman , R. Loganathan , M. S. Vijaya , V. Ajay , K. Shivsubramani, Fast Single-Shot Multiclass Proximal Support Vector Machines and Perceptions, Proceedings of the International Conference on Computing: Theory and Applications, p.294-298, March 05-07, 2007 [doi>10.1109/ICCTA.2007.60]
• 10: Szedmak, S., & Shawe-Taylor, J. (2005). Multiclass learning at one-class complexity. Technical Report No: 1508, School of Electronics and Computer Science, Southampton, UK.
• 11: 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, 12/1/2005
• 12: Vapnik, V. N. (1998). Statistical learning theory. John Wiley and Sons.
• 13: Weston, J., & Watkins, C. (1999). Support Vector Machines for Multi-class Pattern Recognition. Proceedings of the Seventh European Symposium On Artificial Neural Networks (pp. 219--224). Brussels.