Jaka jest różnica między algorytmem do przodu i do tyłu a algorytmem Viterbiego?

Może to trochę wyjaśnienia. trochę.

Mówiąc o HMM (ukrytych modelach Markowa) należy wziąć pod uwagę ogólnie 3 problemy:

1. Problem z oceną

   • Problem z oceną odpowiada na pytanie: jakie jest prawdopodobieństwo, że określona sekwencja symboli jest wytwarzana przez określony model?
   • Do oceny używamy dwóch algorytmów: algorytmu do przodu lub algorytmu do tyłu (NIE myl ich z algorytmem do przodu-do tyłu).

2. Problem z dekodowaniem

   • Problem dekodowania odpowiada na pytanie: Biorąc pod uwagę sekwencję symboli (twoje obserwacje) i model, jaka jest najbardziej prawdopodobna sekwencja stanów, która utworzyła sekwencję.
   • Do dekodowania używamy algorytmu Viterbiego .

3. Problem szkoleniowy

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

Podsumowując, używasz algorytmu Viterbiego do problem z dekodowaniem i Baum Welch / Forward-backward, gdy trenujesz model na zbiorze sekwencji.

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

Dla każdej sekwencji w zbiorze uczącym sekwencji.

1. Oblicz prawdopodobieństwa do przodu za pomocą algorytmu do przodu
2. Oblicz prawdopodobieństwa wsteczne za pomocą algorytmu do przodu
3. Oblicz udział bieżącej sekwencji w przejściach modelu, oblicz udział bieżącej sekwencji w prawdopodobieństwie emisji modelu.
4. Oblicz nowe parametry modelu (prawdopodobieństwa rozpoczęcia, prawdopodobieństwa przejścia, prawdopodobieństwa emisji )
5. Oblicz prawdopodobieństwo nowego dziennika modelu
6. Zatrzymaj, gdy zmiana w prawdopodobieństwie dziennika jest mniejsza niż podany próg lub gdy zostanie przekroczona maksymalna liczba iteracji.

Jeśli potrzebujesz pełny opis równań dekodowania Viterbiego i algorytmu uczącego daj mi znać, a wskażę ci właściwy kierunek.

Komentarze

• Cześć . Jeśli zapiszemy ścieżkę, podczas oceny za pomocą algorytmu do przodu, czy użycie algorytmu Viterbiego w dekodowaniu będzie zbędne?

Do przodu-do tyłu podaje marginalne prawdopodobieństwo dla każdego indywidualnego stanu , a Viterbi podaje prawdopodobieństwo najbardziej prawdopodobnej sekwencji stanów . Na przykład, jeśli twoim zadaniem HMM jest przewidywanie słonecznej i deszczowej pogody na każdy dzień, Forward Backward wskaże Ci prawdopodobieństwo, że będzie „słonecznie” każdego dnia, Viterbi poda najbardziej prawdopodobną sekwencję słonecznych / deszczowych dni, a prawdopodobieństwo wystąpienia tej sekwencji.

Uważam, że te dwa kolejne slajdy z {2} są naprawdę dobre do umiejscowienia – algorytmy do tyłu i Viterbiego spośród wszystkich innych typowych algorytmów używanych z HMM:

Uwagi :

• $ x $ to obserwowane emisje, $ \ pi $ to parametry HMM.
• ścieżka = sekwencja emisji
• decoding = inference
• learning = training = estymacja parametrów
• Niektóre artykuły (np. {1}) twierdzą, że Baum-Welch jest tym samym algorytmem I agr ee z Masterfool i Wikipedia: Baum – Welch to algorytm maksymalizacji oczekiwań, który wykorzystuje algorytm do przodu – do tyłu. Te dwie ilustracje odróżniają również Bauma-Welcha od algorytmu do przodu i do tyłu.

Odniesienia:

• {1} Lember, Jüri i Alexey Kołoydenko. „Dostosowane szkolenie Viterbiego dla ukrytych modeli Markowa”. Bernoulli 14, nie. 1 (2008): 180–206.
• {2} 6.047 / 6.878 Biologia obliczeniowa: genomy, sieci, ewolucja (jesień 2012) Wykład 07 – HMMs 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 to algorytm maksymalizacji oczekiwań, używany do trenowania parametrów HMM. używa algorytmu do przodu i do tyłu podczas każdej iteracji. Algorytm do przodu i do tyłu jest tak naprawdę połączeniem algorytmów do przodu i do tyłu: jedno przejście do przodu, jedno przejście do tyłu. Algorytm naprzód-wstecz nie jest używany samodzielnie do uczenia parametrów HMM, a 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ł precyzyjną odpowiedź. Dodałbym jeden jej przykład, aby powiedzieć różnice między algorytmami forward-back i Viterbi.

Załóżmy, że mamy taki HMM (ze strony Wikipedii HMM). Uwaga, model jest już podany, więc nie ma tu uczenia się na podstawie zadania związanego z danymi.

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

• Algorytm do przodu i do tyłu da probabi lity każdego ukrytego stanu . Oto przykład. Uwaga: suma każdej kolumny w tabeli wynosi 1 USD.

• Algorytm Viterbiego poda 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 maksymalne prawdopodobieństwo. nad wszystkimi innymi sekwencjami (np. $ 2 ^ 4 = 16 $ sekwencje od wszystkich Sunny do wszystkich Rainy).

Oto kilka R kod 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))