Jaka jest różnica między algorytmami do przodu i do tyłu i algorytmami Viterbi?

Chcę wiedzieć, jakie są różnice między algorytmem do przodu i do tyłu i algorytmem Viterbiego do wnioskowania w ukrytych modelach Markowa (HMM).

Najpierw trochę tła, może trochę to wyjaśnia.

Mówiąc o HMM (ukrytych modelach Markowa), na ogół należy rozważyć 3 problemy:

1. Problem z oceną

   • Problem ewaluacji odpowiada na pytanie: jakie jest prawdopodobieństwo, że określona sekwencja symboli zostanie wygenerowana przez dany model?
   • Do oceny używamy dwóch algorytmów: algorytmu do przodu lub algorytmu do tyłu (NIE mylić ich z algorytmem do przodu i do tyłu).

2. Problem z dekodowaniem

   • Problem z dekodowaniem odpowiada na pytanie: Biorąc pod uwagę sekwencję symboli (twoje obserwacje) i model, jaka jest najbardziej prawdopodobna sekwencja stanów, które ją wytworzyły.
   • Do dekodowania używamy algorytmu Viterbi .

3. Problem treningowy

   • Problem szkoleniowy odpowiada na pytanie: Biorąc pod uwagę strukturę modelu i zestaw sekwencji, znajdź model, który najlepiej pasuje do danych.
   • W przypadku tego problemu możemy użyć następujących 3 algorytmów:
     1. MLE (oszacowanie maksymalnego prawdopodobieństwa)
     2. Szkolenie Viterbi (NIE mylić z dekodowaniem Viterbi)
     3. Baum Welch = algorytm do przodu i do tyłu

Podsumowując, używasz algorytmu Viterbi dla problemu dekodowania oraz Baum Welch / Forward-backward, kiedy trenujesz swój model na zestawie sekwencji.

Baum Welch działa w następujący sposób.

Dla każdej sekwencji w zestawie sekwencji treningowych.

1. Oblicz prawdopodobieństwa przekazania za pomocą algorytmu przekazania
2. Oblicz prawdopodobieństwa wsteczne za pomocą algorytmu wstecznego
3. Obliczyć udział bieżącej sekwencji w przejściach modelu, obliczyć udział bieżącej sekwencji w prawdopodobieństwach emisji modelu.
4. Oblicz nowe parametry modelu (prawdopodobieństwo startu, prawdopodobieństwo przejścia, prawdopodobieństwo emisji)
5. Oblicz nowe prawdopodobieństwo dziennika modelu
6. Zatrzymaj, gdy zmiana prawdopodobieństwa dziennika jest mniejsza niż podany próg lub gdy przekroczona zostanie maksymalna liczba iteracji.

Jeśli potrzebujesz pełnego opisu równań dla dekodowania Viterbiego i algorytmu treningowego daj mi znać, a mogę skierować cię we właściwym kierunku.

Forward-Backward daje marginalne prawdopodobieństwo dla każdego stanu , Viterbi daje prawdopodobieństwo najbardziej prawdopodobnej sekwencji stanów . Na przykład, jeśli Twoim zadaniem HMM jest przewidywanie pogody słonecznej i deszczowej na każdy dzień, funkcja Forward Backward poinformuje cię o prawdopodobieństwie, że będzie „słoneczna” każdego dnia, Viterbi poda najbardziej prawdopodobną sekwencję dni słonecznych / deszczowych, a prawdopodobieństwo tej sekwencji.

Uważam, że te dwa slajdy z {2} są naprawdę dobre do umiejscowienia algorytmów do przodu i do tyłu oraz wszystkich innych typowych algorytmów używanych w HMM:

Uwagi:

• $x$ to obserwowana emisja (emisje), to parametry HMM.$\pi$
• ścieżka = sekwencja emisji
• dekodowanie = wnioskowanie
• uczenie się = szkolenie = szacowanie parametrów
• Niektóre artykuły (np. {1}) twierdzą, że Baum – Welch jest taki sam jak algorytm do przodu i do tyłu, ale zgadzam się z Masterfool i Wikipedią: Baum – Welch jest algorytmem maksymalizacji oczekiwań, który wykorzystuje algorytm do przodu i do tyłu. Te dwie ilustracje również odróżniają Bauma – Welcha od algorytmu do przodu i do tyłu.

Bibliografia:

• {1} Lember, Jüri i Alexey Koloydenko. „Dostosowano trening Viterbi dla ukrytych modeli Markowa”. Bernoulli 14, no. 1 (2008): 180–206.
• {2} 6.047 / 6.878 Biologia obliczeniowa: genomy, sieci, ewolucja (jesień 2012 r.) Wykład 07 - HMM II (2012-09-29) http://stellar.mit.edu/S/course/6/fa12/6.047/ courseMaterial / topics / topic2 / lectureNotes / Lecture07_HMMsIIb_6up / Lecture07_HMMsIIb_6up.pdf (Manolis Kellis):

Odpowiedź Morata jest fałszywa w jednym punkcie: Baum-Welch jest algorytmem Expectation-Maximization, używanym do szkolenia parametrów HMM. To wykorzystuje algorytm przód-tył podczas każdej iteracji. Algorytm do przodu i do tyłu jest tak naprawdę kombinacją algorytmów do przodu i do tyłu: jedno przejście do przodu, jedno przejście do tyłu. Sam algorytm przewijania do przodu nie jest wykorzystywany do uczenia parametrów HMM, lecz jedynie do wygładzania: obliczania marginalnych prawdopodobieństw sekwencji stanów.

https://en.wikipedia.org/wiki/Forward%E2%80%93backward_algorithm

https://en.wikipedia.org/wiki/Baum%E2%80%93Welch_algorithm

@Yaroslav Bulatov miał dokładną odpowiedź. Dodałbym jeden przykład tego, żeby powiedzieć różnice między algorytmami do przodu i do tyłu i algorytmami Viterbi.

Załóżmy, że mamy ten HMM (ze strony Wikipedii HMM). Uwaga: model jest już podany, więc nie ma tutaj uczenia się na podstawie zadania danych.

Załóżmy, że nasze dane to sekwencja o długości 4. (Walk, Shop, Walk, Clean). Dwa algorytmy dają różne rzeczy.

• Algorytm przewijania do tyłu poda prawdopodobieństwo każdego z ukrytych stanów . Oto przykład. Uwaga: każda kolumna w tabeli sumuje się do .$1$

• Algorytm Viterbi da najbardziej prawdopodobną sekwencję stanów ukrytych . Oto przykład. Uwaga: istnieje również prawdopodobieństwo związane z tą sekwencją stanu ukrytego. Ta sekwencja ma max prob. nad wszystkimi innymi sekwencjami (np. sekwencji od wszystkich do wszystkich ).$2^4=16$SunnyRainy

Oto Rkod dla wersji demonstracyjnej

library(HMM)
# in education setting,
# hidden state: Rainy and Sunny
# observation: Walk, Shop, Clean

# state transition
P <- as.matrix(rbind(c(0.7,0.3),
                     c(0.4,0.6)))

# emission prob
R <- as.matrix(rbind(c(0.1, 0.4, 0.5),
                     c(0.6,0.3, 0.1)))


hmm = initHMM(States=c("Rainy","Sunny"),
              Symbols=c("Walk","Shop", "Clean"),
              startProbs=c(0.6,0.4),
              transProbs=P,
              emissionProbs=R)
hmm


obs=c("Walk","Shop","Walk", "Clean")
print(posterior(hmm,obs))
print(viterbi(hmm, obs))