Sequential minimal optimization

Sequential minimal optimization (SMO) is an algorithm for solving the optimization problem which arises during the training of support vector machines. It was invented by John Platt in 1998 at Microsoft Research. SMO is widely used for training support vector machines and is implemented by the popular libsvm tool.

The publication of SMO algorithm in 1998 has generated a lot of excitement in SVM community, as previously available methods for SVM training were much more complex and required expensive third-party QP solvers.

Optimization problem

Main article: Support vector machine § Formalization

Consider a binary classification problem with a dataset (x₁, y₁), ..., (x_n, y_n), where x_i is an input vector and y_i ∈ {-1, +1} is a binary label corresponding to it. A soft-margin support vector machine is trained by solving an optimization problem whose dual is the following convex quadratic programming problem:

$\max _{\alpha }\sum _{i=1}^{n}\alpha _{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}y_{j}K(x_{i},x_{j})\alpha _{i}\alpha _{j},$

subject to:

$0\leq \alpha _{i}\leq C,\quad {\mbox{ for }}i=1,2,\ldots ,n,$

$\sum _{i=1}^{n}y_{i}\alpha _{i}=0,$

where C is an SVM hyperparameter and K(x_i, x_j) is the kernel function, both supplied by the user.

SMO is an iterative algorithm for solving this dual SVM optimization problem.

Algorithm

SMO breaks up large QP problems into a series of smallest possible QP problems, which are then solved analytically.

External links

• LIBSVM