Coursera Learner working on a presentation with Coursera logo and
Coursera Learner working on a presentation with Coursera logo and

Algorytm Expectation-Maximization (EM) może być dzięki znalezieniu maksymalnych oszacowań prawdopodobieństwa dla parametrów modelu, gdy dane są niekompletne, mają brakujące punkty danych lub mają niezauważone (ukryte) ukryte zmienne. jest to iteracyjne dzięki funkcji przybliżenia maksymalnego prawdopodobieństwa. Podczas gdy oszacowanie maksymalnego prawdopodobieństwa może znaleźć “najlepiej pasujący” model dla grupy wiedzy, nie działa on szczególnie dobrze dla niekompletnych zbiorów danych. Bardziej złożony algorytm EM może znaleźć parametry modelu, choć brakuje w nim danych. Działa on poprzez wybranie losowych wartości dla brakujących punktów danych i wykorzystanie tych zgadywanek do oszacowania drugiego zbioru wiedzy. Nowe wartości nie pozwolą na znacznie lepsze zgadywanie dla podstawowego zbioru danych, dlatego proces ten trwa do momentu, gdy algorytm zbierze się w twardym i szybkim punkcie.

Patrz również: Algorytm EM wyjaśniony na jednym obrazku.

MLE vs. EM

Chociaż oszacowanie maksymalnego prawdopodobieństwa (MLE) i EM mogą znaleźć “najlepiej dopasowane” parametry, to sposób, w jaki znajdują modele, jest bardzo różny. MLE najpierw gromadzi wszystkie informacje, a następnie wykorzystuje te dane do skonstruowania najbardziej prawdopodobnego modelu. EM najpierw zgaduje parametry – licząc brakujące dane – po czym dopasowuje model do zgadywanek, a tym samym do obserwowanych danych. kluczowe kroki dla algorytmu są następujące:

Wstępne zgadywanie jest tworzone dla parametrów modelu i tworzony jest rozkład prawdopodobieństwa. jest to często nazywane “E-Step” dla rozkładu “oczekiwanego”.

Nowo zaobserwowane dane są wprowadzane do modelu.

Rozkład prawdopodobieństwa z E-kroku jest zmieniany tak, aby uwzględnić nowe dane. jest to często nazywane “Krokiem M”.

Kroki od 2 do 4 są powtarzane aż do osiągnięcia stabilności (tzn. rozkładu, który nie zmienia się z E-stopnia do M-stopnia).

Algorytm EM zawsze poprawia oszacowanie parametru poprzez ten wielostopniowy proces. Czasami potrzeba jednak kilku losowych startów, aby znaleźć najprostszy model, ponieważ algorytm może osiągnąć maksima obszaru, który nie jest na granicy (optymalnych) globalnych maksimów. Innymi słowy, może on działać lepiej, jeśli zmusi się go do ponownego uruchomienia i ponownego podjęcia tego “wstępnego zgadywania” z kroku 1. Spośród wszystkich możliwych parametrów wybierzesz wtedy ten, który ma największe prawdopodobieństwo.

W rzeczywistości kroki te obejmują dość ciężki rachunek (całkowanie) i prawdopodobieństwa warunkowe, co jest poza zakresem tego tekstu . Jeśli chciałbyś dokonać bardziej technicznego (tj. opartego na rachunku) rozbicia metody, gorąco polecam przeczytać artykuł Gupty i Chena z 2010 roku.

Zastosowania

Algorytm EM ma wiele zastosowań, w tym:

Rozłożenie nakładających się na siebie sygnałów,

Oszacowanie modeli mieszanek Gaussian (GMM),

Szacowanie ukrytych modeli Markova (HMM),

Oszacowanie parametrów dla rozkładów mieszanki Dirichleta,

Znalezienie optymalnych mieszanek modeli stałych.