Ukryte modele Markowa i algorytm maksymalizacji oczekiwań

Odpowiedzi:

12

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θ(x,y)θX=x

Lx(θ)=ypθ(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θ
  • E-stopniowy , który jest obliczenie z warunkowego oczekiwania dla zmierzonego w obecnym oszacowaniaxθ
  • 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 ...).

NRH
źródło
3
Welch wynalazł algorytm Baum-Welcha (nazywa to „łatwą częścią”); Baum matematycznie udowadnia, że ​​algorytm działa („trudna część”). Szczegółowe informacje znajdują się na Kursy.cs.tamu.edu/rgutier/cpsc689_s07/welch2003baumWelch.pdf .
Michaił Korobow
@MikhailKorobov, dzięki za te informacje.
NRH
2

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.

William
źródło
4
Nie jest to do końca dokładne, ponieważ łączysz dwa różne rodzaje „wnioskowania”. EM jest algorytmem do szacowania nieznanych parametrów, Viterbi jest algorytmem do obliczania najbardziej prawdopodobnej sekwencji stanów ukrytych. Rzeczywiście użyłbyś EM dla HMM do oszacowania parametrów. W mojej odpowiedzi podałem więcej szczegółów na temat algorytmu EM z odniesieniami historycznymi wyjaśniającymi związek między HMM a EM.
NRH
0

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.KK

  2. Macierz przejścia. Jest macierzą kwadratową o rozmiarze .K×K

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

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.

Riaz Khan
źródło