EM algoritmi (odotus-maksimointi): yksinkertainen määritelmä

Maksimitodennäköisyyden estimointi > EM-algoritmi (odotus-maksimointi)

kannattaa lukea tämä artikkeli ensin: mikä on Maksimitodennäköisyyden estimointi?

mikä on EM-algoritmi?

EM-algoritmia voidaan käyttää arvioimaan latentteja muuttujia, kuten seosjakaumista peräisin olevia muuttujia (tiedät, että ne tulivat seoksesta, mutta et mitä tiettyä jakaumaa).

odotus-maksimointi (em) algoritmi on tapa löytää maksimitodennäköisyysarviot mallin parametreille, kun tietosi ovat epätäydellisiä, niistä puuttuu datapisteitä tai niissä on havaitsemattomia (piilotettuja) piileviä muuttujia. Se on iteratiivinen tapa approksimoida maksimitodennäköisyysfunktiota. Vaikka suurimman todennäköisyyden estimointi voi löytää” parhaiten sopivan ” mallin tietojoukolle, se ei toimi erityisen hyvin epätäydellisissä tietojoukoissa. Monimutkaisempi EM-algoritmi voi löytää mallin parametrit, vaikka tietoja puuttuisi. Se toimii valitsemalla satunnaisia arvoja puuttuvat tiedot pistettä, ja käyttämällä näitä arvauksia arvioida toisen joukon tietoja. Uusien arvojen avulla luodaan parempi arvaus ensimmäiselle joukolle, ja prosessi jatkuu, kunnes algoritmi konvergoituu kiinteässä pisteessä.

Katso myös: EM-algoritmi selitettynä yhdessä kuvassa.

MLE vs. EM

vaikka Maksimitodennäköisyysarvio (MLE) ja EM voivat molemmat löytää ”parhaiten sopivat” parametrit, niiden löytämismallit ovat hyvin erilaisia. MLE kerää kaikki tiedot ensin ja käyttää sitten näitä tietoja muodostaakseen todennäköisimmän mallin. EM tekee arvata parametrit ensin-kirjanpito puuttuvat tiedot-sitten hienosäätää mallin sopivaksi arvauksia ja havaitut tiedot. Algoritmin perusvaiheet ovat:

1. mallin parametreille tehdään alustava arvaus ja luodaan todennäköisyysjakauma. Tätä kutsutaan joskus” odotetun ”jakauman” E-vaiheeksi”.
2. Uudet havaitut tiedot syötetään malliin.
3. todennäköisyysjakauma e-vaiheesta on viritetty sisältämään uudet tiedot. Tätä kutsutaan joskus ”M-askeleeksi.”
4. vaiheet 2-4 toistetaan, kunnes saavutetaan stabiilisuus (eli jakauma, joka ei muutu E-askeleesta M-vaiheeseen).

EM-algoritmi parantaa aina parametrin estimointia tämän monivaiheisen prosessin kautta. Kuitenkin, se joskus tarvitsee muutamia satunnaisia alkaa löytää paras malli, koska algoritmi voi hioa paikallisia maxima, joka ei ole niin lähellä (optimaalinen) globaali maxima. Toisin sanoen, se voi toimia paremmin, jos pakotat sen käynnistämään uudelleen ja ottaa että ”alkuperäinen arvaus” vaiheesta 1 uudelleen. Kaikista mahdollisista parametreista voit sitten valita sen, jolla on suurin suurin todennäköisyys.

todellisuudessa vaiheet sisältävät joitakin melko raskas calculus (integraatio) ja ehdollinen todennäköisyydet, joka on soveltamisalan ulkopuolella tämän artikkelin. Jos tarvitset teknisempää (eli calculus-pohjainen) erittelyä prosessista, suosittelen lämpimästi lukemaan Gupta ja Chen ’ s 2010 paperi.

Sovellukset

EM-algoritmissa on monia sovelluksia, mm.:

• Dis-entanging superplaced signals,
• Estimating Gaussin seosmallit (GMMs),
• estimating hidden Markovin mallit (HMMs),
• Estimating parameters for compound Dirichlet ’ n jakaumat,
• Finding optimal seokset of fixed models.

rajoitukset

em-algoritmi voi olla nopeimmallakin tietokoneella hyvin hidas. Se toimii parhaiten, kun puuttuvasta datasta on vain pieni osa, eikä datan mitoitus ole liian suuri. Mitä suurempi mitoitus, sitä hitaampi e-askel; laajemman mitoituksen omaavissa tiedoissa E-step saattaa toimia erittäin hitaasti, kun toimenpide lähestyy paikallista maksimia.

Dempster, A., Laird, N., and Rubin, D. (1977) Maximum likely from incomplete data via the EM algorithm, Journal of the Royal Statistical Society. Sarja B (Methodological), vol. 39, nro 1, s. 1ñ38.
Gupta, M. & Chen, Y. (2010) Theory and Use of the EM Algorithm. Foundations and Trends in Signal Processing, Vol. 4, nro 3 223-296.

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

Tarvitsetko apua kotitehtävissä tai koekysymyksessä? Chegg Studyn avulla saat askelmittaisia ratkaisuja kysymyksiisi alan asiantuntijalta. Ensimmäinen 30 minuuttia Chegg tutor on ilmainen!