Riassunto Tecnico: SLeDGe – Semi-Supervised Learning su flussi di dati con apprendimento della struttura del grafo

1. Definizione del Problema

Il documento affronta la sfida dell'apprendimento semi-supervisionato (SSL) su flussi di dati (data streams). In questo scenario, i dati arrivano sequenzialmente ($D = \{x_t\}_{t=1}^T$ in alto volume, e l'apprendista deve operare sotto due vincoli rigorosi:

1. Vincoli di Memoria: Il sistema dispone di una capacità di memoria fissa e limitata ($M$) e non può memorizzare l'intera cronologia del flusso.
2. Scarsità di Etichette: Solo una minuscola frazione dei campioni in arrivo presenta etichette osservate ($y_t$), rendendo impraticabile l'apprendimento supervisionato tradizionale.

I metodi SSL esistenti per i flussi di dati spesso falliscono perché trattano i campioni in modo indipendente, si affidano a euristiche di similarità fisse (che non possono catturare le relazioni in evoluzione) o assumono dataset statici offline. Il problema centrale è come propagare efficacemente la limitata supervisione delle etichette ai campioni non etichettati, adattandosi al contempo all'evoluzione continua delle distribuzioni di dati e delle relazioni nel tempo.

2. Metodologia: SLeDGe

Gli autori propongono SLeDGe (Semi-supervised Learning on Data Stream with Graph structure learning), un framework che apprende congiuntamente un modello predittivo e una struttura di grafo adattiva. Il metodo opera in tre fasi continue per ogni campione in entrata $x_t$:

A. Meccanismo di Aggiornamento a Doppia Memoria

Per bilanciare la necessità di un rapido adattamento (plasticità) con la ritenzione della coerenza storica (stabilità), SLeDGe mantiene due distinti buffer di memoria compatta:

• Memoria Etichettata ($M_L$): Ottimizzata per la plasticità. Memorizza i prototipi per ogni classe. Quando arriva un nuovo campione etichettato, esso riempie uno slot vuoto o aggiorna il prototipo esistente più simile tramite una combinazione ponderata. Il peso di aggiornamento $\alpha$ è dinamico, favorendo il nuovo input per facilitare l'integrazione rapida di nuove caratteristiche.
• Memoria Non Etichettata ($M_U$): Ottimizzata per la stabilità. Memorizza prototipi non etichettati rappresentativi. Gli aggiornamenti qui utilizzano un peso $\beta$ che favorisce il prototipo esistente, riflettendo l'incertezza dei dati non etichettati e garantendo un accumulo graduale di informazioni.

B. Apprendimento Dinamico della Struttura del Grafo (GSL)

Invece di utilizzare un grafo fisso o metriche di similarità statiche, SLeDGe costruisce dinamicamente un grafo ad ogni passo temporale sulla memoria combinata ($M_L \cup M_U$) e sul campione corrente $x_t$.

1. Embedding ($f_E$): Un Multi-Layer Perceptron (MLP) mappa le caratteristiche di input in uno spazio latente.
2. Scoring ($f_S$): Una funzione di punteggio (similarità del coseno) calcola i pesi relazionali a coppia tra tutti i nodi nella memoria e il campione corrente, generando una matrice di adiacenza densa.
3. Pruning ($f_P$): Per garantire l'efficienza, la matrice densa viene potata (pruning) per trattenere solo le prime-$k$ connessioni per nodo, risultando in una matrice di adiacenza sparsa $A_t$.
4. Classificazione ($f_B$): Un backbone di tipo Graph Convolutional Network (GCN) propaga la supervisione attraverso la struttura del grafo appresa $A_t$ per generare le predizioni.

C. Ottimizzazione del Modello

Il modello viene aggiornato utilizzando una funzione di perdita composita:

• Perdita Supervisionata ($L_L$): Perdita di cross-entropy calcolata sulla memoria etichettata, ponderata da un fattore di decadimento temporale per dare priorità ai campioni più recenti.
• Regolarizzazione Strutturale ($L_{reg}$): Un termine che incoraggia la coerenza tra le similarità a coppia nello spazio di input e nello spazio latente. Questo stabilizza l'inferenza del grafo dinamico, impedendo alla struttura del grafo di diventare erratica.

D. Variante Leggera: SLeDGe-L

Per affrontare la complessità temporale quadratica ($O(M^2)$) della costruzione del grafo completo quando la dimensione della memoria $M$ è grande, gli autori propongono SLeDGe-L. Questa variante restringe lo scoring del grafo a un approccio centrato sulla classe, calcolando le similarità solo tra i prototipi etichettati e tutti i campioni della memoria. Ciò riduce la complessità a lineare rispetto a $M$ ($O(c \cdot M)$), dove $c$ è il numero di classi.

3. Contributi Chiave

1. Struttura di Grafo Adattiva: A differenza dei precedenti metodi SSL per flussi di dati che si affidano a grafi fissi, SLeDGe apprende una topologia di grafo dinamica che evolve con il flusso di dati, catturando le dipendenze inter-campione variabili nel tempo.
2. Gestione della Memoria a Doppia Strategia: L'introduzione di strategie di aggiornamento distinte per le memorie etichettate (focalizzate sulla plasticità) e non etichettate (focalizzate sulla stabilità) consente al modello di bilanciare l'adattamento a nuove caratteristiche con la preservazione della conoscenza storica.
3. Efficienza sotto Vincoli: Il framework è progettato per operare sotto rigidi budget di memoria ed estrema scarsità di etichette (fino allo 0,1% di etichette) mantenendo l'efficienza computazionale attraverso il pruning del grafo sparso e una variante leggera (SLeDGe-L).
4. Regolarizzazione Strutturale: L'inclusione di un termine di regolarizzazione della coerenza assicura che la struttura del grafo appresa rimanga stabile e significativa durante il processo di streaming.

4. Risultati Sperimentali

Gli autori hanno valutato SLeDGe su 12 dataset che spaziano tra domini web, immagini e tabulari.

• Prestazioni: SLeDGe ha superato i competitor allo stato dell'arte (TLP, ReSSL, HDSSL) in tutti i dataset.
  • Con lo 0,1% di etichette, ha ottenuto un guadagno medio di accuratezza relativa del 31,7% rispetto al baseline più forte.
  • Con l'1,0% di etichette, ha ottenuto un guadagno medio di accuratezza relativa del 14,8%.
• Studi di Ablazione: Gli esperimenti hanno confermato che sia il modulo di memoria che la struttura del grafo dinamico sono critici. Rimuovere il grafo dinamico (tornando a un grafo k-NN statico) ha portato a prestazioni significativamente inferiori, validando la necessità di apprendere relazioni in evoluzione.
• Scalabilità: Il metodo dimostra una scalabilità lineare rispetto alla dimensione del flusso di dati (tempo costante per campione). SLeDGe-L ha mostrato una scalabilità superiore rispetto alla dimensione del buffer di memoria rispetto alla versione completa, confermando l'analisi della complessità teorica.
• Velocità: Nonostante sia un modello di deep learning, SLeDGe è stato competitivo in termini di tempo di esecuzione rispetto ai metodi basati su cluster, particolarmente su dati ad alta dimensionalità dove sfrutta i calcoli a livello di embedding.

5. Significato e Rivendicazioni

Il documento sostiene che SLeDGe colmi una lacuna critica nella letteratura abilitando l'Apprendimento della Struttura del Grafo (GSL) in contesti di streaming dove memoria ed etichette sono severamente vincolate. Gli autori sostengono che i metodi esistenti falliscono perché non possono modellare come le relazioni tra i campioni evolvano nel tempo. Aprendo congiuntamente il modello predittivo e la struttura del grafo, SLeDGe propaga efficacemente la limitata supervisione ai dati non etichettati, ottenendo sostanziali miglioramenti di accuratezza senza richiedere la memorizzazione dell'intera cronologia dei dati. Il lavoro sottolinea che l'inferenza del grafo dinamico è superiore alle misure di similarità statica in ambienti di flussi di dati non stazionari.