EM-algoritmi
EM-algoritmi (EM on eli "odotusarvon maksimointi") on tilastotieteessä käytetty iteratiivinen menetelmä suurimman uskottavuuden estimaattien löytämiseksi tilastollisten mallien parametreille tilanteessa, jossa osa tiedosta puuttuu.
Puuttuva tieto voi olla esimerkiksi piilevä luokkamuuttuja, josta ei saatu lainkaan havaintoja.
Olkoon formula_1 aineiston formula_2 jakaumaan liittyvien tuntemattomien parametrien muodostama vektori. Täydelliselle aineistolle uskottavuusfunktio voidaan kirjoittaa muodossa
Hyvin usein osa oleellisista tiedosta jää kuitenkin havaitsematta. Täydellinen data voidaan jakaa kahteen osaan: havaittuun aineistoon formula_4 ja puuttuvaan aineistoon formula_5. Tällöin täydellisen aineiston uskottavuus saadaan kirjoitettua muotoon
Ottamalla logaritmi puolittain lauseke saadaan muotoon
Oletetaan mallin parametreille tunnettu arvo formula_8 iteraatiolla formula_9. Tällöin edellä esitetyn lausekkeen odotusarvo puuttuvien havaintojen suhteen on
Merkitään nyt täydellisen aineiston logaritmista uskottavuutta seuraavasti:
Algoritmissa toistetaan vuorotellen kahta askelta:
Aluksi tuntemattomille parametreille asetetaan alkuarvot formula_15. Ensimmäinen iteraatio aloitetaan siis laskemalla formula_16.
Varsinainen iteratiivinen algoritmi joudutaan johtamaan erikseen kullekin tilanteelle.
Käytettäessä EM-algoritmia uskottavuusfunktion arvo kasvaa jokaisella iteraatiolla ja parametrin estimaatti lähestyy monotonisesti suurimman uskottavuuden estimaattia.
EM-algoritmi on hyödyllinen uskottavuuden tullessa eksponenttisesta perheestä:
E-askel sievenee tyhjentävien tunnuslukujen odotusarvojen summaksi ja M-askeleessa maksimoidaan lineaarista funktiota. Tällaisessa tapauksessa voidaan usein johtaa suljettu muoto askelten päivittämiseksi Sundbergin kaavalla (Rolf Sundberg julkaisi kaavan, mutta hän hyödynsi Per Martin-Löfin ja Anders Martin-Löfin julkaisemattomia tuloksia).
Olkoon formula_17 formula_18-kokoinen otos riippumattomia havaintoja kahdesta moniulotteisesta normaalijakaumasta, ulottuvuuksien määrä formula_19.
Olkoot formula_20 latentteja muuttujia, jotka kertovat kummasta ryhmästä kyseinen havainto on peräisin.
missä
Tavoite on estimoida jakaumien tuntemattomat keskiarvot ja kovarianssit, sekä jakaumien sekoittumista kuvaava arvo formula_25:
missä uskottavuusfunktio on:
missä formula_28 on indikaattorifunktio ja formula_29 on moniulotteisen normaalijakauman tiheysfunktio. Tämä voidaan kirjoittaa uudelleen eksponenttisen perheen muotoon:
Voidaan huomata, että kullekin "i" indikaattori formula_31 saa arvon yksi vain yhdellä "j", ja toisella "j" indikaattorin arvo on nolla. Sisempi summa siis supistuu yhdeksi lausekkeeksi eikä summausta tarvita.
Oletetaan, että meillä on parametrien estimaatit "θ". Tällöin "Z":n ehdollinen jakauma voidaan kirjoittaa todennäköisyytenä Bayesin kaavan mukaisesti:
Siten E-askel johtaa seuraavaan funktioon:
Huomataan, että formula_34 ja formula_35 voidaan kukin maksimoida toisistaan riippumatta, sillä ne ovat edellä esitetyssä lausekkeessa eri termeissä.
Tarkastellaan aluksi parametria "τ", jolla on rajoite "τ" + "τ"=1:
Tämä on samaa muotoa kuin binomijakauman suurimman uskottavuuden estimaatti. Siten
Tarkastellaan seuraavaksi parametrien formula_38 estimaatteja:
Tämä on samaa muotoa normaalijakauman painotetun SU-estimaatin kanssa, joten
Vastaavasti
Lopeta iterointi, jos formula_44 ja formula_45 ovat riittävän lähellä toisiaan (erotus alle jonkin ennalta asetetun kynnysarvon).
Yllä esitetty algoritmi voidaan yleistää useampien kuin kahden monimuuttujaisen normaalijakauman sekoituksille.
EM-algoritmin historia jaetaan usein kirjoittajien Dempster, Laird ja Rubin vuonna 1977 ilmestynyttä artikkelia edeltävään ja sitä seuraavaan aikaan. Kyseisessä artikkelissa annettiin runsaasti esimerkkejä algoritmin sovelluksista, ja kuvailtiin sen konvergenssiä ja muita perusominaisuuksia. Tätä artikkelia kutsutaan usein DLR-artikkeliksi.
Kirjallisuudessa ensimmäinen maininta liittyen EM-tyyppiseen algoritmiin esiintyy Newcombin vuoden 1886 artikkelissa kahden yksiulotteisen normaalijakauman sekoituksesta.
Vuonna 1960 Buck esitteli p-ulotteisen populaation keskiarvovektorin ja kovarianssimatriisin estimointia tilanteessa, jossa osa aineistosta puuttui. Hän käytti regressiota ja puuttuvien havaintojen selittämistä havaitulla aineistolla. Hänen menetelmässään tarvitut regressiokertoimet ja kovarianssimatriisin kerrointen korjaukset saadaan yhdellä täydellisten havaintojen informaatiomatriisin kääntämisellä ja sopivilla matriisilaskuilla. EM-algoritmin peruselementit esiintyvät Buckin menetelmässä.
EM-algoritmin soveltamista Markov-malleille käsiteltiin sarjassa artikkeleita: Baum ja Petrie (1966), Baum ja Eagon (1967) ja Baum, Petrie, Soules ja Weiss (1970). Nämä artikkelit sisältävät helposti yleistettävissä olevia konvergenssituloksia. Näissä artikkeleissa kehitetty algoritmi toimii myös perustana nykyään käytetyille piilo-Markov-mallien EM-algoritmeille.
Vuonna 1972 Orchard ja Woodbury esittelivät täydellisen ja ei-täydellisen aineiston logaritmisten uskottavuusfunktioiden välisen suhteen.
Rajapyykkinä toimivan artikkelin jälkeen EM-algoritmia on sovellettu muun muassa neuroverkkoihin,
koneoppimisessa, psykometriikassa ja lääketieteellisessä kuvantamisessa (esimerkiksi PET-kuvauksissa).