Ottimizzazione minima sequenziale

Da Wikipedia, l'enciclopedia libera.

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

Problema dell'ottimizzazione[modifica | modifica sorgente]

Considerando il problema della classificazione binaria con un insieme di dati (dataset) (x1, y1), ..., (xn, yn),dove xi è un vettore d'ingresso e yi ∈ {-1, +1}è una etichetta binaria corrispondente ad esso. Una macchina a vettore di supporto è allenata risolvendo il problema della programmazione quadratico, che è espresso in forma duale come segue:

\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,
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 SVM e K(xi, xj) è la funzione kernel, entrambe fornite dall'utente; e le variabili \alpha_i sono moltiplicatori lagrangiani.

Collegamenti esterni[modifica | modifica sorgente]