.

Support Vector Machines on a Budget

Ofer Dekel and Yoram Singer

Abstract

The standard Support Vector Machine formulation does not provide its user with the ability to explicitly control the number of support vectors used to define the generated classifier. We present a modified version of SVM that allows the user to set a budget parameter B and focuses on minimizing the loss attained by the B worst-classified examples while ignoring the remaining examples. This idea can be used to derive sparse versions of both L1-SVM and L2-SVM. Technically, we obtain these new SVM variants by replacing the 1-norm in the standard SVM formulation with various interpolation-norms. We also adapt the SMO optimization algorithm to our setting and report on some preliminary experimental results.

http://books.nips.cc/papers/files/nips19/NIPS2006_0303.pdf‎

.

I like to use linear SVM liblinear (http://www.csie.ntu.edu.tw/~cjlin/liblinear/), this lib have many different optimization technique. And there is a way to create nonlinear classification: projection primary feature space to larger feature space by Homogeneous kernel map (http://www.vlfeat.org/~vedaldi/assets/pubs/vedaldi11efficient.pdf)

But this classification have ONE nonlinear kernel.

@Clerot Fabrice thank you very much for your answer.

The article is interesting, but the L1 aspect is on the loss. Instead, my question was referring to 1-norm SVM as it is described in this article:

http://machinelearning.wustl.edu/mlpapers/paper_files/NIPS2003_AA07.pdf

where the authors are performing L1-norm regularization of the linear coefficients.

I'm wondering if the same is possible in a kernel space ?

@Sergievskiy: Dear Nikolay, many thanks for your answer. It is exactly the kind of work I'm looking for... BUT It's a pity that so few kernels are available !

.

maybe H. Zhang's work around RKB(anach)S with l1 norm ?

Reproducing Kernel Banach Spaces with the ℓ1 Norm

Guohui Song, Haizhang Zhang and Fred J. Hickernell

Abstract

Targeting at sparse learning, we construct Banach spaces B of functions on an input space X with the following properties: (1) B possesses an ℓ1 norm in the sense that B is isometrically isomorphic to the Banach space of integrable functions on X with respect to the counting measure; (2) point evaluations are continuous linear functionals on B and are representable through a bilinear form with a kernel function; and (3) regularized learning schemes on B satisfy the linear representer theorem. Examples of kernel functions admissible for the construction of such spaces are given.

http://arxiv.org/pdf/1101.4388v3.pdf

.