Forventnings-maksimeringsalgoritme

Forventnings-maksimeringsalgoritme

Natur	Data partisjoneringsalgoritme ( d )
Oppfinner	Donald rubin
Oppfinnelsesdato	1977

Den forventning-maksimering algoritme (engelsk forventning-maksimering algoritme , ofte forkortet EM ), foreslått av Dempster et al. (1977), er en iterativ algoritme som gjør det mulig å finne maksimale sannsynlighetsparametere for en sannsynlighetsmodell når sistnevnte er avhengig av ikke observerbare latente variabler. Mange varianter har senere blitt foreslått, og danner en hel klasse algoritmer.

Bruk

EM-algoritmen brukes ofte til dataklassifisering, maskinlæring eller maskinvisjon. Det kan også nevnes bruken av den i medisinsk bildebehandling i sammenheng med tomografisk rekonstruksjon.

Forventnings-maksimeringsalgoritmen består av:

• et trinn for å evaluere forventningen (E), der forventningen om sannsynligheten beregnes ved å ta hensyn til de siste observerte variablene,
• et maksimeringstrinn (M), der maksimal sannsynlighet for parametrene estimeres ved å maksimere sannsynligheten funnet i trinn E.

Vi bruker deretter parametrene som er funnet i M som utgangspunkt for en ny fase av evaluering av forventningen, og vi gjentar på denne måten.

For å løse problemet med å lære skjulte Markov-modeller (HMM), dvs. bestemme parametrene til Markov-modellen, bruker vi Baum-Welch-algoritmen .

Prinsipp for drift

Ved å vurdere et utvalg x = ( x 1 , ..., x n ) av individer i henhold til en fordeling f ( x i , θ ) som er parametrisert av θ , prøver vi å bestemme parameteren θ maksimere log-sannsynligheten gitt av

L(x;θ)=∑Jeg=1ikkeLogg⁡f(xJeg,θ).{\ displaystyle L (\ mathbf {x}; {\ boldsymbol {\ theta}}) = \ sum _ {i = 1} ^ {n} \ log f ({\ boldsymbol {x}} _ {i}, { \ boldsymbol {\ theta}}).}

Denne algoritmen er spesielt nyttig når maksimering av L er veldig komplisert, men når vi, med forbehold om å kjenne visse hensynsfullt valgte data, veldig enkelt kan bestemme θ .

I dette tilfellet stoler vi på data fullført med en ukjent vektor z = ( z 1 , ..., z n ) . Ved å notere f ( z i | x i , θ ) sannsynligheten for z i å vite x i og parameteren θ , kan vi definere den ferdige log-sannsynlighet som mengden

L((x,z);θ)=∑Jeg=1ikke(Logg⁡f(zJeg|xJeg,θ)+Logg⁡f(xJeg;θ)).{\ displaystyle L \ left ((\ mathbf {x, z}); {\ boldsymbol {\ theta}} \ right) = \ sum _ {i = 1} ^ {n} \ left (\ log f (z_ {) i} | {\ boldsymbol {x}} _ {i}, {\ boldsymbol {\ theta}}) + \ log f ({\ boldsymbol {x}} _ {i}; {\ boldsymbol {\ theta}}) \ Ikke sant).}

og så,

L(x;θ)=L((x,z);θ)-∑Jeg=1ikkeLogg⁡f(zJeg|xJeg,θ).{\ displaystyle L (\ mathbf {x}; {\ boldsymbol {\ theta}}) = L \ left (\ mathbf {(x, z)}; {\ boldsymbol {\ theta}} \ right) - \ sum _ {i = 1} ^ {n} \ log f (z_ {i} | {\ boldsymbol {x}} _ {i}, {\ boldsymbol {\ theta}}).}

EM-algoritmen er en iterativ prosedyre basert på forventningen om at dataene blir fullført betinget av den nåværende parameteren. Ved å merke θ ( c ) denne parameteren, kan vi skrive

E[L(x;θ)|θ(vs.)]=E[L((x,z);θ)|θ(vs.)]-E[∑Jeg=1ikkeLogg⁡f(zJeg|xJeg,θ)|θ(vs.)],{\ displaystyle \ mathbb {E} \ left [L (\ mathbf {x}; {\ boldsymbol {\ theta}}) {\ Bigg |} {\ boldsymbol {\ theta}} ^ {(c)} \ right] = \ mathbb {E} \ left [L \ left (\ mathbf {(x, z)}; {\ boldsymbol {\ theta}} \ right) {\ Bigg |} {\ boldsymbol {\ theta}} ^ {( c)} \ right] - \ mathbb {E} \ left [\ sum _ {i = 1} ^ {n} \ log f (z_ {i} | {\ boldsymbol {x}} _ {i}, {\ fettsymbol {\ theta}}) {\ Bigg |} {\ boldsymbol {\ theta}} ^ {(c)} \ høyre],}der forventningen er tatt på z .

eller

L(x;θ)=Q(θ;θ(vs.))-H(θ;θ(vs.)){\ displaystyle L (\ mathbf {x}; {\ boldsymbol {\ theta}}) = Q \ left ({\ boldsymbol {\ theta}}; {\ boldsymbol {\ theta}} ^ {(c)} \ right ) -H \ left ({\ boldsymbol {\ theta}}; {\ boldsymbol {\ theta}} ^ {(c)} \ høyre)}, fordi L ( x  ; θ ) ikke er avhengig av z ,

med og . Q(θ;θ(vs.))=E[L((x,z);θ)|θ(vs.)]{\ displaystyle Q \ left ({\ boldsymbol {\ theta}}; {\ boldsymbol {\ theta}} ^ {(c)} \ right) = \ mathbb {E} \ left [L \ left (\ mathbf {( x, z)}; {\ boldsymbol {\ theta}} \ right) {\ Bigg |} {\ boldsymbol {\ theta}} ^ {(c)} \ right]}H(θ;θ(vs.))=E[∑Jeg=1ikkeLogg⁡f(zJeg|xJeg,θ)|θ(vs.)]{\ displaystyle H \ left ({\ boldsymbol {\ theta}}; {\ boldsymbol {\ theta}} ^ {(c)} \ right) = \ mathbb {E} \ left [\ sum _ {i = 1} ^ {n} \ log f (z_ {i} | {\ boldsymbol {x}} _ {i}, {\ boldsymbol {\ theta}}) {\ Bigg |} {\ boldsymbol {\ theta}} ^ {( c)} \ høyre]}

Vi viser at sekvensen definert av

θ(vs.+1)=arg⁡maksθ(Q(θ,θ(vs.))){\ displaystyle {\ boldsymbol {\ theta}} ^ {(c + 1)} = \ arg \ max _ {\ boldsymbol {\ theta}} \ left (Q \ left ({\ boldsymbol {\ theta}}, { \ boldsymbol {\ theta}} ^ {(c)} \ høyre) \ høyre)}

har en tendens til et lokalt maksimum. L(x;θ(vs.+1)){\ displaystyle L \ left (\ mathbf {x}; {\ boldsymbol {\ theta}} ^ {(c + 1)} \ right)}

EM-algoritmen kan defineres av:

• Tilfeldig initialisering av θ (0)
• c = 0
• Så lenge algoritmen ikke har konvergert, gjør
  • Evaluering av forventning (trinn E): Q(θ;θ(vs.))=E[L((x,z);θ))|θ(vs.)]{\ displaystyle Q \ left ({\ boldsymbol {\ theta}}; {\ boldsymbol {\ theta}} ^ {(c)} \ right) = \ mathbb {E} \ left [L \ left (\ mathbf {( x, z)}; {\ boldsymbol {\ theta}} \ right)) | {\ boldsymbol {\ theta}} ^ {(c)} \ right]}
  • Maksimering (trinn M): θ(vs.+1)=arg⁡maksθ(Q(θ,θ(vs.))){\ displaystyle {\ boldsymbol {\ theta}} ^ {(c + 1)} = \ arg \ max _ {\ boldsymbol {\ theta}} \ left (Q \ left ({\ boldsymbol {\ theta}}, { \ boldsymbol {\ theta ^ {(c)}}} \ høyre) \ høyre)}
  • c = c +1
• Slutt

I praksis roteres EM-algoritmen et stort antall ganger fra forskjellige utgangsverdier for å overvinne den lokale karakteren av det maksimalt oppnådde, for å ha større sjanser for å nå den totale maksimale sannsynligheten.

Detaljert eksempel: applikasjon i automatisk klassifisering

En av EMs viktigste applikasjoner er estimering av parametrene for en blandingstetthet i automatisk klassifisering innenfor rammen av Gaussiske blandingsmodeller . I dette problemet vurderer vi at et utvalg ( x 1 , ..., x n ) av , dvs. preget av p kontinuerlige variabler, faktisk kommer fra g forskjellige grupper. Tatt i betraktning at hver av disse gruppene G k følger en rett f med parameter θ k , og hvis andeler er gitt av en vektor (π 1 , ..., π g ) . Ved å merke Φ = (π 1 , ..., π g , θ 1 , ..., θ g ) parameteren til blandingen, blir densitetsfunksjonen som prøven følger gitt av Rs{\ displaystyle \ mathbb {R} ^ {p}}

g(x,Φ)=∑k=1gπkf(x,θk),{\ displaystyle g (x, \ Phi) = \ sum _ {k = 1} ^ {g} \ pi _ {k} f (x, \ theta _ {k}),}

og derfor blir logg-sannsyn-av para Φ er gitt ved

L(x,Φ)=∑Jeg=1ikkeLogg⁡(∑k=1gπkf(xJeg,θk)).{\ displaystyle L (x, \ Phi) = \ sum _ {i = 1} ^ {n} \ log \ left (\ sum _ {k = 1} ^ {g} \ pi _ {k} f (x_ { i}, \ theta _ {k}) \ høyre).}

Maksimering av denne funksjonen i henhold til Φ er veldig kompleks. For eksempel, hvis man ønsker å bestemme parametrene som tilsvarer to grupper i henhold til en normal lov i et rom med dimensjon 3, er det nødvendig å optimalisere en ikke-lineær funksjon av . R19{\ displaystyle \ mathbb {R} ^ {19}}

På samme tid, hvis vi kjente gruppene som hver enkelt tilhører, ville problemet være et veldig enkelt og veldig klassisk estimeringsproblem.

Styrken til EM-algoritmen ligger nettopp i å stole på disse dataene for å utføre estimatet. Ved å merke z ik størrelsen som er lik 1 hvis individet x i tilhører gruppen G k og 0 ellers, skrives log-sannsynligheten for de fullførte dataene

L(x,z,Φ)=∑Jeg=1ikke∑k=1gzJegkLogg⁡(πkf(xJeg,θk)).{\ displaystyle L (x, z, \ Phi) = \ sum _ {i = 1} ^ {n} \ sum _ {k = 1} ^ {g} z_ {ik} \ log \ left (\ pi _ { k} f (x_ {i}, \ theta _ {k}) \ høyre).}

Vi får da raskt

Q(Φ,Φ(vs.))=∑Jeg=1ikke∑k=1gE(zJegk|x,Φ(vs.))Logg⁡(πkf(xJeg,θk)){\ displaystyle Q \ left (\ Phi, \ Phi ^ {(c)} \ right) = \ sum _ {i = 1} ^ {n} \ sum _ {k = 1} ^ {g} \ mathbb {E } \ left (z_ {ik} {\ Bigg |} x, \ Phi ^ {(c)} \ right) \ log \ left (\ pi _ {k} f (x_ {i}, \ theta _ {k} ) \ Ikke sant)}

Ved å merke t ik mengden gitt av , kan vi skille EM-algoritmen i to trinn, som klassisk kalles, når det gjelder blandingsmodeller, estimeringstrinnet og maksimeringstrinnet. Disse to trinnene gjentas til konvergens. tJegk=E(zJegk|x,Φ(vs.)){\ displaystyle t_ {ik} = \ mathbb {E} \ left (z_ {ik} {\ Bigg |} x, \ Phi ^ {(c)} \ right)}

• Trinn E: beregning av t ik ved Bayes inversjonsregel:

tJegk=πk(vs.)f(xJeg,θk(vs.))∑ℓ=1gπℓ(vs.)f(xJeg,θℓ(vs.)){\ displaystyle t_ {ik} = {\ frac {\ pi _ {k} ^ {(c)} f (x_ {i}, \ theta _ {k} ^ {(c)})} {\ sum _ { \ ell = 1} ^ {g} \ pi _ {\ ell} ^ {(c)} f (x_ {i}, \ theta _ {\ ell} ^ {(c)})}}

• Trinn M: bestemmelse om å maksimere Φ

Q(Φ,Φ(vs.))=∑Jeg=1ikke∑k=1gtJegkLogg⁡(πkf(xJeg,θk)){\ displaystyle Q \ left (\ Phi, \ Phi ^ {(c)} \ right) = \ sum _ {i = 1} ^ {n} \ sum _ {k = 1} ^ {g} t_ {ik} \ log \ left (\ pi _ {k} f (x_ {i}, \ theta _ {k}) \ høyre)}

Fordelen med denne metoden er at vi kan skille problemet i g elementære problemer som generelt er relativt enkle. I alle tilfeller er de optimale proporsjonene gitt av

πk=1ikke∑Jeg=1ikketJegk{\ displaystyle \ pi _ {k} = {\ frac {1} {n}} \ sum _ {i = 1} ^ {n} t_ {ik}}

Anslaget for θ avhenger også av sannsynlighetsfunksjonen f valgt. I det normale tilfellet er dette midlene μ k og varians-kovariansmatriser Σ k . De optimale estimatorene er gitt av

μk=∑Jeg=1ikketJegkxJeg∑Jeg=1ikketJegk{\ displaystyle \ mu _ {k} = {\ frac {\ sum _ {i = 1} ^ {n} t_ {ik} x_ {i}} {\ sum _ {i = 1} ^ {n} t_ { ik}}}} Σk=∑Jeg=1ikketJegk(xJeg-μk)(xJeg-μk)T∑Jeg=1ikketJegk{\ displaystyle \ Sigma _ {k} = {\ frac {\ sum _ {i = 1} ^ {n} t_ {ik} (x_ {i} - \ mu _ {k}) (x_ {i} - \ mu _ {k}) ^ {T}} {\ sum _ {i = 1} ^ {n} t_ {ik}}}}

Med M T er den transponerte matrisen til M og forutsatt at μ k er kolonnevektorer.

Vanlige varianter av EM

EM-algoritmen kombinerer i de fleste tilfeller enkelhet i implementering og effektivitet. Imidlertid har noen få problematiske saker gitt ytterligere utvikling. Blant de eksisterende variantene av denne algoritmen vil vi nevne GEM (generalisert EM) algoritme som forenkler problemet med maksimeringstrinnet; CEM- algoritmen (EM-klassifisering) som gjør det mulig å ta hensyn til klassifiseringsaspektet under estimeringen, så vel som SEM- algoritmen (stokastisk EM), hvis mål er å redusere risikoen for å falle inn i et lokalt sannsynlighetsoptimum.

GEM-algoritme

GEM har blitt foreslått sammen med EM av Dempster et al. (1977) som beviste at for å sikre konvergens mot en lokal maksimal sannsynlighet, er det ikke nødvendig å maksimere Q ved hvert trinn, men at en enkel forbedring av Q er tilstrekkelig.

GEM kan derfor skrives som følger:

• Tilfeldig initialisering av θ(0){\ displaystyle \ theta ^ {(0)} \,}
• vs.=0{\ displaystyle c = 0 \,}
• Så lenge algoritmen ikke har konvergert, gjør
  • velg somθ(vs.+1){\ displaystyle \ theta ^ {(c + 1)} \,}Q(θ(vs.+1),θ(vs.))>Q(θ(vs.),θ(vs.)){\ displaystyle Q \ left (\ theta ^ {(c + 1)}, \ theta ^ {(c)} \ right)> Q \ left (\ theta ^ {(c)}, \ theta ^ {(c) } \ Ikke sant)}
  • vs.=vs.+1{\ displaystyle c = c + 1 \,}
• Slutt

CEM-algoritme

EM-algoritmen er posisjonert i et estimeringsperspektiv , det vil si at vi søker å maksimere sannsynligheten for parameteren , uten å ta i betraktning klassifiseringen som er gjort etterpå ved bruk av Bayes-regelen. θ{\ displaystyle \ theta \,}

Den klassifisering fremgangsmåte , foreslått av Celeux og Govaert (1991) består i å optimalisere, ikke sannsynligheten for parameteren, men direkte den ferdige sannsynlighet, gitt, i tilfellet ved blanding av modeller, etter

L(x,z;θ)=∑Jeg=1ikke∑k=1gzJegkLogg⁡(πkf(x,θk)){\ displaystyle L (x, z; \ theta) = \ sum _ {i = 1} ^ {n} \ sum _ {k = 1} ^ {g} z_ {ik} \ log \ left (\ pi _ { k} f (x, \ theta _ {k}) \ høyre)}

For å gjøre dette, fortsett bare som følger:

• Tilfeldig initialisering av θ(0){\ displaystyle \ theta ^ {(0)} \,}
• vs.=0{\ displaystyle c = 0 \,}
• Så lenge algoritmen ikke har konvergert, gjør
  • z(vs.+1)=arg⁡maksz(L(x,z;θ(vs.))){\ displaystyle z ^ {(c + 1)} = \ arg \ max _ {z} \ left (L \ left (x, z; \ theta ^ {(c)} \ right) \ right)}
  • θ(vs.+1)=arg⁡maksθ(L(x,z(vs.+1);θ)){\ displaystyle \ theta ^ {(c + 1)} = \ arg \ max _ {\ theta} \ left (L \ left (x, z ^ {(c + 1)}; \ theta \ right) \ right) }
  • vs.=vs.+1{\ displaystyle c = c + 1 \,}
• Slutt

Når komponentene i blandingen tilhører den samme eksponensielle familien, ved å bruke sammenhengen mellom Bregman-avvikene og de eksponensielle familiene, får vi k-MLE-algoritmen.

SEM-algoritme

For å redusere risikoen for å falle til en lokal maksimal sannsynlighet, foreslår Celeux og Diebolt ( 1985 ) å sette inn et stokastisk klassifiseringstrinn mellom trinn E og M. Etter å ha beregnet sannsynlighetene trekkes medlemskapet til individer til klasser tilfeldig i henhold til en multinomial fordeling av parametere . tJegk(vs.){\ displaystyle t_ {ik} ^ {(c)}}zJegk(vs.){\ displaystyle z_ {ik} ^ {(c)}}M(1,tJeg1(q),...,tJegg(q)){\ displaystyle {\ mathcal {M}} \ left (1, t_ {i1} ^ {(q)}, \ dots, t_ {ig} ^ {(q)} \ right)}

I motsetning til hva som skjer i CEM-algoritmen, kan vi ikke vurdere at algoritmen har konvergert når individer ikke lenger bytter klasse. Faktisk, når disse trekkes tilfeldig, konvergerer ikke sekvensen i streng forstand. I praksis foreslår Celeux og Diebolt (1985) å kjøre SEM-algoritmen et gitt antall ganger for deretter å bruke CEM-algoritmen til å oppnå en partisjon og et estimat av parameteren . (z(q),θ(q)){\ displaystyle \ left (z ^ {(q)}, \ theta ^ {(q)} \ right)}θ{\ displaystyle \ theta \,}

Se også

• Datadelingering

Referanser

1. (in) AP Dempster , NM Laird og Donald Rubin , "  Maximum Likelihood from Incomplete Data via the EM Algorithm  " , Journal of the Royal Statistical Society. Series B (Methodological) , vol.  39, n o  1,1977, s.  1–38 ( JSTOR  2984875 )
2. (in) G. Celeux og G. Govaert , "  En klassifisering EM-algoritme for klynging og to stokastiske versjoner  " , Computational Statistics Quarterly , Vol.  2, n o  1, 1991, s.  73–82
3. (i) Frank Nielsen , "  k-MLE: En rask algoritme for å lære statistiske blandingsmodeller  " , arxiv (ICASSP 2012) , 2012( les online )
4. (en) G. Celeux og G. Diebolt , "  Sem-algoritmen: en sannsynlig læreralgoritme avledet fra em-algoritmen for blandingsproblemet  " , Forskningsrapport RR-1364, Inria, National Institute for Research in Computer Science and Automation , 1985

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">