Vad är skillnaden mellan framåt-bakåt och Viterbi-algoritmerna?

Lite bakgrund först kanske det rensar upp saker och ting lite.

När vi pratar om HMM: er (dolda Markov-modeller) finns det i allmänhet tre problem att tänka på:

1. Utvärderingsproblem

   • Utvärderingsproblem svarar på frågan: vad är sannolikheten att en viss symbolsekvens produceras av en viss modell?
   • För utvärdering använder vi två algoritmer: framåt-algoritmen eller bakåt-algoritmen (Förväxla dem INTE med framåt-bakåt-algoritmen).

2. Avkodningsproblem

   • Avkodningsproblem svarar på frågan: Med tanke på en sekvens av symboler (dina observationer) och en modell, vad är den mest troliga sekvensen av tillstånd som producerade sekvensen.
   • För avkodning använder vi Viterbi-algoritmen .

3. Träningsproblem

   • Träningsproblem svarar på frågan: Med tanke på en modellstruktur och en uppsättning sekvenser, hitta den modell som bäst passar data .
   • För detta problem kan vi använda följande tre algoritmer:
     1. MLE (maximal sannolikhetsuppskattning)
     2. Viterbi-träning (Förväxla INTE med Viterbi-avkodning)
     3. Baum Welch = bakåt-algoritm

För att sammanfatta det använder du Viterbi-algoritmen för avkodningsproblem och Baum Welch / Framåt-bakåt när du tränar din modell på en uppsättning sekvenser.

Baum Welch fungerar på följande sätt.

För varje sekvens i träningssatsen med sekvenser.

1. Beräkna framåt-sannolikheter med framåt-algoritmen
2. Beräkna bakåt-sannolikheter med bakåt-algoritmen
3. Beräkna bidrag från den aktuella sekvensen till modellens övergångar, beräkna bidrag från den aktuella sekvensen till modellens utsläppssannolikheter. )
4. Beräkna ny logg sannolikhet för modellen
5. Stoppa när förändringen i logg sannolikheten är mindre än en viss tröskel eller när ett maximalt antal iterationer passeras.

Om du behöver en fullständig beskrivning av ekvationerna för Viterbi-avkodning och träningsalgoritmen berätta för mig och jag kan peka dig i rätt riktning.

Kommentarer

• Hej . Om vi sparar vägen, under utvärderingen med framåtalgoritm, gör det användningen av Viterbi-algoritmen för avkodning överflödig?

Jag tycker att dessa två följande bilder från {2} är riktigt bra att placera framåt -backward och Viterbi-algoritmer bland alla andra typiska algoritmer som används med HMM:

Anteckningar :

• $ x $ är de observerade utsläppen, $ \ pi $ är parametrarna för HMM.
• sökväg = en sekvens av utsläpp
• avkodning = inferens
• learning = training = parameteruppskattning
• Vissa papper (t.ex. {1}) hävdar att Baum – Welch är samma som framåt-bakåt-algoritm, men Jag agr ee med Masterfool och Wikipedia: Baum – Welch är en förväntningsmaximeringsalgoritm som använder framåt – bakåt-algoritmen. De två illustrationerna skiljer också Baum – Welch från framåt – bakåt-algoritmen.

Referenser:

• {1} Lember, Jüri och Alexey Koloydenko. ”Den justerade Viterbi-träningen för dolda Markov-modeller.” Bernoulli 14, nr. 1 (2008): 180-206.
• {2} 6.047 / 6.878 Computational Biology: Genomes, Networks, Evolution (Fall 2012) Lecture 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):

Morats svar är falskt på en punkt: Baum -Welch är en förväntningsmaximeringsalgoritm som används för att träna en HMM-parameter. Den använder framåt-bakåt-algoritmen under varje iteration. Framåt-bakåt-algoritmen är egentligen bara en kombination av framåt- och bakåt-algoritmerna: ett framåtpass, ett bakåtpass. På egen hand används inte framåt-bakåt-algoritmen för träning av HMM: s parametrar, utan bara för utjämning: beräkning av marginal sannolikheter för en sekvens av tillstånd.

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

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

@ Yaroslav Bulatov hade ett exakt svar. Jag skulle lägga till ett exempel på det för att berätta för skillnader mellan framåt-bakåt och Viterbi-algoritmer.

Antag att vi har denna HMM (från Wikipedia HMM-sida). Obs! Modellen är redan angiven, så det går inte att lära av datauppgiften här.

Antag att våra data är en längd 4-sekvens. (Walk, Shop, Walk, Clean). Två algoritmer ger olika saker.

• Framåt-bakåt-algoritm ger probabi lity av varje dolda tillstånd . Här är ett exempel. Observera att varje kolumn i tabellen uppgår till $ 1 $.

• Viterbi-algoritmen ger mest sannolika sekvens av dolda tillstånd . Här är ett exempel. Obs! Det finns också en sannolikhet associerad med denna dolda tillståndssekvens. Denna sekvens har max prob. över alla andra sekvenser (t.ex. $ 2 ^ 4 = 16 $ sekvenser från alla Sunny till alla Rainy).

Här är några R kod för demo

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