Ottimizzazione minima sequenziale

L'Ottimizzazione minima sequenziale (in inglese: Sequential minimal optimization, in sigla SMO) è un algoritmo per risolvere efficientemente il problema di ottimizzazione che emerge durante l'addestramento di una Macchine a vettori di supporto. Fu inventato da John Platt nel 1998 al laboratorio Microsoft Research di Redmond. L'Ottimizzazione minima sequenziale è implementata nella famosa libreria software libsvm.

Il problema

Consideriamo il problema della classificazione binaria con un insieme di dati (dataset) $(x_{1},y_{1}),...,(x_{n},y_{n})$, dove $x_{i}$ è un vettore d'ingresso e $y_{i}\in \{-1,+1\}$ è la corrispondente etichetta binaria. Una macchina a vettori di supporto si addestra risolvendo un problema di programmazione quadratica vincolato. Tale problema si può esprimere in forma duale come segue:

$\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},$

vincolato a:

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

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

dove C è un iperparametro e K(x_i, x_j) è la funzione kernel, l'uno e l'altra stabilite dall'utente; le variabili $\alpha _{i}$ sono moltiplicatori di Lagrange.

L'algoritmo

SMO è un algoritmo iterativo che risolve il problema appena descritto. La strategia di SMO consiste nel decomporre il problema in un insieme di sottoproblemi minimali, che possono poi essere risolti analiticamente. Per via della presenza dei vincoli lineari di uguaglianza che includono i moltiplicatori di Lagrange, $\alpha _{i}$, il problema minimo possibile contiene due moltiplicatori. Quindi per una data coppia di moltiplicatori $\alpha _{1}$ e $\alpha _{2}$, i vincoli si riducono a:

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

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

Questo problema ridotto si può risolvere analiticamente: occorre trovare il minimo di una funzione quadratica monodimensionale, cioè una parabola. $k$ è l'opposto della somma su tutti i termini rimanenti nel vincolo di uguaglianza, che in ogni iterazione è fissato.

L'algoritmo procede così:

1. Trovare un moltiplicatore di Lagrange $\alpha _{1}$ che viola le condizioni di Karush–Kuhn–Tucker (KKT) per questo problema.
2. Trovare un secondo moltiplicatore $\alpha _{2}$ e ottimizzare la coppia $(\alpha _{1},\alpha _{2})$.
3. Ripetere i passi 1 e 2 fino a convergenza.

Quando tutti i moltiplicatori di Lagrange soddisfano le condizioni KKT (entro una tolleranza prestabilita), il problema è risolto.

Per questo algoritmo è garantita la convergenza; tuttavia, per accelerarla, vengono utilizzate euristiche per scegliere coppie favorevoli di moltiplicatori. Questo accorgimento è criticamente importante per insiemi di dati di grandi dimensioni $n$, in quanto esistono $n(n-1)$ scelte possibili di $\alpha _{i}$ e $\alpha _{j}$.

Collegamenti esterni

• (EN) LIBSVM, su csie.ntu.edu.tw.