Hvad er forskellen mellem fremad-baglæns og Viterbi algoritmer?

Lidt baggrund først måske rydder det op lidt.

Når vi taler om HMMer (skjulte Markov-modeller), er der generelt tre problemer, der skal overvejes:

1. Evalueringsproblem

   • Evalueringsproblem svarer på spørgsmålet: hvad er sandsynligheden for, at en bestemt sekvens af symboler produceres af en bestemt model?
   • Til evaluering bruger vi to algoritmer: algoritmen fremad eller algoritmen bagud (IKKE forveksle dem med algoritmen fremad og bagud).

2. Afkodningsproblem

   • Afkodningsproblem besvarer spørgsmålet: Hvad er en række symboler (dine observationer) og en model, hvad er den mest sandsynlige rækkefølge af tilstande, der producerede sekvensen.
   • Til afkodning bruger vi Viterbi-algoritmen .

3. Træningsproblem

   • Træningsproblem besvarer spørgsmålet: Givet en modelstruktur og et sæt sekvenser, find den model, der passer bedst til dataene .
   • Til dette problem kan vi bruge følgende 3 algoritmer:
     1. MLE (maksimal sandsynlighedsestimering)
     2. Viterbi-træning (IKKE forveksles med Viterbi-afkodning)
     3. Baum Welch = fremadrettet algoritme

For at opsummere det bruger du Viterbi-algoritmen til afkodningsproblem og Baum Welch / Fremad-bagud, når du træner din model i et sæt sekvenser.

Baum Welch fungerer på følgende måde.

For hver sekvens i træningssættet med sekvenser.

1. Beregn fremover sandsynligheder med den fremadgående algoritme
2. Beregn bagud sandsynligheder med den bagudgående algoritme
3. Beregn bidragene fra den aktuelle sekvens til modelens overgange, beregn bidragene fra den aktuelle sekvens til emissionens sandsynligheder for modellen.
4. Beregn de nye modelparametre (start sandsynligheder, overgangssandsynligheder, emissionssandsynligheder )
5. Beregn ny logsandsynlighed for modellen
6. Stop, når ændringen i logsandsynligheden er mindre end en given tærskel, eller når et maksimalt antal iterationer er bestået.

Hvis du har brug for en komplet beskrivelse af ligningerne til Viterbi-afkodning og træningsalgoritmen, så lad mig det vide, og jeg kan pege dig i den rigtige retning.

Kommentarer

• Hej . Hvis vi gemmer stien under evaluering ved hjælp af fremad-algoritme, gør den brugen af Viterbi-algoritme til afkodning overflødig?

Jeg finder disse to følgende dias fra {2} for at være rigtig god til at placere fremad -backward og Viterbi algoritmer blandt alle andre typiske algoritmer, der bruges med HMM:

Noter :

• $ x $ er den observerede emission (er), $ \ pi $ er parametrene for HMM.
• path = en sekvens af emissioner
• afkodning = slutning
• learning = træning = parameterestimering
• Nogle papirer (f.eks. {1}) hævder, at Baum – Welch er den samme som fremad-bagud-algoritme, men Jeg agr ee med Masterfool og Wikipedia: Baum – Welch er en forventnings-maksimeringsalgoritme, der bruger fremad-bagud-algoritmen. De to illustrationer skelner også Baum – Welch fra fremad-bagud algoritmen.

Referencer:

• {1} Lember, Jüri og Alexey Koloydenko. “Den justerede Viterbi-træning til skjulte 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 er falsk på et punkt: Baum -Welch er en forventnings-maksimeringsalgoritme, der bruges til at træne en HMMs parametre. Det bruger fremad-bagud-algoritmen under hver iteration. Den fremad-bagud-algoritme er virkelig bare en kombination af fremad- og bagud-algoritmerne: et fremadgående, et baglæns pass. For sig selv bruges fremad-bagud-algoritmen ikke til træning af HMM-parametre, men kun til udjævning: beregning af marginal sandsynligheden for en sekvens af tilstande.

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

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

@ Yaroslav Bulatov havde et præcist svar. Jeg vil tilføje et eksempel på det for at fortælle forskelle mellem fremad-bagud og Viterbi-algoritmer.

Antag, at vi har denne HMM (fra Wikipedia HMM-side). Bemærk, modellen er allerede givet, så der læres ikke af dataopgaven her.

Antag at vores data er en længde 4 sekvens. (Walk, Shop, Walk, Clean). To algoritmer giver forskellige ting.

• Fremad bagud algoritme giver probabi lity af hver skjulte tilstand . Her er et eksempel. Bemærk, hver kolonne i tabellen summerer sig til $ 1 $.

• Viterbi-algoritmen giver mest sandsynlige rækkefølge af skjulte tilstande . Her er et eksempel. Bemærk, at der også er en sandsynlighed forbundet med denne skjulte tilstandssekvens. Denne sekvens har maks. Prob. over alle andre sekvenser (f.eks. $ 2 ^ 4 = 16 $ sekvenser fra alle Sunny til alle Rainy).

Her er nogle R kode til 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))