Algoritmus maximalizace očekávání

Algoritmus maximalizace očekávání

Příroda	Algoritmus rozdělení dat ( d )
Vynálezce	Donald Rubin
Datum vynálezu	1977

Očekávání-zvětšení algoritmus (anglicky algoritmus očekávání-zvětšení , často zkrátil EM ), navržený Dempster a kol. (1977), je iterační algoritmus, který umožňuje, aby si maximální věrohodnosti parametry na pravděpodobnostním modelu , když tento závisí na nepozorovatelné latentními proměnnými. Následně bylo navrženo mnoho variant, které tvoří celou třídu algoritmů.

Použití

Algoritmus EM se často používá pro klasifikaci dat, strojové učení nebo strojové vidění. Lze také zmínit jeho použití v lékařském zobrazování v kontextu tomografické rekonstrukce.

Algoritmus maximalizace očekávání zahrnuje:

• krok vyhodnocení očekávání (E), kde se očekávání pravděpodobnosti vypočítá s přihlédnutím k posledním pozorovaným proměnným,
• krok maximalizace (M), kde je maximální pravděpodobnost parametrů odhadnuta maximalizací pravděpodobnosti nalezené v kroku E.

Poté použijeme parametry nalezené v M jako výchozí bod pro novou fázi vyhodnocení očekávání a tímto způsobem iterujeme.

K vyřešení problému učení skrytých Markovových modelů (HMM), tj. Určení parametrů Markovova modelu, používáme algoritmus Baum-Welch .

Princip činnosti

Uvažováním vzorku x = ( x 1 , ..., x n ) jednotlivců podle distribuce f ( x i , θ ) parametrizované pomocí θ se snažíme určit parametr θ maximalizující logaritmickou pravděpodobnost danou

L(X;θ)=∑i=1nelog⁡F(Xi,θ).{\ displaystyle L (\ mathbf {x}; {\ boldsymbol {\ theta}}) = \ součet _ {i = 1} ^ {n} \ log f ({\ boldsymbol {x}} _ {i}, { \ boldsymbol {\ theta}}).}

Tento algoritmus je obzvláště užitečný, když je maximalizace L velmi složitá, ale když, s výhradou znalosti určitých uvážlivě vybraných dat, můžeme velmi jednoduše určit θ .

V tomto případě se spoléháme na data doplněná neznámým vektorem z = ( z 1 , ..., z n ) . Zaznamenáním f ( z i | x i , θ ) pravděpodobnosti, že z i budu znát x i a parametr θ , můžeme definovat dokončenou logaritmickou pravděpodobnost jako veličinu

L((X,z);θ)=∑i=1ne(log⁡F(zi|Xi,θ)+log⁡F(Xi;θ)).{\ 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}}) \ že jo).}

a tak,

L(X;θ)=L((X,z);θ)-∑i=1nelog⁡F(zi|Xi,θ).{\ 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}}).}

Algoritmus EM je iterační postup založený na očekávání dat vyplněných podmíněně na aktuálním parametru. Zaznamenáním θ ( c ) tohoto parametru můžeme psát

E[L(X;θ)|θ(vs.)]=E[L((X,z);θ)|θ(vs.)]-E[∑i=1nelog⁡F(zi|Xi,θ)|θ(vs.)],{\ displaystyle \ mathbb {E} \ vlevo [L (\ mathbf {x}; {\ boldsymbol {\ theta}}) {\ Bigg |} {\ boldsymbol {\ theta}} ^ {(c)} \ vpravo] = \ 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}, {\ boldsymbol {\ theta}}) {\ Bigg |} {\ boldsymbol {\ theta}} ^ {(c)} \ right],}kde je očekávání převzato z .

nebo

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)} \ right)}, protože L ( x  ; θ ) nezávisí na z ,

s a . 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[∑i=1nelog⁡F(zi|Xi,θ)|θ(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)} \ vpravo]}

Ukážeme, že posloupnost definovaná znakem

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

inklinuje k místnímu maximu. L(X;θ(vs.+1)){\ displaystyle L \ left (\ mathbf {x}; {\ boldsymbol {\ theta}} ^ {(c + 1)} \ right)}

Algoritmus EM lze definovat:

• Náhodná inicializace θ (0)
• c = 0
• Dokud se algoritmus nespojil, udělejte to
  • Vyhodnocení očekávání (krok 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]}
  • Maximalizace (krok M): θ(vs.+1)=arg⁡maxθ(Q(θ,θ(vs.))){\ displaystyle {\ boldsymbol {\ theta}} ^ {(c + 1)} = \ arg \ max _ {\ boldsymbol {\ theta}} \ left (Q \ left ({\ boldsymbol {\ theta}}, { \ boldsymbol {\ theta ^ {(c)}}} \ vpravo) \ vpravo)}
  • c = c +1
• Konec

V praxi se k překonání lokálního charakteru dosaženého maxima algoritmus EM mnohokrát otočí z různých počátečních hodnot, aby měl větší šanci dosáhnout celkové maximální pravděpodobnosti.

Podrobný příklad: aplikace v automatické klasifikaci

Jednou z hlavních aplikací EM je odhad parametrů hustoty směsi v automatické klasifikaci v rámci Gaussových modelů směsí . V řešení tohoto problému, domníváme se, že vzorek ( x 1 , ..., x n ) z , tedy vyznačuje p kontinuální proměnné, ve skutečnosti pochází z g různých skupin. Vezmeme-li v úvahu, že každá z těchto skupin G k sleduje zákon f s parametrem θ k a jehož proporce jsou dány vektorem (π 1 , ..., π g ) . Zaznamenáním Φ = (π 1 , ..., π g , θ 1 , ..., θ g ) parametru směsi je funkce hustoty, kterou vzorek následuje, dána Rp{\ displaystyle \ mathbb {R} ^ {p}}

G(X,Φ)=∑k=1GπkF(X,θk),{\ displaystyle g (x, \ Phi) = \ součet _ {k = 1} ^ {g} \ pi _ {k} f (x, \ theta _ {k}),}

a proto je logaritmická pravděpodobnost parametru Φ dána vztahem

L(X,Φ)=∑i=1nelog⁡(∑k=1GπkF(Xi,θk)).{\ displaystyle L (x, \ Phi) = \ součet _ {i = 1} ^ {n} \ log \ left (\ součet _ {k = 1} ^ {g} \ pi _ {k} f (x_ { i}, \ theta _ {k}) \ right).}

Maximalizace této funkce podle Φ je velmi složitá. Například pokud si přejeme určit parametry odpovídající dvěma skupinám podle normálního zákona v prostoru dimenze 3, je nutné optimalizovat nelineární funkci . R19{\ displaystyle \ mathbb {R} ^ {19}}

Současně, kdybychom znali skupiny, do kterých každý jednotlivec patří, pak by problém byl velmi jednoduchým a velmi klasickým problémem odhadu.

Síla algoritmu EM spočívá právě v tom, že se při provádění odhadu spoléháme na tato data. Zaznamenáním z ik velikost, která se rovná 1, pokud jedinec x i patří do skupiny G k a 0, jinak se zapíše logaritmická pravděpodobnost vyplněných dat

L(X,z,Φ)=∑i=1ne∑k=1Gziklog⁡(πkF(Xi,θk)).{\ displaystyle L (x, z, \ Phi) = \ součet _ {i = 1} ^ {n} \ součet _ {k = 1} ^ {g} z_ {ik} \ log \ left (\ pi _ { k} f (x_ {i}, \ theta _ {k}) \ right).}

Poté rychle získáváme

Q(Φ,Φ(vs.))=∑i=1ne∑k=1GE(zik|X,Φ(vs.))log⁡(πkF(Xi,θ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} ) \ že jo)}

Zaznamenáním t ik veličiny dané , můžeme rozdělit EM algoritmus do dvou kroků, které se v případě modelů směsí klasicky nazývají krok odhadu a krok maximalizace. Tyto dva kroky jsou iterovány až do konvergence. tik=E(zik|X,Φ(vs.)){\ displaystyle t_ {ik} = \ mathbb {E} \ vlevo (z_ {ik} {\ Bigg |} x, \ Phi ^ {(c)} \ vpravo)}

• Krok E: Výpočet t ik podle Bayesova inverzního pravidla:

tik=πk(vs.)F(Xi,θk(vs.))∑ℓ=1Gπℓ(vs.)F(Xi,θℓ(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)})}}}

• Krok M: stanovení maximalizace Φ

Q(Φ,Φ(vs.))=∑i=1ne∑k=1Gtiklog⁡(πkF(Xi,θ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}) \ right)}

Výhodou této metody je, že můžeme problém rozdělit na základní problémy g, které jsou obecně relativně jednoduché. Ve všech případech jsou optimální poměry dány vztahem

πk=1ne∑i=1netik{\ displaystyle \ pi _ {k} = {\ frac {1} {n}} \ součet _ {i = 1} ^ {n} t_ {ik}}

Odhad θ závisí také na zvolené pravděpodobnostní funkci f . V normálním případě se jedná o průměr μ k a variance-kovarianční matice Σ k . Optimální odhady jsou pak dány vztahem

μk=∑i=1netikXi∑i=1netik{\ displaystyle \ mu _ {k} = {\ frac {\ sum _ {i = 1} ^ {n} t_ {ik} x_ {i}} {\ sum _ {i = 1} ^ {n} t_ { ik}}}} Σk=∑i=1netik(Xi-μk)(Xi-μk)T∑i=1netik{\ 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}}}}

S M T transponovaná matice M a za předpokladu, že μ k jsou sloupcové vektory.

Běžné varianty EM

Algoritmus EM kombinuje ve většině případů jednoduchost implementace a efektivitu. Některé problematické případy však vedly k dalšímu vývoji. Ze stávajících variant tohoto algoritmu zmíníme algoritmus GEM (generalizovaný EM) , který zjednodušuje problém kroku maximalizace; algoritmus CEM (klasifikace EM) umožňující zohlednění klasifikačního aspektu během odhadu, stejně jako algoritmus SEM (stochastický EM), jehož cílem je snížit riziko pádu do optima místní pravděpodobnosti.

Algoritmus GEM

GEM navrhl spolu s EM Dempster a kol. (1977), který dokázal, že k zajištění konvergence k místní maximální pravděpodobnosti není nutné maximalizovat Q v každém kroku, ale že postačuje jednoduché zlepšení Q.

GEM lze tedy psát následovně:

• Náhodná inicializace θ(0){\ displaystyle \ theta ^ {(0)} \,}
• vs.=0{\ displaystyle c = 0 \,}
• Dokud se algoritmus nespojil, udělejte to
  • zvolit jakoθ(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) } \ že jo)}
  • vs.=vs.+1{\ displaystyle c = c + 1 \,}
• Konec

Algoritmus CEM

Algoritmus EM je umístěn v perspektivě odhadu , to znamená, že se snažíme maximalizovat pravděpodobnost parametru , aniž bychom zvažovali klasifikaci provedenou a posteriori pomocí Bayesova pravidla. θ{\ displaystyle \ theta \,}

Klasifikační přístup navržený Celeuxem a Govaertem (1991) spočívá v optimalizaci nikoli pravděpodobnosti parametru, ale přímo úplné pravděpodobnosti dané, v případě směšovacích modelů,

L(X,z;θ)=∑i=1ne∑k=1Gziklog⁡(πkF(X,θk)){\ displaystyle L (x, z; \ theta) = \ součet _ {i = 1} ^ {n} \ součet _ {k = 1} ^ {g} z_ {ik} \ log \ left (\ pi _ { k} f (x, \ theta _ {k}) \ vpravo)}

Chcete-li to provést, jednoduše postupujte takto:

• Náhodná inicializace θ(0){\ displaystyle \ theta ^ {(0)} \,}
• vs.=0{\ displaystyle c = 0 \,}
• Dokud se algoritmus nespojil, udělejte to
  • z(vs.+1)=arg⁡maxz(L(X,z;θ(vs.))){\ Displaystyle z ^ {(c + 1)} = \ arg \ max _ {z} \ vlevo (L \ left (x, z; \ theta ^ {(c)} \ right) \ right)}
  • θ(vs.+1)=arg⁡maxθ(L(X,z(vs.+1);θ)){\ displaystyle \ theta ^ {(c + 1)} = \ arg \ max _ {\ theta} \ doleva (L \ left (x, z ^ {(c + 1)}; \ theta \ right) \ right) }
  • vs.=vs.+1{\ displaystyle c = c + 1 \,}
• Konec

Když složky směsi patří do stejné exponenciální rodiny, pomocí bijekce mezi Bregmanovými divergencemi a exponenciálními rodinami získáme algoritmus k-MLE.

Algoritmus SEM

Aby se snížilo riziko pádu na místní maximální pravděpodobnost, navrhují Celeux a Diebolt ( 1985 ) vložit stochastický klasifikační krok mezi kroky E a M. Po výpočtu pravděpodobností je členství jednotlivců ve třídách vylosováno náhodně podle multinomické rozdělení parametrů . tik(vs.){\ displaystyle t_ {ik} ^ {(c)}}zik(vs.){\ displaystyle z_ {ik} ^ {(c)}}M(1,ti1(q),...,tiG(q)){\ displaystyle {\ mathcal {M}} \ vlevo (1, t_ {i1} ^ {(q)}, \ tečky, t_ {ig} ^ {(q)} \ vpravo)}

Na rozdíl od toho, co se děje v algoritmu CEM, nemůžeme uvažovat o tom, že algoritmus konvergoval, když jednotlivci již nemění třídy. Ve skutečnosti, když jsou kresleny náhodně, posloupnost se nespojuje v užším slova smyslu. V praxi Celeux a Diebolt (1985) navrhují spustit algoritmus SEM daný počet opakování a poté použít algoritmus CEM k získání oddílu a odhadu parametru . (z(q),θ(q)){\ displaystyle \ left (z ^ {(q)}, \ theta ^ {(q)} \ right)}θ{\ displaystyle \ theta \,}

Podívejte se také

• Rozdělení dat

Reference

1. (in) AP Dempster , NM Laird a Donald Rubin , „  Maximální pravděpodobnost neúplných údajů prostřednictvím algoritmu EM  “ , Journal of the Royal Statistical Society. Řada B (metodická) , sv.  39, n o  1,1977, str.  1–38 ( JSTOR  2984875 )
2. (in) G. Celeux a G. Govaert , „  Klasifikační EM algoritmus pro shlukování a dvě stochastické verze  “ , Computational Statistics Quarterly , sv.  2, n O  1, 1991, str.  73–82
3. (in) Frank Nielsen , „  k-MLE: Rychlý algoritmus pro učení modelů statistické směsi  “ , arxiv (ICASSP 2012) , 2012( číst online )
4. (in) G. Celeux a G. Diebolt , „  Týden algoritmů: pravděpodobnostní algoritmus odvozený z algoritmu učitele em pro směsný problém  “ , Research Report RR-1364, INRIA, National Institute for Research in Computer Science and Control , 1985

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