Algorytm EM (oczekiwanie-maksymalizacja): prosta definicja

Estymacja maksymalnego prawdopodobieństwa > algorytm EM (Expectation-maximization)

warto najpierw przeczytać ten artykuł: Co To jest Estymacja maksymalnego prawdopodobieństwa?

co to jest algorytm EM?

algorytm EM może być użyty do oszacowania zmiennych utajonych, takich jak te, które pochodzą z rozkładów mieszaniny (wiesz, że pochodzą z mieszaniny, ale nie z której konkretnej dystrybucji).

algorytm Expectation-Maximization (EM) jest sposobem na znalezienie szacunków maksymalnego prawdopodobieństwa dla parametrów modelu, gdy dane są niekompletne, mają brakujące punkty danych lub mają nieobserwowane (ukryte) ukryte zmienne. Jest to iteracyjny sposób przybliżania funkcji maksymalnego prawdopodobieństwa. Podczas gdy oszacowanie maksymalnego prawdopodobieństwa może znaleźć model „najlepiej dopasowany” dla zestawu danych, nie działa szczególnie dobrze w przypadku niekompletnych zestawów danych. Bardziej złożony algorytm EM może znaleźć parametry modelu, nawet jeśli brakuje danych. Działa poprzez wybranie losowych wartości dla brakujących punktów danych i wykorzystanie tych przypuszczeń do oszacowania drugiego zestawu danych. Nowe wartości są używane do stworzenia lepszego odgadnięcia dla pierwszego zbioru, a proces trwa do momentu, gdy algorytm zbiega się w ustalonym punkcie.

Zobacz też: algorytm EM wyjaśniony na jednym zdjęciu.

MLE vs. EM

chociaż maksymalne prawdopodobieństwo estymacji (mle) i EM mogą znaleźć „najlepiej dopasowane” parametry, sposób znajdowania modeli są bardzo różne. MLE najpierw gromadzi wszystkie dane, a następnie wykorzystuje je do skonstruowania najbardziej prawdopodobnego modelu. EM najpierw zgaduje parametry-biorąc pod uwagę brakujące dane—a następnie dostosowuje model, aby dopasować go do domysłów i obserwowanych danych. Podstawowe kroki algorytmu to:

1. wstępne odgadnięcie parametrów modelu i tworzony jest rozkład prawdopodobieństwa. Jest to czasami nazywane „e-Step” dla „oczekiwanej” dystrybucji.
2. nowo zaobserwowane dane są wprowadzane do modelu.
3. rozkład prawdopodobieństwa z e-kroku jest modyfikowany, aby uwzględnić nowe dane. Jest to czasami nazywane ” m-step.”
4. kroki od 2 do 4 są powtarzane do momentu osiągnięcia stabilności (tj. rozkładu, który nie zmienia się z e-kroku na m-krok).

algorytm EM zawsze poprawia estymację parametru poprzez ten wieloetapowy proces. Jednak czasami potrzebuje kilku losowych startów, aby znaleźć najlepszy model, ponieważ algorytm może udoskonalić lokalne maksima, która nie jest tak blisko (optymalnej) globalnej maksimy. Innymi słowy, może działać lepiej, jeśli zmusisz go do ponownego uruchomienia i ponownie podejmiesz „wstępne zgadywanie” z kroku 1. Spośród wszystkich możliwych parametrów możesz wybrać ten z największym maksymalnym prawdopodobieństwem.

w rzeczywistości kroki te obejmują dość ciężki rachunek różniczkowy (całkowanie) i prawdopodobieństwa warunkowe, co wykracza poza zakres tego artykułu. Jeśli potrzebujesz bardziej technicznego (tj. opartego na rachunku) podziału procesu, Gorąco polecam przeczytanie artykułu Gupta i Chena z 2010 roku.

Aplikacje

algorytm EM ma wiele zastosowań, w tym:

• sygnały Dis-splątujące nałożone,
• Szacowanie modeli mieszanek Gaussa (GMMs),
• Szacowanie ukrytych modeli Markowa (Hmms),
• Szacowanie parametrów dla złożonych rozkładów Dirichleta,
• znalezienie optymalnych mieszanek modeli stałych.

ograniczenia

algorytm EM może być bardzo powolny, nawet na najszybszym komputerze. To działa najlepiej, gdy masz tylko niewielki procent brakujących danych i wymiarowość danych nie jest zbyt duża. Im wyższa wymiarowość, tym wolniejszy krok E; w przypadku danych o większych wymiarach może się okazać, że e-step działa bardzo wolno, ponieważ procedura zbliża się do lokalnego maksimum.

Dempster, A., Laird, N., and Rubin, D. (1977) Maximum likely from incomplete data via the EM algorithm, Journal of the Royal Statistical Society. Seria B (metodologiczna), t. 39, nr 1, s. 138.
Gupta, M. & Chen, Y. (2010) Teoria i zastosowanie algorytmu em. Podstawy i trendy w przetwarzaniu sygnałów, T. 4, NO. 3 223-296.

——————————————————————————

potrzebujesz pomocy z zadaniem domowym lub pytaniem testowym? Dzięki Chegg Study możesz uzyskać krok po kroku rozwiązania swoich pytań od eksperta w tej dziedzinie. Twoje pierwsze 30 minut z korepetytorem Chegg jest bezpłatne!