Sottoclasse | Algoritmo di classificazione ( d ) |
---|---|
Acronimo | (in) SVM |
Inventori | Vladimir Vapnik , Alexeï Tchervonenkis |
Descritto da | Automazione e controllo remoto ( in ) |
Le macchine supportano vettori o separatori wide margin (inglese support vector machines , SVM) sono un insieme di tecniche di apprendimento supervisionato per risolvere problemi di discriminazione e regressione . Gli SVM sono una generalizzazione dei classificatori lineari .
I separatori ad ampio margine sono stati sviluppati negli anni '90 dalle considerazioni teoriche di Vladimir Vapnik sullo sviluppo di una teoria statistica dell'apprendimento: la teoria di Vapnik-Chervonenkis . Hanno rapidamente adottato per la loro capacità di lavorare con dati di grandi dimensioni , il basso numero di iperparametri , le loro garanzie teoriche e buoni risultati nella pratica.
SVM è stato applicato a numerosi campi ( bioinformatica , recupero di informazioni , visione artificiale , finanza ...). Secondo i dati, le prestazioni delle macchine a vettori di supporto sono dello stesso ordine, o anche migliori, di quelle di una rete neurale o di un modello misto gaussiano .
I separatori a largo margine si basano su due idee chiave: la nozione di margine massimo e la nozione di funzione del kernel. Questi due concetti esistevano da diversi anni prima di essere messi insieme per costruire SVM.
L'idea degli iperpiani a margine massimo è stata esplorata già nel 1963 da Vladimir Vapnik e A. Lerner, e nel 1973 da Richard Duda e Peter Hart nel loro libro Pattern Classification . Le basi teoriche degli SVM furono esplorate da Vapnik e colleghi negli anni '70 con lo sviluppo della teoria di Vapnik-Chervonenkis e dalla teoria dell'apprendimento di Valiant e PAC .
Anche l'idea delle funzioni del kernel non è nuova: il teorema di Mercer risale al 1909 e l'utilità delle funzioni del kernel nel contesto dell'apprendimento automatico è stata dimostrata già nel 1964 da Aizermann, Bravermann e Rozoener.
Tuttavia, non è stato fino al 1992 che queste idee sono state pienamente comprese e riunite da Boser, Guyon e Vapnik in un articolo, che è l'articolo fondante dei separatori ad ampio margine. L'idea delle variabili primaverili, che ha permesso di risolvere alcuni importanti limiti pratici, è stata introdotta solo nel 1995 . Da questa data, che corrisponde alla pubblicazione del libro di Vapnik, gli SVM stanno guadagnando popolarità e vengono utilizzati in molte applicazioni.
Un brevetto statunitense sugli SVM è stato depositato nel 1997 dagli inventori originali.
I separatori ad ampio margine sono classificatori che si basano su due idee chiave, che consentono di affrontare problemi di discriminazione non lineare e di riformulare il problema di classificazione come un problema di ottimizzazione quadratica .
La prima idea chiave è il concetto di margine massimo . Il margine è la distanza tra il confine di separazione e i campioni più vicini. Questi sono chiamati vettori di supporto . Negli SVM, il confine di separazione viene scelto come quello che massimizza il margine. Questa scelta è giustificata dalla teoria di Vapnik-Chervonenkis (o teoria statistica dell'apprendimento), che mostra che la frontiera di separazione del margine massimo ha la capacità più piccola . Il problema è trovare questo confine di divisione ottimale, da un set di allenamento. Ciò viene fatto formulando il problema come un problema di ottimizzazione quadratica, per il quale esistono algoritmi noti.
Per poter affrontare casi in cui i dati non sono separabili linearmente, la seconda idea chiave degli SVM è trasformare lo spazio di rappresentazione dei dati di input in uno spazio di dimensione maggiore (possibilmente di dimensione infinita), in cui è probabile che ci sia una separazione lineare. Ciò si ottiene grazie ad una funzione kernel , che deve rispettare le condizioni del teorema di Mercer , e che ha il vantaggio di non richiedere la conoscenza esplicita della trasformazione da applicare per il cambiamento di spazio. Le funzioni del kernel consentono di trasformare un prodotto dot in uno spazio ampio, che è costoso, in una semplice valutazione una tantum di una funzione. Questa tecnica è nota come trucco del kernel .
Gli SVM possono essere utilizzati per risolvere problemi di discriminazione, ovvero decidere a quale classe appartiene un campione o regressione , ovvero prevedere il valore numerico di una variabile. La risoluzione di questi due problemi implica la creazione di una funzione che abbina un vettore di input a un output :
Ci limitiamo per il momento ad un problema di discriminazione a due classi (discriminazione binaria), cioè il vettore di input essendo in uno spazio X provvisto di un prodotto scalare . Possiamo prendere ad esempio .
Il caso semplice è il caso di una funzione discriminante lineare, ottenuta dalla combinazione lineare del vettore di input , con un vettore peso :
Si decide quindi che è di classe 1 se e di classe -1 altrimenti. È un classificatore lineare .
Il confine di decisione è un iperpiano , chiamato iperpiano separatore o separatore . L'obiettivo di un algoritmo di apprendimento supervisionato è apprendere la funzione h (x) attraverso un set di addestramento:
×dove sono le etichette, è la dimensione del set di addestramento, la dimensione dei vettori di input. Se il problema è separabile linearmente, si deve quindi avere:
Immagina un piano (spazio bidimensionale) in cui sono distribuiti due gruppi di punti. Questi punti sono associati a un gruppo: i punti (+) per y > x e i punti (-) per y < x . Possiamo trovare un ovvio separatore lineare in questo esempio, la linea di equazione y = x . Si dice che il problema sia separabile linearmente .
Per problemi più complicati, di solito non c'è un separatore lineare. Ad esempio, immagina un piano in cui i punti (-) sono raggruppati all'interno di un cerchio, con punti (+) tutt'intorno: nessun separatore lineare può separare correttamente i gruppi: il problema non è separabile linearmente . Non esiste un iperpiano di separazione.
Ci si pone d'ora in poi nel caso in cui il problema sia separabile linearmente. Anche in questo semplice caso la scelta dell'iperpiano separatore non è scontata. Esiste infatti un numero infinito di iperpiani separatori, le cui prestazioni di apprendimento sono identiche (il rischio empirico è lo stesso), ma le cui prestazioni di generalizzazione possono essere molto diverse. Per risolvere questo problema, è stato dimostrato che esiste un unico iperpiano ottimale, definito come iperpiano che massimizza il margine tra i campioni e l'iperpiano di separazione.
Ci sono ragioni teoriche per questa scelta. Vapnik ha dimostrato che la capacità delle classi di iperpiani di separazione diminuisce all'aumentare del loro margine.
Il margine è la distanza tra l'iperpiano e i campioni più vicini. Questi sono chiamati vettori di supporto . L'iperpiano che massimizza il margine è dato da:
Si tratta quindi di trovare w e w 0 che soddisfano queste condizioni, al fine di determinare l'equazione dell'iperpiano di separazione:
Il margine è la distanza più piccola tra i campioni di addestramento e l'iperpiano separatore che soddisfa la condizione di separabilità (cioè come spiegato in precedenza). La distanza di un campione x k dall'iperpiano è data dalla sua proiezione ortogonale sul vettore peso:
.L'iperpiano di separazione (w, w 0 ) del margine massimo è quindi dato da:
Per facilitare l' ottimizzazione , scegliamo di normalizzare w e w 0 , in modo che i campioni a margine ( per i vettori di supporto sul bordo positivo, e per quelli situati sul bordo opposto) soddisfino:
Quindi per tutti i campioni,
Questa normalizzazione è talvolta chiamata forma canonica dell'iperpiano o iperpiano canonico .
Con questo ridimensionamento, il margine ora ne vale la pena , quindi si tratta di massimizzare . La cosiddetta formulazione primaria degli SVM viene quindi espressa nella seguente forma:
Questo può essere risolto con il metodo classico dei moltiplicatori di Lagrange , dove la lagrangiana è data da:
La lagrangiana deve essere minimizzata rispetto a w e w 0 , e massimizzata rispetto ad α.
Doppia formulazioneCancellando le derivate parziali della Lagrangiana, secondo le condizioni di Kuhn-Tucker , si ottiene:
Reiniettando questi valori nell'equazione , otteniamo la doppia formulazione :
Questo dà i moltiplicatori di Lagrange ottimali .
Per ottenere la soluzione iperpiano, sostituiamo w con il suo valore ottimale w * , nell'equazione iperpiano , che dà:
ConseguenzeLa nozione di margine massimo e la procedura per la ricerca dell'iperpiano di separazione presentata per il momento consentono solo di risolvere problemi di discriminazione separabili linearmente. Questa è una limitazione severa che ti condanna a poter risolvere solo problemi di giocattoli, o molto specifici. Per affrontare il problema della mancanza di separatore lineare, l'idea di trick kernel (in inglese metodo kernel ) è riconsiderare il problema in uno spazio di dimensione superiore, possibilmente infinita. In questo nuovo spazio è quindi probabile che ci sia una separazione lineare.
Più formalmente, applichiamo una trasformazione non lineare ai vettori di input x . Lo spazio di arrivo è chiamato spazio di ridescrizione . In questo spazio cerchiamo quindi l'iperpiano
chi controlla
, per tutti i punti del training set, vale a dire l'iperpiano di separazione nello spazio di ridescrizione.Utilizzando la stessa procedura del caso senza trasformazione, si ottiene il seguente problema di ottimizzazione:
Il problema con questa formulazione è che implica un prodotto scalare tra vettori nello spazio di ridescrizione, di dimensioni elevate, che è costoso in termini di calcoli. Per risolvere questo problema, utilizziamo un trucco noto come trucco del kernel , che consiste nell'usare una funzione del kernel , che controlla:
da qui l'espressione dell'iperpiano separatore in funzione della funzione kernel:
L'interesse della funzione kernel è duplice:
In pratica, non conosciamo la trasformazione , costruiamo invece direttamente una funzione del kernel. Questa deve rispettare determinate condizioni, deve corrispondere a un prodotto scalare in uno spazio di grandi dimensioni. Il teorema di Mercer esplicita le condizioni che devono soddisfare per essere una funzione centrale: deve essere simmetrica, semidefinita positiva.
L'esempio più semplice di una funzione del kernel è il kernel lineare:
Torniamo quindi al caso di un classificatore lineare , senza cambio di spazio. L'approccio del trucco del kernel quindi generalizza l'approccio lineare. Il kernel lineare viene talvolta utilizzato per valutare la difficoltà di un problema.
I kernel comuni utilizzati con SVM sono:
In generale, inoltre, non è possibile trovare un separatore lineare nello spazio di ridescrizione. È anche possibile che i campioni siano etichettati in modo errato e che l'iperpiano del separatore non sia la soluzione migliore al problema di classificazione.
Nel 1995, Corinna Cortes e Vladimir Vapnik hanno proposto una tecnica chiamata margine flessibile , che tollera cattive classifiche. La tecnica ricerca un iperpiano di separazione che minimizzi il numero di errori grazie all'introduzione di variabili elastiche ( variabili slack in inglese), che permettono di allentare i vincoli sui vettori di apprendimento:
Con i vincoli precedenti, il problema di ottimizzazione viene modificato da un termine di penalità, che penalizza le variabili di alta molla:
dove è una costante che consente di controllare il trade-off tra il numero di errori di classificazione e l'ampiezza del margine. Deve essere scelto dall'utente, in generale tramite una ricerca esaustiva nello spazio dei parametri, utilizzando ad esempio la validazione incrociata sul training set. La scelta automatica di questo parametro di regolarizzazione è un grosso problema statistico.
Sono stati proposti diversi metodi per estendere il diagramma di cui sopra nel caso in cui si debbano separare più di due classi. Questi schemi sono applicabili a qualsiasi classificatore binario e quindi non sono specifici per SVM. I due più noti sono chiamati uno contro tutti e uno contro uno . Formalmente, i campioni di apprendimento e test possono essere classificati qui in classi .
Il metodo uno contro tutti (a volte chiamato uno contro tutto ) consiste nel costruire classificatori binari assegnando l'etichetta 1 ai campioni di una delle classi e l'etichetta -1 a tutte le altre. Nella fase di test, il classificatore che dà il valore di confidenza più alto (es. Il margine) vince il voto.
Il metodo uno contro uno consiste nel costruire classificatori binari confrontando ciascuna delle classi. In fase di test, il campione da classificare viene analizzato da ciascun classificatore e un voto a maggioranza permette di determinarne la classe. Se annotiamo il campione da classificare e il classificatore SVM separando la classe e la classe e restituendo l'etichetta assegnata al campione da classificare, allora l'etichetta assegnata a può essere annotata formalmente . Questa è la classe a cui verrà assegnata più spesso quando sarà stata analizzata da tutti . Potrebbe esserci un'ambiguità nel risultato del conteggio, se non c'è voto di maggioranza
Una generalizzazione di questi metodi è stata proposta nel 1995 sotto il nome di ECOC , consistente nel rappresentare gli insiemi di classificatori binari come codici su cui possono essere applicate le tecniche di correzione degli errori .
Questi metodi soffrono tutti di due difetti. Nella versione uno contro tutti nulla indica che i valori del risultato di classificazione dei classificatori siano confrontabili (nessuna normalizzazione, quindi possibili problemi di scala). Inoltre, il problema non è più bilanciato, ad esempio con M = 10, solo il 10% degli esempi positivi viene utilizzato per il 90% degli esempi negativi.
Vladimir Vapnik , Harris Drucker, Chris Burges, Linda Kaufman e Alex Smola hanno proposto nel 1996 un metodo per utilizzare gli SVM per risolvere i problemi di regressione.
Troviamo una presentazione in francese della classificazione per macchine a vettori di supporto in: