Sequential minimal optimization

Sequential minimal optimization (SMO) is an algorithm for efficiently 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 the SMO algorithm in 1998 has generated a lot of excitement in the 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

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 a quadratic programming problem, which is expressed in the dual form as follows:

$\max_{\alpha} \sum_{i=1}^n \alpha_i - \frac12 \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; and the variables α_i are Lagrange multipliers.

Algorithm

SMO is an iterative algorithm for solving the optimization problem described above. SMO breaks this problem into a series of smallest possible sub-problems, which are then solved analytically. Because of the linear equality constraint involving the Lagrange multipliers α_i, the smallest possible problem involves two such multipliers. Then, for any two multipliers α₁ and α₂, the constraints are reduced to:

$0 \leq \alpha_1, \alpha_2 \leq C,$

y₁α₁ + y₂α₂ = k

and this reduced problem can be solved analytically.

The algorithm proceeds as follows:

1. Find a Lagrange multiplier α₁ that violates the Karush–Kuhn–Tucker (KKT) conditions for the optimization problem.
2. Pick a second multiplier α₂ and optimize the pair (α₁,α₂).
3. Repeat steps 1 and 2 until convergence.

When all the Lagrange multipliers satisfy the KKT conditions (within a user-defined tolerance), the problem has been solved. Although this algorithm is guaranteed to converge, heuristics are used to choose the pair of multipliers so as to accelerate the rate of convergence.

External links

• LIBSVM