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.
Kuvaus.
Olkoon formula_1 aineiston formula_2 jakaumaan liittyvien tuntemattomien parametrien muodostama vektori. Täydelliselle aineistolle uskottavuusfunktio voidaan kirjoittaa muodossa
formula_3 .
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
formula_6.
Ottamalla logaritmi puolittain lauseke saadaan muotoon 
formula_7.
Oletetaan mallin parametreille tunnettu arvo formula_8 iteraatiolla formula_9. Tällöin edellä esitetyn lausekkeen odotusarvo puuttuvien havaintojen suhteen on 
formula_10.
Merkitään nyt täydellisen aineiston logaritmista uskottavuutta seuraavasti:
formula_11
Algoritmissa toistetaan vuorotellen kahta askelta: 
E-askel: Johda termin formula_12 lauseke.
M-askel: Etsi parametrille formula_13 sellainen arvo formula_14, että uskottavuus maksimoituu.
Aluksi tuntemattomille parametreille asetetaan alkuarvot formula_15. Ensimmäinen iteraatio aloitetaan siis laskemalla formula_16.
Varsinainen iteratiivinen algoritmi joudutaan johtamaan erikseen kullekin tilanteelle. 
Ominaisuuksia.
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).
Esimerkkejä.
Gaussinen sekoitus.
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.
formula_21 \, ja \, formula_22,
missä
formula_23 ja formula_24.
Tavoite on estimoida jakaumien tuntemattomat keskiarvot ja kovarianssit, sekä jakaumien sekoittumista kuvaava arvo formula_25:
formula_26,
missä uskottavuusfunktio on:
formula_27,
missä formula_28 on indikaattorifunktio ja formula_29 on moniulotteisen normaalijakauman tiheysfunktio. Tämä voidaan kirjoittaa uudelleen eksponenttisen perheen muotoon:
formula_30
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.
E-askel.
Oletetaan, että meillä on parametrien estimaatit "θ"("t"). Tällöin "Z""i":n ehdollinen jakauma voidaan kirjoittaa todennäköisyytenä Bayesin kaavan mukaisesti:
formula_32.
Siten E-askel johtaa seuraavaan funktioon:
formula_33
M-askel.
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 + "τ"2=1:
formula_36
Tämä on samaa muotoa kuin binomijakauman suurimman uskottavuuden estimaatti. Siten
formula_37.
Tarkastellaan seuraavaksi parametrien formula_38 estimaatteja:
formula_39
Tämä on samaa muotoa normaalijakauman painotetun SU-estimaatin kanssa, joten
formula_40 ja formula_41.
Vastaavasti
formula_42 ja formula_43.
Lopettaminen.
Lopeta iterointi, jos formula_44 ja formula_45 ovat riittävän lähellä toisiaan (erotus alle jonkin ennalta asetetun kynnysarvon).
Yleistäminen.
Yllä esitetty algoritmi voidaan yleistää useampien kuin kahden monimuuttujaisen normaalijakauman sekoituksille.
Historiaa.
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. 
Ennen DLR-artikkelia.
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.
DLR-artikkelin jälkeen.
Rajapyykkinä toimivan artikkelin jälkeen EM-algoritmia on sovellettu muun muassa neuroverkkoihin,
koneoppimisessa, psykometriikassa ja lääketieteellisessä kuvantamisessa (esimerkiksi PET-kuvauksissa).