Sequential minimal optimization

Sequential minimal optimization (SMO) is an algorithm for solving the quadratic programming (QP) problem that arises during the training of support-vector machines (SVM). 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. Sequential minimal optimization (SMO) is an algorithm for solving the quadratic programming (QP) problem that arises during the training of support-vector machines (SVM). 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. Consider a binary classification problem with a dataset (x1, y1), ..., (xn, yn), where xi is an input vector and yi ∈ {-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: where C is an SVM hyperparameter and K(xi, xj) is the kernel function, both supplied by the user; and the variables α i {displaystyle alpha _{i}} are Lagrange multipliers. 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 {displaystyle alpha _{i}} , the smallest possible problem involves two such multipliers. Then, for any two multipliers α 1 {displaystyle alpha _{1}} and α 2 {displaystyle alpha _{2}} , the constraints are reduced to: and this reduced problem can be solved analytically: one needs to find a minimum of a one-dimensional quadratic function. k {displaystyle k} is the negative of the sum over the rest of terms in the equality constraint, which is fixed in each iteration.