Le Support-Vector Machine o SVM (in italiano Macchine a vettori di supporto) sono modelli di classificazione il cui obiettivo è quello di trovare la retta di separazione delle classi che massimizza il margine tra le classi stesse, dove con margine si intende la distanza minima dalla retta ai punti delle due classi.

Questo obiettivo viene raggiunto utilizzando una parte minimale del dataset di allenamento, i cosiddetti vettori di supporto (da cui il nome della famiglia di modelli).

Nella figura a fianco si nota quale sia la retta di separazione che massimizza il margine tra le due classi di dati. La stella e i due triangoli indicati sono i vettori di supporto, che come si può notare sono gli unici esempi del dataset che risiedono sul margine. Una volta trovati questi, tutti gli altri esempi del dataset saranno ininfluenti ai fini della classificazione, perchè sono loro  a definire la retta di separazione ed il margine.

Ma cosa rappresentano i vettori di supporto? Sono i valori di una classe più vicini alla retta di separazione, quelli che più si avvicinano all’altra classe. In sostanza sono i valori classificabili con maggiore difficoltà.

Ed è proprio questo che differisce la SVM da altri algoritmi di classificazione: mentre una regressione logistica “impara” a classificare prendendo come riferimento gli esempi più rappresentativi di una classe, la SVM cerca gli esempi più difficili, quelli che tendono ad essere più vicini all’altra classe (i vettori di supporto, appunto) e considera solo quelli per eseguire la classificazione.

Questo approccio lo possiamo riassumere con questa frase: “se la classificazione vale per gli esempi più difficili, vale sicuramente anche per tutti gli altri“.

Un’altro aspetto interessante è che maggiore è il margine, migliore sarà la generalizzazione. Il motivo è abbastanza semplice da capire: maggiore è il margine, maggiore è la distanza tra le classi e quindi minore la possibilità di fare confusione.

Codice Python

NOTA: il codice di questo esempio lo trovi qui

Per questo esempio utilizzeremo il dataset Iris, già visto in passato. Al momento mi limito a prendere solo le prime due proprietà, in modo da poter poi visualizzare graficamente i risultati su un piano bidimensionale.

# carico il dataset
iris = load_iris()
# non prendo tutte le feature, ma solo le prime due (così poi posso visualizzarle in un grafico bidimensionale)
X = iris.data[:, :2]
Y = iris.target

In modo analogo a quanto già visto, preparo il dataset di train e di test, poi procedo alla standardizzazione in quanto le proprietà del dataset hanno range di valori diversi e questo influirebbe negativamente sulle prestazioni del modello. L’array dei target è già codificato quindi non necessita di altre elaborazioni.

Procedo a disegnare il dataset di train usando una funzione che consentirà (lo vedremo tra poco) di visualizzare anche i bordi delle rette di separazione che verranno create dalla SVM. La funzione la potete trovare nel codice sorgente e semplicemente prepara uno scatter plot, cioè un grafico di punti XY, colorati in base alla classe di appartenenza (sono presenti 3 classi nel dataset Iris). Se tra i parametri viene passata anche la SVM, la utilizza per visualizzare le rette di separazione.

Si può notare che il dataset presenta una nuvola rossa ben definita nel quadrante in alto a sinistra, mentre le restanti due classi hanno diversi punti mischiati tra loro. Di sicuro non sarà facile classificare questo dataset utilizzando solo queste due proprietà. Ci proviamo.

Usiamo la classe LinearSVC di SciKit-learn per creare una SVM che andremo poi ad allenare con i dati di train. Poi calcoliamo l’accuracy del train set e del test set, per analizzare il risultato.

# creo la SVM e la alleno
svm = LinearSVC()
svm.fit(X_train_std, Y_train)

# calcolo la accuracy del set di train e di test
print("Usando solo due proprietà")
print("Accuracy Train Set:", svm.score(X_train_std, Y_train))
print("Accuracy Test Set:", svm.score(X_test_std, Y_test))
print()

Usando solo due proprietà
Accuracy Train Set: 0.8285714285714286
Accuracy Test Set: 0.6888888888888889

Come si può notare il modello appare soffrire di overfitting (l’accuracy sul train set è sensibilmente migliore di quella sul test set). Potremmo procedere a modificare i parametri di istanza della classe LinearSVC, ad esempio per modificare il coefficiente di regolarizzazione, come già visto negli articoli precedenti, ma non è questo che ci interessa (se volete sperimentare, siete i benvenuti!). Limitiamoci a visualizzare le rette di separazione.

Riutilizziamo la funzione di disegno passandogli anche la SVM tra i parametri. Come avverrà il disegno delle separazioni? Semplicemente la funzione, oltre ai punti dovuti al dataset di train da visualizzare, disegnerà anche tanti altri punti fittizi che ricoprono l’intera area di disegno. Sfrutterà la SVM per classificarli e quindi colorarli. Et voilà le résultat…

Come immaginavamo la classe rossa è stata individuata in modo molto accurato (c’è un unico puntino rosso che è in zona viola), mentre le altre due classi appaiono ancora un po’ confuse, abbassando quindi l’accuracy complessiva del modello.

Bene ora proviamo a rifare il tutto utilizzando questa volta tutte le proprietà del dataset Iris. Ovviamente non potremo mettere in grafica i risultati, in quanto abbiamo a che fare con uno spazio a 4 dimensioni. Limitiamoci a visualizzare le accuracy e a ragionare su quelle.

Usando TUTTE le proprietà
Accuracy Train Set: 0.9428571428571428
Accuracy Test Set: 0.9555555555555556

Il modello è notevolmente migliorato e non soffre più di overfitting, arrivando ad una accuracy superiore al 95,5% sul test set. Notevole.

Kernel SVM

Nell’esercizio precedente eravamo di fronte ad una classificazione lineare, cioè un tipo di classificazione in cui vengono utilizzate rette o in generale iperpiani per creare le separazioni tra classi. Il requisito per utilizzare questo tipo di classificazione è che i dati siano distribuiti in modo da essere linearmente separabili, come indicato nella figura A qui a lato. Nel caso invece di dati non linearmente separabili, ad esempio la figura B qui a lato, è necessario agire in altro modo.

Una possibile soluzione a questo problema è quello che rappresentato nella figura a fianco.

Partendo dal dataset originale a sinistra, non linearmente separabile, utilizziamo una trasformazione che mappa quei dati in uno spazio a dimensione maggiore. Qui i dati diventano linearmente separabili tramite un iperpiano. Il risultato poi lo mappiamo al contrario sullo spazio originale.

In verità, ferma restando la fattibilità di tale approccio, operativamente parlando mappare il dataset in una dimensione maggiore e, viceversa, rimappare il risultato nello spazio originale richiede una forza di calcolo notevole: come abbiamo già visto potremmo disporre di un dataset formato da decine di proprietà, cioè dimensioni. Uno spazio dove questi dati diventano linearmente separabili potrebbe avere un numero notevole di dimensioni (centinaia, migliaia o più).

Il metodo però non è da buttare. Semplicemente ci serve qualche trucco matematico, come il kernel trick con il quale si utilizza una particolare funzione, detta funzione kernel che consente di ottenere lo stesso risultato che avremmo mappando i dati in uno spazio di dimensione maggiore, ma senza farlo veramente.

Una funzione kernel è sostanzialmente una metrica che ci consente di misurare quanto simili siano due esempi. Esistono numerose funzioni kernel, una delle più famose è Radial Basis Function o Kernel Gaussiano.

Come si vede in figura, se la differenza tra x ed l tende a 0, la funzione tenderà ad 1, mentre se la differenza tra x ed l è alta, la funzione tenderà a 0.

Il parametro σ modifica la forma della campana, rendendola più sottile per valori piccoli e più distesa per valori grandi. In sostanza σ modifica la sensibilità della funzione alle differenze tra x ed l.

Ok, ma ora come la usiamo?

Prendiamo l’esempio del dataset in figura a lato, dove abbiamo due classi (punti verdi e punti rossi) che sono distribuiti in cerchi concentrici, quindi non linearmente separabili.

Poniamo un punto l (da landmark) nel centro dei cerchi ed applichiamo il kernel Gaussiano ad ogni punto del dataset. Supponendo di avere un σ ottimale, otterremo valori della funzione tendenti a 0 per i punti che si allontanano troppo da l (i punti rossi) e valori tendenti a 1 per quelli sufficientemente vicini ad l (i punti verdi).

Quindi la classificazione avverrà confrontando il risultato del kernel con un valore di soglia, semplificando decisamente tutta l’elaborazione. Da notare che questo è lo stesso ragionamento che si usava per una classificazione lineare: il dato in ingresso veniva classificato in un modo o in un altro semplicemente valutando la sua posizione rispetto all’iper-piano di separazione (il decision boundary).

Questo approccio può essere applicato anche a dataset molto più complessi, dove non abbiamo centri concentrici: in pratica avremo più punti landmark ed applicheremo la funzione kernel per ogni esempio e per ogni landmark.

Come abbiamo detto poc’anzi, di funzioni kernel ce ne sono diverse. Le più utilizzate sono:

• il kernel lineare
• il kernel Gaussiano
• il kernel sigmoidale
• il kernel polinomiale

Utilizzando questi (o anche altri più rari e specifici) si possono ottenere modelli molto performanti.

Codice Python

NOTA: il codice di questo esempio lo trovi qui

Prendiamo nuovamente il dataset Iris e, come visto in precedenza, consideriamo solo le prime due proprietà in modo da poter mettere in grafica il dataset e le curve di separazione. La classe da utilizzare per creare il modello di SVM si chiama SVC e tramite il suo parametro kernel possiamo indicare quale tipo di kernel utilizzare (useremo i valori linear, rbf, sigmoid e poly).

# creo la SVM con kernel lineare e la alleno
svm = SVC(kernel="linear")
svm.fit(X_train_std, Y_train)

Anche in questo caso procediamo a calcolare la accuracy e a visualizzare lo spazio dei dati con le curve di separazione.

Partiamo dal kernel lineare.

Kernel lineare su due proprietà
Accuracy Train Set: 0.819047619047619
Accuracy Test Set: 0.8

Vediamo che l’accuracy è già migliore del caso di SVM semplice ed il modello non è in overfitting.

Dobbiamo comunque considerare che stiamo lavorando su due sole dimensioni, per ovvi motivi di visualizzazione dei risultati. Utilizzando tutte le dimensioni, il comportamento potrebbe cambiare radicalmente.

Continuiamo con il kernel Gaussiano.

Kernel Gaussiano su due proprietà
Accuracy Train Set: 0.8095238095238095
Accuracy Test Set: 0.7777777777777778

L’accuracy è peggiorata, ma vi rammento che stiamo forzando l’elaborazione su due dimensioni.

Notiamo anche che le curve di separazione sono ben diverse dal caso precedente, in particolare non sono lineari.

Ora vediamo il caso del kernel sigmoidale.

Kernel sigmoidale su due proprietà
Accuracy Train Set: 0.7238095238095238
Accuracy Test Set: 0.8

Il risultato appare migliore di quello ottenuto con kernel lineare, in quanto l’accuracy del train set è minore rispetto a quella del test set, evidenziando una migliore capacità di generalizzazione.

Le curve di separazione sono notevolmente diverse da quanto visto fin’ora.

Infine vediamo il caso del kernel polinomiale.

Kernel polinomiale su due proprietà
Accuracy Train Set: 0.7619047619047619
Accuracy Test Set: 0.6666666666666666

Il modello appare più scarso degli altri, in questo caso.

Ancora una volta, le curve di separazione appaiono diverse.

Compiti a casa!

Potete sperimentare il comportamento di questi kernel utilizzando tutte le proprietà del dataset Iris o altri dataset che potete trovare in giro per la rete. Magari fatemi anche sapere i risultati che otterrete!

Alla prossima. Bye!