Wikipedie

EM algoritmus: Porovnání verzí

Interaktivně procházet historii
← Přejít na předchozí porovnáníPřejít na další porovnání →
Smazaný obsah Přidaný obsah
VizuálníWikitext
Oprava překladu a terminologie
Oprava textu, +Portály|Matematika
Řádek 1:
'''EM algoritmus''' (z anglického {{Cizojazyčně|en|''expectation–maximization''}} – '''očekávaná (střední) hodnota–maximalizace''') je ve [[statistika|statistice]] [[iterační metoda]] pro hledání [[Metoda maximální věrohodnosti|maximálně věrohodného]] odhadu nebo odhadu [[Parametr (matematika)|parametrů]] [[Statistický model|statistického modelu]] s [[maximální aposteriorní pravděpodobnost]]í (MAP), který závisí na nepozorovaných [[Skrytá proměnná|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á [[Věrohodnostní funkce#Log-věrohodnost|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.
 
[[Soubor:EM Clustering of Old Faithful data.gif|vpravo|rám|EM [[Shluková analýza|clusterování]] dat o erupcích gejzíru[[gejzír]]u [[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ír]]u. Vizualizováno pomocí [[ELKI]].]]
 
== Historie ==
Řádek 131:
:<math>L(\boldsymbol\theta; \mathbf{X}) = p(\mathbf{X}\mid\boldsymbol\theta) = \int p(\mathbf{X},\mathbf{Z} \mid \boldsymbol\theta) \, d\mathbf{Z} </math>
 
Tato hodnota je však často nevyčíslitelná (například pokud <math>\mathbf{Z}</math> je posloupnost událostí, poroste počet hodnot bude růst 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 <math>Q(\boldsymbol\theta\mid\boldsymbol\theta^{(t)})</math> jako [[Očekávaná hodnota|očekávanou hodnotu]] logaritmické [[věrohodnostní funkce]] <math>\boldsymbol\theta</math>, vzhledem k aktuálnímu [[podmíněné rozdělení pravděpodobnosti|podmíněnému rozdělení pravděpodobnosti]] <math>\mathbf{Z}</math> danýpro dané <math>\mathbf{X}</math> a aktuálnímaktuální odhadůmodhady parametrů <math>\boldsymbol\theta^{(t)}</math>:
::<math>Q(\boldsymbol\theta\mid\boldsymbol\theta^{(t)}) = \operatorname{E}_{\mathbf{Z}\mid\mathbf{X},\boldsymbol\theta^{(t)}}\left[ \log L (\boldsymbol\theta; \mathbf{X},\mathbf{Z}) \right] \,</math>
 
Řádek 156:
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 [[Metoda maximální věrohodnosti|odhadu maximální věrohodnosti]]. Pro [[bimodální rozdělení|multimodální distribuce]] to znamená, že EM algoritmus může konvergovat k [[lokální maximum|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í [[Heuristika|heuristik]] a [[Metaheuristika|metaheuristik]], jako je například [[gradientní algoritmus]] s opakovaným náhodným opětovným startem (začíná se s &nbsp;několika různými náhodnými počátečními odhady ''θ''<sup>(''t'')</sup>) nebo použitímpoužití metod [[Simulované žíhání|simulovaného žíhání]].
 
EM algoritmus je zvláště užitečný, když věrohodnost patří do [[Rodina exponenciálních rozdělení|rodiny exponenciálních rozdělení]]: v kroku E se použije suma očekávání [[dostačujícíDostačující statistika|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öf|Per Martin-Löfa]] a [[Anders Martin-Löf|Anders Martin-Löfa]]).<ref name="Sundberg1971"/><ref name="Sundberg1976"/><ref name="Martin-Löf1963"/><ref name="Martin-Löf1966"/><ref name="Martin-Löf1970"/><ref name="Martin-Löf1974a"/><ref name="Martin-Löf1974b"/>
 
V původním článku od Dempstera, Lairda a Rubina byla uvedena úprava EM metody pro výpočet [[maximální aposteriorní odhad|maximálního aposteriorního odhadu]] (MAP) pro [[Bayesovské vyvozování]].
Řádek 461:
</ref>
 
Je také možné uvažovatpovažovat EM algoritmus jakoza podtřídu '''[[MM algoritmus|MM algoritmu]]''' (Majorize/Minimize nebo Minorize/Maximize, v závislosti napodle kontextu),<ref>{{Citace elektronické monografie
| příjmení = Lange
| jméno = Kenneth
Řádek 478:
 
=== α-EM algoritmus ===
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. TatoVýsledný dvojicealgoritmus se nazývá α-EM algoritmus,.
<ref>
{{Citace periodika
Řádek 492:
}}
</ref>
který obsahuje logaritmický EM algoritmus jako svou podtřídu. α-EM algoritmus, jehož autorem je [[Yasuo Matsuyama]] je tedy 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 vykazujealgoritmus rychlejší konvergenci než log-EM algoritmus výběrem vhodných α. α-EM algoritmus vede k rychlejší verzi algoritmu α-HMM odhadu [[Skrytý Markovův model|skrytých Markovových modelů]].
<ref>
{{Citace periodika
Řádek 729:
* [http://pages.cs.wisc.edu/~jerryzhu/cs838/EM.pdf EM Algoritmus], autor: Xiaojin Zhu.
* [https://arxiv.org/pdf/1105.1476.pdf EM algoritmus a varianty: neformální tutoriál] Alexise Roche. Podrobný a velmi jasný popis EM algoritmu a mnoha zajímavých variant.
 
{{Portály|Matematika}}
 
{{DEFAULTSORT:EM algoritmus}}
Citováno z „https://cs.wikipedia.org/wiki/EM_algoritmus“