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

Odpowiedzi:

65

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.

Morat
źródło
24

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.

Jarosław Bułatow
źródło
15

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:

wprowadź opis zdjęcia tutaj

wprowadź opis zdjęcia tutaj

Uwagi:

  • πx to obserwowana emisja (emisje), to parametry HMM.π
  • ś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:

Franck Dernoncourt
źródło
12

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

Masterfool
źródło
2

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

wprowadź opis zdjęcia tutaj


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

wprowadź opis zdjęcia tutaj

  • 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 ).24=16SunnyRainy

wprowadź opis zdjęcia tutaj


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))
Haitao Du
źródło