EM algoritmus (z anglického – 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.
vpravo|rám|EM clusterování dat o erupcích gejzíru Old Faithful. Náhodný počáteční model (který kvůli různý měřítkům na osách vypadá jako dvě velmi nízké a široké elipsy) se přizpůsobuje pozorovaným datům. V první iteraci se model změní velmi výrazně, ale pak konverguje k rozlišení dvou režimů erupcí gejzíru. Vizualizováno pomocí ELKI.
Historie EM algoritmus popsali, vysvětlili a pojmenovali Arthur P. Dempster, Nan Laird a Donald Rubin v klasickém článku z roku 1977, 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. 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 vzniklých při jeho spolupráci s Per Martin-Löfem a Anders Martin-LöfemViz uznání od Dempstera, Lairda a Rubina na stránkách 3, 5 a 11.. Č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. Jeho důkaz prokázal konvergenci EM metody i mimo rodinu exponenciálních rozdělení, kterou vyžadoval původní článek.
Úvod 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. 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ů.
Popis Je-li dán statistický model, který generuje množinu pozorovaných dat, množina nepozorovaných skrytých dat nebo chybějících hodnot a vektor neznámých parametrů , spolu s věrohodnostní funkcí , 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 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ů: E krok (Expectation): Definujeme jako očekávanou hodnotu logaritmické věrohodnostní funkce , vzhledem k aktuálnímu podmíněnému rozdělení pravděpodobnosti pro dané a aktuální odhady parametrů :
M krok (Maximalizace): Najdeme parametry, které maximalizují následující výraz:
Typické modely, na které se EM aplikuje, používají jako skrytou proměnnou, což udává příslušnost k jedné z následujících situací: Pozorované datové body mohou být diskrétní (hodnoty tvoří konečnou nebo spočetně nekonečnou množinu) nebo spojité (hodnoty tvoří nespočetně nekonečnou množinu). Každému bodu dat může být přiřazen vektor pozorování. Chybějící hodnoty (nazývané také skryté proměnné) jsou diskrétní, vybírané z pevného počtu hodnot a s jednou skrytou proměnnou na pozorovanou jednotku. Parametry jsou spojité a jsou dvou druhů: Parametry, které jsou přiřazené k všem datovým bodům, a parametry přiřazené určité hodnotě skryté proměnné (tj. přiřazené ke všem datovým bodům, jejichž odpovídající skrytá proměnná má tuto hodnotu). EM je však možné aplikovat i na jiné třídy modelů.
Motivace je následující: Pokud jsou známé hodnoty parametrů , lze hodnotu skryté proměnné obvykle nalézt maximalizací logaritmické věrohodnostní funkce přes všechny možné hodnoty , buď jednoduše iterováním přes nebo pomocí nějakého algoritmu, například Baumova–Welchova algoritmu pro skryté Markovovy modely. Pokud naopak známe hodnoty skryté proměnné , můžeme nalézt odhad parametrů 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ž i jsou neznámé, nabízí se použít iterativní algoritmus: Nejdříve inicializovat parametry na nějaké náhodné hodnoty. Spočítat pravděpodobnost každé možné hodnoty pro dané . Pak, použít právě vypočtené hodnoty pro vypočítání lepšího odhadu parametrů . Opakovat kroky 2 a 3 dokud nekonvergují. Právě popsaný algoritmus se monotónně přibližuje lokálnímu minimu nákladové funkce.
Vlastnosti 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).
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.
Důkaz korektnosti EM algoritmus se snaží zlepšit , místo toho, aby přímo zlepšoval . Ukážeme, že vylepšení prvního znamená také vylepšení druhého.
Pro jakékoli s nenulovou pravděpodobností , můžeme psát
Vezměme očekávání přes možné hodnoty neznámých dat podle aktuálního odhadu parametru , znásobíme obě strany a sečteme (nebo zintegrujeme) podle . Levá strana je očekávaná hodnota konstanty, takže dostáváme:
kde je definované jako opačná hodnota součtu, který nahrazuje. Tato poslední rovnice platí pro každou hodnotu , včetně ,
a odečtením této poslední rovnice od předchozí rovnice dává
Jensenova nerovnost nám však říká, že , z čehož můžeme vyvodit, že
Neboli výběr pro zlepšení způsobí, že se zlepší nejméně o totéž.
Jako postup maximalizace maximalizace EM algoritmus lze chápat jako dva střídající se kroky maximalizace, tj. jako příklad vzestupu podle souřadnice. 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 je podmíněné rozdělení pravděpodobnosti nepozorovaných dat, jsou-li dána pozorovaná data , a je Kullbackova–Leiblerova divergence.
Pak na kroky v EM algoritmu můžeme pohlížet jako: Expectation krok: Zvolíme , které maximalizuje :
Maximalizační krok: Zvolíme , které maximalizuje :
Aplikace 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ů, především v kvantitativní genetice.
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 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).
EM algoritmy pro filtrování a vyhlazování 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:
krok E Použít Kalmanův filtr nebo vyhlazování s minimálním rozptylem navržený s odhady aktuálních parametrů pro získání odhadů aktualizovaných stavů.
krok M