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 lp ≥1 seamlessly, which further extends the SVM model flexibility beyond the usual Ev-SVM models.
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- D.P. Bertsekas. Nonlinear Programming. Athena Scientific, 1995.Google Scholar
- S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004. Google ScholarDigital Library
- S. Boyd and L. Vandenberghe. Subgradients. Notes for EE364b, Stanford University, Winter 2006-07, January 2007.Google Scholar
- 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. Google ScholarDigital Library
- F. H. Clarke. Optimization and Nonsmooth Analysis. Classics in Applied Mathematics. SIAM, 1990.Google ScholarCross Ref
- P.L. Combettes and J.-C. Pesquet. Proximal splitting methods in signal processing. arXiv:0912.3522, 2009.Google Scholar
- C. Cortes and V. Vapnik. Support-vector networks. Machine Learning, 20(3):273-297, 1995. Google ScholarCross Ref
- 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.Google Scholar
- R.O. Duda, P.E. Hart, and D.G. Stork. Pattern Classification. Wiley-Interscience. Wiley & Sons, New York, 2nd edition, 2001. Google ScholarDigital Library
- C. Ericson. The Gilbert-Johnson-Keerthi algorithm. Technical report, Sony Computer Entertainment America, 2005.Google Scholar
- D.G. De Figueiredo and L.A. Karlovitz. On the radial projection in normed spaces. Bulletin of the American Mathematical Society, 1967.Google ScholarCross Ref
- K. Huang, D. Zheng, I. King, and M.R. Lyu. Arbitrary norm support vector machines. Neural Computation, 21(2):560-582, 2009. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- J. López, K. De Brabanter, J.R. Dorronsoro, and JAK Suykens. Sparse LS-SVMs with l0-norm minimization. ESANN, 2011b.Google Scholar
- D.G. Luenberger and Y. Ye. Linear and Nonlinear Programming. Springer, 2008.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- G. Rätsch. Benchmark Repository, 2000. Datasets available at http://www.raetschlab. org/Members/raetsch/benchmark.Google Scholar
- R.T. Rockafellar. Convex Analysis, volume 28 of Princeton Mathematics Series. Princeton University Press, 1970.Google Scholar
- R.T. Rockafellar and S. Uryasev. Conditional value-at-risk for general loss distributions. Journal of Banking & Finance, 26(7):1443-1472, 2002.Google ScholarCross Ref
- B. Schölkopf, A.J. Smola, R.C. Williamson, and P.L. Bartlett. New support vector algorithms. Neural Computation, 12(5):1207-1245, 2000. Google ScholarDigital Library
- Y. Shi, Y. Tian, G. Kou, Y. Peng, and J. Li. Feature selection via lp-norm support vector machines. In Optimization Based Data Mining: Theory and Applications, pages 107-116. Springer, 2011.Google Scholar
- 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. Google ScholarDigital Library
- A. Takeda and M. Sugiyama. On generalization and non-convex optimization of extended v-support vector machine. New Generation Computing, 27:259-279, 2009.Google ScholarCross Ref
- A. Takeda, H. Mitsugi, and T. Kanamori. A unified classification model based on robust optimization. Neural Computation, 25 (3):759-804, 2013. Google ScholarDigital Library
- 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.Google Scholar
Index Terms
- Geometric intuition and algorithms for Ev-SVM
Recommendations
A geometric approach to Support Vector Machine (SVM) classification
The geometric framework for the support vector machine (SVM) classification problem provides an intuitive ground for the understanding and the application of geometric optimization algorithms, leading to practical solutions of real world classification ...
Geometric algorithms for parametric-margin ν-support vector machine
The parametric-margin @n-support vector machine (par-@n-SVM) is a useful classifier in many cases, especially when the noise is heteroscedastic. In this paper, the geometric interpretation for the par-@n-SVM is described, which is equivalent to finding ...
A generalized Gilbert's algorithm for approximating general SVM classifiers
Geometric methods provide an intuitive and theoretically solid viewpoint for the solution of many optimization problems in the fields of pattern recognition and machine learning. The support vector machine (SVM) classification is a typical optimization ...
Comments