Skip to content
Torna ai risultati

Algoritmo EM

Introdotto da
Dempster, Laird & Rubin
Anno
1977
Tipo
Iterative optimization algorithm
Famiglia
Estimation

Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese

Dimensione del carattere

A cosa serve?

L'algoritmo Expectation-Maximization (EM) è una procedura iterativa di ottimizzazione per la ricerca delle stime di massima verosimiglianza o di massimo a posteriori dei parametri in modelli statistici con variabili latenti o dati mancanti.

Introdotto da Dempster, Laird e Rubin nel loro fondamentale articolo del 1977, l'EM alterna il calcolo della log-verosimiglianza attesa dei dati completi (E-step) e la sua massimizzazione rispetto ai parametri (M-step), garantendo una verosimiglianza monotona non decrescente ad ogni iterazione.

L’intuizione alla base del metodo

Immaginate di voler apprendere le regole di un gioco osservando giocatori le cui carte non potete vedere. Ad ogni turno, indovinate quali carte probabilmente possiedono, dato ciò che osservate, quindi aggiornate il vostro modello delle regole assumendo che tali ipotesi siano corrette. L'EM fa esattamente questo: l'E-step riempie probabilisticamente le informazioni mancanti utilizzando le stime attuali dei parametri, e l'M-step ri-adatta il modello come se quei valori riempiti fossero osservazioni reali.

Storia

L'algoritmo è stato formalmente unificato e denominato da Arthur Dempster, Nan Laird e Donald Rubin nel loro articolo JRSS-B del 1977, che rimane uno degli articoli di statistica più citati mai pubblicati. L'articolo ha generalizzato procedure precedenti per casi speciali sviluppate indipendentemente per specifici problemi di dati mancanti. I decenni successivi hanno prodotto numerose estensioni, inclusi gli algoritmi ECM, ECME, AECM e SEM, ampliando l'applicabilità e accelerando la convergenza in molti contesti pratici.

Quando usarlo

Utilizzare l'algoritmo EM quando i dati contengono valori mancanti, stati nascosti o variabili latenti e sono necessarie stime di massima verosimiglianza. È ben adatto per modelli a mistura gaussiana, modelli di Markov nascosti, analisi fattoriale e imputazione di dati mancanti. Le ipotesi chiave includono che i dati mancanti siano mancanti casualmente (MAR) e che il modello dei dati completi sia trattabile. I limiti includono la sensibilità all'inizializzazione, la possibile convergenza a massimi locali e la lenta convergenza vicino ai punti di sella. Le alternative includono l'ottimizzazione basata sul gradiente con integrazione numerica, l'inferenza variazionale o i metodi MCMC.

Limiti e considerazioni

  • Convergenza a un massimo locale piuttosto che al massimo globale quando la superficie di verosimiglianza è multimodale
  • Può mostrare una convergenza molto lenta (lineare) quando la frazione di informazioni mancanti è grande
  • Richiede all'analista di specificare il modello dei dati completi e la distribuzione delle variabili latenti
  • L'EM standard non fornisce direttamente la matrice di covarianza dei dati osservati delle stime; è necessario un passaggio supplementare (ad esempio, il metodo di Louis o l'algoritmo SEM) per gli errori standard

Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.

Punti di forza

  • Aumento monotono garantito della verosimiglianza dei dati osservati ad ogni iterazione, assicurando una convergenza stabile
  • Converte un problema difficile di dati mancanti in una sequenza di ottimizzazioni trattabili di dati completi
  • Ampiamente applicabile a modelli della famiglia esponenziale, modelli a mistura e framework di variabili latenti
  • Aggiornamenti M-step in forma chiusa sono disponibili per molti modelli standard, rendendo l'implementazione efficiente

Applicazioni

  • Adattamento di modelli a mistura gaussiana per il clustering e la stima della densità
  • Addestramento di modelli di Markov nascosti per il riconoscimento vocale e l'analisi di sequenze biologiche
  • Imputazione multipla e analisi dei dati mancanti nella ricerca clinica e nelle scienze sociali
  • Stima dei parametri nell'analisi fattoriale e nell'analisi delle classi latenti
  • Segmentazione e ricostruzione di immagini in diagnostica per immagini

Come funziona

Come funziona

1

Prima dell'inizio dell'iterazione, l'analista seleziona i valori iniziali per i parametri sconosciuti, denotati theta-0. Questi possono essere scelti casualmente, da un adattamento semplificato o tramite conoscenza del dominio. La qualità dell'inizializzazione può influenzare il massimo locale a cui l'algoritmo converge, rendendo la pratica di riavvii casuali multipli una pratica comune.

Formula
\text{Choose initial parameter estimates } \theta^{(0)}
2

Dato l'attuale stimatore dei parametri theta-t, l'E-step calcola Q, il valore atteso della log-verosimiglianza dei dati completi sulla distribuzione delle variabili latenti non osservate Z, condizionato ai dati osservati X. Questa aspettativa sostituisce efficacemente le quantità sconosciute con le loro stime probabilistiche senza impegnarsi in un singolo valore imputato.

Formula
Q(\theta \mid \theta^{(t)}) = \mathbb{E}_{Z \mid X, \theta^{(t)}}[\log p(X, Z \mid \theta)]
3

L'M-step massimizza la funzione Q dall'E-step rispetto a theta, producendo una stima aggiornata theta-(t+1). Poiché la log-verosimiglianza dei dati completi è spesso più semplice da massimizzare rispetto alla verosimiglianza marginale dei dati osservati, questo passaggio è frequentemente trattabile anche quando la massima verosimiglianza diretta non lo è.

Formula
\theta^{(t+1)} = \arg\max_{\theta} \, Q(\theta \mid \theta^{(t)})
4

Gli E-step e M-step vengono ripetuti alternativamente. Dopo ogni ciclo completo, viene valutata la log-verosimiglianza dei dati osservati. L'iterazione si interrompe quando la variazione della log-verosimiglianza (o del vettore dei parametri) scende al di sotto di una tolleranza epsilon definita dall'utente. Dempster et al. hanno dimostrato che ogni ciclo non può diminuire la verosimiglianza dei dati osservati, garantendo una convergenza stabile.

Formula
\text{Repeat E- and M-steps until } |\ell(\theta^{(t+1)}) - \ell(\theta^{(t)})| < \epsilon

Errori comuni

  • L'utilizzo di una singola inizializzazione casuale rischia di terminare in un massimo locale scadente; eseguire sempre più riavvii e selezionare la soluzione con la log-verosimiglianza finale più alta
  • Dichiarare la convergenza troppo presto monitorando solo la variazione dei parametri anziché la log-verosimiglianza dei dati osservati può produrre stime imprecise
  • L'applicazione dell'EM quando i dati sono Missing Not At Random (MNAR) senza aggiustamento del modello può introdurre un bias sistematico nelle stime
  • Ignorare il problema dello scambio di etichette nei modelli a mistura porta ad assegnazioni di componenti non interpretabili anche dopo una corretta convergenza

Domande frequenti

L'algoritmo EM converge sempre al massimo globale?

No. L'EM è garantito solo per trovare un massimo locale (o un punto di sella) della verosimiglianza dei dati osservati. Quando la superficie di verosimiglianza ha più modi, la soluzione finale dipende dall'inizializzazione. Eseguire l'algoritmo da diversi punti di partenza e mantenere la soluzione con la log-verosimiglianza più alta è il rimedio pratico standard.

In che modo l'EM differisce dall'ottimizzazione diretta della massima verosimiglianza?

La MLE diretta massimizza la log-verosimiglianza dei dati osservati, il che può comportare integrali intrattabili sulle variabili latenti. L'EM aggira questo problema massimizzando iterativamente la log-verosimiglianza attesa dei dati completi, che è spesso analiticamente trattabile. Il compromesso è che l'EM può convergere lentamente, mentre i metodi basati sul gradiente possono essere più veloci quando sono disponibili i gradienti della verosimiglianza marginale.

Quando dovrei preferire l'imputazione MICE rispetto all'algoritmo EM?

MICE (Multiple Imputation by Chained Equations) è preferibile quando i dati includono variabili di tipi misti, relazioni non lineari o strutture di interazione complesse che sono difficili da codificare in un singolo modello parametrico di dati completi. L'EM è più naturale quando esiste un modello congiunto ben specificato per tutte le variabili e l'inferenza mira ai parametri del modello piuttosto che ai dataset imputati.

Metodi correlati

Fonti

  1. Dempster, A. P., Laird, N. M., & Rubin, D. B. (1977). Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society: Series B, 39(1), 1–38.

    Apri il riferimento DOI
    Copiato.