Direct convex relaxations of sparse SVM

ABSTRACT

Although support vector machines (SVMs) for binary classification give rise to a decision rule that only relies on a subset of the training data points (support vectors), it will in general be based on all available features in the input space. We propose two direct, novel convex relaxations of a non-convex sparse SVM formulation that explicitly constrains the cardinality of the vector of feature weights. One relaxation results in a quadratically-constrained quadratic program (QCQP), while the second is based on a semidefinite programming (SDP) relaxation. The QCQP formulation can be interpreted as applying an adaptive soft-threshold on the SVM hyperplane, while the SDP formulation learns a weighted inner-product (i.e. a kernel) that results in a sparse hyperplane. Experimental results show an increase in sparsity while conserving the generalization performance compared to a standard as well as a linear programming SVM.

REFERENCES

• 1: Bennett, K. P., & Mangasarian, O. L. (1992). Robust linear programming discrimination of two linearly inseparable sets. Optim. Methods Softw., 1, 23--34.
• 2: Jinbo Bi , Kristin Bennett , Mark Embrechts , Curt Breneman , Minghu Song, Dimensionality reduction via sparse support vector machines, The Journal of Machine Learning Research, 3, 3/1/2003
• 3: Avrim L. Blum , Pat Langley, Selection of relevant features and examples in machine learning, Artificial Intelligence, v.97 n.1-2, p.245-271, Dec. 1997 [doi>10.1016/S0004-3702(97)00063-5]
• 4: Borchers, B. (1999). CSDP, a C library for semidefinite programming. Optim. Methods Softw., 11, 613--623.
• 5: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 6: Paul S. Bradley , O. L. Mangasarian, Feature Selection via Concave Minimization and Support Vector Machines, Proceedings of the Fifteenth International Conference on Machine Learning, p.82-90, July 24-27, 1998
• 7: Bradley, P. S., & Mangasarian, O. L. (2000). Massive data discrimination via linear support vector machines. Optim. Methods Softw., 13(1), 1--10.
• 8: Chan, A. B., Vasconcelos, N., & Lanckriet, G. R. G. (2007). Duals of the QCQP and SDP sparse SVM (Technical Report SVCL-TR-2007-02). University of California, San Diego. http://www.svcl.ucsd.edu.
• 9: Glenn M. Fung , O. L. Mangasarian, A Feature Selection Newton Method for Support Vector Machine Classification, Computational Optimization and Applications, v.28 n.2, p.185-202, July 2004 [doi>10.1023/B:COAP.0000026884.66338.df]
• 10: Grandvalet, Y., & Canu, S. (2003). Adaptive scaling for feature selection in SVMs. Neural Information Processing Systems.
• 11: L. R. Grate , Chiranjib Bhattacharyya , Michael I. Jordan , I. Saira Mian, Simultaneous Relevant Feature Identification and Classification in High-Dimensional Spaces, Proceedings of the Second International Workshop on Algorithms in Bioinformatics, p.1-9, September 17-21, 2002
• 12: Isabelle Guyon , André Elisseeff, An introduction to variable and feature selection, The Journal of Machine Learning Research, 3, 3/1/2003
• 13: Isabelle Guyon , Jason Weston , Stephen Barnhill , Vladimir Vapnik, Gene Selection for Cancer Classification using Support Vector Machines, Machine Learning, v.46 n.1-3, p.389-422, 2002 [doi>10.1023/A:1012487302797]
• 14: Lemaréchal, C., & Oustry, F. (1999). Semidefinite relaxations and Lagrangian duality with application to combinatorial optimization (Technical Report 3710). INRIA.
• 15: MOSEK (2006). MOSEK optimization software (Technical Report). http://www.mosek.com/.
• 16: Julia Neumann , Christoph Schnörr , Gabriele Steidl, Combined SVM-Based Feature Selection and Classification, Machine Learning, v.61 n.1-3, p.129-150, November 2005 [doi>10.1007/s10994-005-1505-9]
• 17: Newman, D. J., Hettich, S., Blake, C. L., & Merz, C. J. (1998). UCI repository of machine learning databases (Technical Report). http://www.ics.uci.edu/~mlearn.
• 18: Peleg, D., & Meir, R. (2004). A feature selection algorithm based on the global minimization of a generalization error bound. Neural Information Processing Systems.
• 19: Alain Rakotomamonjy, Variable selection using svm based criteria, The Journal of Machine Learning Research, 3, 3/1/2003
• 20: Sturm, J. F. (1999). Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw., 11, 625--653.
• 21: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 22: Jason Weston , André Elisseeff , Bernhard Schölkopf , Mike Tipping, Use of the zero norm with linear models and kernel methods, The Journal of Machine Learning Research, 3, 3/1/2003
• 23: Weston, J., Mukherjee, S., Chapelle, O., Pontil, M., Poggio, T., & Vapnik, V. (2000). Feature selection for SVMs. Neural Information Processing Systems.
• 24: Zhu, J., Rossett, S., Hastie, T., & Tibshirani, R. (2003). 1-norm support vector machines. Neural Information Processing Systems.