Label Propagation
- Introdotto da
- Zhu, X. & Ghahramani, Z.
- Anno
- 2002
- Tipo
- Graph-based semi-supervised classification
Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese
A cosa serve?
Label Propagation è un algoritmo di apprendimento semi-supervisionato basato su grafi, introdotto da Zhu e Ghahramani nel 2002, che diffonde le etichette di classe da un piccolo insieme di nodi etichettati a un ampio insieme di nodi non etichettati, diffondendo iterativamente informazioni sulle etichette lungo gli archi di un grafo di similarità, sfruttando la struttura della varietà dei dati.
L’intuizione alla base del metodo
Immagina un social network in cui a poche persone sono state già assegnate delle categorie. Le voci si diffondono naturalmente: ogni persona tende ad adottare l'etichetta più comune tra i propri vicini prossimi. Label Propagation formalizza questa intuizione: costruisce un grafo pesato in cui punti dati simili sono connessi da archi forti, quindi lascia che le etichette note fluiscano gradualmente fino a quando ogni punto non etichettato ha assorbito abbastanza segnale per essere classificato. Poiché la diffusione segue la geometria dei dati piuttosto che confini decisionali arbitrari, può produrre previsioni altamente accurate anche quando gli esempi etichettati sono scarsi.
Storia
Xiaojin (Jerry) Zhu e Zoubin Ghahramani hanno introdotto Label Propagation in un rapporto tecnico della Carnegie Mellon University del 2002 (CMU-CALD-02-107). L'anno successivo, Zhu, Ghahramani e John Lafferty hanno pubblicato il quadro strettamente correlato dei campi Gaussiani e delle funzioni armoniche all'ICML 2003, fornendo un'interpretazione probabilistica tramite passeggiate casuali e campi casuali di Markov Gaussiani. Questi lavori hanno catalizzato un'ondata di metodi semi-supervisionati basati su grafi per tutti gli anni 2000. Dengyong Zhou e colleghi hanno proposto Label Spreading nel 2004 — una variante regolarizzata che consente alle informazioni sulle etichette di sovrascrivere parzialmente le etichette fissate, offrendo robustezza alle annotazioni rumorose. Entrambi i metodi sono ora benchmark standard nell'apprendimento semi-supervisionato e sono inclusi in librerie di machine learning ampiamente utilizzate. Con l'ascesa delle reti neurali su grafi negli anni 2010, Label Propagation è diventato un precursore concettuale e un baseline competitivo, ancora citato per la sua semplicità e le garanzie in forma chiusa.
Quando usarlo
Label Propagation è appropriato quando gli esempi etichettati sono scarsi rispetto alla dimensione totale del dataset, i dati hanno una struttura di cluster o di varietà sottostante che un grafo di similarità può catturare, e c'è motivo di credere che l'assunzione di regolarità sia valida — che punti vicini (nello spazio delle caratteristiche) tendono a condividere la stessa etichetta. Scenari tipici includono la categorizzazione del testo con pochi documenti annotati, la classificazione di immagini con etichette umane sparse e la classificazione di nodi di rete. Il metodo richiede che il grafo sia connesso (o almeno che ogni nodo non etichettato sia raggiungibile da un nodo etichettato). Non è adatto quando lo spazio delle caratteristiche non riflette la similarità semantica, quando il confine decisionale attraversa regioni dense, o quando tutti i dati sono già etichettati.
Limiti e considerazioni
- Scalabilità: memorizzare e operare su una matrice di pesi n x n è proibitivo per dataset di grandi dimensioni senza approssimazioni sparse.
- La costruzione del grafo è sensibile alla scelta della larghezza di banda del kernel sigma e della dimensione del vicinato k; scelte errate degradano sostanzialmente l'accuratezza.
- Assume l'assunzione di regolarità (cluster): violarla — quando i confini decisionali attraversano regioni dense — porta a una classificazione errata sistematica.
- Trasduttivo per impostazione predefinita: le previsioni per nuovi punti di test non visti richiedono la riesecuzione dell'algoritmo o un'estensione induttiva.
- Il rumore delle etichette sui pochi nodi etichettati si propaga e può corrompere una grande porzione del grafo.
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 i dati non etichettati, producendo una forte accuratezza con pochissimi esempi etichettati.
- Garanzia di convergenza in forma chiusa: l'aggiornamento iterativo raggiunge sempre un punto fisso unico.
- Gestisce naturalmente problemi multiclasse senza modifiche.
- Interpretazione geometrica intuitiva basata sulla diffusione di grafi e sull'analisi armonica.
- Nessun parametro del modello da ottimizzare oltre alle scelte di costruzione del grafo (larghezza di banda del kernel, dimensione del vicinato).
Applicazioni
- Classificazione di testi e documenti quando solo una piccola frazione di documenti contiene etichette assegnate manualmente.
- Annotazione di immagini o video dove l'etichettatura manuale è costosa e le immagini non etichettate sono abbondanti.
- Classificazione di nodi in social network e grafi di citazioni (ad esempio, inferire interessi degli utenti o argomenti di articoli).
- Bioinformatica: predizione della funzione genica o dei ruoli di interazione proteica da reti biologiche parzialmente annotate.
- Rilevamento di anomalie semi-supervisionato propagando etichette normali/anomale note attraverso un grafo di similarità.
Come funziona
Come funziona
Viene costruito un grafo di similarità pesato su tutti gli n punti dati, sia etichettati che non etichettati. Una scelta comune è il kernel Gaussiano (RBF): il peso dell'arco W_ij è una funzione decrescente della distanza Euclidea al quadrato tra i punti i e j, controllata da un parametro di larghezza di banda sigma. Vengono mantenuti solo i k vicini più prossimi o quelli entro un raggio epsilon, in modo che il grafo rimanga sparso.
Formula
W_{ij} = \exp\!\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right)La matrice dei pesi W viene normalizzata per colonna per produrre una matrice di transizione T stocastica per righe, dove ogni elemento T_ij rappresenta la probabilità che le informazioni sull'etichetta fluiscano dal nodo j al nodo i. Ciò garantisce che l'influenza totale ricevuta da ciascun nodo sommi a uno.
Formula
T_{ij} = \frac{W_{ij}}{\sum_k W_{kj}}Partendo da una matrice di etichette iniziale F (una colonna per classe), l'algoritmo itera: moltiplica F per T, quindi fissa le righe corrispondenti ai nodi etichettati alle loro vere etichette one-hot Y_L. Questo fissaggio impedisce alle etichette note di deviare e agisce come una condizione al contorno assorbente. L'iterazione viene ripetuta finché le voci non etichettate di F non convergono.
Formula
F^{(t+1)} = T F^{(t)}, \quad F_L = Y_L \text{ (clamp labeled rows after each step)}La soluzione al punto fisso per il blocco non etichettato F_U* è data in forma chiusa come (I - T_UU)^{-1} T_UL Y_L, dove T_UU è la sottomatrice delle transizioni tra nodi non etichettati e T_UL cattura le transizioni dai nodi etichettati a quelli non etichettati. In pratica, la versione iterativa è preferita per grafi di grandi dimensioni perché evita l'inversione della matrice; entrambi i percorsi producono la stessa soluzione unica.
Formula
F_U^* = (I - T_{UU})^{-1} T_{UL} Y_LErrori comuni
- Utilizzo di un grafo completamente connesso senza sparsificazione, che oscura la struttura locale ed è computazionalmente intrattabile su larga scala.
- Scelta di sigma per impostazione predefinita senza validazione incrociata sul set etichettato, portando a distribuzioni di etichette sovra- o sotto-regolarizzate.
- Ignorare lo sbilanciamento delle classi: se una classe domina il set etichettato, la sua etichetta inonda il grafo; sono necessari ribilanciamento o campionamento.
- Trattare le previsioni trasduttive come un modello addestrato e applicarle a nuovi punti senza un wrapper induttivo.
- Mancata verifica della connettività del grafo: i nodi non etichettati in componenti isolate non ricevono alcun segnale e assumono probabilità di classe uniformi.
Domande frequenti
Qual è la differenza tra Label Propagation e Label Spreading?
Label Spreading, proposto da Zhou et al. (2004), introduce un parametro di regolarizzazione alpha che controlla quanto ciascun nodo mantiene la sua etichetta iniziale rispetto all'adozione delle etichette dei suoi vicini. Nel classico Label Propagation i nodi etichettati sono fissati rigidamente, rendendoli completamente assorbenti. Label Spreading consente ai nodi etichettati di essere parzialmente sovrascritti, il che lo rende più robusto al rumore delle etichette a costo di un iperparametro aggiuntivo.
Label Propagation scala a dataset di grandi dimensioni?
La soluzione naive in forma chiusa richiede l'inversione di una matrice (n_U x n_U), che è infattibile per n grandi. In pratica, un grafo sparso k-vicini più prossimi o a raggio epsilon riduce la memoria a O(nk), e l'aggiornamento iterativo scala quindi approssimativamente linearmente rispetto al numero di archi per iterazione. Per grafi molto grandi vengono utilizzati metodi di vicini più prossimi approssimati e varianti mini-batch.
Quanti esempi etichettati sono necessari?
Label Propagation è specificamente progettato per il regime di etichette estremamente basse. Anche un singolo nodo etichettato per classe può produrre previsioni significative se la struttura del grafo si allinea con i confini di classe, sebbene avere almeno alcuni esempi etichettati per classe sia fortemente raccomandato per l'affidabilità. Le prestazioni degradano all'aumentare del rumore delle etichette o quando il grafo diventa meno informativo sull'appartenenza alla classe.
Label Propagation può prevedere su punti dati nuovi e non visti?
Nella sua forma trasduttiva standard, no — l'algoritmo opera su un grafo fisso e non ha meccanismi per prevedere al di fuori di quel grafo. Per un uso induttivo, un approccio comune è connettere nuovi punti ai loro k vicini più prossimi nel grafo esistente ed eseguire un passo di propagazione parziale, oppure utilizzare la matrice di etichette convergente per addestrare un classificatore supervisionato standard come secondo stadio.
Metodi correlati
Fonti
Zhu, X., & Ghahramani, Z. (2002). Learning from labeled and unlabeled data with label propagation. Technical Report CMU-CALD-02-107, Carnegie Mellon University.
Apri il riferimento della pubblicazioneCopiato.Zhu, X., Ghahramani, Z., & Lafferty, J. (2003). Semi-supervised learning using Gaussian fields and harmonic functions. Proceedings of the 20th International Conference on Machine Learning (ICML-2003), pp. 912–919.
Apri il riferimento della pubblicazioneCopiato.Chapelle, O., Scholkopf, B., & Zien, A. (Eds.) (2006). Semi-Supervised Learning. MIT Press.
ISBN: 978-0-262-03358-9Copiato.