Dopo aver discusso come funziona la Logistic Regression, ci soffermiamo ad analizzare un altro algoritmo di apprendimento largamente diffuso ovvero le Support Vector Machine (SVM).

SVM può essere considerato un’estensione del Perceptron. Nell’ultimo si minimizza l’errore di predizione, nell’SVM invece si cerca di massimizzare il così detto margin ovvero la distanza che separa i confini decisionali tra una classe e l’altra, chiamati per l’appunto support-vectors.

Maximum Margin

Massimizzare i margini decisionali di un modello, comporta l’avere un minore errore di generalizzazione e quindi minor rischio di overfitting. Guardando l’immagine precedente, prendiamo per riferimento gli iperpiani positivi e negativi:

w_0 +\mathbf{ w^Tx_{pos}} = 1

w_0 +\mathbf{ w^Tx_{neg}} = -1

se sottraiamo le due equazioni lineari otteniamo:

\mathbf{w^T}(\mathbf{x_{pos} - x_{neg}}) = 2

a questo punto possiamo normalizzare l’equazione appena ricavata con la lunghezza del vettore w così definito:

\left \| \boldsymbol{w} \right \| = \sqrt{\sum_{j=1}^{m} w_j^2}

ottenendo la seguente equazione:

\frac{\boldsymbol{w^T}(\boldsymbol{x_{pos} - x_{neg}})}{\left \| \boldsymbol{w} \right \|} = \frac{2}{\left \| \boldsymbol{w} \right \|}

La parte a sinistra non è altro che la distanza tra l’iperpiano positivo e negativo, chiamato per l’appunto margin e che vogliamo massimizzare.

Nella pratica è più conveniente minimizzare il termine reciproco, ovvero:

\frac{1}{2}\left \| \boldsymbol{w} \right \|^2

La funzione obiettivo quindi per la SVM diventa la minimizzazione del margin appena definito, a patto che i campioni vengano classificati correttamente, ovvero:

w_0 + \boldsymbol{w^Tx^{(i)}} \geq 1 if y^{(i)} = 1

w_0 + \boldsymbol{w^Tx^{(i)}} \leq 1 if y^{(i)} = -1

per i = 1..N, con N il numero di campioni nel nostro dataset.

Queste equazioni dicono sostanzialmente che tutti i campioni negativi devono cadere all’interno dell’iperpiano negativo, mentre i positivi devono cadere in quello positivo.

Slack Variables

Nel 1995 Vladimir Vapnik introduce al modello appena definito un concetto che rende le SVM ancora più efficaci: la slack variable \boldsymbol{\xi } .

La motivazione della sua introduzione è che talvolta, sopratutto nel caso di dataset non linearmente separabili, è necessario rilassare i vincoli definiti in precedenza per permettere la convergenza e l’ottimizzazione della rete anche in caso di errori di classificazione.

w_0 + \boldsymbol{w^Tx^{(i)}} \geq 1 - \xi^{(i)} if y^{(i)} = 1

w_0 + \boldsymbol{w^Tx^{(i)}} \leq 1 + \xi^{(i)} if y^{(i)} = -1

quindi la nuova funzione obiettivo da minimizzare diventa:

\frac{1}{2}\left \| \boldsymbol{w} \right \|^2 + C\left ( \sum_{I}^{} \xi^{(i)}\right )

tramite la variabile C possiamo controllare la penalità nel caso di errore di classificazione.

Valori grandi di C corrispondono ovviamente a penalità grandi e quindi costringiamo il modello ad avvicinarsi il più possibile al training set, siamo invece meno stringenti a riguardo di errori di classificazione con valori più piccoli di C.

questo concetto richiama inevitabilmente quello di regularization discusso nel precedente articolo.

Kernel SVM

Le Support Vector Machine hanno un altro asso nella manica che permette di utilizzarle, come introdotto inizialmente, in scenari non linearmente separabili: il kernel.

Immaginiamo un dataset dove i vari campioni sono mischiati in modo da non poter trovare un piano che li divida:

questo avviene molto spesso in applicazioni reali. Ovviamente utilizzare le tecniche viste in precedenza non porterà a risultati degni di nota. E’ necessario cambiare approccio.

L’idea alla base del kernel method è quella di creare combinazioni non lineari delle feature originali per proiettarle in uno spazio dimensionalmente più grande rispetto a quello di partenza. Questa proiezione è resa possibile dalla funzione \phi. Successivamente, se la conformazione del dataset lo consente, trovandoci in uno spazio dimensionalmente più grande, possiamo sperare che il dataset diventi a questo punto separabile.

senza andare troppo nel dettaglio, presentiamo ora uno dei kernel più diffusi che prende il nome di Radial Basis Function (RBF) o Gaussian kernel:

K(x^{(i)},x^{(j))}) = exp(-\gamma \left \| x^{(i)} - x^{(j)} \right \|^2)

con \gamma =\frac{1}{2\sigma ^2}, un parametro da ottimizzare.

Addestriamo una SVM

Bene, dopo aver fatto la nostra solita introduzione teorica all’algoritmo, vediamo come poterlo utilizzare su un progetto pratico.

Come già fatto in precedenza, faremo uso della libreria Python scikit-learn, e del nostro dataset dei nomi di persona italiani che abbiamo costruito in uno dei nostri primi articoli.

Lo script che ti vado a presentare si basa su due metodi per il caricamento del dataset e il calcolo delle feature, per motivi di brevità ti rimando all’articolo dove le presento per la prima volta, in modo che tu possa avere accesso sia al codice che alla spiegazione di quello che viene fatto.

Similmente a quanto fatto in passato, partiamo dalla riga 5 con il caricare il nostro dataset e il dividerlo in training set e test set. Successivamente creiamo l’oggetto SVC (riga 7) e definiamo in ingresso l’utilizzo del kernel e dei parametri \gamma e C.

A questo punto eseguiamo il training (riga 8) e stampiamo poi le performance raggiunte sul test set (riga 10).

In questo caso, a differenza degli algoritmi visti negli articoli precedenti, siamo riusciti a raggiungere una precisione del 97.25%, il che dimostra come effettivamente utilizzare un kernel di questo tipo su un dataset non linearmente separabile può garantire un vantaggio di fondo.

Terminiamo infine lo script chiedendo all’utente di inserire in input delle parole a scelta per testare ulteriormente le capacità di classificazione della rete.

Conclusioni

In questo articolo, abbiamo presentato le SVM un algoritmo di classificazione largamente usato nel ML.  A differenza di algoritmi come il Perceptron o la Logistic Regression, SVM ha performance computazionali meno buone ma garantisce buone performance di classificazione anche in scenari in cui il dataset non è linearmente separabile.

A questo proposito, il nostro semplice esempio, ci fornisce effettivamente una dimostrazione pratica del come un kernel non lineare come l’RBF possa ottenere risultati migliori in classificazione.