A Quadratic Loss Multi-Class SVM for which a Radius–Margin Bound Applies

Article type: Research Article

Authors: Guermeur, Yann | Monfrini, Emmanuel

Affiliations: LORIA-CNRS, Campus Scientifique, BP 239, 54506 Vandœuvre-lès-Nancy cedex, France, E-mail: yann.guermeur@loria.fr | TELECOM SudParis, 9 rue Charles Fourier, 91011 EVRY cedex, France, E-mail: emmanuel.monfrini@it-sudparis.eu

Abstract: To set the values of the hyperparameters of a support vector machine (SVM), the method of choice is cross-validation. Several upper bounds on the leave-one-out error of the pattern recognition SVM have been derived. One of the most popular is the radius–margin bound. It applies to the hard margin machine, and, by extension, to the 2-norm SVM. In this article, we introduce the first quadratic loss multi-class SVM: the M-SVM2. It can be seen as a direct extension of the 2-norm SVM to the multi-class case, which we establish by deriving the corresponding generalized radius–margin bound.

Keywords: multi-class SVMs, model selection, leave-one-out cross-validation error, radius–margin bounds

Journal: Informatica, vol. 22, no. 1, pp. 73-96, 2011