Geometric intuition and algorithms for Ev-SVM

Abstract

In this work we address the Ev-SVM model proposed by Pérez-Cruz et al. as an extension of the traditional v support vector classification model (v-SVM). Through an enhancement of the range of admissible values for the regularization parameter v, the Ev-SVM has been shown to be able to produce a wider variety of decision functions, giving rise to a better adaptability to the data. However, while a clear and intuitive geometric interpretation can be given for the v-SVM model as a nearest-point problem in reduced convex hulls (RCH-NPP), no previous work has been made in developing such intuition for the Ev-SVM model. In this paper we show how Ev-SVM can be reformulated as a geometrical problem that generalizes RCH-NPP, providing new insights into this model. Under this novel point of view, we propose the RapMinos algorithm, able to solve Ev-SVM more efficiently than the current methods. Furthermore, we show how RapMinos is able to address the Ev-SVM model for any choice of regularization norm l_p ≥1 seamlessly, which further extends the SVM model flexibility beyond the usual Ev-SVM models.

References

1. A. Beck and M. Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM Journal of Imaging Sciences, 2(1):183-202, 2009.
2. K.P. Bennett and E.J. Bredensteiner. Duality and geometry in SVM classifiers. In Proceedings of the 17th International Conference on Machine Learning, pages 57-64, 2000.
3. D.P. Bertsekas. Nonlinear Programming. Athena Scientific, 1995.
4. S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
5. S. Boyd and L. Vandenberghe. Subgradients. Notes for EE364b, Stanford University, Winter 2006-07, January 2007.
6. C.-C. Chang and C.-J. Lin. LIBSVM: a Library for Support Vector Machines, 2001. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.
7. F. H. Clarke. Optimization and Nonsmooth Analysis. Classics in Applied Mathematics. SIAM, 1990.
8. P.L. Combettes and J.-C. Pesquet. Proximal splitting methods in signal processing. arXiv:0912.3522, 2009.
9. C. Cortes and V. Vapnik. Support-vector networks. Machine Learning, 20(3):273-297, 1995.
10. D.J. Crisp and C.J.C. Burges. A geometric interpretation of v-SVM classifiers. In Advances in Neural Information Processing Systems, volume 12, 2000.
11. R.O. Duda, P.E. Hart, and D.G. Stork. Pattern Classification. Wiley-Interscience. Wiley & Sons, New York, 2nd edition, 2001.
12. C. Ericson. The Gilbert-Johnson-Keerthi algorithm. Technical report, Sony Computer Entertainment America, 2005.
13. D.G. De Figueiredo and L.A. Karlovitz. On the radial projection in normed spaces. Bulletin of the American Mathematical Society, 1967.
14. K. Huang, D. Zheng, I. King, and M.R. Lyu. Arbitrary norm support vector machines. Neural Computation, 21(2):560-582, 2009.
15. S. S. Keerthi, S. K. Shevade, C. Bhattacharyya, and K. R. K. Murthy. A fast iterative nearest point algorithm for support vector machine classifier design. IEEE Transactions on Neural Networks, 11(1):124-136, 2000.
16. J. López, Á. Barbero, and J.R. Dorronsoro. On the equivalence of the SMO and MDM algorithms for SVM training. In Lecture Notes in Computer Science: Machine Learning and Knowledge Discovery in Databases, volume 5211, pages 288-300. Springer, 2008.
17. J. López, Á. Barbero, and J.R. Dorronsoro. Clipping algorithms for solving the nearest point problem over reduced convex hulls. Pattern Recognition, 44(3):607-614, 2011a.
18. J. López, K. De Brabanter, J.R. Dorronsoro, and JAK Suykens. Sparse LS-SVMs with l₀-norm minimization. ESANN, 2011b.
19. D.G. Luenberger and Y. Ye. Linear and Nonlinear Programming. Springer, 2008.
20. M.E. Mavroforakis and S. Theodoridis. A geometric approach to support vector machine (SVM) classification. IEEE Transactions on Neural Networks, 17(3):671-682, 2006.
21. M.E. Mavroforakis, M. Sdralis, and S. Theodoridis. A geometric nearest point algorithm for the efficient solution of the SVM classification task. IEEE Transactions on Neural Networks, 18(5):1545-1549, 2007.
22. F. Pérez-Cruz, J. Weston, D.J.L. Hermann, and B. Schölkopf. Extension of the v-SVM range for classification. In Advances in Learning Theory: Methods, Models and Applications, volume 190, pages 179-196, 2003.
23. G. Rätsch. Benchmark Repository, 2000. Datasets available at http://www.raetschlab. org/Members/raetsch/benchmark.
24. R.T. Rockafellar. Convex Analysis, volume 28 of Princeton Mathematics Series. Princeton University Press, 1970.
25. R.T. Rockafellar and S. Uryasev. Conditional value-at-risk for general loss distributions. Journal of Banking & Finance, 26(7):1443-1472, 2002.
26. B. Schölkopf, A.J. Smola, R.C. Williamson, and P.L. Bartlett. New support vector algorithms. Neural Computation, 12(5):1207-1245, 2000.
27. Y. Shi, Y. Tian, G. Kou, Y. Peng, and J. Li. Feature selection via l_p-norm support vector machines. In Optimization Based Data Mining: Theory and Applications, pages 107-116. Springer, 2011.
28. A. Takeda and M. Sugiyama. v-support vector machine as conditional value-at-risk minimization. In Proceedings of the 25th International Conference on Machine Learning, pages 1056-1063, 2008.
29. A. Takeda and M. Sugiyama. On generalization and non-convex optimization of extended v-support vector machine. New Generation Computing, 27:259-279, 2009.
30. A. Takeda, H. Mitsugi, and T. Kanamori. A unified classification model based on robust optimization. Neural Computation, 25 (3):759-804, 2013.
31. J. Zhu, S. Rosset, T. Hastie, and R. Tibshirani. 1-norm support vector machines. In S. Thrun, L.K. Saul, and B. Schölkopf, editors, Neural Information Processing Systems. MIT Press, 2003.

Index Terms

• Computing methodologies

  • Machine learning

• Information systems

  • Information systems applications

    • Decision support systems

      • Expert systems

• Theory of computation

  • Randomness, geometry and discrete structures

    • Computational geometry