On Model-Based Clustering With Entropic Optimal Transport

Sintesi Tecnica: Sulla Clustering Basata su Modelli con Trasporto Ottimo Entropico

Enunciato del Problema
Il clustering basato su modelli, in particolare tramite Misure di Miscele Gaussiane (GMM), si basa sulla massimizzazione della verosimiglianza logaritmica per inferire strutture di gruppo latenti. Lo strumento computazionale standard per questa inferenza è l'algoritmo di Massimizzazione delle Aspettative (EM). Tuttavia, la funzione di verosimiglianza logaritmica nei modelli di miscele è tipicamente non convessa, portando l'algoritmo EM a convergere frequentemente verso punti stazionari spurii (ottimi locali) piuttosto che verso l'ottimo globale. I praticanti mitigano attualmente questo rischio attraverso euristiche come inizializzazioni multiple casuali (ad esempio, k-means++), che non offrono alcuna garanzia teorica di trovare la soluzione globale e possono selezionare sistematicamente configurazioni subottimali.

Metodologia
Gli autori propongono una nuova metodologia per il clustering basato su modelli che sostituisce l'obiettivo di verosimiglianza logaritmica con una funzione di perdita derivata dal Trasporto Ottimo Entropico (OT).

1. La Funzione di Perdita ($L(\theta)$):
   La funzione di perdita proposta $L(\theta)$ è definita come la distanza di trasporto ottimo entropico tra la distribuzione empirica dei dati $Q^*$ e la distribuzione del modello $Q_\theta$. Nello specifico, minimizza l'entropia relativa tra un accoppiamento $\pi$ e un nucleo di Gibbs derivato dalla densità del modello, soggetto a vincoli marginali.

   • Relazione con la Verosimiglianza Logaritmica: Il lavoro stabilisce che $L(\theta) \geq \ell(\theta)$ (dove $\ell$ è la negativa della verosimiglianza logaritmica), con l'uguaglianza che vale al vero parametro $\theta^*$ in contesti ben specificati.
   • Proprietà Geometriche: A differenza della verosimiglianza logaritmica, $L(\theta)$ risulta coercitiva (tende all'infinito quando i parametri divergono) e possiede una curvatura strettamente maggiore intorno al minimo vero. Crucialmente, il gradiente di $L$ corrisponde al gradiente della verosimiglianza logaritmica valutato a pesi di miscela "inclinati" $\alpha(\theta)$, che vengono aggiustati dinamicamente tramite il potenziale semi-duale del problema OT.

2. L'Algoritmo (Sinkhorn-EM):
   Per ottimizzare $L(\theta)$, gli autori introducono Sinkhorn-EM (SEM), un algoritmo analogo al classico algoritmo EM ma adattato al framework del trasporto ottimo entropico.

   • Passo E: Invece di calcolare le responsabilità standard (probabilità condizionate), il Passo E risolve un problema di trasporto ottimo entropico per trovare l'accoppiamento ottimale $\pi$. Questo viene risolto efficientemente utilizzando l'algoritmo di Sinkhorn-Knopp, che converge in tempo quasi lineare $\tilde{O}(nK)$.
   • Passo M: Il Passo M aggiorna i parametri del modello (posizioni $\theta$) massimizzando la verosimiglianza logaritmica attesa sotto l'accoppiamento $\pi$ ottenuto nel Passo E.
   • Aggiornamenti dei Pesi: Mentre il Passo E standard fissa i pesi marginali, gli autori estendono il metodo per permettere l'inferenza dei pesi tramite aggiornamenti del gradiente esponenziale, assicurando che l'algoritmo possa gestire pesi di miscela sconosciuti.

Contributi Teorici Chiave

• Evitamento di Ottimi Locali Spuri: Il lavoro fornisce una caratterizzazione teorica delle configurazioni "molti-ad-uno", un tipo pervasivo di ottimo locale spurio in cui molteplici componenti adattate collassano su un'unica componente vera. Gli autori dimostrano che, sotto specifiche condizioni di separazione, tali configurazioni non possono essere punti stazionari di $L(\theta)$, mentre sono comuni per $\ell(\theta)$.
• Garanzie di Convergenza: Il Teorema 1 stabilisce che Sinkhorn-EM converge a un punto stazionario di $L(\theta)$. A differenza delle prove di convergenza dell'EM standard che spesso richiedono condizioni di coercività stringenti sulla verosimiglianza logaritmica, gli autori sfruttano la coercività intrinseca della funzione di perdita OT entropica per garantire la convergenza.
• Analisi di Miscele Simmetriche: Nel caso specifico di una miscela di due Gaussiane, gli autori dimostrano che l'insieme dei parametri per cui $L(\theta)$ possiede un unico minimo globale è strettamente più ampio di quello per $\ell(\theta)$. Inoltre, mostrano che SEM converge esponenzialmente veloce verso il minimo globale e, all'interno di una specifica regione di inizializzazione, non performa mai peggio dell'EM standard.

Risultati Empirici
La metodologia è valutata attraverso estesi esperimenti numerici e due applicazioni nel mondo reale:

1. Dati Simulati: Gli esperimenti su GMM sintetiche mostrano che Sinkhorn-EM supera costantemente sia l'EM standard che k-means, in particolare in scenari con un gran numero di cluster ($K$) o alta varianza. Mentre l'EM spesso fallisce nell'uscire da ottimi locali poveri anche con molteplici semi, SEM identifica frequentemente la soluzione globale.
2. Microscopia di C. elegans: In un compito di segmentazione neurale che coinvolge l'identificazione dei neuroni in C. elegans, SEM evita con successo il "collasso" di neuroni vicini in singole componenti, un modo di fallimento osservato nell'EM standard.
3. Trascrittomica Spaziale: Applicato al co-clustering (biclustering) dei dati di espressione genica nella corteccia prefrontale dorsolaterale umana, un algoritmo Variational Sinkhorn-EM (SVEM) ha prodotto partizioni tissutali che riflettevano fedelmente gli strati anatomici noti rispetto ai metodi standard di Variational EM e biclustering spettrale, nonostante il modello non codificasse esplicitamente informazioni spaziali.

Significato e Limitazioni
Il lavoro afferma che il trasporto ottimo entropico fornisce un'alternativa principiale e statisticamente fondata all'ottimizzazione della verosimiglianza logaritmica che mitiga il rischio di convergere verso soluzioni subottimali. Il significato principale risiede nella dimostrazione che il "paesaggio" della funzione di perdita OT entropica è meglio comportato rispetto a quello della verosimiglianza logaritmica, offrendo un obiettivo di ottimizzazione più robusto per i praticanti.

Gli autori riconoscono due limitazioni principali:

1. Costo Computazionale: Il Passo E in Sinkhorn-EM implica la risoluzione di un problema di trasporto ottimo, rendendolo computazionalmente più costoso (tipicamente 10–100 volte più lento per iterazione) rispetto all'EM standard. Gli autori suggeriscono che questo compromesso è giustificato in regimi in cui i metodi standard falliscono nel trovare l'ottimo globale.
2. Ottimi Locali Residui: Sebbene il metodo eviti specifiche patologie "molti-ad-uno", $L(\theta)$ è ancora non convessa e può possedere altri cattivi ottimi locali, in particolare in casi con pesi di miscela altamente disuguali, dove il guadagno di prestazioni rispetto all'EM diminuisce.

Il lavoro conclude che, sebbene i risultati teorici siano più specializzati per GMM con varianze uguali, la metodologia è abbastanza generale da accomodare varie famiglie di posizione-scala e offre uno strumento prezioso per compiti di clustering in cui gli approcci basati sulla verosimiglianza standard faticano con la sensibilità all'inizializzazione.