Sequential minimal optimization: Difference between revisions

Revision as of 07:33, 6 October 2015

Revision as of 01:42, 12 October 2015

Line 6:

|space=

}}

'''Sequential minimal optimization''' ('''SMO''') is an algorithm for solving the [[quadratic programming]] (QP) problem that arises during the training of [[support vector machine]]s. It was invented by [[John Platt (Principal Researcher)|John Platt]] in 1998 at [[Microsoft Research]].<ref name = "Platt">{{Citation

| last = Platt | first = John

| year = 1998

Line 53:

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) possible choices for <math>\alpha_i</math> and <math>\alpha_j</math>.

== Related Work ==

The first approach to splitting large SVM learning problems into a series of smaller optimization tasks was proposed by Bernhard E Boser, Isabelle M Guyon, Vladimir N Vapnik.<ref name="ReferenceA">{{Cite book | doi = 10.1145/130385.130401| chapter = A training algorithm for optimal margin classifiers| title = Proceedings of the fifth annual workshop on Computational learning theory - COLT '92| pages = 144| year = 1992| last1 = Boser | first1 = B. E. | last2 = Guyon | first2 = I. M. | last3 = Vapnik | first3 = V. N. | isbn = 089791497X}}</ref> It is known as the "chunking algorithm". The algorithm starts with a random subset of the data, solves this problem, and iteratively adds examples which violate the optimality conditions. One disadvantage of this algorithm is that it is necessary to solve QP-problems scaling with the number of SVs. On real world sparse data sets, SMO can be more than 1000 times faster than the chunking algorithm.<ref name = "Platt"/>

== See also ==

* [[Kernel perceptron]]