EM-algoritmi

EM-algoritmi ( eng. Expectation-maximization (EM) algoritmi ) on algoritmi, jota käytetään matemaattisissa tilastoissa maksimitodennäköisyysestimaattien löytämiseen todennäköisyysmallien parametreille siinä tapauksessa, että malli riippuu joistakin piilomuuttujista . Jokainen algoritmin iteraatio koostuu kahdesta vaiheesta. E-vaiheessa (odotus) lasketaan todennäköisyysfunktion odotusarvo , kun taas piileviä muuttujia pidetään havainnoitavina .. M-vaiheessa (maksimointi) lasketaan maksimitodennäköisyysestimaatti, mikä lisää E-vaiheessa laskettua odotettua todennäköisyyttä. Tätä arvoa käytetään sitten E-vaiheessa seuraavassa iteraatiossa. Algoritmi suoritetaan konvergenssiin asti.

Usein EM-algoritmia käytetään erottamaan Gaussin sekoitus .

Algoritmin kuvaus

Olkoon joitain havaittujen muuttujien arvoja ja olemaan piilotettuja muuttujia. Yhdessä ne muodostavat täydellisen tietojoukon. Yleisesti ottaen ongelman tiedossa voi olla jokin vihje, joka helpottaa ongelman ratkaisemista. Jos esimerkiksi jakaumia on sekoitus , todennäköisyysfunktio ilmaistaan helposti seoksen yksittäisten jakaumien parametreilla. ${\textbf {X}}$ ${\textbf {T}}$ ${\textbf {X}}$ ${\textbf {T}}$ ${\textbf {T}}$

Oletetaan, että se on täydellisen parametrien sisältävän tietojoukon todennäköisyystiheys (jatkuvassa tapauksessa) tai todennäköisyysfunktio (diskreetissä tapauksessa) : Tämä funktio voidaan ymmärtää koko mallin todennäköisyydeksi , jos ajatellaan sitä parametrien funktio . Huomaa, että piilotetun komponentin ehdollinen jakautuminen tietyn havainnon ja kiinteän parametrijoukon aikana voidaan ilmaista seuraavasti: $s$ $\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} } }}

käyttämällä laajennettua Bayesin kaavaa ja kokonaistodennäköisyyskaavaa . Näin ollen meidän tarvitsee vain tietää havaitun komponentin jakautuminen kiinteälle latentille ja piilevän datan todennäköisyys . $p({\mathbf X}|{\mathbf T},\Theta )$ $p({\mathbf T}|\Theta )$

EM-algoritmi parantaa iteratiivisesti alkuperäistä pistemäärää laskemalla uusia pistearvoja ja niin edelleen. Jokaisessa vaiheessa siirtyminen kohteesta suoritetaan seuraavasti: $\Theta _{0}$ $\Theta _{1},\Theta _{2},$ $\Theta _{{n+1}}$ $\Theta_n$

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

missä on todennäköisyyden odotettu logaritmi. Toisin sanoen emme voi heti laskea tarkkaa todennäköisyyttä, mutta tunnetuista tiedoista ( ) voimme löytää jälkiarvion piilevien muuttujien eri arvojen todennäköisyyksistä . Jokaiselle arvo- ja parametrijoukolle voimme laskea tämän joukon todennäköisyysfunktion odotukset . Se riippuu edellisestä arvosta, koska tämä arvo vaikuttaa piilevien muuttujien todennäköisyyksiin . $Q(\Theta)$ $X$ $T$ $T$ $\Theta$ $X$ $\Theta$ $T$

$Q(\Theta)$ lasketaan seuraavasti:

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

eli tämä on ehdollinen odotus ehdolla . $\log p\left({\mathbf X},{\mathbf T}\,|\,\Theta \oikea)$ $\mathbf {X}$

Toisin sanoen on arvo, joka maksimoi (M) log-todennäköisyyden ehdollisen keskiarvon (E) havaittujen muuttujien annetuille arvoille ja parametrien edelliselle arvolle. Jatkuvassa tapauksessa arvo lasketaan seuraavasti: $\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}

Vaihtoehtoinen kuvaus

Tietyissä olosuhteissa on kätevää ajatella EM-algoritmia kahdeksi vuorottelevaksi maksimointivaiheeksi. [1] [2] Harkitse funktiota:

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

missä q on havaitsemattomien muuttujien Z todennäköisyysjakauma ; p Z | X ( · | x ; θ ) on havainnoimattomien muuttujien ehdollinen jakauma kiinteille havaittaville x ja parametreille θ ; H on entropia ja D KL on Kullback-Leibler-etäisyys .

Sitten EM-algoritmin vaiheet voidaan esittää seuraavasti:

E(odotus)vaihe : Valitse q maksimoidaksesi F :

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

M(maksimointi) askel : Valitse θ maksimoidaksesi F :

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

Käyttöesimerkkejä

k-means - klusterointialgoritmi , joka on rakennettu EM-algoritmin ideaan
Elastinen karttamenetelmä epälineaarisen datan ulottuvuuden vähentämiseen
Baum-Welsh-algoritmi - algoritmi piilotettujen Markov-mallien parametrien arvioimiseksi

Muistiinpanot

↑ Radford; Neal; Hinton, Geoffrey . Näkymä EM-algoritmista, joka oikeuttaa inkrementaaliset, harvat ja muut variantit // 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-algoritmi // Tilastollisen oppimisen elementit (uuspr.) . - New York: Springer, 2001. - S. 236-243. — ISBN 0-387-95284-5 .

Linkit

Koneoppiminen ja tiedon louhinta
Tehtävät	Luokittelu ongelma Oppiminen ilman opettajaa Opettajan avustama oppiminen Taantumisanalyysi AutoML Yhdistyksen säännöt Ominaisuuksien erottaminen Ominaisuuksien koulutus Ranking koulutus Kieliopillinen johtaminen Verkko-oppiminen
Opettajan kanssa oppimista	k-lähimmän naapurin menetelmä Naiivi Bayesin luokitin päätöspuu Tuki vektorikonetta Lineaarinen regressio Logistinen regressio perceptron Mallien kokoonpanot Pussittaminen tehostaa satunnainen metsä Asiaankuuluva vektorimenetelmä
ryhmäanalyysi	k-keinomenetelmä Sumea klusterointimenetelmä Hierarkkinen klusterointi EM-algoritmi KOIVU PARANTAA DBSCAN OPTIIKKA Keskimääräinen siirto
Mittasuhteiden vähentäminen	Tekijäanalyysi Pääkomponenttimenetelmä CCA ICA LDA Ei-negatiivinen matriisin laajennus t-SNE
Rakenteellinen ennustaminen	Graafinen todennäköisyysmalli Bayesin verkko Piilotettu Markovin malli CRF
Anomalian havaitseminen	k-lähimmän naapurin menetelmä Paikallinen päästötaso
Piirrä todennäköisyysmallit	Bayesin verkko Markovin verkko Piilotettu Markovin malli
Neuroverkot	Rajoitettu Boltzmann-kone itseorganisoituva kartta Aktivointitoiminto Sigmoidi softmax Radiaalinen kantafunktio Takaisin lisäysmenetelmä Syväoppiminen Monikerroksinen perceptroni Toistuva neuroverkko pitkä lyhytaikainen muisti Hallittu toistuva esto Konvoluutiohermoverkko U-verkko Autoenkooderi
Vahvistusoppiminen	Markovin prosessi Bellmanin yhtälö Ahne algoritmi Q-oppiminen SARSA Aikaero (TD)
Teoria	Vapnik-Chervonenkis teoria Bias-dispersion dilemma Laskennallinen oppimisteoria Empiirinen riskin minimointi Occam oppii PAC-oppiminen Tilastollinen oppimisteoria
Lehdet ja konferenssit	NeurIPS ICML ML JMLR ArXiv:cs.LG