Le macchine a vettori di supporto (SVM, dall'inglese support-vector machines o networks) sono dei modelli di apprendimento supervisionato associati ad algoritmi di apprendimento per la regressione e la classificazione.

Dato un insieme di esempi di addestramento, ognuno dei quali etichettato con la classe di appartenenza fra due possibili classi, l'algoritmo di addestramento per le SVM costruisce un modello che assegna i nuovi esempi a una delle due classi, ottenendo quindi un classificatore lineare binario non probabilistico. Un modello SVM lavora su una rappresentazione degli esempi come punti nello spazio, mappati in modo tale che gli esempi appartenenti alle due diverse categorie siano chiaramente separati con un margine il più possibile ampio. Nuovi esempi saranno mappati nello stesso spazio e la predizione della categoria alla quale essi appartengono viene fatta sulla base del lato nel quale ricadono.

Oltre alla classificazione lineare è possibile fare uso delle SVM per risolvere problemi non linearmente separabili, utilizzando il kernel trick, comune ai metodi kernel, ossia mappando implicitamente i dati di input su uno spazio di caratteristiche multidimensionale nel quale si possono applicare modelli lineari, essendo la soluzione basata sul prodotto scalare in tale spazio codificato dalla funzione kernel . Le SVM possono essere usate anche per la regressione, utilizzando opportune funzioni obiettivo ε-sensbili.

Con dati non etichettati non è possibile addestrare in modo supervisionato e si rende necessario ricorrere all'apprendimento non supervisionato: questo approccio mira a identificare classi naturali in cui si raggruppino i dati, mappando successivamente nuove istanze ai gruppi identificati. L'algoritmo di raggruppamento a vettori di supporto, ideato da Hava Siegelmann e Vladimir Vapnik, applica le statistiche dei vettori di supporto, sviluppate per gli algoritmi relativi alle SVM, per classificare dati non etichettati, e rappresenta uno degli algoritmi di raggruppamento maggiormente utilizzati in ambito industriali.

Motivazioni Le macchine a vettori di supporto possono essere pensate come una tecnica alternativa per l'apprendimento di classificatori non lineari, contrapposti alle classiche reti neurali artificiali. Le reti neurali a un solo strato (cfr. il percettrone) prevedono algoritmi di apprendimento efficiente, ma risultano utili soltanto nel caso di dati linearmente separabili. Viceversa, le reti neurali (percettroni) multistrato possono rappresentare funzioni non lineari, ma risultano più difficili d'addestrare a causa dell'alto numero di dimensioni dello spazio dei pesi e poiché le tecniche più diffuse, come la back-propagation, permettono di ottenere i pesi della rete risolvendo problemi di ottimizzazione non convessi e non vincolati che, di conseguenza, presentano un numero indeterminato di minimi locali.

La tecnica di addestramento SVM risolve entrambi i problemi: presenta un algoritmo efficiente ed è in grado di rappresentare funzioni non lineari complesse. I parametri caratteristici del modello sono ottenuti mediante la risoluzione di un problema di programmazione quadratica convesso con vincoli di uguaglianza o di tipo boxed (in cui il valore del parametro deve essere mantenuto all'interno di un intervallo), che prevede un unico minimo globale.

Definizione Formalmente, una macchina a vettori di supporto costruisce un iperpiano o un insieme di iperpiani in uno spazio a più dimensioni o a infinite dimensioni, il quale può essere usato per classificazione, regressione e altri scopi come il rilevamento delle anomalie. Intuitivamente una buona separazione si può ottenere dall'iperpiano che ha la distanza maggiore dal punto (del training set) più vicino di ognuna delle classi; in generale maggiore è il margine fra questi punti, minore è l'errore di generalizzazione commesso dal classificatore.

Mentre il problema originale può essere definito in uno spazio di finite dimensioni, spesso succede che gli insiemi da distinguere non siano linearmente separabili in quello spazio. Per questo motivo è stato proposto che lo spazio originale di dimensioni finite venisse mappato in uno spazio con un numero di dimensioni maggiore, rendendo presumibilmente più facile trovare una separazione in questo nuovo spazio. Per mantenere il carico computazionale accettabile, le mappature utilizzate dalle SVM sono fatte in modo tale che i prodotti scalari dei vettori delle coppie di punti in ingresso siano calcolati facilmente in termini delle variabili dello spazio originale, attraverso la loro definizione in termini di una funzione kernel scelta in base al problema da risolvere. Gli iperpiani in uno spazio multidimensionale sono definiti come l'insieme di punti il cui prodotto scalare con un vettore in quello spazio è costante, dove tale insieme di vettori è un insieme ortogonale (e quindi minimale) di vettori che definiscono un iperpiano. I vettori che definiscono gli iperpiani possono essere scelti come combinazioni lineari con parametri delle immagini dei vettori delle caratteristiche . Con tale scelta dell'iperpiano, i punti nello spazio delle caratteristiche che sono mappati nell'iperpiano sono definiti dalla relazione . Si noti che se diventa più piccolo al crescere di rispetto a , ogni termine della somma misura il grado di vicinanza del punto di test al corrispondente punto di base . Si noti che l'insieme di punti mappato in un qualsiasi iperpiano può produrre un risultato piuttosto complicato, permettendo discriminazioni molto più complesse fra insiemi non completamente convessi nello spazio originario.

Storia L'algoritmo SVM originale è stato inventato da Vladimir Vapnik e Aleksej Červonenkis nel 1963.

Nel 1992 Bernhard Boser, Isabelle Guyon e lo stesso Vapnik suggerirono un modo per creare un classificatore non lineare applicando il metodo kernel all'iperpiano con il massimo margine. Lo standard corrente che propone l'utilizzo di un margine soft (non rigido) fu invece proposto da Corinna Cortes e Vapnik nel 1993 e pubblicato nel 1995 . Un modello analogo è costituito dalla cosiddetta -SVM.

SVM lineare Sia dato un training set di punti della forma

dove le sono o , per indicare la classe di appartenenza del punto . Ciascun è un vettore -dimensionale di numeri reali. Si vuole trovare "l'iperpiano di massimo margine" che divida il gruppo di punti per i quali da quello per cui , definito in modo che la distanza fra l'iperpiano e il punto più vicino per ciascun gruppo risulti massimale.

Un iperpiano si può scrivere come insieme di punti che soddisfano

dove un vettore normale (non necessariamente normalizzato) rispetto all'iperpiano. Tale forma è molto simile alla forma normale di Hesse, tranne per il fatto che non è necessariamente un vettore unitario. Il parametro determina lo scarto dell'iperpiano dall'origine lungo il vettore normale .

Spesso nella letteratura sull'argomento si definisce un termine noto in modo che

Margine rigido Se i dati di training sono linearmente separabili, si possono scegliere due iperpiani paralleli che separino le due classi di dati, in modo che la distanza fra di essi sia la più grande possibile. La regione limitata da tali due iperpiani sarà il "margine", e l'iperpiano di margine massimo è quello che si trova compreso fra di essi equidistante da entrambi. Con un dataset normalizzato o standardizzato, tali iperpiani possono essere descritti attraverso le equazioni

(ciascun punto su questo limite o al di sopra di esso è di una classe, con etichetta 1)

e

(ciascun punto su questo limite o al di sopra di esso è di una classe, con etichetta −1).

Geometricamente, la distanza fra questi due iperpiani è , quindi per massimizzare la distanza fra i piani si deve minimizzare . La distanza viene calcolata come distanza da un punto all'equazione del piano. Si deve anche evitare che i punti ricadano nel margine, perciò si aggiunge il vincolo seguente: per ogni si ha se oppure se Tali vincoli stabiliscono che ogni punto debba trovarsi sul lato corretto del margine. Ciò si può riscrivere anche come

Si ottiene così il seguente problema di ottimizzazione:

I valori di e che risolvono tale problema determinano il classificatore finale, , dove è la funzione segno.

Una conseguenza importante di questa descrizione geometrica è che l'iperpiano di massimo margine viene completamente determinato dai che si trovano più vicini ad esso. Essi sono i vettori di supporto.

Margine Flessibile Per estendere la SVM a casi nei quali i dati non siano linearmente separabili, è d'aiuto la funzione di perdita a cerniera o hinge loss:

Si noti che è l' i-esimo obiettivo (ossia, in tal caso, 1 o -1), e è l' i-esimo output.

Questa funzione è nulla se i vincoli del problema sono soddisfatti, in altre parole, se si trova sul lato corretto del margine. Per dati sul lato sbagliato del margine, il valore della funzione è proporzionale alla distanza dal margine.

L'obiettivo dell'ottimizzazione è allora di minimizzare:

dove il parametro determina il compromesso fra l'aumento delle dimensioni del margine e assicurare che si trovi sul lato corretto del margine (Si noti che si può aggiungere un peso a entrambi i termini nella equazione sopra). Decostruendo la hinge loss, questo problema di ottimizzazione può essere riformulato come segue:

Pertanto, per grandi valori di , si comporterà in modo simile a una SVM a margine rigido, se i dati di input sono linearmente classificabili, ma comunque imparerà se una regola di classificazione sia valida o meno.

Classificazione non lineare

L'algoritmo originale dell'iperpiano di massimo margine proposto da Vapnik nel 1963 costruiva un classificatore lineare. Tuttavia, nel 1992, Bernhard Boser, Isabelle Guyon e Vladimir Vapnik suggerivano un modo per creare classificatori non lineari applicando il "trucco del kernel" (proposto originariamente da Aizerman et al.) a iperpiani di massimo margine. Il trucco del kernel, in cui i prodotti scalari sono sostituiti con kernel, si deriva facilmente nella rappresentazione duale del problema risolto dalla SVM. Ciò consente all'algoritmo di adattare un iperpiano a massimo margine in uno spazio delle caratteristiche trasformato. La trasformazione può essere non lineare e lo spazio trasformato ad alte dimensioni; sebbene il classificatore sia un iperpiano nello spazio delle caratteristiche trasformato, potrebbe essere non lineare nello spazio di input originario.

È da rimarcare che lavorare in uno spazio a maggiori dimensioni space incrementa l'errore di generalizzazione delle SVM, sebbene con un numero di esempi sufficiente l'algoritmo si comporta ancora bene.

Fra i kernel più comuni ci sono: il polinomiale (omogeneo): . In particolare, quando , si ha il kernel lineare. il polinomiale (non omogeneo): . la funzione radiale di base gaussiana: for . A volte parametrizzata usando . la funzione sigmoide (tangente iperbolica): per qualche (non tutti) e .

Il kernel è correlato con la trasformazione tramite l'equazione . Il valore è anche nello spazio trasformato space, con . I prodotti scalari con per la classificazione possono di nuovo essere calcolati tramite kernel trick, cioè .

Calcolo del classificatore SVM Il calcolo del classificatore SVM (con margine flessibile) richiede la minimizzazione di un'espressione della forma

Ci si focalizzerà sui classificatori a margine flessibile poiché, come detto in precedenza, scegliendo un valore di sufficientemente piccolo si ottiene anche la versione a margine rigido utile nel caso di dati di input linearmente separabili. Nel seguito verrà descritto in dettaglio l'approccio classico, che richiede la riduzione dell'equazione precedente a un problema di programmazione quadratica.

Primale Il problema di minimizzazione descritto nella formula precedente può essere riscritto come problema di ottimizzazione con vincoli usando una funzione obiettivo differenziabile nel modo nel seguito descritto.