Forventning – maksimering algoritme - Expectation–maximization algorithm

I statistikk er en forventning -maksimering ( EM ) algoritme en iterativ metode for å finne (lokal) maksimal sannsynlighet eller maksimal a posteriori (MAP) estimater av parametere i statistiske modeller , der modellen er avhengig av uobserverte latente variabler . EM-iterasjonen veksler mellom å utføre et forventning (E) -steg, som skaper en funksjon for forventningen til logg-sannsynligheten som evalueres ved hjelp av det nåværende estimatet for parametrene, og et maksimalisering (M) -trinn, som beregner parametere som maksimerer den forventede loggen. sannsynlighet funnet på E -trinnet. Disse parameterestimatene brukes deretter til å bestemme fordelingen av de latente variablene i neste E-trinn.

EM -gruppering av Old Faithful -utbruddsdata. Den tilfeldige initialmodellen (som på grunn av aksenes forskjellige skalaer ser ut til å være to veldig flate og brede sfærer) passer til de observerte dataene. I de første iterasjoner, endres modellen i det vesentlige, men deretter konvergerer til de to modusene i geyser . Visualisert ved hjelp av ELKI .

Historie

EM -algoritmen ble forklart og gitt navnet i et klassisk papir fra 1977 av Arthur Dempster , Nan Laird og Donald Rubin . De påpekte at metoden hadde blitt "foreslått mange ganger under spesielle omstendigheter" av tidligere forfattere. En av de tidligste er gen-tellingsmetoden for estimering av allelfrekvenser av Cedric Smith . En meget detaljert behandling av EM-metoden for eksponentielle familier ble publisert av Rolf Sundberg i hans avhandling og flere artikler etter hans samarbeid med Per Martin-Löf og Anders Martin-Löf . Dempster - Laird - Rubin -papiret i 1977 generaliserte metoden og skisserte en konvergensanalyse for en større klasse problemer. Dempster - Laird - Rubin -papiret etablerte EM -metoden som et viktig verktøy for statistisk analyse.

Konvergensanalysen av Dempster - Laird - Rubin -algoritmen var feil og en korrekt konvergensanalyse ble publisert av CF Jeff Wu i 1983. Wu's bevis etablerte EM -metodens konvergens utenfor den eksponentielle familien , som hevdet av Dempster - Laird - Rubin.

Introduksjon

EM -algoritmen brukes til å finne (lokale) maksimal sannsynlighetsparametere for en statistisk modell i tilfeller der ligningene ikke kan løses direkte. Vanligvis involverer disse modellene latente variabler i tillegg til ukjente parametere og kjente dataobservasjoner. Det vil si at enten mangler verdier blant dataene, eller at modellen kan formuleres enklere ved å anta eksistensen av ytterligere uobserverte datapunkter. For eksempel kan en blandingsmodell beskrives enklere ved å anta at hvert observerte datapunkt har et tilsvarende ikke -observert datapunkt, eller latent variabel, som angir blandingskomponenten som hvert datapunkt tilhører.

Å finne en maksimal sannsynlighetsløsning krever vanligvis å ta derivatene av sannsynlighetsfunksjonen med hensyn til alle de ukjente verdiene, parametrene og de latente variablene, og samtidig løse de resulterende ligningene. I statistiske modeller med latente variabler er dette vanligvis umulig. I stedet er resultatet vanligvis et sett med sammenlåsende ligninger der løsningen på parameterne krever verdiene til de latente variablene og omvendt, men å erstatte det ene settet med ligninger i det andre gir en uløselig ligning.

EM -algoritmen går ut fra observasjonen at det er en måte å løse disse to settene med ligninger numerisk. Man kan ganske enkelt velge vilkårlige verdier for ett av de to settene med ukjente, bruke dem til å estimere det andre settet, deretter bruke disse nye verdiene til å finne et bedre estimat for det første settet, og deretter fortsette å veksle mellom de to til de resulterende verdiene begge konvergerer til faste punkter. Det er ikke åpenbart at dette vil fungere, men det kan bevises i denne sammenhengen. I tillegg kan det bevises at derivatet av sannsynligheten er (vilkårlig nær) null på det punktet, noe som igjen betyr at punktet enten er et lokalt maksimum eller et sadelpunkt . Generelt kan flere maksima forekomme, uten garanti for at det globale maksimumet blir funnet. Noen sannsynligheter har også særegenheter i seg, det vil si meningsløse maksima. For eksempel innebærer en av løsningene som EM kan finne i en blandingsmodell å sette en av komponentene for å ha null varians og gjennomsnittsparameteren for at den samme komponenten skal være lik et av datapunktene.

Beskrivelse

Gitt den statistiske modellen som genererer et sett med observerte data, et sett med ubemerkede latente data eller manglende verdier , og en vektor med ukjente parametere , sammen med en sannsynlighetsfunksjon , bestemmes maksimal sannsynlighetsestimat (MLE) for de ukjente parameterne ved å maksimere den marginale sannsynligheten for de observerte dataene ${\ displaystyle \ mathbf {X}}$ ${\ displaystyle \ mathbf {Z}}$${\ displaystyle {\ boldsymbol {\ theta}}}$ ${\ displaystyle L ({\ boldsymbol {\ theta}}; \ mathbf {X}, \ mathbf {Z}) = p (\ mathbf {X}, \ mathbf {Z} \ mid {\ boldsymbol {\ theta}} )}}$

${\ displaystyle L ({\ boldsymbol {\ theta}}; \ mathbf {X}) = p (\ mathbf {X} \ mid {\ boldsymbol {\ theta}}) = \ int p (\ mathbf {X}, \ mathbf {Z} \ mid {\ boldsymbol {\ theta}}) \, d \ mathbf {Z} = \ int p (\ mathbf {Z} \ mid \ mathbf {X}, {\ boldsymbol {\ theta}} ) p (\ mathbf {X} \ mid {\ boldsymbol {\ theta}}) \, d \ mathbf {Z}}$

Imidlertid er denne mengden ofte vanskelig å håndtere siden den ikke blir observert, og fordelingen av den er ukjent før den oppnås . ${\ displaystyle \ mathbf {Z}}$${\ displaystyle \ mathbf {Z}}$${\ displaystyle {\ boldsymbol {\ theta}}}$

EM -algoritmen søker å finne MLE for den marginale sannsynligheten ved å iterativt bruke disse to trinnene:

Forventningstrinn (E -trinn) : Definer som forventet verdi av log -sannsynlighetsfunksjonen for , med hensyn til gjeldende betinget fordeling av gitt og gjeldende estimater av parametrene : ${\ displaystyle Q ({\ boldsymbol {\ theta}} \ mid {\ boldsymbol {\ theta}}^{(t)})}$${\ displaystyle {\ boldsymbol {\ theta}}}$${\ displaystyle \ mathbf {Z}}$${\ displaystyle \ mathbf {X}}$${\ displaystyle {\ boldsymbol {\ theta}}^{(t)}}$

${\ displaystyle Q ({\ boldsymbol {\ theta}} \ mid {\ boldsymbol {\ theta}}^{(t)}) = \ operatorname {E} _ {\ mathbf {Z} \ mid \ mathbf {X} , {\ boldsymbol {\ theta}}^{(t)}} \ venstre [\ log L ({\ boldsymbol {\ theta}}; \ mathbf {X}, \ mathbf {Z}) \ right] \,}$

Maksimeringstrinn (M -trinn) : Finn parametrene som maksimerer denne mengden:

${\ displaystyle {\ boldsymbol {\ theta}}^{(t+1)} = {\ undersett {\ boldsymbol {\ theta}} {\ operatorname {arg \, max}}} \ Q ({\ boldsymbol {\ theta}} \ mid {\ boldsymbol {\ theta}}^{(t)}) \,}$

De typiske modellene som EM brukes på, brukes som en latent variabel som indikerer medlemskap i en av et sett med grupper: ${\ displaystyle \ mathbf {Z}}$

1. De observerte datapunktene kan være diskrete (tar verdier i et begrenset eller uendelig sett) eller kontinuerlige (tar verdier i et uendelig sett). Tilknyttet hvert datapunkt kan det være en observasjonsvektor.${\ displaystyle \ mathbf {X}}$
2. De manglende verdiene (aka latente variabler ) er diskrete , hentet fra et fast antall verdier, og med en latent variabel per observert enhet.${\ displaystyle \ mathbf {Z}}$
3. Parametrene er kontinuerlige og er av to slag: Parametere som er knyttet til alle datapunkter, og de som er knyttet til en spesifikk verdi av en latent variabel (dvs. assosiert med alle datapunkter som tilsvarende latente variabel har denne verdien).

Imidlertid er det mulig å bruke EM på andre typer modeller.

Motivasjonen er som følger. Hvis verdien av parametrene er kjent, kan man vanligvis finne verdien av de latente variablene ved å maksimere logg-sannsynligheten for alle mulige verdier av , enten ganske enkelt ved å iterere over eller gjennom en algoritme som Baum-Welch-algoritmen for skjult Markov modeller . Omvendt, hvis vi kjenner verdien av de latente variablene , kan vi finne et estimat av parametrene ganske enkelt, vanligvis ved ganske enkelt å gruppere de observerte datapunktene i henhold til verdien av den tilhørende latente variabelen og gjennomsnitt av verdiene, eller en funksjon av verdier, av punktene i hver gruppe. Dette antyder en iterativ algoritme, i tilfelle hvor begge og er ukjente: ${\ displaystyle {\ boldsymbol {\ theta}}}$${\ displaystyle \ mathbf {Z}}$${\ displaystyle \ mathbf {Z}}$${\ displaystyle \ mathbf {Z}}$${\ displaystyle \ mathbf {Z}}$${\ displaystyle {\ boldsymbol {\ theta}}}$${\ displaystyle {\ boldsymbol {\ theta}}}$${\ displaystyle \ mathbf {Z}}$

1. Initialiser først parametrene til noen tilfeldige verdier.${\ displaystyle {\ boldsymbol {\ theta}}}$
2. Beregn sannsynligheten for hver mulig verdi av , gitt .${\ displaystyle \ mathbf {Z}}$${\ displaystyle {\ boldsymbol {\ theta}}}$
3. Deretter bruker du de nettopp beregnede verdiene til å beregne et bedre estimat for parametrene .${\ displaystyle \ mathbf {Z}}$${\ displaystyle {\ boldsymbol {\ theta}}}$
4. Iterer trinn 2 og 3 til konvergens.

Algoritmen som nettopp beskrevet, nærmer seg monotont et lokalt minimum av kostnadsfunksjonen.

Egenskaper

Apropos et forventning (E) trinn er litt av en misvisende navn . Hva regnes i det første trinn er de faste, data-avhengige parametere i funksjonen Q . Når parametrene til Q er kjent, er det fullt ut bestemt og maksimert i det andre (M) trinnet i en EM -algoritme.

Selv om en EM -iterasjon øker den observerte data (dvs. marginal) sannsynlighetsfunksjon, finnes det ingen garanti for at sekvensen konvergerer til en maksimal sannsynlighetsestimator . For multimodale distribusjoner betyr dette at en EM -algoritme kan konvergere til et lokalt maksimum for den observerte datasannsynlighetsfunksjonen, avhengig av startverdier. Det finnes en rekke heuristiske eller metaheuristiske tilnærminger for å unnslippe et lokalt maksimum, for eksempel tilfeldig omstart av åsbestigning (starter med flere forskjellige tilfeldige innledende estimater θ ^{( t )} ), eller bruk av simulerte glødemetoder .

EM er spesielt nyttig når sannsynligheten er en eksponentiell familie : E -trinnet blir summen av forventningene til tilstrekkelig statistikk , og M -trinnet innebærer å maksimere en lineær funksjon. I et slikt tilfelle er det vanligvis mulig å hente lukkede uttrykksoppdateringer for hvert trinn ved å bruke Sundberg-formelen (utgitt av Rolf Sundberg ved hjelp av upubliserte resultater av Per Martin-Löf og Anders Martin-Löf ).

EM -metoden ble modifisert for å beregne maksimale a posteriori (MAP) estimater for Bayesian slutning i originalpapiret av Dempster, Laird og Rubin.

Det finnes andre metoder for å finne maksimale sannsynlighetsestimater, for eksempel nedstigning av gradient , konjugert gradient eller varianter av Gauss - Newton -algoritmen . I motsetning til EM krever slike metoder vanligvis evaluering av første og/eller andre derivater av sannsynlighetsfunksjonen.

Bevis på korrekthet

Forventningsmaksimering virker bedre enn å forbedre seg direkte . Her er det vist at forbedringer av førstnevnte innebærer forbedringer av sistnevnte. ${\ displaystyle Q ({\ boldsymbol {\ theta}} \ mid {\ boldsymbol {\ theta}}^{(t)})}$${\ displaystyle \ log p (\ mathbf {X} \ mid {\ boldsymbol {\ theta}})}$

For alle med ikke-null sannsynlighet kan vi skrive ${\ displaystyle \ mathbf {Z}}$${\ displaystyle p (\ mathbf {Z} \ mid \ mathbf {X}, {\ boldsymbol {\ theta}})}}$

${\ displaystyle \ log p (\ mathbf {X} \ mid {\ boldsymbol {\ theta}}) = \ log p (\ mathbf {X}, \ mathbf {Z} \ mid {\ boldsymbol {\ theta}}) -\ log p (\ mathbf {Z} \ mid \ mathbf {X}, {\ boldsymbol {\ theta}}).}$

Vi tar forventningen over mulige verdier av de ukjente dataene under gjeldende parameterestimat ved å multiplisere begge sider med og summere (eller integrere) over . Venstre side er forventningen om en konstant, så vi får: ${\ displaystyle \ mathbf {Z}}$${\ displaystyle \ theta ^{(t)}}$${\ displaystyle p (\ mathbf {Z} \ mid \ mathbf {X}, {\ boldsymbol {\ theta}}^{(t)})}$${\ displaystyle \ mathbf {Z}}$

${\ displaystyle {\ begin {align} \ log p (\ mathbf {X} \ mid {\ boldsymbol {\ theta}}) & = \ sum _ {\ mathbf {Z}} p (\ mathbf {Z} \ mid \ mathbf {X}, {\ boldsymbol {\ theta}}^{(t)}) \ log p (\ mathbf {X}, \ mathbf {Z} \ mid {\ boldsymbol {\ theta}})-\ sum _ {\ mathbf {Z}} p (\ mathbf {Z} \ mid \ mathbf {X}, {\ boldsymbol {\ theta}}^{(t)}) \ log p (\ mathbf {Z} \ mid \ mathbf {X}, {\ boldsymbol {\ theta}}) \\ & = Q ({\ boldsymbol {\ theta}} \ mid {\ boldsymbol {\ theta}}^{(t)})+H ({\ fet symbol {\ theta}} \ mid {\ boldsymbol {\ theta}}^{(t)}), \ ende {justert}}}$

hvor er definert av den negerte summen den erstatter. Denne siste ligningen gjelder for hver verdi av å inkludere , ${\ displaystyle H ({\ boldsymbol {\ theta}} \ mid {\ boldsymbol {\ theta}}^{(t)})}$${\ displaystyle {\ boldsymbol {\ theta}}}$${\ displaystyle {\ boldsymbol {\ theta}} = {\ boldsymbol {\ theta}}^{(t)}}$

${\ displaystyle \ log p (\ mathbf {X} \ mid {\ boldsymbol {\ theta}}^{(t)}) = Q ({\ boldsymbol {\ theta}}^{(t)} \ mid {\ fet symbol {\ theta}}^{(t)})+H ({\ boldsymbol {\ theta}}^{(t)} \ mid {\ boldsymbol {\ theta}}^{(t)}),}$

og trekker denne siste ligningen fra den forrige ligningen gir

${\ displaystyle \ log p (\ mathbf {X} \ mid {\ boldsymbol {\ theta}})-\ log p (\ mathbf {X} \ mid {\ boldsymbol {\ theta}}^{(t)}) = Q ({\ boldsymbol {\ theta}} \ mid {\ boldsymbol {\ theta}}^{(t)})-Q ({\ boldsymbol {\ theta}}^{(t)} \ mid {\ boldsymbol {\ theta}}^{(t)})+H ({\ boldsymbol {\ theta}} \ mid {\ boldsymbol {\ theta}}^{(t)})-H ({\ boldsymbol {\ theta} }^{(t)} \ mid {\ boldsymbol {\ theta}}^{(t)}),}$

Imidlertid forteller Gibbs ulikhet oss det , så vi kan konkludere med det ${\ displaystyle H ({\ boldsymbol {\ theta}} \ mid {\ boldsymbol {\ theta}}^{(t)}) \ geq H ({\ boldsymbol {\ theta}}^{(t)} \ mid {\ boldsymbol {\ theta}}^{(t)})}$

${\ displaystyle \ log p (\ mathbf {X} \ mid {\ boldsymbol {\ theta}})-\ log p (\ mathbf {X} \ mid {\ boldsymbol {\ theta}}^{(t)}) \ geq Q ({\ boldsymbol {\ theta}} \ mid {\ boldsymbol {\ theta}}^{(t)})-Q ({\ boldsymbol {\ theta}}^{(t)} \ mid {\ fet symbol {\ theta}}^{(t)}).}$

Med ord, det å velge å forbedre fører til at man forbedrer minst like mye. ${\ displaystyle {\ boldsymbol {\ theta}}}$${\ displaystyle Q ({\ boldsymbol {\ theta}} \ mid {\ boldsymbol {\ theta}}^{(t)})}$${\ displaystyle \ log p (\ mathbf {X} \ mid {\ boldsymbol {\ theta}})}$

Som en prosedyre for maksimering - maksimering

EM -algoritmen kan sees på som to alternerende maksimeringstrinn, det vil si som et eksempel på koordinatnedstigning . Vurder funksjonen:

${\ displaystyle F (q, \ theta): = \ operatorname {E} _ {q} [\ log L (\ theta; x, Z)]+H (q),}$

hvor q er en vilkårlig sannsynlighetsfordeling over de ikke -observerte dataene z og H (q) er entropien til fordelingen q . Denne funksjonen kan skrives som

${\ displaystyle F (q, \ theta) =-D _ {\ mathrm {KL}} {\ big (} q \ parallel p_ {Z \ mid X} (\ cdot \ mid x; \ theta) {\ big)} +\ log L (\ theta; x),}$

hvor er den betingede fordelingen av de ikke -observerte dataene gitt de observerte dataene, og er Kullback - Leibler -divergensen . ${\ displaystyle p_ {Z \ mid X} (\ cdot \ mid x; \ theta)}$${\ displaystyle x}$${\ displaystyle D_ {KL}}$

Deretter kan trinnene i EM -algoritmen sees på som:

Forventningstrinn : Velg å maksimere : ${\ displaystyle q}$${\ displaystyle F}$

${\ displaystyle q ^{(t)} = \ operatorname {arg \, max} _ {q} \ F (q, \ theta ^{(t)})}}$

Maksimeringstrinn : Velg å maksimere : ${\ displaystyle \ theta}$${\ displaystyle F}$

${\ displaystyle \ theta ^{(t+1)} = \ operatorname {arg \, max} _ {\ theta} \ F (q ^{(t)}, \ theta)}$

applikasjoner

EM brukes ofte for parameterestimering av blandede modeller , særlig innen kvantitativ genetikk .

I psykometrikk er EM et viktig verktøy for å estimere elementparametere og latente evner for elementresponssteorimodeller .

Med muligheten til å håndtere manglende data og observere uidentifiserte variabler, blir EM et nyttig verktøy for å prise og håndtere risiko for en portefølje.

EM-algoritmen (og dens raskere variant bestilt delmengdeforventningsmaksimering ) er også mye brukt i medisinsk bilderekonstruksjon , spesielt i positronemisjonstomografi , enkeltfotonemisjonstomografi og røntgencomputertomografi . Se nedenfor for andre raskere varianter av EM.

I konstruksjonsteknikk er algoritmen Structural Identification using Expectation Maximization (STRIDE) en utgangsmetode for å identifisere naturlige vibrasjonsegenskaper for et konstruksjonssystem ved hjelp av sensordata (se Operational Modal Analysis ).

EM brukes også til dataklynge . I behandling av naturlig språk er to fremtredende forekomster av algoritmen Baum-Welch-algoritmen for skjulte Markov-modeller , og algoritmen innvendig og utvendig for uovervåket induksjon av sannsynlige kontekstfrie grammatikker .

Filtrering og utjevning av EM -algoritmer

Et Kalman-filter brukes vanligvis for estimering av tilstander på nettet, og en jevnere variante med minsteavvik kan benyttes for off-line eller batchstatistimering. Disse løsningene med minsteavvik krever imidlertid estimater av parametrene for state-space-modellen. EM -algoritmer kan brukes til å løse felles tilstand og parameterestimeringsproblemer.

Filtrering og utjevning av EM-algoritmer oppstår ved å gjenta denne to-trinns prosedyren:

E-trinn

Bruk et Kalman-filter eller en jevner med en minimumsavvik designet med gjeldende parameterestimater for å få oppdaterte tilstandsestimater.

M-trinn

Bruk estimerte filtrerte eller utjevnede tilstander innen maksimal sannsynlighetsberegninger for å få oppdaterte parameterestimater.

Anta at et Kalman-filter eller en mykere varianter med minsteavvik opererer på målinger av et enkeltinngang-enkelt-utgangssystem som har additiv hvit støy. En oppdatert målestøy varians estimat kan oppnås fra maksimum sannsynlighetsberegning

${\ displaystyle {\ widehat {\ sigma}} _ {v}^{2} = {\ frac {1} {N}} \ sum _ {k = 1}^{N} {(z_ {k}-{ \ widehat {x}} _ {k})}^{2},}$

hvor beregnes skalarutmatingsestimater beregnet av et filter eller en mykere fra N -skalarmålinger . Oppdateringen ovenfor kan også brukes på oppdatering av en Poisson -målestøyintensitet. Tilsvarende, for en førsteordens auto-regressiv prosess, kan et oppdatert estimat for støyavvik for prosess beregnes av ${\ displaystyle {\ widehat {x}} _ {k}}$${\ displaystyle z_ {k}}$

${\ displaystyle {\ widehat {\ sigma}} _ {w}^{2} = {\ frac {1} {N}} \ sum _ {k = 1}^{N} {({\ widehat {x} } _ {k+1}-{\ widehat {F}} {\ widehat {x}} _ {k})}^{2},}$

hvor og er skalarstatsestimater beregnet av et filter eller en mykere. Det oppdaterte modellkoeffisientestimatet oppnås via ${\ displaystyle {\ widehat {x}} _ {k}}$${\ displaystyle {\ widehat {x}} _ {k+1}}$

${\ displaystyle {\ widehat {F}} = {\ frac {\ sum _ {k = 1}^{N} ({\ widehat {x}} _ {k+1}-{\ widehat {F}} { \ widehat {x}} _ {k})} {\ sum _ {k = 1}^{N} {\ widehat {x}} _ {k}^{2}}}.}$

Konvergensen av parameterestimater som de ovenfor er godt studert.

Varianter

En rekke metoder har blitt foreslått for å akselerere den til tider sakte konvergensen av EM -algoritmen, for eksempel de som bruker konjugert gradient og modifiserte Newtons metoder (Newton - Raphson). EM kan også brukes med begrensede estimeringsmetoder.

Parameter-utvidet forventningsmaksimering (PX-EM) -algoritme gir ofte hastighet ved "oss [en] kovariansjustering" for å korrigere analysen av M-trinnet, og utnytte ekstra informasjon fanget i de tilregnede komplette dataene ".

Forventning betinget maksimalisering (ECM) erstatter hvert M -trinn med en sekvens med betinget maksimalisering (CM) trinn der hver parameter θ _i maksimeres individuelt, betinget av at de andre parameterne forblir faste. Selv kan utvides inn i Expectation conditional maximization enten (ECME) algoritmen.

Denne ideen er ytterligere utvidet i generalisert forventningsmaksimering (GEM) -algoritme, der det bare søkes en økning i objektivfunksjonen F for både E -trinnet og M -trinnet som beskrevet i avsnittet Om en maksimering - maksimalisering . GEM er videreutviklet i et distribuert miljø og viser lovende resultater.

Det er også mulig å betrakte EM -algoritmen som en underklasse av MM (Majorize/Minimize eller Minorize/Maximize, afhængig av kontekst) algoritme, og derfor bruke alle maskiner utviklet i det mer generelle tilfellet.

α-EM algoritme

Q-funksjonen som brukes i EM-algoritmen er basert på logg sannsynligheten. Derfor blir det sett på som log-EM-algoritmen. Bruken av logg sannsynligheten kan generaliseres til den for α-log sannsynlighetsforholdet. Deretter kan α-log sannsynlighetsforholdet for de observerte dataene uttrykkes nøyaktig som likhet ved å bruke Q-funksjonen til α-log sannsynlighetsforholdet og α-divergensen. Å få denne Q-funksjonen er et generalisert E-trinn. Maksimeringen er et generalisert M -trinn. Dette paret kalles α-EM-algoritmen som inneholder log-EM-algoritmen som sin underklasse. Dermed er α-EM-algoritmen av Yasuo Matsuyama en eksakt generalisering av log-EM-algoritmen. Ingen beregning av gradient eller hessisk matrise er nødvendig. Α-EM viser raskere konvergens enn log-EM-algoritmen ved å velge en passende α. Α-EM-algoritmen fører til en raskere versjon av Hidden Markov-modellestimeringsalgoritmen α-HMM.

Forhold til variasjon Bayes metoder

EM er en delvis ikke-bayesisk, maksimal sannsynlighetsmetode. Det endelige resultatet gir en sannsynlighetsfordeling over de latente variablene (i bayesiansk stil) sammen med et poengestimat for θ (enten et maksimal sannsynlighetsestimat eller en posterior modus). En fullt bayesisk versjon av dette kan være ønsket, noe som gir en sannsynlighetsfordeling over θ og de latente variablene. Den bayesianske tilnærmingen til slutning er ganske enkelt å behandle θ som en annen latent variabel. I dette paradigmet forsvinner skillet mellom E- og M -trinnene. Hvis du bruker den faktoriserte Q -tilnærmingen som beskrevet ovenfor ( variasjonelle Bayes ), kan løsning iterere over hver latent variabel (nå inkludert θ ) og optimalisere dem en om gangen. Nå er k trinn per iterasjon nødvendig, hvor k er antall latente variabler. For grafiske modeller er dette enkelt å gjøre, ettersom hver variabels nye Q bare er avhengig av Markov -teppet , så lokal meldingssending kan brukes for effektiv slutning.

Geometrisk tolkning

I informasjonsgeometri tolkes E-trinnet og M-trinnet som projeksjoner under to affine forbindelser , kalt e-tilkoblingen og m-forbindelsen; den Kullback-Leibler divergens kan også bli forstått i disse vilkårene.

Eksempler

Gaussisk blanding

Sammenligning av k-midler og EM på kunstige data visualisert med ELKI . Ved å bruke avvikene kan EM -algoritmen beskrive normalfordelingene nøyaktig, mens k -midler deler dataene i Voronoi -celler. Klyngesenteret er angitt med det lettere, større symbolet.

En animasjon som demonstrerer EM -algoritmen som passer en tokomponent gaussisk blandingsmodell til Old Faithful -datasettet. Algoritmen går fra en tilfeldig initialisering til konvergens.

La oss være et eksempel på uavhengige observasjoner fra en blanding av to multivariate normale dimensjonsfordelinger , og la være de latente variablene som bestemmer komponenten observasjonen kommer fra. ${\ displaystyle \ mathbf {x} = (\ mathbf {x} _ {1}, \ mathbf {x} _ {2}, \ ldots, \ mathbf {x} _ {n})}$${\ displaystyle n}$${\ displaystyle d}$${\ displaystyle \ mathbf {z} = (z_ {1}, z_ {2}, \ ldots, z_ {n})}$

${\ displaystyle X_ {i} \ mid (Z_ {i} = 1) \ sim {\ mathcal {N}} _ {d} ({\ boldsymbol {\ mu}} _ {1}, \ Sigma _ {1} )}$ og ${\ displaystyle X_ {i} \ mid (Z_ {i} = 2) \ sim {\ mathcal {N}} _ {d} ({\ boldsymbol {\ mu}} _ {2}, \ Sigma _ {2} ),}$

hvor

${\ displaystyle \ operatorname {P} (Z_ {i} = 1) = \ tau _ {1} \,}$ og ${\ displaystyle \ operatorname {P} (Z_ {i} = 2) = \ tau _ {2} = 1- \ tau _ {1}.}$

Målet er å estimere de ukjente parameterne som representerer blandingsverdien mellom gausserne og middelene og kovariansene til hver:

${\ displaystyle \ theta = {\ big (} {\ boldsymbol {\ tau}}, {\ boldsymbol {\ mu}} _ {1}, {\ boldsymbol {\ mu}} _ {2}, \ Sigma _ { 1}, \ Sigma _ {2} {\ big)},}$

der sannsynlighetsfunksjonen for ufullstendig data er

${\ displaystyle L (\ theta; \ mathbf {x}) = \ prod _ {i = 1}^{n} \ sum _ {j = 1}^{2} \ tau _ {j} \ f (\ mathbf {x} _ {i}; {\ boldsymbol {\ mu}} _ {j}, \ Sigma _ {j}),}$

og sannsynlighetsfunksjonen for fullstendig data er

${\ displaystyle L (\ theta; \ mathbf {x}, \ mathbf {z}) = p (\ mathbf {x}, \ mathbf {z} \ mid \ theta) = \ prod _ {i = 1}^{ n} \ prod _ {j = 1}^{2} \ [f (\ mathbf {x} _ {i}; {\ boldsymbol {\ mu}} _ {j}, \ Sigma _ {j}) \ tau _ {j}]^{\ mathbb {I} (z_ {i} = j)},}$

eller

${\ displaystyle L (\ theta; \ mathbf {x}, \ mathbf {z}) = \ exp \ left \ {\ sum _ {i = 1}^{n} \ sum _ {j = 1}^{2 } \ mathbb {I} (z_ {i} = j) {\ big [} \ log \ tau _ {j}-{\ tfrac {1} {2}} \ log | \ Sigma _ {j} |-{ \ tfrac {1} {2}} (\ mathbf {x} _ {i}-{\ boldsymbol {\ mu}} _ {j})^{\ top} \ Sigma _ {j}^{-1} ( \ mathbf {x} _ {i}-{\ boldsymbol {\ mu}} _ {j})-{\ tfrac {d} {2}} \ log (2 \ pi) {\ big]} \ right \} ,}$

hvor er en indikatorfunksjon og er sannsynlighetstetthetsfunksjonen til en multivariat normal. ${\ displaystyle \ mathbb {I}}$${\ displaystyle f}$

I den siste likheten, for hver i , er en indikator lik null, og en indikator er lik en. Den indre summen reduseres dermed til ett begrep. ${\ displaystyle \ mathbb {I} (z_ {i} = j)}$

E trinn

Gitt vårt nåværende estimat av parametrene θ ^{( t )} , bestemmes den betingede fordelingen av Z _i av Bayes -setningen til å være proporsjonal høyde for normal tetthet vektet av τ :

${\ displaystyle T_ {j, i} ^{(t)}: = \ operatorname {P} (Z_ {i} = j \ mid X_ {i} = \ mathbf {x} _ {i}; \ theta ^{ (t)}) = {\ frac {\ tau _ {j}^{(t)} \ f (\ mathbf {x} _ {i}; {\ boldsymbol {\ mu}} _ {j}^{( t)}, \ Sigma _ {j}^{(t)})} {\ tau _ {1}^{(t)} \ f (\ mathbf {x} _ {i}; {\ boldsymbol {\ mu }} _ {1}^{(t)}, \ Sigma _ {1}^{(t)})+\ tau _ {2}^{(t)} \ f (\ mathbf {x} _ {i }; {\ boldsymbol {\ mu}} _ {2}^{(t)}, \ Sigma _ {2}^{(t)})}}}}$

Disse kalles "medlemssannsynligheter", som normalt regnes som utgangen av E -trinnet (selv om dette ikke er Q -funksjonen nedenfor).

Dette E -trinnet tilsvarer konfigurering av denne funksjonen for Q:

${\ displaystyle {\ begin {align} Q (\ theta \ mid \ theta ^{(t)}) & = \ operatorname {E} _ {\ mathbf {Z} \ mid \ mathbf {X}, \ mathbf {\ theta} ^{(t)}} [\ log L (\ theta; \ mathbf {x}, \ mathbf {Z})] \\ & = \ operatorname {E} _ {\ mathbf {Z} \ mid \ mathbf {X}, \ mathbf {\ theta} ^{(t)}} [\ log \ prod _ {i = 1} ^{n} L (\ theta; \ mathbf {x} _ {i}, Z_ {i })] \\ & = \ operatorname {E} _ {\ mathbf {Z} \ mid \ mathbf {X}, \ mathbf {\ theta} ^{(t)}} [\ sum _ {i = 1} ^ {n} \ log L (\ theta; \ mathbf {x} _ {i}, Z_ {i})] \\ & = \ sum _ {i = 1}^{n} \ operatorname {E} _ {Z_ {i} \ mid \ mathbf {X}; \ mathbf {\ theta} ^{(t)}} [\ log L (\ theta; \ mathbf {x} _ {i}, Z_ {i})] \ \\ & = \ sum _ {i = 1}^{n} \ sum _ {j = 1}^{2} P (Z_ {i} = j \ mid X_ {i} = \ mathbf {x} _ {i} ; \ theta ^{(t)}) \ log L (\ theta _ {j}; \ mathbf {x} _ {i}, j) \\ & = \ sum _ {i = 1} ^{n} \ sum _ {j = 1}^{2} T_ {j, i}^{(t)} {\ big [} \ log \ tau _ {j}-{\ tfrac {1} {2}} \ log | \ Sigma _ {j} |-{\ tfrac {1} {2}} (\ mathbf {x} _ {i}-{\ boldsymbol {\ mu}} _ {j})^{\ top} \ Sigma _ {j}^{-1} (\ mathbf {x} _ {i}-{\ boldsymbol {\ mu}} _ {j})-{\ tfrac {d} {2}} \ log (2 \ pi) {\ big]}. \ end {align}}}$

Forventningen om innsiden av summen er tatt med hensyn til sannsynlighetstetthetsfunksjonen , som kan være forskjellig for hvert treningssett. Alt i E -trinnet er kjent før trinnet er tatt bortsett fra , som beregnes i henhold til ligningen i begynnelsen av E -trinnseksjonen. ${\ displaystyle \ log L (\ theta; \ mathbf {x} _ {i}, Z_ {i})}$${\ displaystyle P (Z_ {i} \ mid X_ {i} = \ mathbf {x} _ {i}; \ theta ^{(t)})}$${\ displaystyle \ mathbf {x} _ {i}}$${\ displaystyle T_ {j, i}}$

Denne fulle betingede forventningen trenger ikke å beregnes i ett trinn, fordi τ og μ / Σ vises i separate lineære termer og dermed kan maksimeres uavhengig.

M trinn

Q ( θ  |  θ ^{( t )} ) som er kvadratisk i form betyr at det er relativt enkelt å bestemme maksimalverdiene for θ . Dessuten kan τ , ( μ ₁ , Σ ₁ ) og ( μ ₂ , Σ ₂ ) maksimeres uavhengig av hverandre siden de alle vises i separate lineære termer.

For å begynne, tenk på τ , som har begrensningen τ ₁ + τ ₂ = 1:

${\ displaystyle {\ begin {align} {\ boldsymbol {\ tau}}^{(t+1)} & = {\ underset {\ boldsymbol {\ tau}} {\ operatorname {arg \, max}}} \ Q (\ theta \ mid \ theta ^{(t)}) \\ & = {\ undersett {\ boldsymbol {\ tau}} {\ operatorname {arg \, max}}} \ \ left \ {\ left [\ sum _ {i = 1}^{n} T_ {1, i}^{(t)} \ høyre] \ log \ tau _ {1}+\ venstre [\ sum _ {i = 1}^{n} T_ {2, i}^{(t)} \ right] \ log \ tau _ {2} \ right \}. \ End {align}}}$

Dette har samme form som MLE for den binomiske fordelingen , så

${\ displaystyle \ tau _ {j}^{(t+1)} = {\ frac {\ sum _ {i = 1}^{n} T_ {j, i}^{(t)}} {\ sum _ {i = 1}^{n} (T_ {1, i}^{(t)}+T_ {2, i}^{(t)})}} = {\ frac {1} {n}} \ sum _ {i = 1}^{n} T_ {j, i}^{(t)}.}$

For de neste estimatene av ( μ ₁ , Σ ₁ ):

${\ displaystyle {\ begin {align} ({\ boldsymbol {\ mu}} _ {1}^{(t+1)}, \ Sigma _ {1}^{(t+1)}) & = {\ undersett {{\ boldsymbol {\ mu}} _ {1}, \ Sigma _ {1}} {\ operatorname {arg \, max}}} Q (\ theta \ mid \ theta ^{(t)}) \\ & = {\ undersett {{\ boldsymbol {\ mu}} _ {1}, \ Sigma _ {1}} {\ operatorname {arg \, max}}} \ sum _ {i = 1}^{n} T_ {1, i}^{(t)} \ left \ {-{\ tfrac {1} {2}} \ log | \ Sigma _ {1} |-{\ tfrac {1} {2}} (\ mathbf {x} _ {i}-{\ boldsymbol {\ mu}} _ {1})^{\ top} \ Sigma _ {1}^{-1} (\ mathbf {x} _ {i}-{\ fet symbol {\ mu}} _ {1}) \ høyre \} \ ende {justert}}.}$

Dette har samme form som en vektet MLE for en normalfordeling, så

${\ displaystyle {\ boldsymbol {\ mu}} _ {1}^{(t+1)} = {\ frac {\ sum _ {i = 1}^{n} T_ {1, i}^{(t )} \ mathbf {x} _ {i}} {\ sum _ {i = 1}^{n} T_ {1, i}^{(t)}}}}}$ og ${\ displaystyle \ Sigma _ {1}^{(t+1)} = {\ frac {\ sum _ {i = 1}^{n} T_ {1, i}^{(t)} (\ mathbf { x} _ {i}-{\ boldsymbol {\ mu}} _ {1}^{(t+1)}) (\ mathbf {x} _ {i}-{\ boldsymbol {\ mu}} _ {1 }^{(t+1)})^{\ top}} {\ sum _ {i = 1}^{n} T_ {1, i}^{(t)}}}}}$

og symmetri,

${\ displaystyle {\ boldsymbol {\ mu}} _ {2}^{(t+1)} = {\ frac {\ sum _ {i = 1}^{n} T_ {2, i}^{(t )} \ mathbf {x} _ {i}} {\ sum _ {i = 1}^{n} T_ {2, i}^{(t)}}}}$ og ${\ displaystyle \ Sigma _ {2}^{(t+1)} = {\ frac {\ sum _ {i = 1}^{n} T_ {2, i}^{(t)} (\ mathbf { x} _ {i}-{\ boldsymbol {\ mu}} _ {2}^{(t+1)}) (\ mathbf {x} _ {i}-{\ boldsymbol {\ mu}} _ {2 }^{(t+1)})^{\ top}} {\ sum _ {i = 1}^{n} T_ {2, i}^{(t)}}}.}$

Avslutning

Konkluderer den iterative prosessen hvis for under en viss forhåndsinnstilt terskel. ${\ displaystyle E_ {Z \ mid \ theta ^{(t)}, \ mathbf {x}} [\ log L (\ theta ^{(t)}; \ mathbf {x}, \ mathbf {Z})] \ leq E_ {Z \ mid \ theta ^{(t-1)}, \ mathbf {x}} [\ log L (\ theta ^{(t-1)}; \ mathbf {x}, \ mathbf {Z })]+\ varepsilon}$${\ displaystyle \ varepsilon}$

Generalisering

Algoritmen illustrert ovenfor kan generaliseres for blandinger av mer enn to flervariate normalfordelinger .

Avkortet og sensurert regresjon

EM -algoritmen er implementert i tilfelle der det eksisterer en underliggende lineær regresjonsmodell som forklarer variasjonen av en viss mengde, men hvor verdiene som faktisk observeres er sensurert eller avkortet versjoner av de som er representert i modellen. Spesielle tilfeller av denne modellen inkluderer sensurerte eller avkortede observasjoner fra en normalfordeling .

Alternativer

EM konvergerer vanligvis til et lokalt optimalt, ikke nødvendigvis det globale optimumet, uten noen begrensning på konvergenshastigheten generelt. Det er mulig at det kan være vilkårlig dårlig i høye dimensjoner, og det kan være et eksponentielt antall lokale optima. Derfor eksisterer det et behov for alternative metoder for garantert læring, spesielt i høydimensjonale omgivelser. Alternativer til EM finnes med bedre garantier for konsistens, som kalles øyeblikksbaserte tilnærminger eller de såkalte spektrale teknikkene . Øyeblikksbaserte tilnærminger for å lære parametrene til en sannsynlighetsmodell er av stadig større interesse siden de nyter garantier som global konvergens under visse forhold i motsetning til EM som ofte er plaget av problemet med å bli sittende fast i lokale optima. Algoritmer med læringsgarantier kan utledes for en rekke viktige modeller, for eksempel blandingsmodeller, HMMer osv. For disse spektrale metodene forekommer det ingen falske lokale optima, og de sanne parametrene kan konsekvent estimeres under noen regelmessighetsforhold.

Se også

• blandingsfordeling
• sammensatt distribusjon
• estimering av tetthet
• total absorpsjonsspektroskopi
• EM-algoritmen kan sees på som et spesielt tilfelle av algoritmen for majorisering-minimering (MM) .

Referanser

Videre lesning

• Hogg, Robert; McKean, Joseph; Craig, Allen (2005). Introduksjon til matematisk statistikk . Upper Saddle River, NJ: Pearson Prentice Hall. s. 359–364.
• Dellaert, Frank (2002). "Algoritmen for forventningsmaksimering". CiteSeerX  10.1.1.9.9735 . Cite journal krever |journal=( hjelp ) gir en enklere forklaring på EM -algoritmen for lavere maksimalisering.
• Biskop, Christopher M. (2006). Mønstergjenkjenning og maskinlæring . Springer. ISBN 978-0-387-31073-2.
• Gupta, MR; Chen, Y. (2010). "Teori og bruk av EM -algoritmen". Fundamenter og trender i signalbehandling . 4 (3): 223–296. CiteSeerX  10.1.1.219.6830 . doi : 10.1561/2000000034 . En velskrevet kort bok om EM, inkludert detaljert avledning av EM for GMM, HMM og Dirichlet.
• Bilmes, Jeff (1998). "En skånsom opplæring av EM -algoritmen og dens anvendelse på parameterestimering for Gauss -blanding og skjulte Markov -modeller". CiteSeerX  10.1.1.28.613 . Cite journal krever |journal=( hjelp ) inkluderer en forenklet avledning av EM -ligningene for gaussiske blandinger og gaussiske blandinger skjulte Markov -modeller.
• McLachlan, Geoffrey J .; Krishnan, Thriyambakam (2008). EM -algoritmen og utvidelsene (2. utg.). Hoboken: Wiley. ISBN 978-0-471-20170-0.

Eksterne linker

• Ulike 1D-, 2D- og 3D -demonstrasjoner av EM sammen med blandingsmodellering tilbys som en del av de sammenkoblede SOCR -aktivitetene og appletene. Disse appletene og aktivitetene viser empirisk egenskapene til EM -algoritmen for parameterestimering i forskjellige innstillinger.
• k-MLE: En rask algoritme for å lære statistiske blandingsmodeller
• Klassehierarki i C ++ (GPL) inkludert gaussiske blandinger
• Den elektroniske læreboken: Informasjonsteori, slutning og læringsalgoritmer , av David JC MacKay inkluderer enkle eksempler på EM -algoritmen, for eksempel gruppering ved hjelp av den myke k -middelalgoritmen, og understreker variasjonssynet til EM -algoritmen, som beskrevet i Kapittel 33.7 i versjon 7.2 (fjerde utgave).
• Variasjonsalgoritmer for omtrentlig Bayesian inferens , av MJ Beal inkluderer sammenligninger av EM med Variational Bayesian EM og avledninger av flere modeller, inkludert Variational Bayesian HMM ( kapitler ).
• The Expectation Maximization Algorithm: A short tutorial , A self-contain derivation of the EM Algorithm by Sean Borman.
• EM -algoritmen , av Xiaojin Zhu.
• EM -algoritme og varianter: en uformell opplæring av Alexis Roche. En kortfattet og veldig tydelig beskrivelse av EM og mange interessante varianter.