EM algoritm

EM-algoritm ( eng. Expectation-maximization (EM) algorithm ) är en algoritm som används i matematisk statistik för att hitta maximala sannolikhetsuppskattningar för parametrarna för probabilistiska modeller, i det fall då modellen beror på några dolda variabler . Varje iteration av algoritmen består av två steg. I E-steget (förväntning) beräknas sannolikhetsfunktionens förväntade värde medan de latenta variablerna betraktas som observerbara. I M-steget (maximering) beräknas den maximala sannolikhetsuppskattningen, vilket ökar den förväntade sannolikheten som beräknas i E-steget. Detta värde används sedan för E-steget i nästa iteration. Algoritmen exekveras tills konvergens.

Ofta används EM-algoritmen för att separera en blandning av Gausser .

Beskrivning av algoritmen

Låt vara några av värdena för de observerade variablerna och vara dolda variabler. Tillsammans bildar de en komplett datamängd. I allmänhet kan det finnas någon ledtråd som gör det lättare att lösa problemet om det är känt. Till exempel, om det finns en blandning av distributioner , är sannolikhetsfunktionen lätt att uttrycka i termer av parametrarna för de individuella fördelningarna av blandningen. ${\textbf {X}}$ ${\textbf {T}}$ ${\textbf {X}}$ ${\textbf {T}}$ ${\textbf {T}}$

Låt oss anta att det är sannolikhetstätheten (i det kontinuerliga fallet) eller sannolikhetsfunktionen (i det diskreta fallet) för en komplett datamängd med parametrar : Denna funktion kan förstås som sannolikheten för hela modellen, om vi betraktar den som en funktion av parametrarna . Observera att den villkorliga fördelningen av den dolda komponenten under viss observation och en fast uppsättning parametrar kan uttryckas enligt följande: $sid$ $\Theta$ $p({\mathbf X},{\mathbf T}|\Theta ).$ $\Theta$

p(\mathbf {T} |\mathbf {X} ,\Theta )={\frac {p(\mathbf {X} |\mathbf {T} ,\Theta )p(\mathbf {T} | \Theta )}{p(\mathbf {X} |\Theta )}}={\frac {p(\mathbf {X} |\mathbf {T} ,\Theta )p(\mathbf {T} |\Theta )}{\int p(\mathbf {X} |\mathbf {\hat {T)) ,\Theta )p(\mathbf {\hat {T)) |\Theta )d\mathbf {\hat {T} } }}

med den utökade Bayes- formeln och den totala sannolikhetsformeln . Således behöver vi bara veta fördelningen av den observerade komponenten för en fix latent och sannolikheten för latent data . $p({\mathbf X}|{\mathbf T},\Theta )$ $p({\mathbf T}|\Theta )$

EM-algoritmen förbättrar iterativt den initiala poängen genom att beräkna nya poängvärden och så vidare. Vid varje steg utförs övergången till från enligt följande: $\Theta _{0}$ $\Theta _{1},\Theta _{2},$ $\Theta _{{n+1}}$ $\Theta_n$

\Theta _{{n+1}}=\arg \max _{{\Theta }}Q(\Theta)

var är den förväntade logaritmen för sannolikheten. Med andra ord kan vi inte omedelbart beräkna den exakta sannolikheten, men från kända data ( ) kan vi hitta en efterhandsuppskattning av sannolikheterna för olika värden av de latenta variablerna . För varje uppsättning värden och parametrar kan vi beräkna förväntan på sannolikhetsfunktionen för denna uppsättning . Det beror på det tidigare värdet eftersom detta värde påverkar sannolikheterna för de latenta variablerna . $Q(\Theta )$ $X$ $T$ $T$ $\Theta$ $X$ $\Theta$ $T$

$Q(\Theta )$ beräknas enligt följande:

Q(\Theta )=E_{{{\mathbf T))}\!\!\left[\log p\left({\mathbf X},{\mathbf T}\,|\,\Theta \right) {\Big |}{\mathbf X}\right]

det vill säga detta är en villkorad förväntan under villkoret . $\log p\left({\mathbf X},{\mathbf T}\,|\,\Theta \right)$ $\mathbf {X}$

Med andra ord är värdet som maximerar (M) det villkorliga medelvärdet (E) av log-sannolikheten för de givna värdena för de observerade variablerna och det tidigare värdet av parametrarna. I det kontinuerliga fallet beräknas värdet så här: $\Theta _{{n+1}}$ $Q(\Theta )$

Q(\Theta )=E_{\mathbf {T} }\!\!\left[\log p\left(\mathbf {X} ,\mathbf {T} \,|\,\Theta \right ){\Big |}\mathbf {X} \right]=\int _{-\infty }^{\infty }p\left(\mathbf {T} \,|\,\mathbf {X} ,\Theta _{n}\right)\log p\left(\mathbf {X} ,\mathbf {T} \,|\,\Theta \right)d\mathbf {T}

Alternativ beskrivning

Under vissa omständigheter är det bekvämt att tänka på EM-algoritmen som två alternerande maximeringssteg. [1] [2] Tänk på funktionen:

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

där q är sannolikhetsfördelningen för oobserverade variabler Z ; p Z | X ( · | x ; θ ) är den villkorliga fördelningen av icke observerade variabler för fixerade observerbara värden x och parametrarna θ ; H är entropin och D KL är avståndet Kullback-Leibler .

Sedan kan stegen i EM-algoritmen representeras som:

Förväntningssteg : Välj q för att maximera F :

q^{(t)}=\operatörsnamn {*} {\arg \,\max }_{q}\ F(q,\theta ^{(t)})

M(aximisering) steg : Välj θ för att maximera F :

\theta ^{(t+1)}=\operatörsnamn {*} {\arg \,\max }_{\theta }\ F(q^{(t)},\theta )

Användningsexempel

k-means - klustringsalgoritm byggd på idén om EM-algoritmen
Elastisk kartmetod för icke-linjär datadimensionalitetsreduktion
Baum-Welsh algoritm - en algoritm för att uppskatta parametrarna för dolda Markov-modeller

Anteckningar

↑ Radford; Neal; Hinton, Geoffrey . En vy av EM-algoritmen som motiverar inkrementella, sparsamma och andra varianter // Learning in Graphical Models : journal / Michael I. Jordan . - Cambridge, MA: MIT Press, 1999. - P. 355-368 . — ISBN 0262600323 .
↑ Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome. 8.5 EM-algoritmen // The Elements of Statistical Learning (neopr.) . - New York: Springer, 2001. - S. 236-243. — ISBN 0-387-95284-5 .

Länkar

Maskininlärning och datautvinning
Uppgifter	Klassificeringsproblem Lärande utan lärare Lärarassisterat lärande Regressionsanalys AutoML Föreningens regler Särdragsextraktion Egenskapsträning Ranking utbildning Grammatisk härledning Online lärande
Att lära sig med en lärare	k-närmaste granne metod Naiv Bayes klassificerare beslutsträd Stöd vektor maskin Linjär regression Logistisk tillbakagång perceptron Ensembler av modeller Säckväv förstärkning slumpmässig skog Relevant vektormetod
klusteranalys	k-betyder metod Fuzzy klustringsmetod Hierarkisk klustring EM algoritm BJÖRK BOTA DBSCAN OPTIK Genomsnittlig förskjutning
Dimensionalitetsreduktion	Faktoranalys Huvudkomponentmetoden CCA ICA LDA Icke-negativ matrisexpansion t-SNE
Strukturell prognos	Graph probabilistisk modell Bayesiskt nätverk Dold Markov-modell CRF
Anomali upptäckt	k-närmaste granne metod Lokal utsläppsnivå
Grafisk probabilistiska modeller	Bayesiskt nätverk Markov nätverk Dold Markov-modell
Neurala nätverk	Begränsad Boltzmann-maskin självorganiserande karta Aktiveringsfunktion Sigmoid softmax Radiell basfunktion Ryggförökningsmetod Djup lärning Flerskiktsperceptron Återkommande neurala nätverk långtidsminne Kontrollerat återkommande block Konvolutionellt neuralt nätverk U-Net Autokodare
Förstärkningsinlärning	Markov process Bellmans ekvation Girig algoritm Q-lärande SARSA Temporell skillnad (TD)
Teori	Vapnik-Chervonenkis teori Bias-Dispersion Dilemma Beräkningslärandeteori Empirisk riskminimering Occam lär sig PAC-inlärning Statistisk inlärningsteori
Tidskrifter och konferenser	NeurIPS ICML ML JMLR ArXiv:cs.LG