Mi a különbség az előre-hátra és a Viterbi algoritmusok között?

Először egy kis háttér, talán tisztázza a dolgokat egy kicsit.

Ha HMM-ekről (Rejtett Markov modellek) beszélünk, általában 3 problémát kell figyelembe venni:

2. Az értékeléshez két algoritmust használunk: a előre algoritmust vagy a visszafelé algoritmust (NE keverd össze őket a előre-hátra algoritmussal).

3. Dekódolási probléma

   • A dekódolási probléma megválaszolja a kérdést: Adott egy szimbólumsorozat (a megfigyelések) és egy modell, mi a legvalószínűbb állapotsorozat, amely előállította a szekvenciát.
   • A dekódoláshoz a Viterbi algoritmust használjuk.

4. Képzési probléma

   • Az edzésprobléma megválaszolja a kérdést: Adott egy modell felépítése és egy sor szekvencia, keresse meg az adatoknak leginkább megfelelő modellt .
   • Ehhez a problémához a következő 3 algoritmust használhatjuk:
     1. MLE (maximális valószínűség becslés)
     2. Viterbi edzés (NE keverd össze Viterbi dekódolással)
     3. Baum Welch = előre-hátra algoritmus

Összefoglalva a Viterbi algoritmust használja a dekódolási probléma és Baum Welch / Forward-backward, amikor a modellt egy sor sorozatra edzi.

Baum Welch a következő módon működik.

A szekvenciák edzéskészletének minden szekvenciájához.

1. Számítsa az előrejelzési valószínűségeket a továbbítási algoritmussal
2. A visszafelé eső valószínűségeket a visszalépéses algoritmussal számolja ki
3. Számítsa ki az aktuális szekvencia hozzájárulását a modell átmeneteihez, számítsa ki az aktuális szekvencia hozzájárulását a modell emissziós valószínűségeihez.
4. Számolja ki az új modell paramétereit (kezdési valószínűségek, átmenet valószínűségek, emissziós valószínűségek) )
5. Számítsa ki a a modell új napló valószínűsége
6. akkor állítsa le, ha a napló valószínűségének változása kisebb, mint egy adott küszöb, vagy ha az iterációk maximális száma megtörténik.

Ha szüksége van a Viterbi dekódolás egyenleteinek teljes leírása és a képzési algoritmus tudatja velem, és jó irányba terelhetem.

Megjegyzések

• Szia . Ha elmentjük az útvonalat, az előre algoritmus használatával végzett értékelés során feleslegessé teszi a Viterbi algoritmus dekódolásban való használatát?

Az előre-hátra marginális valószínűséget ad minden egyedi állapot ra, a Viterbi pedig a legvalószínűbb állapotok sorozatának valószínűségét. Például, ha a HMM feladata a napos és az esős idő előrejelzése minden napra, a Forward Backward megmondja annak valószínűségét, hogy minden nap “napos” lesz, a Viterbi megadja a legvalószínűbb napos / esős napok sorrendjét, és ennek a sorrendnek a valószínűsége.

Ezt a két következő diát {2} -ból nagyon jónak találom az előre helyezéshez -backward és Viterbi algoritmusok a HMM-mel együtt használt összes többi tipikus algoritmus között:

Megjegyzések :

• $ x $ a megfigyelt kibocsátás (ok), $ \ pi $ a HMM paraméterei.
• path = kibocsátássorozat
• dekódolás = következtetés
• tanulás = tréning = paraméter becslés
• Egyes cikkek (pl. {1}) azt állítják, hogy Baum – Welch ugyanaz, mint az előre-hátra algoritmus, de I agr ee a Masterfool és a Wikipedia segítségével: A Baum – Welch egy várakozás-maximalizáló algoritmus, amely az előre-hátra algoritmust használja. A két illusztráció megkülönbözteti Baum – Welch-t az előre-hátra algoritmustól.

Hivatkozások:

• {1} Lember, Jüri és Alexey Koloydenko. “A korrigált Viterbi edzés rejtett Markov modellek számára.” Bernoulli 14, sz. 1 (2008): 180-206.
• {2} 6.047 / 6.878 Számítási biológia: Genomok, hálózatok, evolúció (2012. ősz) 07. előadás – 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):

Morat válasza egy ponton hamis: Baum A -Welch egy Expectation-Maximization algoritmus, amelyet egy HMM paramétereinek képzésére használnak. Minden iteráció során használja a előre-hátra algoritmust. Az előre-hátra algoritmus valójában csak az előre és hátra algoritmus kombinációja: egy előre, egy vissza. Önmagában az előre-hátra algoritmust nem a HMM paramétereinek kiképzésére használják, hanem csak a simításra: egy állapotsorozat marginális valószínűségének kiszámításához.

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

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

@ Jaroslav Bulatov pontos választ adott. Hozzátennék egy példát, hogy elmondjam különbségek az előre-hátra és a Viterbi algoritmusok között.

Tegyük fel, hogy van egy ilyen HMM (a Wikipedia HMM oldaláról). Megjegyzés: a modell már meg van adva, tehát itt nem lehet tanulni az adatfeladatból.

Tegyük fel, hogy adataink egy 4 hosszúságú szekvencia. (Walk, Shop, Walk, Clean). Két algoritmus különböző dolgokat ad meg.

• A visszafelé irányuló algoritmus megadja a probabit az egyes rejtett állapotok állapota. Itt egy példa. Ne feledje, hogy a táblázat minden oszlopának összege $ 1 $.

• A Viterbi algoritmus a rejtett állapotok legvalószínűbb szekvenciáját adja . Itt egy példa. Megjegyezzük, hogy van egy valószínűség is ehhez a rejtett állapot-szekvenciához. Ennek a sorozatnak max probja van. az összes többi szekvencia felett (pl. $ 2 ^ 4 = 16 $ szekvencia az összes Sunny -től az összes Rainy -ig).

Íme néhány R a bemutató kód

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))