EM algoritmus (z anglického expectation–maximization – očekávaná (střední) hodnota–maximalizace) je ve statistice iterační metoda pro hledání maximálně věrohodného odhadu nebo odhadu parametrů statistického modelu s maximální aposteriorní pravděpodobností (MAP), který závisí na nepozorovaných skrytých proměnných. Při EM iteracích se pravidelně střídají kroky výpočtu střední hodnoty (očekávání, E) s kroky maximalizace (M). V kroku E se vytváří očekávaná logaritmická věrohodnostní funkce na základě aktuálního odhadu parametrů. V kroku M se počítají parametry maximalizující očekávanou logaritmickou věrohodnostní funkci nalezenou v kroku E. Tyto odhady parametrů se pak používají pro určení rozdělení skrytých proměnných v dalším kroku E.
EM algoritmus popsali, vysvětlili a pojmenovali Arthur P. Dempster, Nan Laird a Donald Rubin v klasickém článku z roku 1977,[1] ve kterém zmínili, že EM algoritmus byl v minulosti „mnohokrát navržen a popsán pro speciální případy“ jinými autory. Jedním z prvních popisů byla metoda počítání genů pro odhadování frekvence alel, kterou popsal Cedric Smith[2]. Velmi podrobný popis EM metody pro exponenciální funkce publikoval Rolf Sundberg ve své diplomové práci a několika odborných článcích[3][4][5] vzniklých při jeho spolupráci s Per Martin-Löfem a Anders Martin-Löfem[6][7][8][9][10].[11][12] Článek Dempstera, Lairda a Rubina z roku 1977 zobecňuje metodu a načrtává analýzu konvergence pro širší třídu problémů. Bez ohledu na dřívější objevy, inovativní článek Dempstera, Lairda a Rubina v Journal of Royal Statistical Society vyvolal nadšenou diskuzi na setkání Royal Statistical Society se Sundberg vedl k označení článku za „brilantní“. Zmiňovaný článek učinil z EM metody důležitý nástroj statistické analýzy.
Později se ukázalo, že analýza konvergence EM algoritmu ve výše zmíněném článku byl chybná; opravenou analýzu konvergence publikoval C. F. Jeff Wu v roce 1983.[13] Jeho důkaz prokázal konvergenci EM metody i mimo rodinu exponenciálních rozdělení, kterou vyžadoval původní článek.[13]
EM algoritmus se používá pro hledání (lokální) maximálně věrohodných parametrů statistického modelu v případech, kdy rovnice nelze vyřešit přímo. Tyto modely typicky kromě neznámých parametrů a známých dat pozorování zahrnují skryté proměnné. To znamená, že buď v datech existují chybějící hodnoty nebo lze model formulovat jednodušeji, pokud předpokládáme, že existují další nepozorované datové body. Například smíšený model lze popsat jednodušeji, pokud předpokládáme, že ke každému pozorovanému datovému bodu existuje další nepozorovaný datový bod nebo skrytá proměnná, která popisuje kombinační komponentu, do které každý datový bod patří.
Hledání maximálně věrohodného řešení typicky vyžaduje použití derivace věrohodnostní funkce podle všech neznámých hodnot, parametrů a skrytých proměnných a současně řešení výsledné rovnice. U statistických modelů se skrytými proměnnými to obvykle není možné. Místo toho bývá výsledkem soustava vzájemně propojených rovnic, ve které řešení parametrů vyžaduje hodnoty skrytých proměnných a naopak, přičemž substituce jedné sady rovnic do druhé produkuje neřešitelné rovnice.
EM algoritmus vychází z pozorování, že tyto dvě sady rovnic lze řešit numericky: Je možné vybrat libovolné hodnoty pro jednu ze obou sad neznámých a pomocí nich odhadnout druhou sadu. Pak pomocí nových hodnot najít lepší odhad první sady, a tak pokračovat ve střídání obou kroků dokud výsledné hodnoty nekonvergují k pevným bodům. Lze dokázat, že v tomto kontextu tento postup konverguje, a že v tomto bodě je derivace věrohodnostní funkce libovolně blízko k nule, což znamená, že nalezený bod je buď maximem nebo sedlovým bodem.[13] Obecně však může existovat více maxim, a není záruka, že algoritmus nalezne globální maximum. Některé věrohodnostní funkce mají v sobě také singularity, tj. nesmyslná maxima. Například jedno z řešení, které může EM algoritmus nalézt ve smíšeném modelu, spočívá v tom, že jedna ze složek má nulový rozptyl a střední parametr pro stejnou složku se rovná jednomu z datových bodů.
Je-li dán statistický model, který generuje množinu X {\displaystyle \mathbf {X} } pozorovaných dat, množina nepozorovaných skrytých dat nebo chybějících hodnot Z {\displaystyle \mathbf {Z} } a vektor neznámých parametrů θ {\displaystyle {\boldsymbol {\theta }}} , spolu s věrohodnostní funkcí L ( θ ; X , Z ) = p ( X , Z ∣ θ ) {\displaystyle L({\boldsymbol {\theta }};\mathbf {X} ,\mathbf {Z} )=p(\mathbf {X} ,\mathbf {Z} \mid {\boldsymbol {\theta }})} , pak maximálně věrohodný odhad (MLE) neznámých parametrů je určen maximalizací marginální věrohodnosti pozorovaných dat
Tato hodnota je však často nevyčíslitelná (například pokud Z {\displaystyle \mathbf {Z} } je posloupnost událostí, poroste počet hodnot exponenciálně s délkou posloupnosti, takže přesný výpočet sumy bude extrémně obtížný).
EM algoritmus se snaží najít MLE marginální věrohodnosti iterativním používáním následujících dvou kroků:
Typické modely, na které se EM aplikuje, používají Z {\displaystyle \mathbf {Z} } jako skrytou proměnnou, což udává příslušnost k jedné z následujících situací:
EM je však možné aplikovat i na jiné třídy modelů.
Motivace je následující: Pokud jsou známé hodnoty parametrů θ {\displaystyle {\boldsymbol {\theta }}} , lze hodnotu skryté proměnné Z {\displaystyle \mathbf {Z} } obvykle nalézt maximalizací logaritmické věrohodnostní funkce přes všechny možné hodnoty Z {\displaystyle \mathbf {Z} } , buď jednoduše iterováním přes Z {\displaystyle \mathbf {Z} } nebo pomocí nějakého algoritmu, například Baumova–Welchova algoritmu pro skryté Markovovy modely. Pokud naopak známe hodnoty skryté proměnné Z {\displaystyle \mathbf {Z} } , můžeme nalézt odhad parametrů θ {\displaystyle {\boldsymbol {\theta }}} docela snadno, typicky jednoduchým seskupováním pozorovaných datových bodů podle hodnoty příslušných skrytých proměnných a průměrováním hodnot, nebo nějaké funkce hodnot, bodů z každé skupiny. V případě, když θ {\displaystyle {\boldsymbol {\theta }}} i Z {\displaystyle \mathbf {Z} } jsou neznámé, nabízí se použít iterativní algoritmus:
Právě popsaný algoritmus se monotónně přibližuje lokálnímu minimu nákladové funkce.
Označení krok očekávání (E) je poněkud nevhodné pojmenování. V prvním kroku se počítají pevné parametry funkce Q (závislé na datech). Jakmile jsou parametry Q známé, je Q plně určena a ve druhém (M) kroku EM algoritmu se provádí její maximalizace.
Ačkoli EM iterace skutečně zvyšuje (marginální) hodnotu věrohodnostní funkce na pozorovaných datech, není záruka, že posloupnost konverguje k odhadu maximální věrohodnosti. Pro multimodální distribuce to znamená, že EM algoritmus může konvergovat k lokálnímu maximu pozorované věrohodnostní funkce, v závislosti na počátečních hodnotách. Pro únik z lokálního maxima existuje množství heuristik a metaheuristik, například gradientní algoritmus s opakovaným náhodným startem (začíná s několika různými náhodnými počátečními odhady θ(t)) nebo použití metod simulovaného žíhání.
EM algoritmus je zvláště užitečný, když věrohodnost patří do rodiny exponenciálních rozdělení: v kroku E se použije suma očekávání dostačujících statistik a v kroku M se maximalizuje lineární funkce. V takovém případě je obvykle možné odvodit tvaru analytické řešení aktualizací v každém kroku pomocí Sundbergova vzorce (který publikoval Rolf Sundberg na základě nepublikovaných výsledků Per Martin-Löfa a Anders Martin-Löfa).[4][5][8][9][10][11][12]
V původním článku od Dempstera, Lairda a Rubina byla uvedena úprava EM metody pro výpočet maximálního aposteriorního odhadu (MAP) pro bayesovské vyvozování.
Existují i jiné metody pro hledání maximálně věrohodných odhadů, jako například metoda gradientního spádu, metoda sdružených gradientů nebo varianty Gaussova–Newtonova algoritmu. Na rozdíl od EM však tyto metody typicky vyžadují vyhodnocování první nebo druhé derivace věrohodnostní funkce.
EM algoritmus se snaží zlepšit Q ( θ ∣ θ ( t ) ) {\displaystyle Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})} , místo toho, aby přímo zlepšoval log p ( X ∣ θ ) {\displaystyle \log p(\mathbf {X} \mid {\boldsymbol {\theta }})} . Ukážeme, že vylepšení prvního znamená také vylepšení druhého.[14]
Pro jakékoli Z {\displaystyle \mathbf {Z} } s nenulovou pravděpodobností p ( Z ∣ X , θ ) {\displaystyle p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }})} , můžeme psát
Vezměme očekávání přes možné hodnoty neznámých dat Z {\displaystyle \mathbf {Z} } podle aktuálního odhadu parametru θ ( t ) {\displaystyle \theta ^{(t)}} , znásobíme obě strany p ( Z ∣ X , θ ( t ) ) {\displaystyle p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }}^{(t)})} a sečteme (nebo zintegrujeme) podle Z {\displaystyle \mathbf {Z} } . Levá strana je očekávaná hodnota konstanty, takže dostáváme:
kde H ( θ ∣ θ ( t ) ) {\displaystyle H({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})} je definované jako opačná hodnota součtu, který nahrazuje. Tato poslední rovnice platí pro každou hodnotu θ {\displaystyle {\boldsymbol {\theta }}} , včetně θ = θ ( t ) {\displaystyle {\boldsymbol {\theta }}={\boldsymbol {\theta }}^{(t)}} ,
a odečtením této poslední rovnice od předchozí rovnice dává
Jensenova nerovnost nám však říká, že H ( θ ∣ θ ( t ) ) ≥ H ( θ ( t ) ∣ θ ( t ) ) {\displaystyle H({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})\geq H({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)})} , z čehož můžeme vyvodit, že
Neboli výběr θ {\displaystyle {\boldsymbol {\theta }}} pro zlepšení Q ( θ ∣ θ ( t ) ) {\displaystyle Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})} způsobí, že se log p ( X ∣ θ ) {\displaystyle \log p(\mathbf {X} \mid {\boldsymbol {\theta }})} zlepší nejméně o totéž.
EM algoritmus lze chápat jako dva střídající se kroky maximalizace, tj. jako příklad vzestupu podle souřadnice.[15][16] Uvažujme funkci:
kde q je libovolné rozdělení pravděpodobnosti nepozorovaných dat z a H(q) je entropie rozdělení q. Tuto funkci lze zapsat jako
kde p Z ∣ X ( ⋅ ∣ x ; θ ) {\displaystyle p_{Z\mid X}(\cdot \mid x;\theta )} je podmíněné rozdělení pravděpodobnosti nepozorovaných dat, jsou-li dána pozorovaná data x {\displaystyle x} , a D K L {\displaystyle D_{KL}} je Kullbackova–Leiblerova divergence.
Pak na kroky v EM algoritmu můžeme pohlížet jako:
EM se často používá pro shlukovou analýzu ve strojovém učení a počítačovém vidění. Při zpracování přirozeného jazyka se velmi často používají dvě varianty EM algoritmu – Baumův–Welchův algoritmus pro skryté Markovovy modely a inside-outside algoritmus pro učení pravděpodobnostních bezkontextových gramatik bez učitele.
EM se často používá pro odhad parametrů smíšených modelů,[17][18] především v kvantitativní genetice[19].
V psychometrice je EM algoritmus téměř nepostradatelný pro odhadování parametrů položek a skrytých schopností modelů teorie odpovědi na položku.
Díky schopnosti pracovat s chybějícími daty a pozorovat neidentifikované proměnné se EM stává užitečným nástrojem pro oceňování a správu rizik portfolia.
EM algoritmus (a jeho rychlejší varianta OSEM Ordered subset expectation maximization) se často používá při vytváření obrazu v zobrazovacích metodách v lékařství, zvláště pro pozitronovou emisní tomografii a jednofotonovou emisní výpočetní tomografii. Rychlejší varianty EM jsou popsány dále.
Ve strukturálním inženýrství je algoritmus STRIDE Structural Identification using Expectation Maximization[20] pouze výstupní metoda pro identifikaci přirozených vibračních vlastností strukturálního systému pomocí senzorových dat (viz operační modální analýza).
Kalmanův filtr se typicky používá pro online odhad stavu a vyhlazování s minimálním rozptylem může být použito pro offline nebo dávkový odhad stavu. Nicméně tato řešení s minimálním rozptylem vyžadují odhady parametrů modelu stavového prostoru. EM algoritmy lze používat pro řešení problémů sdružených stavů a odhady parametrů.
Filtrovací a vyhlazovací EM algoritmy vznikají opakováním následujícího dvoukrokového postupu:
Předpokládejme, že Kalmanův filtr nebo vyhlazování s minimálním rozptylem pracuje s měřeními systému s jediným vstupem a jediným výstupem, který je ovlivněn aditivním bílým šumem. Aktualizovaný odhad měření rozptylu šumu lze získat z výpočtu maximální věrohodnosti
kde x ^ k {\displaystyle {\widehat {x}}_{k}} jsou odhady skalárního výstupu vypočítané filtrem nebo vyhlazováním z N skalárních měření z k {\displaystyle z_{k}} . Výše uvedená aktualizace může také být aplikována na aktualizaci Poissonovo měření intenzity šumu. Podobně pro autoregresivní proces prvního řádu lze vypočítat odhad rozptylu aktualizovaného šumu procesu podle vzorce
kde x ^ k {\displaystyle {\widehat {x}}_{k}} a x ^ k + 1 {\displaystyle {\widehat {x}}_{k+1}} jsou skalární odhady stavu vypočítané filtrem nebo vyhlazování. Aktualizovaný odhad koeficientů modelu je získaný podle vzorce
Konvergence odhadů parametrů obdobných jako jsou uvedeny výše jsou dobře studované.[21][22][23][24]
Bylo navrženo několik metod pro zrychlení někdy pomalé konvergence EM algoritmu, například metody používající sdružený gradient a modifikace Newtonovy metody (Newtonova–Raphsonova metoda)[25]. EM lze také používat pro metody omezeného odhadu.
Algoritmus Parameter-expanded expectation maximization (PX-EM) vede často ke zrychlení díky „použití `nastavení kovariance' pro opravu analýzy kroku M, přičemž využívá zvláštní informace zachycené v přisuzovaných úplných datech“[26].
Expectation conditional maximization (ECM) nahrazuje každý M krok v posloupností kroků podmíněné maximalizace (CM), ve kterých se každý parametr θi maximalizuje samostatně, když se ostatní parametry nemění.[27] Rozšířením tohoto algoritmu je Expectation conditional maximization either (ECME).[28]
Uvedený přístup lze dále rozšířit na algoritmus generalized expectation maximization (GEM), u kterého se hledají pouze přírůstky účelové funkce F jak v kroku E tak v kroku M, jak je popsané v části Jako postup maximalizace maximalizace.[15] GEM se dále vyvíjí v distribuovaném prostředí a vykazuje slibné výsledky.[29]
Je také možné považovat EM algoritmus za podtřídu MM algoritmu (Majorize/Minimize nebo Minorize/Maximize, podle kontextu),[30][31] a používat pro něj všechny techniky vyvinuté pro obecnější případ.
Funkce Q používaná v EM algoritmu je založena na logaritmické věrohodnostní funkci. Proto je považována za log-EM algoritmus. Použití logaritmické věrohodnostní funkce lze zobecnit na použití α-logaritmu poměru věrohodností. Potom lze α-log poměru věrohodností pozorovaných dat přesně vyjádřit jako rovnost použitím funkce Q aplikované na α-logaritmus poměru věrohodností a α-divergence. Získání této funkce Q je zobecněný krok E. Jeho maximalizace je zobecněný krok M. Výsledný algoritmus se nazývá α-EM algoritmus. [32] α-EM algoritmus, jehož autorem je Yasuo Matsuyama je zobecněním log-EM algoritmu. Není potřeba žádný výpočet gradientu nebo matice Hessianů. Při výběru vhodného α vykazuje α-EM algoritmus rychlejší konvergenci než log-EM. α-EM algoritmus vede k rychlejší verzi algoritmu α-HMM odhadu skrytých Markovových modelů. [33]
EM je částečně nebayesovská metoda založená na maximální věrohodnosti. Její konečný výsledek dává rozdělení pravděpodobnosti přes skryté proměnné (v bayesovském stylu) spolu s bodovým odhadem θ (buď maximálně věrohodný odhad anebo v a posterior režimu). Může být požadována jeho plně bayesovská verze, která dává rozdělení pravděpodobnosti podle θ a skryté proměnné. Při bayesovském přístupu k inference bychom jednoduše považovali θ za další skrytou proměnnou. Při tomto přístupu mizí rozdíl mezi kroky E a M. Při použití faktorizované aproximace Q popsané výše (variační bayesovská metoda) může řešení iterovat přes každou skrytou proměnnou (včetně θ) a optimalizovat je po jedné. Nyní je potřeba k kroků pro každou iteraci, kde k je počet skrytých proměnných. Pro grafické modely je to snadné udělat, protože nové Q pro každou proměnnou závisí pouze na jeho Markovově blanketu, takže pro efektivní inference lze používat lokální předávání variačních zpráv (Variational message passing, VMP).
V informační geometrii jsou kroky E a M interpretovány jako projekce pod duální afinní konexe, nazývané e-spojení a m-spojení; Pomocí těchto termínů lze pohlížet na Kullbackovu–Leiblerovu divergenci.
Nechť x = ( x 1 , x 2 , … , x n ) {\displaystyle \mathbf {x} =(\mathbf {x} _{1},\mathbf {x} _{2},\ldots ,\mathbf {x} _{n})} jsou vzorky n {\displaystyle n} nezávislých pozorování z kombinace dvou vícerozměrných normálních rozdělení dimenze d {\displaystyle d} a nechť z = ( z 1 , z 2 , … , z n ) {\displaystyle \mathbf {z} =(z_{1},z_{2},\ldots ,z_{n})} jsou skryté proměnné, které určují komponentu, z nichž pozorování pochází[16].
kde
Cílem je odhadnout neznámé parametry reprezentující mísení hodnot dvou normálních rozdělení a střední hodnoty a kovariance obou:
kde Věrohodnostní funkce věrohodnosti pro neúplná data je
a Věrohodnostní funkce věrohodnosti pro úplná data je
nebo
kde I {\displaystyle \mathbb {I} } je charakteristická funkce a f {\displaystyle f} je hustota pravděpodobnosti vícerozměrného normálního rozdělení.
V poslední rovnosti se pro každé i jedna hodnota charakteristické funkce I ( z i = j ) {\displaystyle \mathbb {I} (z_{i}=j)} rovná nule a jedna jedničce. Vnitřní součet tedy má vždy pouze jeden člen.
Máme-li aktuální odhad parametrů θ(t), bude podmíněné rozdělení pravděpodobnosti Zi určeno Bayesovou větou, aby to byla proporcionální výška normální hustoty vážená parametrem τ:
Tyto hodnoty, které jsou obvykle považovány za výstup kroku E (přestože to není funkce Q popsaná níže), se nazývají „členské pravděpodobnosti“.
Tento E krok odpovídá nastavení této funkce pro Q:
Střední hodnota („očekávání“) log L ( θ ; x i , Z i ) {\displaystyle \log L(\theta ;\mathbf {x} _{i},Z_{i})} v sumě se bere vzhledem k hustotě pravděpodobnosti P ( Z i ∣ X i = x i ; θ ( t ) ) {\displaystyle P(Z_{i}\mid X_{i}=\mathbf {x} _{i};\theta ^{(t)})} , která může být pro každé x i {\displaystyle \mathbf {x} _{i}} z trénovací množiny jiná. Před provedením kroku E jsou známé všechny potřebné hodnoty kromě T j , i {\displaystyle T_{j,i}} , které se počítají podle rovnice na začátku kroku E.
Tuto plně podmíněnou střední hodnotu není třeba počítat v jednom kroku, protože τ a μ/Σ se vyskytují ve zvláštních lineárních členech a mohou být tedy maximalizovány nezávisle.
Protože Q(θ | θ(t)) je kvadratická funkce, je určování maximalizujících hodnot θ relativně přímočaré. Také τ, (μ 1,Σ1) a (μ 2,Σ2) mohou být vesměs maximalizovány nezávisle, protože se všechny vyskytují v samostatných lineárních členech.
Pro začátek uvažujme τ s omezením τ1 + τ2=1:
což má stejný tvar jako MLE pro binomické rozdělení, takže
Pro další odhady (μ 1,Σ1):
což má stejný tvar jako vážené MLE pro normální rozdělení, takže
a díky symetrii
Iterativní proces ukončíme, jakmile E Z ∣ θ ( t ) , x [ log L ( θ ( t ) ; x , Z ) ] ≤ E Z ∣ θ ( t − 1 ) , x [ log L ( θ ( t − 1 ) ; x , Z ) ] + ε {\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 } pro předem zvolenou hodnotu ε {\displaystyle \varepsilon } .
Výše popsaný algoritmus lze zobecnit pro kombinaci více než dvou vícerozměrných normálních rozdělení.
EM algoritmus byl implementován pro případ, kdy existuje podkladový model lineární regrese, který vysvětluje variace určité velikosti, ale skutečně pozorované hodnoty jsou cenzurovanou nebo zkrácenou verzí hodnot reprezentovaných v modelu.[34] Speciální případy tohoto modelu zahrnují cenzurované nebo zkrácené pozorování z jednoho normální rozdělení.[34]
EM algoritmus typicky konverguje k lokální optimu. Toto lokální optimum však nemusí být globálním optimem, a také nemáme jakýhokoli odhad rychlosti konvergence. V mnoharozměrném prostoru může být konvergence libovolně špatná a může existovat exponenciální počet lokálních optim. Proto existuje potřeba pro alternativní metody pro zaručené učení, zvláště v mnohadimanzionálních prostředích. Vedle algoritmu EM existují i jiné algoritmy, které lépe zaručují konzistenci. Tyto algoritmy využívají přístupy založené na momentech[35] nebo tak zvané spektrální techniky[36][37]. Zájem o algoritmy pro učení parametrů pravděpodobnostního modelu používající momenty se v poslední době stále zvyšuje, protože za určitých podmínek mohou na rozdíl od EM algoritmu, jehož velkým problémem je uváznutí v lokálním optimu, zaručit například globální konvergenci. Algoritmy se zaručeným učením mohou být odvozeny pro několik důležitých modelů, jako jsou smíšené modely, skryté Markovovy modely atd. V těchto spektrálních metodách, se neobjevují žádná nepravá lokální optima, a skutečné parametry lze při splnění určitých podmínek regularity konzistentně odhadnout.
V tomto článku byl použit překlad textu z článku Expectation–maximization algorithm na anglické Wikipedii.
