Algoritam očekivanja-maksimizacije

U statistici, algoritam maksimizacije očekivane verodostojnosti (EM - engl. Expectation-maximization) je iterativna procedura za procenu parametara na osnovu kriterijuma maksimalne verodostojnosti (ML - engl. Maximum Likelihood) ili ocene aposteriornog maksimuma (MAP - engl. Maximum a posteriori), kod kojih su prisutne vrednosti posmatranih veličina koje imaju osobinu θ koja se ne može izmeriti, ili se ne može direktno izmeriti (latentne promenljive).

EM algoritam naizmenično primenjuje "korak E" u kojem se generiše funkcija očekivane vrednosti logaritma verodostojnosti izračunatu korišćenjem trenutne procene parametara, i "korak M", u kojem se izračunavaju parametri za koje funkcije generisana u koraku E uzima maksimalnu vrednost. Parametri dobijeni u koraku M se potom koriste za određivanje raspodele latentnih varijabli za sledeći korak E.

Istorijat

Ime EM algoritma i način funkcionisanja, dato je u radu iz 1977. godine, koji su napisali Artur Dempster, Nan Laird i Donald Rubin. Njihov rad je generalizovao metodu i skicirao analizu konvergencije za širu klasu problema. Bez obzira na ranije pronalaske, njihova inovativna metoda se proslavila u javnosti i njivov rad okategorisan kao brilijantan. Rad Dempster-Laird-Rubin je osnovao EM metod kao veoma važan deo statističke analize.

Uvod

EM algoritam se koristi za pronalaženje parametra maksimalne verodostojnosti statističkog modela u slučajevima kod kojih se jednačine ne mogu rešiti direktno. Obično ovi modeli pored nepoznatih parametara i poznatih rezultata merenja uključuju i latentne promenljive. To znači da, ili nedostaju neke od merenih vrednosti, ili se model može formulisati jednostavnije pretpostavljajući postojanje dodatnih neizmerenih vrednosti posmatranih veličina.

Pronalaženje rešenja maksimalne verodostojnosti zahteva uzimanje izvoda funkcije verovatnoće po svim nepoznatim vrednostima. Kod statističih modela sa latentnim promenljivima ovo obično nije moguće. Umesto toga, rezultat je skup međusobno povezanih jednačina u kojoj rešenje za parametre zahteva poznavanje vrednosti latentnih promenljivih i obratno, ali zamena jednog skupa jednačina u drugi dovodi do nerešivih jednačina. EM algoritam polazi od zapažanja da se ova dva seta jednačina mogu rešiti numerički. To se može izvesti tako što se izaberu proizvoljne vrednosti za jedan od dva skupa nepoznatih, zatim se te proizvoljne vrednosti upotrebe za procenu drugog skupa, a zatim pomoću ovih novih vrednosti nađe bolja procena prvog skupa. Procedura se nastavlja iterativno dok rezultujuće vrednosti ne konvergiraju ka fiksnim tačkama. Nije očigledno da se ovim algoritmom može doći do rešenja u opštem slučaju, ali se može dokazati da je moguće u konkretnim slučajevima. Pri tome se izvod verodostojnosti može privesti proizvoljno blizu nuli, što znači da je pronađena tačka ili lokalni maksimum ili sedlasta tačka. Nije garantovano da će pronađeni maksimum biti globalni maksimum. U nekim slučajevima funkcija verodostojnosti ima singularitete koji obično predstavljaju maksimume bez smislene interpretacije u kontekstu u kojem se algoritam primenjuje.

Opis algoritma

Dati statistički model koji se sastoji od skupa $\mathbf {X}$ posmatranih podataka, skup neprimećenih latentnih podataka ili vrednosti koje nedostaju $\mathbf {Z}$ i vektr nepoznatih parametara ${\boldsymbol {\theta }}$, zajedno sa funkcijom verodostojnosti $L({\boldsymbol {\theta }};\mathbf {X} ,\mathbf {Z} )=p(\mathbf {X} ,\mathbf {Z} |{\boldsymbol {\theta }})$, procena maksimalne verodostojnosti (MLE - engl. Maximum likelihood estimate) od nepoznatih parametara određuje marginalne verodostojnosti posmatranih podataka

$L({\boldsymbol {\theta }};\mathbf {X} )=p(\mathbf {X} |{\boldsymbol {\theta }})=\sum _{\mathbf {Z} }p(\mathbf {X} ,\mathbf {Z} |{\boldsymbol {\theta }})$

Međutim, ovo je često nerešivo (npr. Ako se desi da broj vrednosti raste eksponencijalno što je sekvenca duža, onda će tačan proračun sume biti izuzetno težak).

EM algoritam pokušava da pronađe MLE od granične verodostojnosti iterativnom primenom sledeća dva koraka:

Korak očekivanja (E korak): Izračunava očekivanu vrednost log verodostojnosti funkcije verovatnoće, u pogledu na uslovnu raspodelu $\mathbf {Z}$ datim $\mathbf {X}$ pod trenutnom procenom parametara ${\boldsymbol {\theta }}^{(t)}$:

$Q({\boldsymbol {\theta }}|{\boldsymbol {\theta }}^{(t)})=\operatorname {E} _{\mathbf {Z} |\mathbf {X} ,{\boldsymbol {\theta }}^{(t)}}\left[\log L({\boldsymbol {\theta }};\mathbf {X} ,\mathbf {Z} )\right]\,$

Korak maksimizacije (M korak): Pronalazi parametar koji maksimizuje sledeće:

${\boldsymbol {\theta }}^{(t+1)}={\underset {\boldsymbol {\theta }}{\operatorname {arg\,max} }}\ Q({\boldsymbol {\theta }}|{\boldsymbol {\theta }}^{(t)})\,$

Tipični modeli na koje se primenjuje EM:

1. Posmatrane tačke podataka $\mathbf {X}$ mogu biti diskretne (uzimajući vrednosti iz konačnog ili prebrojivo beskonačnog skupa) ili neprekidne (uzmanjući vrednosti iz neprebrojivo beskonačnog skupa). Mogu, u stavri, biti i vektor opsevacije povezan sa svakom tačkom podataka.
2. Vrednosti koje nedostaju (latentne varijable) $\mathbf {Z}$ su diskretne, izvučene iz fiksnog broja vrednosti, a postoji jedna latentna promenljiva po posmatranoj tački podataka.
3. Parametri su neprekidni, i ima dve vrste: Parametri koji su povezani sa svim tačkama podataka, i parametara povezanim sa određenom vrednošću latentne varijable.

Međutim, moguće je da se EM primeni i na druge vrste modela. Ako znamo vrednosti parametara ${\boldsymbol {\theta }}$, obično se može naći vrednost latentnih varijabli $\mathbf {Z}$ povećavanjem log-verodostojnosti po svim mogućim vrednostima $\mathbf {Z}$, ili jednostavno iterativno preko $\mathbf {Z}$ ili preko algoritma, kao što je Viterbi algoritam za skrivene Markove modele. Nasuprot tome, ako znamo vrednosti latentnih varijabli $\mathbf {Z}$, možemo naći procenu parametrara ${\boldsymbol {\theta }}$ prilično lako, jednostavnim grupisanjem posmatrane tačke podataka na osnovu vrednosti pridružene latente varijable i proseka vrednosti, ili neka funkcija vrednosti, od tačaka u svakoj grupi. Ovo sugeriše iterativni algoritam, u slučaju kada su ${\boldsymbol {\theta }}$ i $\mathbf {Z}$nepoznati:

1. Prvo, inicijalizujte parametre ${\boldsymbol {\theta }}$ nekim slučajnim vrednostima.
2. Izračunaj najbolju vrednost za $\mathbf {Z}$ pomoću ovih vrednosti parametara.
3. Zatim, koristite ove izračunate vrednosti $\mathbf {Z}$ da izračunate bolju procenu parametara ${\boldsymbol {\theta }}$. Parametri povezani sa određenom vrednošću $\mathbf {Z}$ će koristiti samo one tačke podataka kod kojih pridružene latentne varijable imaju tu vrednost.
4. Vršite iteraciju koraka 2 i 3 do konvergencije.

Upravo opisan algoritam monotono prilazi lokanom minimumu funkcije, a najčešće se naziva hard EM. K-mean algoritam je primer ove klase algoritma.

Svojstva

Govoreći o E koraku, malo je pogrešan. Ono što se računa u prvom koraku su fiksni parametri zavisni od podataka funkcije Q. Kada su parametri Q poznati, potpuno su određeni i uvećani u drugom M koraku EM alogritma. 

Iako EM iteracija povećava broj posmatranih podataka (tj. marginali) funkcije verodostojnosti, ne postoji garancija da niz konvergira ka proceni maksimalne verodostojnosti (MLE). Za bimodalne distribucije, ovo znači da EM algoritam može konvergirati do lokalnog maksimuma posmatranih podataka funkcije verodostojnosti, zaviseći od početnih vrednosti. Postoji niz heurističkih ili metaheurističkih pristupa za "bežanje" lokalnim maksimumima, kao što su nasumični restart (krenuvši od nekoliko različitih slučajnih početnih procena θ^{(t)), ili primenom algoritma simulacije žarenja.}

EM je naročito koristan kada je verodostojnost u porodici eksponencijalnih algoritama: E korak postaje zbir očekivanja dovoljne statistike, a M korak podrazumeva maksimizovanje linearne funkcije. U tom slučaju obično je moguće izvesti ispravke u zatvorenoj formi za svaki korak, koristeći Sundberg formulu (Objavio Ralf Sundberg koristeći neobjavljene rezultate Per Martin–Lofa i Anders Martin-Lofa).

EM metoda je modifikovana za izračunavanje maksimalne aposteriorne procene (MAP), sa Bajesovom statistikom, u originalnom radu Dempster, Laird i Rubin.

Postoje i druge metode za pronalaženje maksimalne verodostojnosti, jedna od metoda je varijacija Gaus-Njutnovog algoritma, a postoje i još neke. Za razliku od EM, takve metode obično zahtevaju procenu prvog ili drugog derivata funkcije verodostojnosti.

Dokaz korektnosti

EM algoritam radi na poboljšanju $Q({\boldsymbol {\theta }}|{\boldsymbol {\theta }}^{(t)})$, a ne poboljšava direktno $\log p(\mathbf {X} |{\boldsymbol {\theta }})$. Ovde smo pokazali da poboljšanja prvog podrazumeva poboljšanje poslednjg. Za bilo koje $\mathbf {Z}$ sa ne nultom verovatnoćom $p(\mathbf {Z} |\mathbf {X} ,{\boldsymbol {\theta }})$, možemo zapisati

$\log p(\mathbf {X} |{\boldsymbol {\theta }})=\log p(\mathbf {X} ,\mathbf {Z} |{\boldsymbol {\theta }})-\log p(\mathbf {Z} |\mathbf {X} ,{\boldsymbol {\theta }})\,.$

Uzimamo očekivanje nad vrednostima $\mathbf {Z}$ množenjem obe strane sa $p(\mathbf {Z} |\mathbf {X} ,{\boldsymbol {\theta }}^{(t)})$. Sabiranjem i (ili integrisanjem) preko $\mathbf {Z}$. Leva strana je konstanta očekivanja, pa dobijamo:

${\begin{aligned}\log p(\mathbf {X} |{\boldsymbol {\theta }})&=\sum _{\mathbf {Z} }p(\mathbf {Z} |\mathbf {X} ,{\boldsymbol {\theta }}^{(t)})\log p(\mathbf {X} ,\mathbf {Z} |{\boldsymbol {\theta }})-\sum _{\mathbf {Z} }p(\mathbf {Z} |\mathbf {X} ,{\boldsymbol {\theta }}^{(t)})\log p(\mathbf {Z} |\mathbf {X} ,{\boldsymbol {\theta }})\\&=Q({\boldsymbol {\theta }}|{\boldsymbol {\theta }}^{(t)})+H({\boldsymbol {\theta }}|{\boldsymbol {\theta }}^{(t)})\,,\end{aligned}}$

gde je $H({\boldsymbol {\theta }}|{\boldsymbol {\theta }}^{(t)})$ određen negiranjem sume koju je zamenio. Ova poslednja jednačina važi za bilo koju vrednost ${\boldsymbol {\theta }}$, uključujući ${\boldsymbol {\theta }}={\boldsymbol {\theta }}^{(t)}$,

$\log p(\mathbf {X} |{\boldsymbol {\theta }}^{(t)})=Q({\boldsymbol {\theta }}^{(t)}|{\boldsymbol {\theta }}^{(t)})+H({\boldsymbol {\theta }}^{(t)}|{\boldsymbol {\theta }}^{(t)})\,,$

i oduzimanjem ove poslednje jednačine sa onom iz prethodne, dobijamo

$\log p(\mathbf {X} |{\boldsymbol {\theta }})-\log p(\mathbf {X} |{\boldsymbol {\theta }}^{(t)})=Q({\boldsymbol {\theta }}|{\boldsymbol {\theta }}^{(t)})-Q({\boldsymbol {\theta }}^{(t)}|{\boldsymbol {\theta }}^{(t)})+H({\boldsymbol {\theta }}|{\boldsymbol {\theta }}^{(t)})-H({\boldsymbol {\theta }}^{(t)}|{\boldsymbol {\theta }}^{(t)})\,,$

Međutim, Gisova nejednakost nam govori da $H({\boldsymbol {\theta }}|{\boldsymbol {\theta }}^{(t)})\geq H({\boldsymbol {\theta }}^{(t)}|{\boldsymbol {\theta }}^{(t)})$, pa možemo zaključiti da

$\log p(\mathbf {X} |{\boldsymbol {\theta }})-\log p(\mathbf {X} |{\boldsymbol {\theta }}^{(t)})\geq Q({\boldsymbol {\theta }}|{\boldsymbol {\theta }}^{(t)})-Q({\boldsymbol {\theta }}^{(t)}|{\boldsymbol {\theta }}^{(t)})\,.$

Drugim rečima, birajući ${\boldsymbol {\theta }}$ da unapredimo $Q({\boldsymbol {\theta }}|{\boldsymbol {\theta }}^{(t)})$ izvan $Q({\boldsymbol {\theta }}^{(t)}|{\boldsymbol {\theta }}^{(t)})$ će unaprediti $\log p(\mathbf {X} |{\boldsymbol {\theta }})$ preko $\log p(\mathbf {X} |{\boldsymbol {\theta }}^{(t)})$ najmanje toliko.

Aplikacije

Pod nekim okolnostima, vrlo je zgodno gledati na EM algoritam kao dva naizmenična koraka maksimiziranja. Razmotrimo funkciju:

$F(q,\theta )=\operatorname {E} _{q}[\log L(\theta ;x,Z)]+H(q)=-D_{\mathrm {KL} }{\big (}q{\big \|}p_{Z|X}(\cdot |x;\theta ){\big )}+\log L(\theta ;x)$

gde je q proizvoljna raspodela verovatnoća nad neposmatranim podacima z, p_Z|X(· |x;θ) je uslovna raspodela neposmatranih podataka gde su dati posmatrani podaci x, H je entropija i D_KL je Kulbak-Lajbler divergencija.

Onda se koraci EM algoritma mogu posmatrati kao:

Korak očekivanja: Izaberi q da maksimizuješ F:

$q^{(t)}=\operatorname {*} {arg\,max}_{q}\ F(q,\theta ^{(t)})$

Korak maksimizacije: Izaberi θ da maksimizuješ F:

$\theta ^{(t+1)}=\operatorname {*} {arg\,max}_{\theta }\ F(q^{(t)},\theta )$

Primer

Gausova raspodela

Animacija koja demonstrira EM algoritam koristeći model dvokomponentne Gausove raspodele nad podacima gejzira Stari Verni. Algoritam ide od nasumične inicijalizacije do konvergencije.

Neka je x = (x₁,x₂,…,x_n) primer od n nezavisnih opservacija iz raspodele dve multivarijacione normalne raspodele dimenzije d, i neka je z=(z₁,z₂,…,z_n) latentna varijabla kojom se određuje komponenta iz koje potiče posmatranje.

$X_{i}|(Z_{i}=1)\sim {\mathcal {N}}_{d}({\boldsymbol {\mu }}_{1},\Sigma _{1})$ i $X_{i}|(Z_{i}=2)\sim {\mathcal {N}}_{d}({\boldsymbol {\mu }}_{2},\Sigma _{2})$

gde je

$\operatorname {P} (Z_{i}=1)=\tau _{1}\,$ i $\operatorname {P} (Z_{i}=2)=\tau _{2}=1-\tau _{1}$

Cilj je da se procene nepoznati parametari koji predstavljaju “mešanje” vrednosti između Gausovih i načini i kovarijanse svakog.

$\theta ={\big (}{\boldsymbol {\tau }},{\boldsymbol {\mu }}_{1},{\boldsymbol {\mu }}_{2},\Sigma _{1},\Sigma _{2}{\big )}$

gde je funkcija verodostojnosti:

$L(\theta ;\mathbf {x} ,\mathbf {z} )=P(\mathbf {x} ,\mathbf {z} \vert \theta )=\prod _{i=1}^{n}\sum _{j=1}^{2}\mathbb {I} (z_{i}=j)\ \tau _{j}\ f(\mathbf {x} _{i};{\boldsymbol {\mu }}_{j},\Sigma _{j})$

gde je $\mathbb {I}$ indikator funkcije, a f je raspodela verovatnoće od više varijanta. Ovo može biti prepisano familiji eksponencijalnih formi:

$L(\theta ;\mathbf {x} ,\mathbf {z} )=\exp \left\{\sum _{i=1}^{n}\sum _{j=1}^{2}\mathbb {I} (z_{i}=j){\big [}\log \tau _{j}-{\tfrac {1}{2}}\log |\Sigma _{j}|-{\tfrac {1}{2}}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{j})^{\top }\Sigma _{j}^{-1}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{j})-{\tfrac {d}{2}}\log(2\pi ){\big ]}\right\}.$

Da bi se videla poslednja jednakost, imajte na umu da za svako i svi indikatori $\mathbb {I} (z_{i}=j)$ su jednaki nuli, osim jednog koji je jednak jedan. Unutrašnja suma se na taj način smanjuje na jedan član.

Korak E

Trenutna procena parametara θ^(t) uslovna raspodela Z_i je determinisana sa Bajesovom teoremom, da bude proporcionalne visine od normalne raspodele verovatnoće, sa težinom τ:

$T_{j,i}^{(t)}:=\operatorname {P} (Z_{i}=j|X_{i}=\mathbf {x} _{i};\theta ^{(t)})={\frac {\tau _{j}^{(t)}\ f(\mathbf {x} _{i};{\boldsymbol {\mu }}_{j}^{(t)},\Sigma _{j}^{(t)})}{\tau _{1}^{(t)}\ f(\mathbf {x} _{i};{\boldsymbol {\mu }}_{1}^{(t)},\Sigma _{1}^{(t)})+\tau _{2}^{(t)}\ f(\mathbf {x} _{i};{\boldsymbol {\mu }}_{2}^{(t)},\Sigma _{2}^{(t)})}}$.

Rezultat E koraka u funkciji:

${\begin{aligned}Q(\theta |\theta ^{(t)})&=\operatorname {E} [\log L(\theta ;\mathbf {x} ,\mathbf {Z} )]\\&=\sum _{i=1}^{n}\sum _{j=1}^{2}T_{j,i}^{(t)}{\big [}\log \tau _{j}-{\tfrac {1}{2}}\log |\Sigma _{j}|-{\tfrac {1}{2}}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{j})^{\top }\Sigma _{j}^{-1}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{j})-{\tfrac {d}{2}}\log(2\pi ){\big ]}\end{aligned}}$

Da bismo videli poslednju jednakost, imajte na umu da smo sumiranjem po svim mogućim vrednostima od z gde je verovatnoća svakog z proizvod $\prod _{i=1}^{n}T_{j,i}^{(t)}$. Sada pogledajmo koeficijente svakog člana unutar sume za.$L(\theta ;\mathbf {x} ,\mathbf {z} )$. Biće dva člana $T_{1,i}^{(t)}(\sum _{j=1,2}\prod _{k\neq i}T_{j,k}^{(t)})$ and $T_{2,i}^{(t)}(\sum _{j=1,2}\prod _{k\neq i}T_{j,k}^{(t)})$. Budući da termin u zagradi marginalizuje po svim mogućim slučajevima kad $k\neq i$, je jednako 1. Tako su koeficijenti svakog člana $T_{1,i}^{(t)}$ i $T_{2,i}^{(t)}$ koji teže jednakosti.

Korak M

Kvadratni oblik Q(θ|θ^(t)) znači da određivanje maksimalne vrednosti θ je relativno jednostavno. Imajte na umu da τ, (μ₁,Σ₁) i (μ₂,Σ₂) mogu biti sve maskimizovano nezavisno jedni od drugih, jer se svi oni pojavljuju u odvojenim linearnim članovima. Za početak, uzmimo u obzir τ, koje ima ograničenje τ₁ + τ₂=1:

${\begin{aligned}{\boldsymbol {\tau }}^{(t+1)}&={\underset {\boldsymbol {\tau }}{\operatorname {arg\,max} }}\ Q(\theta |\theta ^{(t)})\\&={\underset {\boldsymbol {\tau }}{\operatorname {arg\,max} }}\ \left\{\left[\sum _{i=1}^{n}T_{1,i}^{(t)}\right]\log \tau _{1}+\left[\sum _{i=1}^{n}T_{2,i}^{(t)}\right]\log \tau _{2}\right\}\end{aligned}}$

Ovo ima isti oblik kao MLE za binomnu raspodelu, tako da:

$\tau _{j}^{(t+1)}={\frac {\sum _{i=1}^{n}T_{j,i}^{(t)}}{\sum _{i=1}^{n}(T_{1,i}^{(t)}+T_{2,i}^{(t)})}}={\frac {1}{n}}\sum _{i=1}^{n}T_{j,i}^{(t)}$

U narednim procenama (μ₁,Σ₁):

${\begin{aligned}({\boldsymbol {\mu }}_{1}^{(t+1)},\Sigma _{1}^{(t+1)})&={\underset {{\boldsymbol {\mu }}_{1},\Sigma _{1}}{\operatorname {arg\,max} }}\ Q(\theta |\theta ^{(t)})\\&={\underset {{\boldsymbol {\mu }}_{1},\Sigma _{1}}{\operatorname {arg\,max} }}\ \sum _{i=1}^{n}T_{1,i}^{(t)}\left\{-{\tfrac {1}{2}}\log |\Sigma _{1}|-{\tfrac {1}{2}}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{1})^{\top }\Sigma _{1}^{-1}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{1})\right\}\end{aligned}}$

Ovo ima istu formu kao i težak MLE za normalnu raspodelu, tako da

${\boldsymbol {\mu }}_{1}^{(t+1)}={\frac {\sum _{i=1}^{n}T_{1,i}^{(t)}\mathbf {x} _{i}}{\sum _{i=1}^{n}T_{1,i}^{(t)}}}$ and $\Sigma _{1}^{(t+1)}={\frac {\sum _{i=1}^{n}T_{1,i}^{(t)}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{1}^{(t+1)})(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{1}^{(t+1)})^{\top }}{\sum _{i=1}^{n}T_{1,i}^{(t)}}}$

i, preko simetrije:

${\boldsymbol {\mu }}_{2}^{(t+1)}={\frac {\sum _{i=1}^{n}T_{2,i}^{(t)}\mathbf {x} _{i}}{\sum _{i=1}^{n}T_{2,i}^{(t)}}}$ and $\Sigma _{2}^{(t+1)}={\frac {\sum _{i=1}^{n}T_{2,i}^{(t)}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{2}^{(t+1)})(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{2}^{(t+1)})^{\top }}{\sum _{i=1}^{n}T_{2,i}^{(t)}}}$.

Literatura

• Robert Hogg, Joseph McKean and Allen Craig. Introduction to Mathematical Statistics. pp. 359-364. Upper Saddle River, NJ: Pearson Prentice Hall, 2005.
• The on-line textbook: Information Theory, Inference, and Learning Algorithms, by David J.C. MacKay includes simple examples of the EM algorithm such as clustering using the soft k-means algorithm, and emphasizes the variational view of the EM algorithm, as described in Chapter 33.7 of version 7.2 (fourth edition).
• Theory and Use of the EM Method by M. R. Gupta and Y. Chen is a well-written short book on EM, including detailed derivation of EM for GMMs, HMMs, and Dirichlet.
• Bilmes, Jeff. „A Gentle Tutorial of the EM Algorithm and its Application to Parameter Estimation for Gaussian Mixture and Hidden Markov Models”. CiteSeerX 10.1.1.28.613 ,  includes a simplified derivation of the EM equations for Gaussian Mixtures and Gaussian Mixture Hidden Markov Models.
• Variational Algorithms for Approximate Bayesian Inference, by M. J. Beal includes comparisons of EM to Variational Bayesian EM and derivations of several models including Variational Bayesian HMMs (chapters).
• Dellaert, Frank. „The Expectation Maximization Algorithm”. CiteSeerX 10.1.1.9.9735 ,  gives an easier explanation of EM algorithm in terms of lowerbound maximization.
• The Expectation Maximization Algorithm: A short tutorial, A self-contained derivation of the EM Algorithm by Sean Borman.
• The EM Algorithm, by Xiaojin Zhu.
• Roche, Alexis (2011). „EM algorithm and variants: an informal tutorial”. arXiv:1105.1476 . 
• Bishop, Christopher M. (2006). Pattern Recognition and Machine Learning. Springer. ISBN 978-0-387-31073-2. 
• Einicke, G.A. (2012). Smoothing, Filtering and Prediction: Estimating the Past, Present and Future. Rijeka, Croatia: Intech. ISBN 978-953-307-752-9. 

Spoljašnje veze

• Various 1D, 2D and 3D demonstrations of EM together with Mixture Modeling are provided as part of the paired SOCR activities and applets. These applets and activities show empirically the properties of the EM algorithm for parameter estimation in diverse settings.
• Class hierarchy in C++ (GPL) including Gaussian Mixtures
• Fast and clean C implementation of the Expectation Maximization (EM) algorithm for estimating Gaussian Mixture Models (GMMs).