Skip to content
Torna ai risultati

Boosting Semi-Supervisionato

Introdotto da
Mallapragada, P. K.; Bennett, K. P.; and others
Anno
1999–2009
Tipo
Semi-supervised ensemble method
Famiglia
Machine learning

Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese

Dimensione del carattere

A cosa serve?

Il Boosting Semi-Supervisionato è un paradigma di apprendimento d'insieme (ensemble learning) che estende gli algoritmi di boosting classici — come AdaBoost — per sfruttare sia i dati etichettati che quelli non etichettati.

Propagando le informazioni sulle etichette attraverso una struttura di similarità sulle istanze non etichettate, esso addestra classificatori più robusti rispetto al solo boosting supervisionato quando i dati etichettati sono scarsi.

L’intuizione alla base del metodo

Il boosting classico si concentra iterativamente sugli esempi etichettati mal classificati. Il boosting semi-supervisionato aggiunge una nuova dimensione: utilizza la struttura geometrica dei dati non etichettati per inferire etichette "soft" o per ripesare gli esempi. Intuitivamente, se due punti non etichettati sono molto simili tra loro, dovrebbero ricevere la stessa etichetta. Incorporando questa pressione di consistenza negli aggiornamenti dei pesi del boosting, l'ensemble può generalizzare meglio anche quando è disponibile solo una manciata di esempi etichettati. Il risultato è un modello che prende segnale dalla maggioranza non etichettata pur essendo guidato dalla minoranza etichettata.

Storia

L'idea di combinare il boosting con dati non etichettati è emersa alla fine degli anni '90, con Bennett e Demiriz (1999) tra i primi a esplorare strategie di ensemble semi-supervisionate. L'algoritmo SemiBoost, formalizzato da Mallapragada et al. in un articolo IEEE TPAMI del 2009, è diventato il riferimento canonico per il boosting semi-supervisionato basato su grafo. Lavori successivi hanno esteso il framework a contesti multi-classe e lo hanno collegato alla teoria della regolarizzazione di varietà (manifold regularization), stabilendo il boosting semi-supervisionato come una baseline standard nella letteratura sull'apprendimento semi-supervisionato.

Quando usarlo

Il Boosting Semi-Supervisionato è appropriato quando i dati etichettati sono scarsi e costosi da ottenere, ma è prontamente disponibile un pool più ampio di dati non etichettati — comune nell'annotazione di immagini mediche, nella categorizzazione del testo e nel monitoraggio basato su sensori. È più adatto per compiti di classificazione binaria o multi-classe in cui l'assunto di cluster o varietà (manifold) è plausibilmente valido (input simili condividono etichette). Evitarlo quando i dati non etichettati non sono rappresentativi della distribuzione di test, quando l'assunto di cluster è implausibile (ad esempio, dati provenienti da processi fondamentalmente diversi), o quando il set etichettato è già sufficientemente grande da saturare un booster supervisionato — in tal caso, il semplice gradient boosting eguaglierà o supererà le sue prestazioni con molta meno complessità.

Limiti e considerazioni

  • Le prestazioni degradano drasticamente se i dati non etichettati non condividono la stessa distribuzione dei dati etichettati (dataset shift).
  • Il rumore delle pseudo-etichette può accumularsi attraverso i round di boosting, portando all'amplificazione dell'errore quando le previsioni iniziali sono scarse.
  • La costruzione del grafo di similarità richiede la scelta della larghezza di banda del kernel o del numero di vicini, che è sensibile e richiede validazione.
  • Il costo computazionale è sostanzialmente più elevato rispetto al boosting supervisionato a causa della costruzione del grafo e del ricalcolo delle pseudo-etichette ad ogni round.

Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.

Punti di forza

  • Sfrutta abbondanti dati non etichettati per migliorare l'accuratezza oltre quanto supportato dal solo set etichettato.
  • Eredita le solide prestazioni empiriche e la flessibilità dei framework di boosting come AdaBoost.
  • La struttura di similarità basata su grafo rende la propagazione delle etichette interpretabile e sintonizzabile.
  • Funziona con qualsiasi learner base che accetti pesi di istanza, mantenendo il framework modulare.
  • Supera costantemente il boosting puramente supervisionato in regimi a basso tasso di etichettatura, documentato in esperimenti di benchmark.

Applicazioni

  • Classificazione di testi e documenti dove i corpora etichettati sono piccoli ma sono disponibili grandi corpora non etichettati.
  • Classificazione di immagini mediche con immagini limitate annotate da esperti insieme a grandi archivi non etichettati.
  • Categorizzazione di contenuti web che sfrutta la struttura del grafo di hyperlink come fonte di similarità.
  • Rilevamento di guasti industriali con abbondanti letture di sensori ma pochi eventi di guasto etichettati manualmente.
  • Compiti di bioinformatica come la previsione della funzione proteica con scarse annotazioni validate.

Come funziona

Come funziona

1

Un classificatore base — tipicamente uno stump di decisione (decision stump) o un albero poco profondo — viene addestrato sulla porzione etichettata del dataset. Questo fornisce l'ipotesi iniziale e imposta il framework di boosting. Tutte le istanze etichettate ricevono pesi uniformi in questo primo round.

2

Viene costruita una similarità a coppie o un grafo sui dati combinati etichettati e non etichettati, spesso utilizzando un kernel a funzione di base radiale (RBF) o un grafo k-nearest-neighbor. Questo codifica l'assunto che punti vicini nello spazio delle feature abbiano probabilmente la stessa classe.

3

Utilizzando l'attuale modello d'insieme e il grafo di similarità, vengono assegnate pseudo-etichette "soft" alle istanze non etichettate. I punti vicini a esempi etichettati classificati con confidenza ereditano le loro etichette; i punti vicini ai confini di decisione ricevono pseudo-etichette a bassa confidenza e contribuiscono meno all'aggiornamento.

4

L'attuale weak learner viene adattato sul dataset aumentato — esempi etichettati più quelli non etichettati con pseudo-etichette — utilizzando la distribuzione dei pesi del boosting. Il peso del learner alpha_t viene calcolato dall'errore pesato, esattamente come in AdaBoost, ma l'errore pesato ora riflette i contributi sia dalle istanze etichettate che da quelle non etichettate.

Formula
F_t(x) = F_{t-1}(x) + \alpha_t h_t(x)
5

I pesi delle istanze vengono aggiornati in modo che gli esempi mal classificati dall'attuale learner ricevano un peso maggiore nel round successivo. Per le istanze non etichettate, l'aggiornamento del peso è modulato dalla confidenza della pseudo-etichetta: le pseudo-etichette ad alta confidenza vengono pesate maggiormente come gli esempi etichettati, mentre quelle a bassa confidenza vengono pesate meno per limitare la propagazione del rumore.

6

Dopo T round di boosting, la previsione finale è il segno del voto a maggioranza pesata di tutti i weak learner. L'ensemble combina il segnale della supervisione etichettata e le informazioni strutturali propagate dai dati non etichettati in un unico, robusto confine di decisione.

Formula
\hat{y} = \text{sign}\left(\sum_{t=1}^{T} \alpha_t h_t(x)\right)

Errori comuni

  • Assumere che i dati non etichettati siano rappresentativi senza verificare la sovrapposizione distributiva con gli esempi etichettati.
  • Utilizzare troppi round di boosting con pseudo-etichette rumorose, causando l'overfitting del modello ad assegnazioni "soft" errate.
  • Ignorare la sintonizzazione degli iperparametri del grafo (larghezza di banda del kernel, k in k-NN) — una scarsa qualità del grafo invalida l'intero passo di propagazione.
  • Riportare solo l'accuratezza senza metriche stratificate (F1, AUC) quando il set etichettato è sbilanciato per classe.
  • Saltare un set di test etichettato "held-out" e valutare sullo stesso pool etichettato utilizzato per inizializzare le pseudo-etichette.

Domande frequenti

Quando il boosting semi-supervisionato supera il semplice AdaBoost?

Più affidabilmente quando il set etichettato è molto piccolo — tipicamente meno di qualche centinaio di esempi per classe — e i dati non etichettati sono abbondanti e tratti dalla stessa distribuzione. Con set etichettati grandi, il divario si riduce e il boosting supervisionato standard è più semplice e veloce.

Come dovrei costruire il grafo di similarità?

Un kernel a funzione di base radiale (RBF) con larghezza di banda sintonizzata tramite cross-validazione sul set etichettato è la scelta più comune. I grafi k-nearest-neighbor sono un'alternativa più semplice. Il criterio chiave è che il grafo dovrebbe connettere esempi della stessa classe e separare cluster di classi diverse nel modo più pulito possibile.

Quale learner base funziona meglio?

Gli stump di decisione (alberi di profondità 1) sono la scelta standard, coerente con il classico AdaBoost. Gli alberi poco profondi (profondità 2-4) possono migliorare l'accuratezza quando il confine di decisione è complesso, ma aumentano il rischio di fare eccessivo affidamento su pseudo-etichette rumorose.

Quanti round di boosting sono necessari?

Iniziare con 100-200 round e monitorare l'errore di validazione etichettato. A differenza del boosting puramente supervisionato, l'aggiunta di troppi round può amplificare il rumore delle pseudo-etichette, quindi l'early stopping su un piccolo set di validazione etichettato è fortemente raccomandato.

Lo sbilanciamento delle classi è un problema?

Sì. Quando il pool etichettato è sbilanciato per classe, le previsioni iniziali sono distorte e le pseudo-etichette propagheranno tale distorsione al set non etichettato. Ripesare le classi etichettate prima dell'addestramento o sovracampionare la classe minoritaria per mitigare questo problema.

Metodi correlati

Fonti

  1. Mallapragada, P. K., Jin, R., Jain, A. K., & Liu, Y. (2009). SemiBoost: Boosting for Semi-supervised Learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 31(11), 2000–2014.

    Apri il riferimento DOI
    Copiato.
  2. Bennett, K. P., & Demiriz, A. (1999). Semi-supervised Support Vector Machines. Advances in Neural Information Processing Systems (NIPS), 11, 368–374.

    Apri il riferimento della pubblicazione
    Copiato.