Inference for Clustering: Conformal Sets for Cluster Labels

1. Il Problema: Incertezza nelle Etichette di Clustering

Il clustering è un compito fondamentale nell'apprendimento non supervisionato, ampiamente utilizzato in settori come la biomedicina e l'analisi delle reti sociali. Tuttavia, nonostante la maturità degli algoritmi, l'incertezza nelle assegnazioni dei cluster è raramente quantificata con garanzie rigorose.

• La sfida principale: Le etichette dei cluster non sono osservate ma stimate dai dati. Utilizzare etichette deterministiche (fisse) per applicare metodi di inferenza standard viola l'assunzione di scambiabilità (exchangeability), portando a una grave sottocopertura (under-coverage), ovvero la probabilità che il vero cluster sia incluso nell'intervallo di confidenza è inferiore al livello nominale.
• Limiti degli approcci esistenti:
  • I metodi basati sulla "cutoff" (soglia) delle probabilità soft (es. prendere i cluster con probabilità cumulativa > 1-α) non sono calibrati e tendono a produrre set troppo grandi (conservativi) o troppo piccoli.
  • Gli approcci di inferenza selettiva o bayesiana si concentrano spesso sull'esistenza dei cluster o sulla struttura del modello, non direttamente sull'incertezza delle etichette specifiche per un punto dati.
  • Non esiste un framework generale, agnostico rispetto al modello, che fornisca garanzie finite per le etichette di output di un algoritmo di clustering.

2. Metodologia Proposta: Split Conformal Clustering con Etichette Stocastiche

Gli autori propongono un nuovo framework basato sull'inferenza conformale per costruire insiemi di confidenza per le etichette dei cluster. L'obiettivo è costruire un insieme $\hat{C}(x) \subseteq \{1, \dots, K\}$ tale che, con probabilità $1-\alpha$, contenga l'etichetta vera del punto di test $x$.

Il Nucleo dell'Approccio

Il metodo supera la violazione dell'scambiabilità introducendo etichette stocastiche nel processo di clustering.

1. Splitting dei Dati: I dati vengono divisi casualmente in un set di addestramento ($I_{tr}$) e un set di calibrazione ($I_{ca}$).
2. Clustering Stocastico: Invece di assegnare etichette fisse, l'algoritmo di clustering (es. GMM stocastico o Fuzzy C-Means) genera etichette campionando da una distribuzione di probabilità (vettori soft).
   • Si ottengono etichette $Y_i$ per il set di addestramento e $Y_i$ per il set di calibrazione campionando dalle distribuzioni stimate.
3. Addestramento del Classificatore: Un classificatore "soft" (es. una rete neurale o SVM con kernel RBF) viene addestrato sul set di addestramento usando le etichette stocastiche ottenute al passo 2.
4. Allineamento delle Etichette: Poiché il clustering su due sottoinsiemi diversi può produrre permutazioni diverse delle etichette, si risolve un problema di assegnazione lineare per allineare le etichette del set di calibrazione con le previsioni del classificatore.
5. Costruzione dell'Insieme di Confidenza: Si calcolano i punteggi di conformità (conformity scores) sul set di calibrazione. Per un nuovo punto $x$, l'insieme di confidenza $\hat{C}(x)$ include tutte le etichette $y$ il cui punteggio di conformità è inferiore a un quantile empirico calcolato sui punteggi di calibrazione.

Perché funziona?

L'introduzione della stocasticità nel processo di etichettatura ripristina una forma di scambiabilità approssimata. Le etichette campionate riflettono meglio la distribuzione sottostante rispetto alle assegnazioni deterministiche, permettendo all'inferenza conformale di funzionare correttamente.

3. Contributi Chiave e Risultati Teorici

Garanzie Teoriche

Gli autori derivano un limite inferiore finito per la copertura marginale, che dipende da due proprietà dell'algoritmo di clustering:

1. Consistenza: L'errore di stima delle probabilità di risposta (soft labels) deve convergere a zero.
2. Stabilità "Replace-One": La distribuzione congiunta delle etichette non deve cambiare significativamente se un singolo punto dati viene sostituito.

Teorema Principale (Teorema 1): La copertura è garantita da $1 - \alpha$ meno termini di errore legati alla consistenza e alla stabilità. Se l'algoritmo di clustering è consistente e stabile (come nel caso di modelli parametrici ben specificati), la copertura asintotica è garantita.

Validazione Empirica

• Simulazioni su Modelli di Mischia (GMM e GaMM):
  • Il metodo proposto (Split CC Stocastico) raggiunge la copertura target (es. 90%) in diverse configurazioni di varianza e dimensionalità.
  • I metodi "naive" (Split CC con etichette dure o metodi a soglia) falliscono: quelli con etichette dure mostrano forte sottocopertura, mentre quelli a soglia producono insiemi di confidenza inutilmente grandi e non informativi.
  • La dimensione degli insiemi di confidenza è informativa: aumenta nelle regioni di confine tra i cluster (dove l'incertezza è alta) e rimane un singolo elemento nelle regioni ben separate.
• Applicazione Reale: Single-Cell RNA-seq:
  • Applicato a un dataset di cellule PBMC (3000 cellule).
  • Il metodo identifica con alta certezza (insiemi di dimensione 1) i tipi cellulari distinti (es. cellule B, NK).
  • Assegna insiemi più grandi (dimensione > 1) a popolazioni biologicamente ambigue o sovrapposte (es. monociti, cellule T CD4/CD8), riflettendo correttamente l'incertezza biologica e metodologica.

4. Significato e Impatto

Questo lavoro rappresenta uno dei primi tentativi riusciti di applicare l'inferenza conformale a un problema puramente non supervisionato.

• Agnosticismo del Modello: Il framework non richiede di conoscere la distribuzione sottostante dei dati, purché si utilizzi un algoritmo di clustering stocastico.
• Interpretabilità: Fornisce agli scienziati uno strumento visivo e quantitativo per distinguere tra assegnazioni di cluster affidabili e regioni ambigue, migliorando la riproducibilità e l'affidabilità delle decisioni a valle (es. scoperta di nuovi tipi cellulari).
• Superamento delle Limitazioni: Risolve il problema fondamentale della non scambiabilità nelle etichette stimate, offrendo garanzie finite e asintotiche che mancano nei metodi attuali.

In sintesi, gli autori forniscono un "meta-algoritmo" che trasforma qualsiasi procedura di clustering stocastica in un metodo di previsione con garanzie di copertura rigorose, colmando il divario tra apprendimento non supervisionato e inferenza statistica rigorosa.