Support Vector Machine

L’SVM è un algoritmo di classificazione strettamente binario, cioè è direttamente applica- bile solamente a problemi di classificazione a due classi.

Il processo decisionale avviene mediante la rappresentazione del dataset di addestramento in uno spazio multidimensionale, determinato in modo che gli elementi appartenenti alle due categorie siano separati da un iperpiano. L’SVM poi predice la classe di appartenenza dei nuovi elementi a seconda che essi si trovino da una parte o dall’altra dell’iperpiano nello spazio creato dal modello. Per questo motivo, l’SVM è un algoritmo non probabilistico, cioè durante il processo di inferenza non assegna agli elementi una probabilità di appartenere ad una classe: la determina in modo categorico.

A volte il dataset di addestramento mostra già inizialmente una chiara separazione tra le due classi in una specifica direzione (Fig. 5.4). In questo caso esse sono dette linearmente separabili ed è possibile calcolare l’iperpiano senza ulteriori trasformazioni del dataset. Questo tipo di SVM viene definito lineare.

Quando ciò non è possibile, i vettori delle feature degli elementi vengono mappati in uno spa- zio a dimensione maggiore, da un’opportuna funzione non lineare, detta funzione di kernel, scelta appositamente in modo che nel nuovo spazio le due classi siano meglio separabili. In questo caso si parla di SVM non lineare.

40 5 − Algoritmi di Machine Learning

Figura 5.4:Esempio in cui le due classi sono chiaramente separabili nello spazio delle feature. Il piano H3è quello a massima distanza dagli elementi più vicini delle due classi.

Implementazione dell’algoritmo SVM lineare

Descrivendo il problema in modo più formale, il dataset di addestramento può essere visto come un insieme di N vettori reali di feature #»xip-dimensionali a ciascuno dei quali è assegnata una classe yi = ±1.

L’algoritmo SVM ricerca l’iperpiano H (a dimensione p-1) che meglio separa gli elementi appartenenti a ciascuna delle due classi. Se le due classi sono linearmente separabili in più direzioni, viene scelto l’iperpiano che massimizza la distanza tra esso e gli elementi più vicini di ciascuna classe (Fig.5.4).

Un qualsiasi iperpiano può essere definito dall’equazione: #»

w·#»x −b=0 (5.4.10) Dove #»w è un vettore normale all’iperpiano (cioè ne determina la direzione) e il parametro b/||#»w||ne determina lo spostamento dall’origine lungo la direzione identificata dal vettore #»w. Supponendo che le due classi siano linearmente separabili è possibile definire due iperpiani paralleli che separano le due classi in modo tale che la distanza tra loro sia la massima possibile (Fig. 5.5). Essi possono essere definiti dallo stesso vettore normale #»w come:

#»

w·#»x −b= +1 (5.4.11) #»

w·#»x −b= −1 (5.4.12) La distanza che li separa è 2/||w#»||, pertanto per massimizzarla è necessario minimizzare il valore di||w#»||.

§5.4 − Algoritmi di ML utilizzati 41

Figura 5.5:I due iperpiani tratteggiati automaticamente definiscono l’iperpiano di miglior separazione.

Date queste premesse, si può formulare il problema della ricerca di #»w con i seguenti step: • Fissare come vincolo che le due classi siano interamente contenute nella parte di spazio

delimitata da uno dei due iperpiani: #»

w·x#»i−b≥ +1 ∀xi|yi = +1 (5.4.13) #»

w·x#»i−b≤ −1 ∀xi|yi = −1 (5.4.14) Questo può essere riscritto come:

yi(w#»·x#»i−b) ≥ +1 ∀xi (5.4.15) • Minimizzare||w#»||soggetto al vincolo in Eq. 5.4.15.

• Impostare che l’iperpiano ricercato abbia l’equazione #»w·#»x −b=0

E’ importante notare che l’iperpiano ricercato da SVM è interamente definito dai punti #»xi delle due classi che gli sono più vicini, detti anche vettori di supporto (support vectors). Ci sono poi i casi in cui le classi non sono completamente separabili da un iperpiano. Per estendere l’SVM a queste situazioni è possibile definire una funzione di costo:

max(0, 1−yi(~w· ~xi−b)) (5.4.16) Questa funzione è zero per i punti che soddisfano l’Eq. 5.4.15 (cioè per quelli che si trovano dalla parte giusta dell’iperpiano), mentre per gli altri è proporzionale alla loro distanza dall’iperpiano.

42 5 − Algoritmi di Machine Learning

La funzione da minimizzare diventa dunque: " 1 n n

∑

Dove il parametro λ rappresenta il compromesso tra avere classi sufficientemente separate e accettare la presenza di punti incorrettamente classificati. Per piccoli valori di λ l’algoritmo cercherà di separare al meglio le classi.

L’operazione di inferenza della classe y di un generico vettore #»x è dunque rappresentata dal semplice calcolo di y=sign(#»x ·w#»−b).

Implementazione dell’algoritmo SVM non lineare

Quando i dati non sono linearmente separabili nello spazio p-dimensionale delle feature, è possibile proiettarli su uno spazio a maggiore dimensione, dove le probabilità di individuare un iperpiano tra le due classi sono maggiori (Fig. 5.6). La dimensionalità dello spazio viene aumentata utilizzando una funzione non lineare delle feature pre-esistenti.

Dal momento che calcolare le trasformate di ogni vettore del dataset di addestramento nel nuovo spazio potrebbe essere computazionalmente molto costoso, ci si limita a calcolare i prodotti scalari tra i vari vettori (visto che sono l’unica cosa che è realmente necessaria all’algoritmo) senza definire formalmente la trasformazione.

Le funzioni che definiscono i prodotti scalari tra due vettori k(#»xi, #»xj)sono dette funzioni di kernel e le più utilizzate sono:

• Kernel polinomiale omogeneo: k(~xi,~xj) = (~xi· ~xj)d

• Kernel polinomiale non omogeneo: k(~xi,~xj) = (~xi· ~xj+1)d

• Kernel gaussiano radiale: k(~xi,~xj) =exp(−γk~xi− ~xjk2), con γ>0 • Kernel iperbolico: k(~xi,~xj) =tanh(κ~xi· ~xj+c)

Figura 5.6:Le coppie(x, y), non separabili linearmente in questo spazio, vengono proiettate nello spazio(x, y, x2+y2), dove risultano nettamente divise lungo l’asse z.

Il kernel è legato alle trasformate φ(#»x) dei vettori nel nuovo spazio dalla relazione k(#»xi, #»xj) =φ(#»xi) ·φ(#»xj). Si noti che una esplicita rappresentazione di φ(#»x)non è necessa- ria, fintanto che lo spazio definito da essa sia dotato di prodotto scalare.

§5.4 − Algoritmi di ML utilizzati 43

definire nello spazio individuato da φ(#»x)una misura tale per cui k rappresenti un prodotto scalare propriamente definito.

La conoscenza della funzione k è sufficiente a determinare l’iperpiano in questo nuovo spazio, dal momento che è definito dai prodotti scalari φ(w#») ·φ(x#»i) =k(w, #»#» xi).

La classe y di un generico vettore #»x non appartenente al dataset di addestramento è data da y=sign(k(#»x , #»w) −b).

Vantaggi e svantaggi

I classificatori SVM sono molto efficaci quando il numero di feature è elevato, anche quan- do è superiore al numero di elementi nel dataset di addestramento, inoltre rappresentano una buona soluzione per risolvere problemi predittivi, in quanto mirano a massimizzare la distanza tra le due classi.

Tuttavia le performance degli SVM tendono a dipendere molto dalla scelta del kernel (che ovviamente, se non lineare, comporta una perdita di generalità dei risultati).

Inoltre hanno una complessità computazionale molto elevata, richiedono una notevole quan- tità di memoria e i risultati del modello generato possono essere complessi da interpretare. Infine sono applicabili solo a problemi di classificazione binaria, pertanto un problema a più classi, per essere affrontato con un SVM, va scomposto in una serie di problemi a binari.

CAPITOLO6

Analisi degli Outlier

In statistica, un outlier è un elemento di un dataset particolarmente distante dalle altre registrazioni. La sua anomalia può essere dovuta a una forte eterogeneità del campione o a errori sperimentali di acquisizione.

Nel secondo caso ovviamente tale dato deve essere rigettato.

Infatti, specialmente le analisi statistiche sono profondamente influenzate dalla presenza di outlier, ad esempio, le regressioni tendono ad adattare la forma della funzione che meglio approssima i dati alla presenza di valori anomali e quindi in parte li nascondono, a discapito della qualità generale del fit.

Inoltre nel caso specifico di questa tesi, che si propone di classificare con algoritmi di appren- dimento supervisionato soggetti sani e affetti da Autismo a partire da valori anatomici delle loro regioni cerebrali, è particolarmente importante avere un dataset il più possibile privo di elementi anomali, che potrebbero rappresentare essi stessi una logica di classificazione "confondente".

Infine è importante avere una stima fin dall’inizio della qualità dei dati. Infatti se essi possono essere fortemente compromessi dal metodo di acquisizione o del preprocessamento a cui sono stati sottoposti, ci si può aspettare un elevano numero di outlier e questo complica l’identificazione stessa di tali dati per cui diventa necessario adottare accorgimenti specifici.

46 6 − Analisi degli Outlier

6.1

Riconoscimento degli outlier

Gli outlier possono presentarsi essenzialmente in due modi: univariati e multivariati. Gli outlier univariati sono elementi di un dataset che presentano un valore di una particolare va- riabile molto diverso dalla norma, mentre gli outlier multivariati sono quegli elementi per cui un particolare gruppo di variabili presenta valori che non risultano anomali per nessuna delle variabili prese singolarmente, ma che lo sono visti nel loro insieme. I metodi per identificare le due tipologie di outlier sono ovviamente diversi tra loro, dovendo analizzare situazioni differenti; le principali tecniche utilizzate per riconoscere questi elementi all’interno di un dataset sono descritte di seguito, è importante però osservare che tutte queste metodologie si basano su alcune conoscenze a priori del campione o della distribuzione statistica che esso dovrebbe seguire.