EM algoritmus

Az EM-algoritm ( eng. Expectation-maximization (EM) algoritmus ) egy olyan algoritmus, amelyet a matematikai statisztikákban használnak a valószínűségi modellek paramétereinek maximális valószínűségi becslésére abban az esetben, ha a modell néhány rejtett változótól függ . Az algoritmus minden iterációja két lépésből áll. Az E-lépésben (elvárás) a likelihood függvény várható értékét számítjuk ki , míg a látens változókat megfigyelhetőként kezeljük . Az M-lépésben (maximalizálás) a maximális likelihood becslés kerül kiszámításra, így növelve az E-lépésben számított várható valószínűséget. Ezt az értéket azután az E-lépéshez használja a következő iterációban. Az algoritmus a konvergenciáig fut.

Gyakran az EM algoritmust használják Gauss -féle keverék elválasztására .

Az algoritmus leírása

Legyen a megfigyelt változók néhány értéke, és legyen rejtett változó. Ezek együtt egy teljes adathalmazt alkotnak . Általánosságban elmondható, hogy van néhány tipp, amely megkönnyíti a probléma megoldását, ha ismert. Például, ha eloszlások keveréke van , a valószínűségi függvény könnyen kifejezhető a keverék egyes eloszlásának paramétereivel. ${\textbf {X}}$ ${\textbf {T}}$ ${\textbf {X}}$ ${\textbf {T}}$ ${\textbf {T}}$

Tegyük fel , hogy ez egy teljes, paraméterekkel rendelkező adathalmaz valószínűségi sűrűsége (folytonos esetben) vagy valószínűségi függvénye (diszkrét esetben) : Ez a függvény a teljes modell valószínűségeként fogható fel, ha úgy tekintjük, a paraméterek függvénye . Vegye figyelembe, hogy a rejtett komponens feltételes eloszlása bizonyos megfigyelések és egy rögzített paraméterkészlet mellett a következőképpen fejezhető ki: $p$ $\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} } }}

a kiterjesztett Bayes -képlet és a teljes valószínűségi képlet segítségével . Így csak tudnunk kell a megfigyelt komponens eloszlását egy rögzített látens esetén és a látens adatok valószínűségét . $p({\mathbf X}|{\mathbf T},\Theta )$ $p({\mathbf T}|\Theta )$

Az EM algoritmus iteratív módon javítja a kezdeti pontszámot új pontszámértékek kiszámításával stb. Minden lépésnél a következőképpen történik az áttérés a következőről : $\Theta _{0}$ $\Theta _{1},\Theta _{2},$ $\Theta _{{n+1}}$ $\Theta_n$

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

hol van a valószínűség várható logaritmusa. Más szóval, nem tudjuk azonnal kiszámítani a pontos valószínűséget, de az ismert adatokból ( ) utólagos becslést találhatunk a látens változók különböző értékeinek valószínűségére . Minden egyes érték- és paraméterkészlethez kiszámíthatjuk a valószínűségi függvény várható értékét ehhez a halmazhoz . Ez az előző értéktől függ, mert ez az érték befolyásolja a látens változók valószínűségét . $Q(\Theta)$ $x$ $T$ $T$ $\Theta$ $x$ $\Theta$ $T$

$Q(\Theta)$ a következőképpen számítják ki:

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

vagyis ez egy feltételes elvárás a feltétel alatt . $\log p\left({\mathbf X},{\mathbf T}\,|\,\Theta \jobbra)$ $\mathbf {X}$

Más szóval, az az érték, amely maximalizálja (M) a log-valószínűség feltételes átlagát (E) a megfigyelt változók adott értékeire és a paraméterek előző értékére. Folyamatos esetben az értéket a következőképpen számítjuk ki: $\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}

Alternatív leírás

Bizonyos körülmények között célszerű az EM algoritmust két váltakozó maximalizálási lépésnek tekinteni. [1] [2] Tekintsük a függvényt:

F(q,\theta )=\operátornév {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)

ahol q a nem megfigyelt Z változók valószínűségi eloszlása ; p Z | X ( · | x ; θ ) a nem megfigyelt változók feltételes eloszlása fix megfigyelhető x és θ paraméterek esetén ; H az entrópia , D KL pedig a Kullback-Leibler távolság .

Ekkor az EM algoritmus lépései a következőképpen ábrázolhatók:

E(elvárás) lépés : Válassza a q -t az F maximalizálásához :

q^{(t)}=\operátornév {*} {\arg \,\max }_{q}\ F(q,\theta ^{(t)})

M(aximizálás) lépés : Válassza a θ -t az F maximalizálásához :

\theta ^{(t+1)}=\operátornév {*} {\arg \,\max }_{\theta }\ F(q^{(t)},\theta )

Használati példák

k-means - klaszterezési algoritmus , amely az EM algoritmus ötletére épül
Elasztikus leképezési módszer nemlineáris adatdimenziós csökkentésére
Baum-Welsh algoritmus - rejtett Markov modellek paramétereinek becslésére szolgáló algoritmus

Jegyzetek

↑ Radford; Neal; Hinton, Geoffrey . Az EM-algoritmus nézete, amely inkrementális, ritka és egyéb változatokat indokol // 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 Az EM algoritmus // A statisztikai tanulás elemei (neopr.) . - New York: Springer, 2001. - S. 236-243. — ISBN 0-387-95284-5 .

Linkek

Gépi tanulás és adatbányászat
Feladatok	Osztályozási feladat Tanulás tanár nélkül Tanár által segített tanulás Regresszió analízis AutoML Egyesületi szabályzat Funkció kivonás Tulajdonságok képzése Rangsorképzés Nyelvtani levezetés Online tanulás
Tanulás tanárral	k-legközelebbi szomszéd módszer Naiv Bayes osztályozó döntési fa Támogatja a vektoros gépet Lineáris regresszió Logisztikus regresszió perceptron Modellegyüttesek Zsákolás fellendítése véletlenszerű erdő Releváns vektoros módszer
klaszteranalízis	k-módszer Fuzzy klaszterezési módszer Hierarchikus klaszterezés EM algoritmus NYÍR GYÓGYMÓD DBSCAN OPTIKA Átlageltolás
Dimenziócsökkentés	Faktoranalízis Főkomponens módszer CCA ICA LDA Nem negatív mátrix kiterjesztése t-SNE
Strukturális előrejelzés	Grafikon valószínűségi modell Bayesi hálózat Rejtett Markov-modell CRF
Anomália észlelése	k-legközelebbi szomszéd módszer Helyi kibocsátási szint
Grafikon valószínűségi modellek	Bayesi hálózat Markov hálózat Rejtett Markov-modell
Neurális hálózatok	Limitált Boltzmann gép önszerveződő térkép Aktiválási funkció Szigma alakú softmax Radiális bázisfüggvény Hátsó szaporítási módszer Mély tanulás Többrétegű perceptron Ismétlődő neurális hálózat hosszú távú rövid távú memória Ellenőrzött visszatérő blokk Konvolúciós Neurális Hálózat U-háló Autoencoder
Megerősítő tanulás	Markov folyamat Bellman egyenlet Mohó algoritmus Q-learning SARSA Időbeli különbség (TD)
Elmélet	Vapnik-Chervonenkis elmélet Elfogultság-diszperziós dilemma Számítógépes tanuláselmélet Empirikus kockázatminimalizálás Occam tanul PAC tanulás Statisztikai tanuláselmélet
Folyóiratok és konferenciák	NeurIPS ICML ML JMLR ArXiv:cs.LG