Lagrangian Support Vector Machines
Abstract
An implicit Lagrangian for the dual of a simple reformulation of
the standard quadratic program of a linear support vector machine
is proposed. This leads to the minimization of an unconstrained
di erentiable convex function in a space of dimensionality equal to
the number of classi ed points. This problem is solvable by an ex-
tremely simple linearly convergent Lagrangian support vector machine
(LSVM) algorithm. LSVM requires the inversion at the outset of a
single matrix of the order of the much smaller dimensionality of the
original input space plus one. The full algorithm is given in this paper
in 11 lines of MATLAB code without any special optimization tools
such as linear or quadratic programming solvers. This LSVM code
can be used \as is" to solve classi cation problems with millions of
points. For example, 2 million points in 10 dimensional input space
were classi ed by a linear surface in 82 minutes on a Pentium III 500
MHz notebook with 384 megabytes of memory (and additional swap
space), and in 7 minutes on a 250 MHz UltraSPARC II processor with
2 gigabytes of memory. Other standard classi cation test problems
were also solved. Nonlinear kernel classi cation can also be solved by
LSVM. Although it does not scale up to very large problems, it can
handle any positive semide nite kernel and is guaranteed to converge.
A short MATLAB code is also given for nonlinear kernels and tested
on a number of problems.
Permanent Link
http://digital.library.wisc.edu/1793/64288Citation
00-06