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  aineiston  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  ja puuttuvaan aineistoon . Tällöin täydellisen aineiston uskottavuus saadaan kirjoitettua muotoon
.
Ottamalla logaritmi puolittain lauseke saadaan muotoon 
.

Oletetaan mallin parametreille tunnettu arvo  iteraatiolla . 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: 
E-askel: Johda termin  lauseke.
M-askel: Etsi parametrille  sellainen arvo , että uskottavuus maksimoituu.

Aluksi tuntemattomille parametreille asetetaan alkuarvot . Ensimmäinen iteraatio aloitetaan siis laskemalla .

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   -kokoinen otos riippumattomia havaintoja kahdesta moniulotteisesta normaalijakaumasta, ulottuvuuksien määrä .
Olkoot  latentteja muuttujia, jotka kertovat kummasta ryhmästä kyseinen havainto on peräisin.
 \, ja \,  ,
missä
 ja .

Tavoite on estimoida jakaumien tuntemattomat keskiarvot ja kovarianssit, sekä jakaumien sekoittumista kuvaava arvo :
,
missä uskottavuusfunktio on:
,
missä  on indikaattorifunktio ja  on moniulotteisen normaalijakauman tiheysfunktio. Tämä voidaan kirjoittaa uudelleen eksponenttisen perheen muotoon:

Voidaan huomata, että kullekin i indikaattori  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 Zi:n ehdollinen jakauma voidaan kirjoittaa todennäköisyytenä Bayesin kaavan mukaisesti:
.

Siten E-askel johtaa seuraavaan funktioon:

M-askel 
Huomataan, että  ja  voidaan kukin maksimoida toisistaan riippumatta, sillä ne ovat edellä esitetyssä lausekkeessa eri termeissä.

Tarkastellaan aluksi parametria τ, jolla on rajoite τ1 + τ2=1:

Tämä on samaa muotoa kuin binomijakauman suurimman uskottavuuden estimaatti. Siten
.

Tarkastellaan seuraavaksi parametrien  estimaatteja:

Tämä on samaa muotoa normaalijakauman painotetun SU-estimaatin kanssa, joten
 ja .
Vastaavasti
 ja .

Lopettaminen 

Lopeta iterointi, jos  ja  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).

Lähteet 

Tilastotiede