Weighted Conformal Clustering

Sintesi Tecnica: Clustering Conforme Pesato

Formulazione del Problema
Il clustering è uno strumento fondamentale per scoprire strutture latenti in dati non etichettati, tuttavia le pipeline standard tipicamente producono assegnazioni "hard" delle osservazioni ai cluster senza una rigorosa quantificazione dell'incertezza di assegnazione. Sebbene i metodi esistenti affrontino l'incertezza tramite bootstrapping, test di esistenza globale dei cluster o set di credibilità bayesiana, essi spesso trascurano l'incertezza specifica inerente all'assegnazione delle singole osservazioni.

Un lavoro recente [11] ha introdotto un framework di inferenza conforme per il clustering trattando l'assegnazione delle etichette come un problema predittivo. Tuttavia, esiste un limite teorico critico: le etichette di calibrazione utilizzate in [11] sono sintetiche, generate da un algoritmo di clustering dipendente dai dati, piuttosto che etichette di verità fondamentale (ground-truth) osservate. Di conseguenza, l'assunzione di scambiabilità richiesta per una valida predizione conforme viene violata, portando a una potenziale sottocopertura. La sfida consiste nel costruire set di confidenza per le etichette dei cluster che mantengano garanzie di copertura a campioni finiti nonostante questo disallineamento distributivo tra le etichette di calibrazione sintetiche e le etichette latenti di verità fondamentale non osservate.

Metodologia
Gli autori propongono un framework di Clustering Conforme Pesato che affronta il disallineamento distributivo formulando il problema come uno shift condizionale della distribuzione delle etichette. La metodologia centrale procede in tre fasi:

1. Clustering Conforme Split con Pesi Oracle:
   Gli autori derivano prima una procedura "oracle" che raggiunge una copertura marginale esatta a campioni finiti. Questo approccio utilizza la predizione conforme pesata, dove i pesi sono costruiti per correggere la discrepanza tra la distribuzione delle etichette sintetiche (indotta dall'algoritmo di clustering) e la vera distribuzione delle etichette latenti. I pesi sono definiti come rapporti di verosimiglianza che confrontano la densità di etichetta condizionale vera $p^*_{Y|X}$ con le probabilità di etichetta sintetica generate dall'algoritmo di clustering. Sebbene teoricamente solido, questa procedura oracle è computazionalmente intrattabile perché richiede la valutazione della regola di clustering su dataset aumentati "leave-one-out" per ogni punto di calibrazione e punto di test.

2. Meccanismo di Calibrazione Aumentata:
   Per rendere il metodo computazionalmente fattibile, gli autori introducono un nuovo meccanismo di calibrazione aumentata. Invece di adattare l'algoritmo di clustering separatamente sul set di calibrazione e ripetutamente sui set leave-one-out, l'algoritmo adatta il modello di clustering una sola volta su un dataset aumentato $D_{aug} = D_{ca} \cup \{x\}$, dove $D_{ca}$ è il set di calibrazione e $x$ è il punto di test. Questo singolo adattamento permette ai termini di verosimiglianza sintetica di fattorizzarsi e annullarsi durante la normalizzazione, riducendo i pesi a una forma di rapporto di verosimiglianza puntuale. Questo meccanismo colma il divario tra gli approcci full-conformal e split-conformal, eliminando la necessità di ripetuti ri-adattamenti (refitting).

3. Costruzione dei Pesi Stimati:
   Poiché la vera densità condizionale $p^*_{Y|X}$ è sconosciuta, il metodo sostituisce i pesi oracle con pesi stimati utilizzando un classificatore soft $\hat{\pi}$ addestrato su un separato split di addestramento. L'algoritmo finale (Algoritmo 1) prevede:

   • Suddivisione dei dati in set di addestramento e di calibrazione.
   • Adattamento di un algoritmo di clustering sul set di addestramento per generare etichette e un classificatore soft.
   • Adattamento dell'algoritmo di clustering sul set di calibrazione aumentato ($D_{ca} \cup \{x\}$) per generare etichette sintetiche.
   • Allineamento delle etichette sintetiche con le etichette di addestramento tramite una permutazione $\hat{\sigma}$.
   • Calcolo dei punteggi di conformità e costruzione del set di confidenza utilizzando i pesi stimati derivati dal rapporto tra la densità condizionale stimata e le probabilità di clustering aumentate.

Contributi Chiave
Il documento presenta tre contributi principali:

1. Framework Novello: Introduce un framework per la quantificazione dell'incertezza nel clustering che modella esplicitamente il problema come uno shift condizionale della distribuzione delle etichette, utilizzando la predizione conforme pesata per gestire la natura non scambiabile delle etichette sintetiche.
2. Calibrazione Aumentata: Propone un meccanismo di "calibrazione aumentata" computazionalmente trattabile. Questa innovazione rimuove l'onere computazionale del refitting leave-one-out pur mantenendo i benefici teorici della predizione conforme pesata, offrendo un nuovo principio applicabile all'apprendimento non supervisionato oltre il clustering.
3. Garanzie Teoriche: Gli autori stabiliscono limiti di copertura a campioni finiti per la procedura con pesi stimati. La perdita di copertura è esplicitamente limitata dalla distanza di variazione totale tra la distribuzione delle etichette condizionali stimata e la distribuzione latente vera. A differenza degli approcci precedenti, questo framework non si basa su assunzioni di stabilità "replace-one", poiché il meccanismo di aumento stabilizza intrinsecamente il processo.

Risultati Empirici
Il metodo proposto (Algoritmo 1) è valutato rispetto al metodo di clustering conforme split ([11]) e a un metodo di cutoff ingenuo in diversi setting:

• Modelli a Miscela Gaussiana (GMM): Sia in contesti a bassa dimensionalità ($R^2$) che ad alta dimensionalità ($R^{50}$), l'approccio pesato mantiene una copertura valida con dimensioni dei set di confidenza informative (più piccole). In alta dimensionalità utilizzando il clustering spettrale, il metodo conforme split produce set eccessivamente grandi e non informativi, mentre il metodo pesato rimane informativo.
• Clustering Non Lineare: Gli esperimenti sui dataset "three moons" e "two concentric circles" dimostrano che il metodo pesato mantiene dimensioni dei set informative su un intervallo più ampio di livelli di rumore (varianza) rispetto al metodo conforme split, il quale fallisce nel produrre set informativi man mano che il clustering diventa più difficile.
• Applicazione MNIST: Applicato al deep clustering sul dataset MNIST, il metodo quantifica con successo l'incertezza. Produce set singoli per i centri dei cluster chiari e set più ampi per le regioni di confine ambigue, identificando correttamente le cifre difficili da classificare.

Significato e Rivendicazioni
Il documento posiziona questo lavoro come un passo avanti sostanziale nel campo emergente del clustering conforme. Trattando le etichette sintetiche come induttrici di uno shift di distribuzione, gli autori estendono l'applicabilità della predizione conforme oltre i modelli di miscela parametrici fluidi considerati nel lavoro precedente ([11]). Il metodo è particolarmente significativo per applicazioni di clustering ad alta dimensionalità e non lineari, dove gli approcci conformi standard faticano a fornire set di confidenza informativi. Gli autori affermano che il loro framework offre un approccio più rigoroso e versatile per la quantificazione dell'incertezza, fornendo garanzie di copertura valide anche quando l'algoritmo di clustering sottostante è complesso o la distribuzione dei dati è non standard. Il documento conclude che il meccanismo di calibrazione aumentata rappresenta un principio metodologico più ampio con potenziali applicazioni nell'apprendimento non supervisionato oltre il contesto specifico del clustering.