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. \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 \alpha_i are Lagrange multipliers. y_1 \alpha_1 + y_2 \alpha_2 = k, and this reduced problem can be solved analytically: one needs to find a minimum of a one-dimensional quadratic function. k is the negative of the sum over the rest of terms in the equality constraint, which is fixed in each iteration. The algorithm proceeds as follows: Find a Lagrange multiplier \alpha_1 that violates the Karush–Kuhn–Tucker (KKT) conditions for the optimization problem. Pick a second multiplier \alpha_2 and optimize the pair (\alpha_1,\alpha_2) . 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. This is critical for large data sets since there are n(n-1)/2 possible choices for \alpha_i and \alpha_j .

Text derived from https://en.wikipedia.org/w/index.php?oldid=1373933737 under CC BY-SA 4.0; modifications have been made.