Algoritmo EM (Expectation-maximization): Definizione semplice

Stima della massima verosimiglianza > Algoritmo EM (Expectation-maximization)

Potresti leggere prima questo articolo: Cos’è la stima della massima verosimiglianza?

Che cos’è l’algoritmo EM?

L’algoritmo EM può essere utilizzato per stimare variabili latenti, come quelle che provengono da distribuzioni di miscele (sai che provengono da una miscela, ma non da quale distribuzione specifica).

L’algoritmo di Expectation-Maximization (EM) è un modo per trovare stime di massima verosimiglianza per i parametri del modello quando i dati sono incompleti, mancano punti dati o hanno variabili latenti non osservate (nascoste). È un modo iterativo per approssimare la funzione di massima verosimiglianza. Mentre la stima della massima verosimiglianza può trovare il modello “più adatto” per un set di dati, non funziona particolarmente bene per i set di dati incompleti. L’algoritmo EM più complesso può trovare i parametri del modello anche se mancano dati. Funziona scegliendo valori casuali per i punti dati mancanti e utilizzando tali ipotesi per stimare un secondo set di dati. I nuovi valori vengono utilizzati per creare un’ipotesi migliore per il primo set e il processo continua fino a quando l’algoritmo converge su un punto fisso.

Vedi anche: Algoritmo EM spiegato in un’immagine.

MLE vs. EM

Sebbene la stima della massima verosimiglianza (MLE) ed EM possano trovare entrambi i parametri “best-fit”, il modo in cui trovano i modelli è molto diverso. MLE accumula prima tutti i dati e poi li utilizza per costruire il modello più probabile. EM prende una supposizione ai parametri prima-contabilità per i dati mancanti – quindi modifica il modello per adattarsi alle ipotesi e ai dati osservati. I passaggi di base per l’algoritmo sono:

1. Viene fatta un’ipotesi iniziale per i parametri del modello e viene creata una distribuzione di probabilità. Questo è talvolta chiamato “E-Step” per la distribuzione “Attesa”.
2. I dati appena osservati vengono inseriti nel modello.
3. La distribuzione di probabilità dall’E-step è ottimizzata per includere i nuovi dati. Questo è talvolta chiamato il ” M-step.”
4. I passaggi da 2 a 4 vengono ripetuti fino a raggiungere la stabilità (cioè una distribuzione che non cambia dal passaggio E al passaggio M).

L’algoritmo EM migliora sempre la stima di un parametro attraverso questo processo multi-step. Tuttavia, a volte ha bisogno di alcuni inizi casuali per trovare il modello migliore perché l’algoritmo può affinare un massimo locale che non è così vicino ai massimi globali (ottimali). In altre parole, può funzionare meglio se lo costringi a riavviare e riprendi quella “ipotesi iniziale” dal Passaggio 1. Da tutti i parametri possibili, è quindi possibile scegliere quello con la massima probabilità massima.

In realtà, i passaggi coinvolgono alcuni calcoli (integrazione) piuttosto pesanti e probabilità condizionali, che vanno oltre lo scopo di questo articolo. Se hai bisogno di una ripartizione più tecnica (cioè basata sul calcolo) del processo, ti consiglio vivamente di leggere il documento 2010 di Gupta e Chen.

Applicazioni

L’algoritmo EM ha molte applicazioni, tra cui:

• Dis-entangling segnali sovrapposti,
• Stima Gaussian mixture models (GMM),
• Stima hidden Markov models (HMM),
• Stima dei parametri per le distribuzioni composte di Dirichlet,
• Ricerca di miscele ottimali di modelli fissi.

Limitazioni

L’algoritmo EM può essere molto lento, anche sul computer più veloce. Funziona meglio quando hai solo una piccola percentuale di dati mancanti e la dimensionalità dei dati non è troppo grande. Maggiore è la dimensionalità, più lento è il passo E; per i dati con dimensionalità maggiore, è possibile che l’E-step venga eseguito estremamente lentamente man mano che la procedura si avvicina a un massimo locale.

Dempster, A., Laird, N. e Rubin, D. (1977) Massima verosimiglianza da dati incompleti tramite l’algoritmo EM, Journal of the Royal Statistical Society. Serie B (Metodologica), vol. 39, n. 1, pp. 1ñ38.
Gupta ,M. & Chen, Y. (2010) Teoria e uso dell’algoritmo EM. Fondamenti e tendenze nell’elaborazione del segnale, Vol. 4, n. 3 223-296.

——————————————————————————

Hai bisogno di aiuto con un compito a casa o una domanda di prova? Con Chegg Studio, è possibile ottenere soluzioni passo-passo alle vostre domande da un esperto del settore. I tuoi primi 30 minuti con un tutor Chegg sono gratuiti!