Sequential minimal optimization: Difference between revisions

Revision as of 03:56, 25 October 2010

Revision as of 21:39, 8 November 2010

Line 1:

'''Sequential minimal optimization''' ('''SMO''') is an algorithm for solving the optimization problem which arises during the training of [[support vector machine]]s. It was invented by [[John Platt]] in 1998 at [[Microsoft Research]].<ref>{{Citation

{{Orphan|date=June 2010}}

| last = Platt | first = John

| year = 1998

| title = Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines

| url = http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.43.4376&rep=rep1&type=pdf

}}</ref> SMO is widely used for training support vector machines and is implemented by the popular libsvm tool.<ref>Chih-Chung Chang and Chih-Jen Lin (2001). ''[http://www.csie.ntu.edu.tw/~cjlin/papers/libsvm.pdf LIBSVM: a Library for Support Vector Machines]''.</ref><ref>Luca Zanni (2006) ''[http://jmlr.csail.mit.edu/papers/volume7/zanni06a/zanni06a.pdf Parallel Software for Training Large Scale Support Vector Machines on Multiprocessor Systems]''.</ref>

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 [[Quadratic programming|QP]] solvers.<ref>{{Citation

In [[mathematical optimization]] and [[machine learning]], '''sequential minimal optimization (SMO)''' is an algorithm for solving large [[quadratic programming]] (QP) [[optimization (mathematics)|optimization]] problems, widely used for the training of [[support vector machine]]s. First developed by [[John Platt|John C. Platt]] in 1999,<ref name=Platt1999>{{Citation

| last = PlattRifkin | first = J.C.Ryan

| year = 19992002

| url = http://dspace.mit.edu/handle/1721.1/17549

| title = Fast training of support vector machines using sequential minimal optimization

| title = Everything Old is New Again: a Fresh Look at Historical Approaches in Machine Learning

| url = http://portal.acm.org/citation.cfm?id=299094.299105

| journal = Ph.D. thesis

}}</ref> SMO breaks up large QP problems into a series of smallest possible QP problems, which are then solved analytically.

| pages = p.18

}}</ref>

== Optimization problem ==

==References==

{{main|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 {{nobr|''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 [[Wolde dual|dual]] is the following convex quadratic programming problem:

{{framebox|blue}}

:<math>\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,</math>

:subject to:

::<math>0 \leq \alpha_i \leq C, \quad \mbox{ for } i=1, 2, \ldots, n,</math>

::<math>\sum_{i=1}^n y_i \alpha_i = 0,</math>

{{frame-footer}}

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 ==

{{section-stub}}

}}</ref> SMO breaks up large QP problems into a series of smallest possible QP problems, which are then solved analytically.

== References ==

{{reflist}}

== External links ==

* [http://www.csie.ntu.edu.tw/~cjlin/libsvm/ LIBSVM]

[[Category:Optimization algorithms]]

[[Category:Machine learning]]

{{algorithmstatistics-stub}}

{{Optimization algorithms}}