In questo articolo introduciamo una tecnica di machine learning estremamente potente nota come Support Vector Machine (SVM). È una delle migliori tecniche di classificazione supervisionate “fuori dagli schemi”. In quanto tale, è uno strumento importante sia per il ricercatore di trading quantitativo che per il data scientist.
E’ molto importante per un ricercatore quantistico o uno scienziato dei dati essere a proprio agio sia con gli aspetti teorici che con l’uso pratico delle tecniche presenti nella propria cassetta degli attrezzi. Quindi questo articolo costituirà la prima parte di una serie di articoli che approfondiscono le macchine a vettore di supporto. In particolare questo articolo descrive la teoria dei maximal margin classifiers, support vector classifiers e support vector machines. Negli articoli successivi si utilizzerà la libreria scikit-learn di Python per dimostrare alcuni esempi delle suddette tecniche teoriche su dati reali.
Come con qualsiasi classificatore binario supervisionato, il compito di una macchina a vettore di supporto è individuare un confine di separazione (lineare o altro) in uno spazio di elementi in modo tale che le osservazioni successive possano essere automaticamente classificate in gruppi separati. Un buon esempio di questo sistema è classificare un insieme di documenti in gruppi di documenti con sentiment positivi o negativi. Allo stesso modo, potremmo classificare le e-mail in spam o non spam. Gli SVM sono altamente applicabili a tali situazioni.
Procederemo considerando il concetto di un iperpiano di separazione ottimale, che consiste in un semplice tipo di classificatore lineare noto come maximal margin classifier. Mostreremo che spesso non sono applicabili a molte situazioni del “mondo reale” e come tali necessitano di modifiche, che prendono la forma di un classificatore di vettori di supporto (SVC). Abbondoniamo quindi il vincolo della linearità e prenderemo in considerazione classificatori non lineari, ovvero macchine vettoriali di supporto, che utilizzano le funzioni del kernel per migliorare l’efficienza computazionale.
Iperpiano di Separazione Ottimale
Prima di qualsiasi discussione sul funzionamento di un SVC o SVM, è necessario delineare un concetto noto come iperpiano di separazione ottimale (OSH).
Si consideri uno spazio \(p\)-dimensionale a valore reale (ad esempio \(\mathbb{R}^p\)). Un iperpiano di separazione ottimale è essenzialmente uno spazio affine \(p-1\)-dimensionale che vive all’interno del più grande spazio \(p\)-dimensionale. Descriveremo in seguito da dove deriva la “separazione ottimale” presente nel nome.
Nel caso di \(p=2\) questo spazio affine è semplicemente una linea unidimensionale, mentre per \(p=3\) lo spazio affine è un piano bidimensionale (vedi Fig 1 e Fig 2).
\(\begin{eqnarray} \beta_0 + \beta_1 X_1 + … + \beta_p X_p = 0 \end{eqnarray}\)
o equivalentemente:\(\begin{eqnarray} \beta_0 + \sum^{p}_{j=1} \beta_j X_j = 0 \end{eqnarray}\)
Se un elemento \(x\in\mathbb{R}^p\) soddisfa questa relazione allora vive sull’iperpiano latex]p-1[/latex]-dimensionale. Possiamo anche considerare altri punti \(x\) tali che:\(\begin{eqnarray} \beta_0 + \sum^{p}_{j=1} \beta_j X_j > 0 \end{eqnarray}\)
nel qual caso \(x\) si trova sopra l’iperpiano, o\(\begin{eqnarray}\beta_0+\sum^{p}_{j=1}\beta_j X_j <0 \end{eqnarray}\)
in tal caso \(x\) si trova al di sotto dell’iperpiano. Quindi l’iperpiano divide lo spazio \(p\)-dimensionale in due parti (vedi la seguente Figura 3), da cui deriva la “separazione” presente nella denominazione di “iperpiano di separazione ottimale”. Non abbiamo ancora discusso della parte “ottimale”!
Classificazione
Se traduciamo questo in un problema matematico, l’impostazione standard per una procedura di classificazione supervisionata consiste nel considerare un insieme di \(n\) osservazioni di addestramento, \(x_i\), ognuna delle quali è un vettore \(p\)-dimensionale di features. Ogni osservazione di addestramento ha associata un class label, \(y_i\in\{-1,1\}\). Quindi possiamo pensare a \(n\) coppie di osservazioni di addestramento \((x_i, y_i)\) che rappresentano le caratteristiche e le class label (elenchi di parole chiave e spam / non spam). Oltre alle osservazioni di addestramento possiamo fornire osservazioni di prova, \(x^{*}=(x^{*}_1,…,x^{*}_p)\) che vengono successivamente utilizzate per testare le prestazioni dei classificatori. Queste osservazioni di prova sarebbero nuove e-mail che non sono state ancora viste.
Il nostro obiettivo è sviluppare un classificatore, basato sulle osservazioni di addestramento fornite, che classificherà correttamente le successive osservazioni di test utilizzando solo i valori delle loro caratteristiche. Ciò si traduce nella possibilità di classificare un’e-mail come spam o non spam esclusivamente in base alle parole chiave contenute al suo interno. Inizialmente si ipotizza che sia possibile, tramite un mezzo ancora da determinare, costruire un iperpiano che separa perfettamente i dati di addestramento secondo le loro etichette di classe (vedi Fig. 4 e 5). Ciò significherebbe separare in modo pulito le e-mail di spam da quelle non di spam esclusivamente utilizzando specifiche parole chiave. Il diagramma seguente mostra solo \(p=2\), mentre per gli elenchi di parole chiave potremmo avere \(p>10000\). Quindi le figure 4 e 5 sono solo rappresentative del problema.
\(\begin{eqnarray} \beta_0 + \beta_1 X_{i1} + … + \beta_p X_{ip} = \beta_0 + \sum^{p}_{j=1} \beta_j X_{ij} > 0\end{eqnarray}\) , se \(y_i=1\)
e\(\begin{eqnarray} \beta_0 + \beta_1 X_{i1} + … + \beta_p X_{ip} = \beta_0 + \sum^{p}_{j=1} \beta_j X_{ij} < 0\end{eqnarray}\) , se \(y_i=-1\)
Cioè se ogni osservazione di addestramento è sopra o sotto l’iperpiano di separazione, secondo l’equazione geometrica che definisce il piano, la sua etichetta di classe associata sarà \(+1\) o \(-1\). Così abbiamo (potenzialmente) sviluppato un semplice processo di classificazione. Assegniamo un’osservazione di prova ad una classe a seconda del lato dell’iperpiano in cui si trova. Questo può essere formalizzato considerando la seguente funzione \(f(x)\), con un’osservazione di prova \( x^{*} = (X ^ {*} _ 1, …, X ^ {*} _ p)\):\(\begin{eqnarray} f(x^{*}) = \beta_0 + \sum^{p}_{j=1} \beta_j X^{*}_j \end{eqnarray}\)
Se \(f (x ^ {*}) > 0 \) allora \( y ^ {*} = + 1 \), mentre se \( f (x ^ {*}) < 0 \) allora \( y ^ {*} = -1 \).Possiamo anche considerare l’ampiezza della distanza \( f (x) \). Per \( | f (x ^ {*}) | \) molto maggiore di zero possiamo essere sicuri della nostra particolare etichetta di classe, poiché il valore è lontano dall’iperpiano di separazione. Al contrario per \( | f (x ^ {*}) | \) vicino a zero, l’osservazione del test si trova vicino all’iperpiano di separazione e quindi abbiamo meno fiducia nella nostra class label.
Maximal Margin Classifiers
In generale, gli iperpiani di separazione non sono unici, poiché è possibile traslare o ruotare leggermente un iperpiano senza toccare alcuna osservazione di addestramento (vedi Fig 4).
Allora come possiamo decidere qual è il “migliore” iperpiano di separazione o quella più “ottimale”? Possiamo costruire un iperpiano del margine massimo (MMH), che è l’iperpiano di separazione più lontano da qualsiasi osservazione di addestramento.
Come può essere eseguita? In primo luogo, si calcola la distanza perpendicolare da ciascuna osservazione di addestramento \(x_i\) per un dato iperpiano di separazione. La distanza perpendicolare più vicina a un’osservazione di training dall’iperpiano è nota come margine. MMH è l’iperpiano di separazione in cui il margine è il più grande. Ciò garantisce che sia la distanza minima più lontana da un’osservazione di training.
La procedura di classificazione è quindi semplicemente un caso per determinare su quale lato cade un’osservazione di prova. Questo può essere eseguito utilizzando la formula sopra per \(f (x ^ {*})\). Tale classificatore è noto come classificatore del margine massimo (MMC). Dobbiamo sperare che un ampio margine sulla serie di osservazioni di addestramento porti anche a un ampio margine sulle osservazioni di prova, e quindi fornisca un buon tasso di classificazione.
Si noti tuttavia che dobbiamo fare attenzione a evitare l’overfitting quando il numero di dimensioni delle feature è elevato (ad esempio nelle applicazioni di elaborazione del linguaggio naturale come la classificazione dello spam e-mail). In questo caso l’overfitting significa che l’MMH si adatta molto bene ai dati di allenamento, ma può funzionare abbastanza male se esposto ai dati di test. L’obiettivo di tale algoritmo è produrre i valori \(\beta_j\) (cioè correggere la geometria dell’iperpiano) e quindi consentire la determinazione di \(f(x^{*})\) per qualsiasi osservazione di prova.
Se consideriamo la Fig 6, possiamo vedere che la MMH è la linea mediana del “blocco” più largo che possiamo inserire tra le due classi in modo che siano perfettamente separate.
Una delle caratteristiche chiave della MMC (e successivamente della SVC e SVM) è la dipendenza della posizione della MMH solamente dai vettori di supporto, che sono le osservazioni di addestramento che si trovano direttamente sul confine del margine (ma non dell’iperpiano) (vedere i punti A , B e C della Fig 6). Ciò significa che la posizione dell’MMH NON dipende da altre osservazioni di addestramento.
Si può immediatamente osservare come il potenziale svantaggio dell’MMC è che il suo MMH (e quindi le sue prestazioni di classificazione) può essere estremamente sensibile alle posizioni del vettore di supporto.
Costruzione del Maximal Margin Classifier
Ritengo sia istruttivo delineare completamente il problema di ottimizzazione che deve essere risolto per creare l’MMH (e quindi lo stesso MMC). Mentre descriverò i vincoli del problema di ottimizzazione, la soluzione algoritmica a questo problema va oltre lo scopo dell’articolo. Per fortuna queste routine di ottimizzazione sono già implementate all’interno della libreria scikit-learn (in realtà, tramite la libreria LIBSVM).
La procedura per determinare un iperpiano del margine massimo per un classificatore del margine massimo è la seguente. Date \(n\) osservazioni di addestramento \(x_1,…,x_n\in\mathbb{R}^p\) e \(n\) class label \(y_1,…,y_n\in\{- 1,1\}\), l’MMH è la soluzione alla seguente procedura di ottimizzazione:
Massimizza \(M\in\mathbb{R}\), variando \(\beta_1,…,\beta_p\) in modo che:
\(\begin{eqnarray} \sum^{p}_{j=1} \beta^2_j = 1 \end{eqnarray}\)
e
\(\begin{eqnarray} y_i \left( \beta_0 + \sum^{p}_{j=1} \beta_j X_{ij} \right) \geq M, \quad \forall i = 1,…,n \end{eqnarray}\)
Nonostante i complessi vincoli formali, in realtà si afferma che ogni osservazione deve essere sul lato corretto dell’iperpiano e almeno \(M\) di distanza da esso. Poiché l’obiettivo della procedura è massimizzare \(M\), questa è precisamente la condizione necessaria per creare la MMC!
Chiaramente, il caso ideale è la perfetta separabilità. La maggior parte dei dataset del “mondo reale” non avrà una separabilità così perfetta tramite un iperpiano lineare (vedi Fig 7). Tuttavia, se non c’è separabilità, non siamo in grado di costruire un MMC con la procedura di ottimizzazione descritta sopra. Allora, come creiamo una forma di iperpiano separatore?
Essenzialmente dobbiamo approssimare il requisito che un iperpiano di separazione divida perfettamente ogni osservazione di training sul lato corretto della linea (cioè garantisca che sia associata alla sua vera class label), utilizzando quello che viene chiamato margine morbido. Ciò motiva il concetto di un classificatore di vettori di supporto (SVC).
Support Vector Classifiers (SVC)
Come accennato in precedenza, uno dei problemi con il MMC è l’estrema sensibilità all’aggiunta di nuove osservazioni di training.
Si consideri le figure 8 e 9. Nella figura 8 si può vedere che esiste un MMH che separa perfettamente le due classi. Tuttavia, nella Figura 9 se si aggiunge un punto alla classe \(+1\) vediamo che la posizione dell’MMH cambia drasticamente. Quindi in questa situazione l’MMH ha avuto chiaramente un over-fit:
Ecco come funziona un classificatore SVC o a margine morbido. Un SVC consente ad alcune osservazioni di trovarsi sul lato errato del margine (o iperpiano), quindi fornisce una separazione “morbida”. Le seguenti figure 10 e 11 dimostrano che le osservazioni si trovano rispettivamente sul lato sbagliato del margine e sul lato sbagliato dell’iperpiano:
Come prima, un’osservazione viene classificata a seconda del lato dell’iperpiano di separazione su cui si trova, ma alcuni punti possono essere classificati erroneamente.
È istruttivo vedere come la procedura di ottimizzazione differisce da quella sopra descritta per la MMC. Dobbiamo introdurre nuovi parametri, vale a dire i valori \(n\) \(\epsilon_i\) (noti come valori di slack) e un parametro \(C\), noto come budget. Si vuole massimizzare \(M\), attraverso \(\beta_1,…,\beta_p,\epsilon_1,…,\epsilon_n\) in modo che:
\(\begin{eqnarray} \sum^{p}_{j=1} \beta^2_j = 1 \end{eqnarray}\)
e
\(\begin{eqnarray} y_i \left( \beta_0 + \sum^{p}_{j=1} \beta_j X_{ij} \right) \geq M, \quad \forall i = 1,…,n \end{eqnarray}\)
e
\(\begin{eqnarray} \epsilon_i \geq 0, \quad \sum^{n}_{i=1} \epsilon_i \leq C \end{eqnarray}\)
Dove \(C\), il budget, è un parametro di “regolazione” non negativo. \(M\) rappresenta ancora il margine e le variabili slack \(\epsilon_i\) consentono alle singole osservazioni di trovarsi sul lato sbagliato del margine o dell’iperpiano.
In sostanza, \(\epsilon_i\) ci dice dove si trova l’osservazione \(i\)-esima rispetto al margine e all’iperpiano. Per \(\epsilon_i = 0 \) si afferma che l’osservazione di addestramento \(x_i\) si trova sul lato corretto del margine. Per \(\epsilon_i>0\) abbiamo che \(x_i\) è dalla parte sbagliata del margine, mentre per \(\epsilon_i > 1\) abbiamo che \(x_i\) è dalla parte sbagliata dell’iperpiano.
\(C\) controlla collettivamente quanto il singolo \(\epsilon_i\) può essere modificato per violare il margine. \(C = 0 \) implica che \(\epsilon_i = 0, \forall i \) e quindi non è possibile alcuna violazione del margine, nel qual caso (per classi separabili) abbiamo la situazione MMC.
Per \(C>0 \) significa che non più di \(C\) osservazioni possono violare l’iperpiano. All’aumentare di \(C\), il margine aumenterà. Vedi Fig 12 e 13 per due diversi valori di \(C\):
Come scegliamo in pratica \(C\)? In genere questo viene fatto tramite la convalida incrociata. In sostanza \(C\) è il parametro che regola il compromesso di bias-varianza per SVC. Un piccolo valore di \(C\) indica una situazione di basso bias e alta varianza. Un valore elevato di \(C\) indica una situazione di alto bias e bassa varianza.
Come prima, per classificare una nuova osservazione di prova \(x^{*}\) calcoliamo semplicemente il segno di \(f(x^{*})=\beta_0 + \sum^{p}_{i = 1} \beta_j X^{*}_j\).
Tutto questo va bene per le classi che sono separate linearmente (o quasi linearmente). Tuttavia, che dire dei confini di separazione che non sono lineari? Come affrontiamo queste situazioni? È qui che entrano in gioco le macchine a vettore di supporto.
Macchine a Vettori di Supporto
La motivazione dietro l’estensione di una SVC è quella di consentire confini decisionali non lineari. Questo è il dominio della Support Vector Machine (SVM). Si consideri le seguenti figure 14 e 15. In una tale situazione un SVC puramente lineare avrà prestazioni estremamente scarse, semplicemente perché i dati non hanno una chiara separazione lineare:
Quindi le SVC possono essere inutili in problemi di confine di classe altamente non lineari.
Per motivare il funzionamento di una SVM, possiamo considerare un “trucco” standard nella regressione lineare, quando si considerano situazioni non lineari. In particolare un insieme di \(p\) caratteristiche \(X_1, …, X_p\) può essere trasformato, diciamo, in un insieme di \(2p\) caratteristiche \(X_1, X^2_1, …, X_p, X^2_p \). Questo ci permette di applicare una tecnica lineare a un insieme di caratteristiche non lineari.
Mentre il confine di decisione è lineare nel nuovo spazio degli elementi \(2p\)-dimensionale, non è lineare nello spazio \(p\)-dimensionale originale. Il risultato è un confine di decisione dato da \( q(x)=0\) dove \(q\) è una funzione polinomiale quadratica delle features originali, cioè è una soluzione non lineare.
Questo chiaramente non è limitato ai polinomi quadratici. Potrebbero essere presi in considerazione polinomi di dimensione superiore, termini di interazione e altre forme funzionali. Anche se lo svantaggio è che aumenta notevolmente la dimensione dello spazio delle features al punto che alcuni algoritmi possono diventare non trattabili.
Il vantaggio principale degli SVM consiste in un ampliamento non lineare dello spazio delle funzionalità, pur mantenendo una significativa efficienza computazionale, utilizzando un processo noto come “metodo kernel“, che verrà delineato di seguito.
Allora cosa sono gli SVM? In sostanza sono un’estensione di SVC che risulta dall’ampliamento dello spazio delle features attraverso l’uso di funzioni note come kernel. Per capire i kernel, dobbiamo discutere brevemente alcuni aspetti della soluzione al problema di ottimizzazione SVC delineato sopra.
Durante il calcolo della soluzione al problema di ottimizzazione SVC, l’algoritmo deve solamente fare uso di prodotti interni tra le osservazioni e le loro stesse non-osservazioni. Ricorda che per due \(p\)-vettori dimensionali \(u, v\) un prodotto interno è definito come:
\(\begin{eqnarray} \langle u,v \rangle = \sum^{p}_{i=1} u_i v_i \end{eqnarray}\)
Quindi per due osservazioni un prodotto interno è definito come:
\(\begin{eqnarray} \langle x_i,x_k \rangle = \sum^{p}_{j=1} x_{ij} x_{kj} \end{eqnarray}\)
Anche se non ci soffermeremo sui dettagli (poiché esulano dallo scopo di questo articolo), è possibile mostrare che un classificatore di vettore di supporto lineare per una particolare osservazione \(x\) può essere rappresentato come una combinazione lineare di prodotti interni:
\(\begin{eqnarray} f(x) = \beta_0 + \sum^{n}_{i=1} \alpha_i \langle x, x_i \rangle \end{eqnarray}\)
Con i coefficienti \(n\) e \(\alpha_i\(, uno per ciascuna delle osservazioni di addestramento.
Per stimare i coefficienti \(\)\beta_0\(\) e \(\)\alpha_i\) dobbiamo solo calcolare \({n \choose 2} = n(n-1)/2\) prodotti interni tra tutte le coppie di osservazioni di addestramento. In effetti, dobbiamo SOLO calcolare i prodotti interni per il sottoinsieme di osservazioni di addestramento che rappresentano i vettori di supporto. Chiamerò questo sottoinsieme \(\mathscr{S}\). Ciò significa che:
\(\begin{eqnarray} \alpha_i = 0 \enspace \text{if} \enspace x_i \notin \mathscr{S} \end{eqnarray}\)
Quindi possiamo riscrivere la formula di rappresentazione come:
\(\begin{eqnarray} f(x) = \beta_0 + \sum_{i \in \mathscr{S}} \alpha_i \langle x, x_i \rangle \end{eqnarray}\)
Questo risulta essere un grande vantaggio per l’efficienza computazionale.
Questo motiva l’estensione agli SVM. Se consideriamo il prodotto interno \(\langle x_i, x_k \rangle\) e lo sostituiamo con la più generale funzione “kernel” del prodotto interno \(K = K(x_i, x_k) \), possiamo modificare la rappresentazione SVC per usare le funzioni non lineari del kernel e quindi modificare il modo in cui calcoliamo la “somiglianza” tra due osservazioni. Ad esempio, per ripristinare l’SVC, prendiamo solo \(K\) come segue:
\(\begin{eqnarray} K(x_i, x_k) = \sum^{p}_{j=1} x_{ij} x_{kj} \end{eqnarray}\)
Poiché questo kernel è lineare nelle sue caratteristiche, l’SVC è noto come SVC lineare. Possiamo anche considerare kernel polinomiali, di grado \(d\):
\(\begin{eqnarray} K(x_i, x_k) = (1 + \sum^{p}_{j=1} x_{ij} x_{kj})^d \end{eqnarray}\)
Ciò fornisce un confine decisionale significativamente più flessibile ed essenzialmente equivale ad adattare una SVC in uno spazio di caratteristiche di dimensione superiore che coinvolge polinomi di \(d\) gradi delle caratteristiche (vedi la Figura 16).
Quindi, la definizione di una macchina vettoriale di supporto è un classificatore di vettori di supporto con una funzione kernel non lineare. Possiamo anche considerare il popolare kernel radiale (vedi Fig 17):
\(\begin{eqnarray} K(x_i, x_k) = \exp \left(-\gamma \sum^{p}_{j=1} (x_{ij} – x_{kj})^2 \right), \quad \gamma > 0 \end{eqnarray}\)
Allora come funzionano i kernel radiali? Sono chiaramente abbastanza diversi dai kernel polinomiali. Essenzialmente se la nostra osservazione di prova \(x^{*}\) è lontana da un’osservazione di addestramento \(x_i\) nella distanza euclidea standard, allora la somma \(\sum^{p}_{j=1} (x^{*}_j-x_{ij})^2\) sarà grande e quindi \(K(x^{*}, x_i)\) sarà molto piccolo. Questa particolare osservazione di addestramento \(x_i\) non avrà quasi alcun effetto sulla posizione dell’osservazione di prova \(x^{*}\), tramite \(f(x^{*})\).
Quindi il kernel radiale ha un comportamento estremamente localizzato e solo le osservazioni di addestramento vicine a \(x^{*}\) avranno un impatto sulla sua class label.
Per rendere concreta la teoria di cui sopra, negli articoli successivi eseguiremo classificazioni di esempio utilizzando la libreria scikit-learn di Python.
