The windowEM algorithm

Sintesi Tecnica dell'algoritmo "windowEM"

Definizione del Problema
L'algoritmo di Expectation-Maximization (EM) è un metodo standard per la stima della massima verosimiglianza in modelli con variabili latenti. Tuttavia, nel contesto di set di dati su larga scala (ad esempio, dati genomici che comprendono miliardi di punti), l'algoritmo EM standard diventa computazionalmente impraticabile perché richiede l'elaborazione dell'intero dataset in ogni iterazione. Sebbene siano state proposte versioni stocastiche dell'EM (utilizzando mini-batch) per accelerare la convergenza, esse producono spesso stime dei parametri grossolane o rumorose, particolarmente quando lo spazio dei parametri è complesso o quando certe variabili latenti sono rappresentate in modo sparso nei dati. Questo rumore può portare ad artefatti, come "gobbe" artificiali nelle distribuzioni stimate come gli spettri di frequenza dei siti (SFS), e può contribuire all'over-fitting.

Metodologia: L'algoritmo windowEM
Gli autori propongono windowEM, una variante stocastica dell'algoritmo EM che partiziona i dati in $B$ blocchi e dispone questi blocchi su un cerchio. L'algoritmo opera attraverso il seguente meccanismo:

1. Partizione in Blocchi: I dati sono divisi in $B$ blocchi ($x_1, \dots, x_B$). I blocchi possono variare in dimensione e distribuzione e non si assume che siano indipendenti.
2. Aggiornamenti Sequenziali: L'algoritmo esegue una sequenza di aggiornamenti in cui la stima per il blocco corrente $k$ è derivata dalla stima del blocco precedente $k-1$ utilizzata come seme. Nello specifico, una stima preliminare $\psi_{t+1}$ viene ottenuta eseguendo un'iterazione dell'algoritmo EM standard sul blocco $b(t+1)$ utilizzando l'attuale stima del parametro $\theta_t$:
   $$\psi_{t+1} = f_{b(t+1)}(\theta_t) = \arg\max_{\theta'} Q_{b(t+1)}(\theta' | \theta_t)$$
3. Media a Finestra Mobile (Rolling Window Averaging): Per contrastare il rumore inerente agli aggiornamenti su singolo blocco, l'algoritmo mantiene una "popolazione" di stime. La stima finale $\theta_t$ per un dato passo è la media delle $w$ stime preliminari più recenti all'interno di una finestra mobile di dimensione $w$:
   $$\theta_t = \frac{1}{w} \sum_{i=t-w+1}^{t} \psi_i$$
4. Iterazione Circolare: I blocchi sono disposti ciclicamente. Se $B$ è finito, l'algoritmo itera attraverso i blocchi ripetutamente (epoche). Se $B = \infty$, l'algoritmo procede attraverso una sequenza infinita di blocchi unici.
5. Stima Finale: Una singola stima puntuale può essere prodotta mediando la popolazione di $B$ stime.

Gli autori osservano che, sebbene l'algoritmo sia ispirato al Polyak-Ruppert averaging, esso differisce applicando la media alle stime generate dai passi di EM sequenziali su una disposizione circolare dei dati, piuttosto che mediare i gradienti o gli aggiornamenti in un modo standard di discesa del gradiente stocastico.

Contributi Teorici Chiave
Il documento investiga le proprietà di convergenza di windowEM sotto due scenari, $B$ finito e $B$ infinito.

• $B$ Finito: Gli autori utilizzano la teoria della contrazione. Stabiliscono che se la funzione di aggiornamento è una contrazione, la sequenza di stime dei blocchi converge. Un risultato chiave è che se esiste un punto fisso per un blocco, esiste un punto fisso per tutti i blocchi. La distribuzione di queste stime dei blocchi dipende dalla dimensione della finestra $w$; empiricamente, dimensioni della finestra più grandi risultano in una minore varianza tra le stime dei blocchi.
• $B$ Infinito: Per il caso in cui $B = \infty$ (o sufficientemente grande da non ripetere i blocchi), gli autori applicano la teoria delle iterazioni casuali per dati dipendenti. Forniscono le condizioni in cui le stime convergono a un punto fisso per grandi indici di blocco. Inoltre, stabiliscono le condizioni che garantiscono la convergenza della media ergodica delle stime dei blocchi quando $B \to \infty$.
• Famiglie Esponenziali: L'analisi è particolarmente rigorosa per le famiglie esponenziali. Gli autori dimostrano che, per la parametrizzazione del valore medio, la funzione di aggiornamento è spesso una funzione lineare delle statistiche sufficienti. Nel caso di miscele di distribuzioni di famiglie esponenziali, le funzioni di aggiornamento rimangono lineari rispetto alle statistiche osservate, pesate dalle probabilità di classe stimate.
• Casi Speciali: Il documento analizza configurazioni specifiche, come $w=1$ (che si riduce a un EM sequenziale senza mediazione) e $w=B$ (dove l'aggiornamento diventa una media su tutti i blocchi, potenzialmente producendo un punto fisso equivalente alla soluzione dell'EM standard sotto ipotesi di linearità).

Risultati Empirici
Il documento valida l'algoritmo utilizzando due esempi primari:

1. Esempio Binomiale Illustrativo: Un problema di stima della frequenza genica. I risultati mostrano che windowEM converge alla stima della massima verosimiglianza (MLE) rapidamente. La varianza delle stime diminuisce all'aumentare della dimensione della finestra $w$, sebbene la velocità di convergenza possa rallentare leggermente con $w$ più grande.
2. Miscele Gaussiane Univariate: L'algoritmo è testato su miscele di distribuzioni Gaussiane.
   • In una simulazione con $n=10^5$ punti dati e $B=10$ blocchi, windowEM ha raggiunto una log-verosimiglianza vicina alla MLE dei dati completi significativamente più velocemente dell'EM standard.
   • Notevolmente, mentre l'EM standard ha infine raggiunto una log-verosimiglianza superiore rispetto a windowEM, ha anche superato la MLE dei dati completi, suggerendo un over-fitting. La stima di windowEM, derivata dalla media di una popolazione di stime, sembrava agire come un regolarizzatore, rimanendo più vicina alla vera distribuzione sottostante senza l' "overshoot" osservato nell'EM standard.
   • Simili tendenze sono state osservate con dataset più piccoli ($n=10^4$) e più grandi ($n=10^6$), dove windowEM si è stabilizzato più vicino alla MLE dei dati completi più velocemente rispetto all'EM standard.

Significato e Rivendicazioni
Gli autori affermano che windowEM offre una soluzione pratica per l'inferenza su larga scala dove l'EM standard è impraticabile e l'EM stocastico standard è troppo rumoroso. La significatività primaria risiede nell'effetto di regolarizzazione indotto dalla media di una popolazione di stime su una finestra mobile.

• Prevenzione dell'Over-fitting: Il documento specula, sulla base dell'evidenza empirica in genomica (stima SFS) e nelle miscele Gaussiane, che windowEM aiuti a prevenire l'over-fitting. Mediando le stime che potrebbero essere artificialmente gonfiate da eventi rari in specifici blocchi, l'algoritmo produce stime dei parametri più stabili.
• Fondamento Teorico: Il documento fornisce la prima investigazione teorica sulla convergenza di questo specifico schema, distinguendo tra scenari di blocchi finiti e infiniti e utilizzando le teorie della contrazione e delle iterazioni casuali.
• Modestia: Gli autori sono modesti nelle loro rivendicazioni, notando che, sebbene windowEM possa non raggiungere sempre la stima assoluta della massima verosimiglianza (e possa anche avere una log-verosimiglianza inferiore rispetto all'EM standard), le stime risultanti possono essere più robuste e statisticamente significative grazie alla riduzione della varianza e dell'over-fitting. Non rivendicano una superiorità universale rispetto all'EM standard, ma piuttosto un compromesso che favorisce la stabilità e la velocità nei regimi di grandi dati.