Support Vector Machine Semi-Supervised (S3VM)
- Introdotto da
- Joachims, T.
- Anno
- 1999
- Tipo
- Semi-supervised classifier
- Famiglia
- Machine learning
Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese
A cosa serve?
Il Support Vector Machine Semi-Supervised (S3VM) estende il classico SVM incorporando grandi quantità di dati non etichettati accanto a un piccolo set di addestramento etichettato.
Cerca un iperpiano a margine massimo che non solo separi gli esempi etichettati, ma passi anche attraverso regioni a bassa densità della distribuzione completa dei dati, producendo una migliore generalizzazione quando i campioni etichettati sono scarsi.
L’intuizione alla base del metodo
Un SVM standard apprende un confine basandosi esclusivamente su punti etichettati. L'S3VM osserva che i dati non etichettati portano ancora informazioni geometriche su dove i cluster di dati sono densi e dove si diradano. Richiedendo che il confine decisionale eviti regioni ad alta densità — indipendentemente dal fatto che tali punti abbiano etichette o meno — il modello può sfruttare la maggioranza non etichettata per affinare il confine che altrimenti traccerebbe basandosi solo su una manciata di esempi etichettati. Il risultato è un margine che rispetta la struttura sottostante dei dati, non solo le etichette note.
Storia
Le fondamenta dell'S3VM furono poste da Vapnik nel suo primo lavoro sull'inferenza trasduttiva, ma il metodo divenne ampiamente adottato dopo che Joachims (1999) ne dimostrò l'efficacia per la classificazione del testo sotto il nome di Transductive SVM. Il trattamento completo in Chapelle, Scholkopf e Zien (2006) consolidò l'S3VM accanto ad altri approcci semi-supervisionati e rimane il riferimento standard. Lavori successivi introdussero rilassamenti convessi e risolutori scalabili per affrontare le sfide computazionali e degli ottimi locali del metodo originale.
Quando usarlo
L'S3VM è la scelta giusta quando i dati etichettati sono costosi o scarsi (ad esempio, meno di qualche centinaio di esempi) ma sono disponibili abbondanti dati non etichettati — uno scenario comune nella classificazione del testo, nella bioinformatica o in qualsiasi dominio in cui l'annotazione è costosa. Funziona al meglio quando l'assunzione del cluster (cluster assumption) è valida: le classi formano cluster distinti e il confine decisionale si trova in una regione a bassa densità. Evitare l'S3VM quando i dati etichettati sono già abbondanti (un SVM standard eguaglierà o supererà le sue prestazioni a un costo inferiore), quando l'assunzione del cluster è violata (le classi si sovrappongono pesantemente nello spazio delle caratteristiche), o quando la distribuzione non etichettata diverge dalla distribuzione etichettata, il che può spingere il confine nella direzione sbagliata.
Limiti e considerazioni
- L'ottimizzazione non è convessa a causa delle pseudo-etichette, rendendola sensibile all'inizializzazione e incline a ottimi locali.
- Il costo computazionale scala male con il numero di esempi non etichettati — grandi pool non etichettati diventano costosi.
- Si basa sull'assunzione del cluster; se le classi non formano cluster ben separati, i dati non etichettati possono degradare le prestazioni.
- Richiede un'attenta messa a punto del peso della perdita etichettata C e del peso della perdita non etichettata C*, aggiungendo complessità alla selezione del modello.
Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.
Punti di forza
- Sfrutta efficacemente grandi set di dati non etichettati per migliorare la generalizzazione quando gli esempi etichettati sono scarsi.
- Eredita le garanzie di margine massimo e la flessibilità del kernel degli SVM standard.
- Adatto a dati sparsi ad alta dimensionalità come il testo, dove i corpora non etichettati sono abbondanti.
- Esistono estensioni probabilistiche (Gaussian Process S3VM) e varianti kernel per confini non lineari.
- Accuratezza competitiva in regimi con pochi dati etichettati rispetto alle alternative puramente supervisionate.
Applicazioni
- Classificazione di testi e documenti con pochi esempi di addestramento etichettati.
- Compiti di bioinformatica come la predizione della funzione proteica, dove la marcatura sperimentale è costosa.
- Categorizzazione di pagine web sfruttando ampi corpora strisciati ma non annotati.
- Analisi di immagini mediche dove l'etichettatura da parte di esperti richiede tempo e denaro.
- Qualsiasi problema di classificazione ad alta dimensionalità con dati non etichettati abbondanti e etichette scarse.
Come funziona
Come funziona
Un SVM iniziale viene adattato sugli esempi etichettati disponibili, apprendendo un confine decisionale e un margine preliminari. Questo fornisce un modello di partenza e previsioni iniziali per il pool non etichettato, fondando la successiva ottimizzazione semi-supervisionata su una soluzione supervisionata.
L'SVM preliminare assegna etichette di classe provvisorie (pseudo-etichette) a tutti gli esempi non etichettati in base al lato della corrente confine su cui cadono. Queste pseudo-etichette consentono ai punti non etichettati di partecipare alla massimizzazione del margine anche se la loro vera classe è sconosciuta.
L'obiettivo centrale dell'S3VM minimizza congiuntamente la perdita a cerniera (hinge loss) sugli esempi etichettati e la pseudo-perdita a cerniera (pseudo-hinge loss) sugli esempi non etichettati, massimizzando al contempo il margine. Un parametro di bilanciamento C* controlla quanto fortemente i punti non etichettati influenzano il confine, bilanciando lo sfruttamento della struttura nei dati non etichettati e l'adattamento alla verità di base etichettata.
Formula
\min_{w,b,y^*} \frac{1}{2}\|w\|^2 + C\sum_{i}\xi_i + C^*\sum_{j}\xi_j^*Poiché le pseudo-etichette potrebbero essere errate, l'algoritmo itera: riassegna le pseudo-etichette utilizzando il confine aggiornato e risolve nuovamente l'ottimizzazione congiunta. Scambiando esempi non etichettati erroneamente assegnati alla classe opposta e ri-ottimizzando, il confine si sposta progressivamente verso le lacune a minore densità nei dati.
Una volta raggiunta la convergenza, i nuovi esempi vengono classificati dal segno della funzione decisionale lineare appresa. L'iperpiano risultante è posizionato in una regione a bassa densità della distribuzione completa dei dati, offrendo una migliore generalizzazione su esempi tenuti da parte (held-out) rispetto a un SVM puramente supervisionato addestrato sullo stesso piccolo set etichettato.
Formula
f(x) = \text{sign}(w^\top x + b)Errori comuni
- Presuppone che i dati non etichettati aiutino sempre — se l'assunzione del cluster è violata, l'S3VM può performare peggio di un SVM supervisionato.
- Utilizzare un C* molto grande rispetto a C, sovra-pesando i punti non etichettati e permettendo al confine di allontanarsi dal segnale etichettato.
- Non validare su un set etichettato tenuto da parte, rendendo impossibile rilevare quando i dati non etichettati hanno peggiorato le prestazioni.
- Applicare l'S3VM quando i dati etichettati e non etichettati provengono da distribuzioni diverse (covariate shift), il che viola le assunzioni del metodo.
Domande frequenti
In che modo l'S3VM differisce da un SVM standard?
Un SVM standard utilizza solo dati etichettati per posizionare il suo confine decisionale. L'S3VM incorpora inoltre esempi non etichettati richiedendo che il confine passi attraverso regioni a bassa densità della distribuzione completa dei dati, migliorando la generalizzazione quando i dati etichettati sono scarsi.
Cos'è l'assunzione del cluster e perché è importante?
L'assunzione del cluster afferma che il confine decisionale si trova in una regione di bassa densità dei dati, il che significa che le classi formano cluster separabili. L'S3VM sfrutta questo aspetto allontanando il confine dalle regioni dense. Se le classi si sovrappongono pesantemente, questa assunzione fallisce e i dati non etichettati possono fuorviare il modello.
Come scelgo il peso non etichettato C*?
C* controlla quanto fortemente gli esempi non etichettati influenzano il margine. Una strategia comune è iniziare con C* molto più piccolo di C e aumentarlo gradualmente monitorando l'accuratezza di validazione su un piccolo set etichettato tenuto da parte, fermandosi prima che le prestazioni degradino.
L'S3VM può gestire confini non lineari?
Sì. Come gli SVM standard, l'S3VM supporta funzioni kernel (RBF, polinomiale, ecc.) che mappano implicitamente i dati in spazi a dimensionalità superiore dove un confine lineare diventa non lineare nello spazio delle caratteristiche originale.
Quando dovrei preferire il self-training o la propagazione delle etichette rispetto all'S3VM?
Il self-training è più semplice da implementare e scala meglio con grandi pool non etichettati; preferirlo quando le risorse computazionali sono limitate. La propagazione delle etichette funziona bene su dati strutturati a grafo. L'S3VM è preferito quando si desiderano garanzie di margine massimo e si ritiene che l'assunzione del cluster sia soddisfatta.
Metodi correlati
Fonti
Joachims, T. (1999). Transductive Inference for Text Classification using Support Vector Machines. Proceedings of the 16th International Conference on Machine Learning (ICML), 200–209.
Apri il riferimento della pubblicazioneCopiato.Chapelle, O., Scholkopf, B., & Zien, A. (Eds.). (2006). Semi-Supervised Learning. MIT Press.
ISBN: 978-0-262-03358-9Copiato.