Macchine a vettori di supporto

Da Wikipedia, l'enciclopedia libera.
(Reindirizzamento da Macchina a vettori di supporto)
Jump to navigation Jump to search
Esempio di separazione lineare, usando le SVM.

Le macchine a vettori di supporto (SVM, dall'inglese Support-Vector Machines) sono dei modelli di apprendimento supervisionato associati ad algoritmi di apprendimento per la regressione e la classificazione. Dato un insieme di esempi per l'addestramento (training set), ognuno dei quali etichettato con la classe di appartenenza fra le due possibili classi, un algoritmo di addestramento per le SVM costruisce un modello che assegna i nuovi esempi ad una delle due classi, ottenendo quindi un classificatore lineare binario non probabilistico. Un modello SVM è una rappresentazione degli esempi come punti nello spazio, mappati in modo tale che gli esempi appartenenti alle due diverse categorie siano chiaramente separati da uno spazio il più possibile ampio. I nuovi esempi sono quindi mappati nello stesso spazio e la predizione della categoria alla quale appartengono viene fatta sulla base del lato nel quale ricade.

Oltre alla classificazione lineare è possibile fare uso delle SVM per svolgere efficacemente la classificazione non-lineare utilizzando il metodo kernel, mappando implicitamente i loro input in uno spazio delle feature multi-dimensionale.

Quando gli esempi non sono etichettati è impossibile addestrare in modo supervisionato e si rende necessario l'apprendimento non supervisionato, questo approccio cerca di identificare i naturali cluster in cui si raggruppano i dati, mappando successivamente i nuovi dati nei cluster ottenuti. L'algoritmo di clustering a vettori di supporto, creato da Hava Siegelmann e Vladimir N. Vapnik, applica le statistiche dei vettori di supporto, sviluppate negli algoritmi delle SVM, per classificare dati non etichettati, ed è uno degli algoritmi di clustering maggiormente utilizzato nelle applicazioni industriali.

Motivazioni[modifica | modifica wikitesto]

Le macchine a vettori di supporto possono essere pensate come una tecnica alternativa per l'apprendimento di classificatori polinomiali, contrapposta alle tecniche classiche di addestramento delle reti neurali artificiali.

Le reti neurali ad un solo strato hanno un algoritmo di apprendimento efficiente, ma sono utili soltanto nel caso di dati linearmente separabili. Viceversa, le reti neurali multistrato possono rappresentare funzioni non lineari, ma sono difficili da 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 un problema di ottimizzazione non convesso e non vincolato che, di conseguenza, presenta 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 della rete sono ottenuti mediante la soluzione di un problema di programmazione quadratica convesso con vincoli di uguaglianza o di tipo box (in cui il valore del parametro deve essere mantenuto all'interno di un intervallo), che prevede un unico minimo globale.

Definizione[modifica | modifica wikitesto]

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, i mapping utilizzati dalle SVM sono fatti in modo tale che i prodotti scalari dei vettori delle coppie di punti in input 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 feature . Con tale scelta dell'iperpiano, i punti nello spazio delle feature che sono mappati nell'iperpiano sono definiti dalla relazione . Si noti che se diventa più piccolo al crescere di rispetto ad , 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[modifica | modifica wikitesto]

L'originale algoritmo SVM è stato inventato da Vladimir N. Vapnik e Alexey Ya. Chervonenkis nel 1963. Nel 1992 Bernhard E. Boser, Isabelle M. Guyon e Vladimir N. 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 leggero fu invece proposto da Corinna Cortes e Vapnik nel 1993 e pubblicato nel 1995.

SVM lineare[modifica | modifica wikitesto]

Classificazione non lineare[modifica | modifica wikitesto]

Calcolo del classificatore SVM[modifica | modifica wikitesto]

Minimizzazione del rischio empirico[modifica | modifica wikitesto]

Estensioni[modifica | modifica wikitesto]

  • Support vector clustering (SVC)
  • SVM Multiclasse
  • SVM trasduttiva
  • SVM strutturata
  • Regressione

Utilizzi[modifica | modifica wikitesto]

Alcune applicazioni per cui le SVM sono state utilizzate con successo sono:

Implementazioni[modifica | modifica wikitesto]

I seguenti framework mettono a disposizione un'implementazione di SVM:

Note[modifica | modifica wikitesto]

Bibliografia[modifica | modifica wikitesto]

  • Stuart Russell e Peter Norvig, Intelligenza artificiale: un approccio moderno, Prentice Hall, 2003, ISBN 88-7192-229-8

Voci correlate[modifica | modifica wikitesto]

Altri progetti[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

Controllo di autoritàLCCN (ENsh2008009003 · GND (DE4505517-8 · BNF (FRcb16627142b (data)