Ukryte modele Markowa i algorytm maksymalizacji oczekiwań

Czy ktoś może wyjaśnić, w jaki sposób ukryte modele Markowa są powiązane z maksymalizacją oczekiwań? Przejrzałem wiele linków, ale nie mogłem uzyskać jasnego widoku.

Dzięki!

Algorytm EM (maksymalizacja oczekiwań) jest ogólnym algorytmem optymalizacji funkcji prawdopodobieństwa w przypadkach, w których model jest określony probabilistycznie w kategoriach obserwowanego i nieobserwowanego (ukrytego) komponentu. HMM (ukryte modele Markowa) są modelami tej formy, ponieważ mają nieobserwowany komponent, ukryte stany, a rzeczywiste obserwacje są często nazywane emisjami w terminologii HMM. Dlatego HMM tworzą klasę modeli, dla których algorytm EM może być użyteczny.

W generelu, jeśli model składa się z dwóch składników , dla których zakładamy, że dla uproszczenia przyjmujemy wartości w skończonej przestrzeni, a specyfikacja modelu probabilistycznego składa się z prawdopodobieństw punktów wspólnych , sparametryzowane przez , wówczas prawdopodobieństwo przy obserwacji tylko wynosi $(X,Y)$$p_{\theta}(x,y)$$\theta$$X = x$

$$L_x(\theta) = \sum_{y} p_{\theta}(x,y).$$ Chociaż suma wygląda na niewinną, nie jest. W przypadku HMM suma będzie obejmowała wszystkie możliwe przejścia między stanami ukrytymi, które szybko stają się znaczącą liczbą, gdy rośnie długość obserwowanej sekwencji. Na szczęście istnieją algorytmy dla HMM (do przodu i do tyłu) do szybkiego obliczania prawdopodobieństwa, a prawdopodobieństwo można w zasadzie podłączyć do dowolnego algorytmu optymalizacji ogólnego przeznaczenia w celu oszacowania maksymalnego prawdopodobieństwa . Alternatywą jest algorytm EM. Jest to algorytm, który zmienia się iteracyjnie$\theta$

• E-stopniowy , który jest obliczenie z warunkowego oczekiwania dla zmierzonego w obecnym oszacowania$x$$\theta$
• M etap , który jest maksymalizacja

Algorytm EM ma sens, jeśli dwa powyższe kroki można zaimplementować w sposób efektywny obliczeniowo, np. Gdy mamy zamknięte wyrażenia formularza dla warunkowego oczekiwania i maksymalizacji.

Historycznie, ogólny algorytm EM przypisuje się Dempsterowi, Lairdowi i Rubinowi , którzy udowodnili w swojej pracy z 1977 r., Między innymi, że algorytm prowadzi do sekwencji parametrów o monotonnej wartości rosnącego prawdopodobieństwa. Stworzyli również termin „algorytm EM”. Co ciekawe, algorytm EM dla HMM został opisany już w 1970 roku przez Bauma i in. , i jest często nazywany algorytmem Bauma-Welcha w literaturze HMM (nie wiem dokładnie, co zrobił Welch ...).

Oczekiwanie Maksymalizacja jest iteracyjną metodą stosowaną do przeprowadzania wnioskowania statystycznego na wielu różnych generatywnych modelach statystycznych, na przykład na mieszaninie Gaussów i innych modelach sieci bayesowskiej. Jedynym połączeniem jest to, że HMM to także sieci bayesowskie. Ale prawdopodobnie nie użyłby się EM na HMM, ponieważ istnieje dokładny algorytm wnioskowania w HMM zwany algorytmem Viterbi. Więc chociaż można użyć EM do wnioskowania na HMM, nie zrobiłbyś tego, ponieważ nie ma powodu.

W HMM staramy się oszacować głównie trzy parametry:

1. Prawdopodobieństwa stanu początkowego. Jest to wektor z elementami , gdzie jest liczbą stanów.$K$$K$

2. Macierz przejścia. Jest macierzą kwadratową o rozmiarze .$K\times K$

3. Warunkowe prawdopodobieństwa obserwacji przedmiotu, uwarunkowane pewnym stanem. Jest to również macierz wielkości , gdzie jest liczbą obserwacji.$K\times N$$N$

Teraz część EM pojawia się, gdy próbujesz oszacować ilości / parametry określone powyżej. Zaczynając od losowych przypuszczeń, ocenia się prawdopodobieństwo obserwacji, a parametry dostosowuje się iteracyjnie, aż do uzyskania maksymalnego prawdopodobieństwa. Tak więc za pomocą HMM modelujemy pewien proces i do tego musimy wprowadzić pewne parametry. Aby oszacować parametry, renderowany jest EM.

To jest bardzo krótka odpowiedź. Wdrożenie EM wymaga szeregu innych podproblemów do rozwiązania za pomocą szeregu technik. Dla dokładnego zrozumienia wysoce zalecany jest samouczek Rabiner classic.