====== Support Vector Machine Software ======

===== Early Support Vector Machine Solvers =====
{{svm-linear.png?200 }}
[[wp>Support_vector_machine|Support Vector Machines]] (SVMs) were discovered in three steps:
In the sixties, Vapnik and Learner propose the //Optimal Hyperplane// classifier.
In 1991, Boser, Guyon and Vapnik add the //Kernel Trick//.
In 1994, Cortes and Vapnik finalize the modern //Soft Margin// formulation of SVMs.

The second step happened while I was working at [[wp>Bell_Labs|Bell Labs]].
We were all very excited.  Bernhard Boser's first implementation of SVM was derived from ideas 
suggested in [[http://www.amazon.com/gp/product/0387308652|Vapnik's 82 book]].
That involves considering all pairs of examples belonging to different classes.
I wrote the second SVM implementation, named GP2 for //Generalized Portrait// version 2.
This was the first implementation using the standard dual formulation of the SVMs
with an equality constraint. The GP2 optimizer was using [[:papers:bottou-lin-2006|modified gradient projection]] with chunking and conjugation.
This code was later used as a starting point 
by [[http://homepage.mac.com/corinnacortes|Corinna Cortes]].
===== The Royal Holloway Support Vector Machine =====

Around 1997, we decided to contribute a quadratic programming optimizer
for the [[http://svm.dcs.rhbnc.ac.uk/dist/index.shtml|Royal Holloway Support Vector Machine]] code.
The GP2 code was running inside an early version of [[projects:lush|Lush]].
I quickly rewrote its core in C++ and renamed it SVQP.  
[[http://www.kyb.mpg.de/bs/people/weston|Jason Weston]]
and [[http://www.stitson.com/|Mark Stitson]] then implemented sophisticated chunking stategies 
around the "Bottou" optimizer.  
SVQP is still available in the [[projects:lush|Lush]] CVS repository.
This is no longer a state-of-the art SVM solver, but it can be handy 
for solving non quadratic convex problems in moderately large dimensions.

   * [[https://sourceforge.net/p/lush/code/HEAD/tree/lush1/trunk/packages/svm/svqp/]]


===== The SVQP2 solver =====

Support Vector Machine solvers are now much faster than these early codes.
[[http://research.microsoft.com/~jplatt|John Platt]]'s SMO method was a big 
improvement. Around 2003, I decided to implement SVQP2, 
a state-of-the-art SVM solver using the latest known techniques
for caching kernel values and choosing example pairs.
Although SVQP2 is the main SVM solver implemented in [[projects:lush|Lush]],
it does not rely on the Lush facilities and can be used as a standalone library.
It is available in the [[projects:lush|Lush]] CVS repository:

   * [[https://sourceforge.net/p/lush/code/HEAD/tree/lush1/trunk/packages/svm/svqp2/]]

===== Publications =====

<box 99% orange>
Léon Bottou and Chih-Jen Lin: **Support Vector Machine Solvers**, in //Large Scale Kernel Machines//, Léon Bottou, Olivier Chapelle, Dennis DeCoste, and Jason Weston editors, 1–28, MIT Press, Cambridge, MA., 2007.

[[:papers/bottou-lin-2006|more...]]
</box>