Optimització mínima seqüencial

L'optimització mínima seqüencial (SMO) és un algorisme per resoldre el problema de programació quadràtica (QP) que sorgeix durant l'entrenament de màquines de vectors de suport (SVM). Va ser inventat per John Platt l'any 1998 a Microsoft Research. SMO s'utilitza àmpliament per a la formació de màquines vectorials de suport i està implementat per la popular eina LIBSVM. La publicació de l'algorisme SMO l'any 1998 ha generat molta il·lusió a la comunitat SVM, ja que els mètodes disponibles anteriorment per a la formació de SVM eren molt més complexos i requerien solucionadors QP de tercers costosos.

Problema d'optimització

Considereu un problema de classificació binària amb un conjunt de dades (x₁, y₁),... , (x_n, y_n), on x_i és un vector d'entrada i y_i ∈ {-1, +1} és una etiqueta binària que li correspon. Una màquina vectorial de suport de marge suau s'entrena resolent un problema de programació quadràtica, que s'expressa en la forma dual de la següent manera:

$\max _{\alpha }\sum _{i=1}^{n}\alpha _{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}y_{j}K(x_{i},x_{j})\alpha _{i}\alpha _{j},$

subjecte a:

$0\leq \alpha _{i}\leq C,\quad {\mbox{ per }}i=1,2,\ldots ,$

$\sum _{i=1}^{n}y_{i}\alpha _{i}=0$

on C és un hiperparàmetre SVM i K(x_i, x_j) és la funció del nucli, ambdues proporcionades per l'usuari; i les variables $\alpha _{i}$ són multiplicadors de Lagrange.

Algorisme

SMO és un algorisme iteratiu per resoldre el problema d'optimització descrit anteriorment. SMO divideix aquest problema en una sèrie de subproblemes més petits possibles, que després es resolen analíticament. A causa de la restricció d'igualtat lineal que implica els multiplicadors de Lagrange $\alpha _{i}$, el problema més petit possible implica dos d'aquests multiplicadors. Aleshores, per a dos multiplicadors qualsevol $\alpha _{1}$ i $\alpha _{2}$, les restriccions es redueixen a:

$0\leq \alpha _{1},\alpha _{2}\leq C,$

$y_{1}\alpha _{1}+y_{2}\alpha _{2}=k,$

i aquest problema reduït es pot resoldre analíticament: cal trobar un mínim d'una funció quadràtica unidimensional. $k$ és el negatiu de la suma sobre la resta de termes de la restricció d'igualtat, que es fixa en cada iteració.

1. Trobeu un multiplicador de Lagrange que viola les condicions de Karush–Kuhn–Tucker (KKT) per al problema d'optimització.
2. Trieu un segon multiplicador i optimitzar la parella.
3. Repetiu els passos 1 i 2 fins a la convergència.

Quan tots els multiplicadors de Lagrange compleixen les condicions KKT (dins d'una tolerància definida per l'usuari), el problema s'ha resolt. Tot i que es garanteix la convergència d'aquest algorisme, s'utilitzen heurístiques per triar el parell de multiplicadors per accelerar la velocitat de convergència. Això és fonamental per a grans conjunts de dades, ja que n'hi ha $n(n-1)/2$ opcions possibles per $\alpha _{i}$ i $\alpha _{j}$.