A Minmax Chebyshev Approach to Optimal Binary Classification
About this article
Abstract
Linear programming (LP) techniques for optimal binary classification have inspired research studies in recent years; they pose an alternative to the quadratic programming (QP) approach, which is usually credited with having greater complexity. In this paper, we describe an LP approach that is based on the minmax Chebyshev criterion, for which we demonstrate that it can determine an optimal solution with competitive properties. The approach is then extended so that two of the most attractive properties of the traditional QP approach (the direct formulation of the optimal classifier in higher dimensions and the sparseness of its coefficients) are preserved. The proposed method demonstrates its capabilities to successfully address situations that have separable and inseparable classes.
References
[1] B.E. Boser, I.M.Guyon, V.Vapnik, A training algorithm for optimal margin classifiers, Proceedings Fifth ACM Workshop on Computational Learning Theory, Pittsburgh, 1992
[2] N. Cristianini, J. Shawe-Taylor, An Introduction to Support Vector Machines, Cambridge University Press, 2000
[3] S. Abe, Support Vector Machines for Pattern Classification, Springer-Verlag London, 2005
[4] C.J.C. Burges, A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, 2, 121–167 (1998)
[5] W. Zhou, L. Zhang, L. Jiao, Linear programming support vector machines, Pattern Recognition, 35(12):2927-36, 2002
View more references (11)
[6] V. Kecman, T. Arthanari, I. Hadzic, LP and QP based learning from empirical data, Proceedings of International Joint Conference on Neural Networks (IJCNN), Como, Italy, 2000
[7] M.C. Ferris, O.L. Mangasarian, S.J. Wright, Linear Programming with MATLAB, MPS-SIAM Series on Optimization, 2007
[8] R.O. Duda, P.E. Hart, D.G. Stork, Pattern Classification, 2nd ed., Wiley Interscience, 2000; freely available at: http://neuron.tuke.sk/hudecm/helps/NN/DUDA_HART_STORK/
[9] D.G. Luenberger, Linear and Nonlinear Programming, Addison-Wesley Publishing Company, 2nd ed., 1984
[10] G.B. Dantzig, M.N. Thapa, Linear Programming, vol.1: Introduction, Springer series in operations research, 1997
[11] G. Ratsch, T. Onoda, K-R. Muller, Soft Margins for AdaBoost, NeuroCOLT2 Technical Report Series, NC-TR-1998-021, 1998
[12] Chih-Chung Chang, Chih-Jen Lin, LIBSVM : a library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2:27:1--27:27, 2011
[13] Chih-Wei Hsu, Chih-Chung Chang, Chih-Jen Lin, A practical guide to Support Vector Classification, http://www.csie.ntu.edu.tw/~cjlin/papers/guide/guide.pdf, 2010
[14] T. Joachims, Making large-Scale SVM Learning Practical. Advances in Kernel Methods - Support Vector Learning, B. Schölkopf, C. Burges and A. Smola (Eds.), MIT Press, 1999.
[15] P. Drineas, M.W. Mahoney, Approximating a Gram Matrix for Improved Kernel-Based Learning, COLT 2005, P. Auer and R. Meir (Eds.), pp. 323-337, Springer-Verlag 2005
[16] Hsuan-Tien Lin, Chih-Jen Lin, A Study on Sigmoid Kernels for SVM and the Training of non-PSD Kernels by SMO-type Methods, Department of Computer Science and Information Engineering, National Taiwan University; available on-line: www.csie.ntu.edu.tw/~cjlin/papers/tanh.pdf