Hva er forskjellen mellom fremover-bakover og Viterbi-algoritmene?

Litt bakgrunn først, kanskje det rydder opp i ting litt.

Når vi snakker om HMM (skjulte Markov-modeller), er det generelt tre problemer som skal vurderes:

1. Evalueringsproblem

   • Evalueringsproblem svarer på spørsmålet: hva er sannsynligheten for at en bestemt sekvens av symboler produseres av en bestemt modell?
   • For evaluering bruker vi to algoritmer: fremoveralgoritmen eller bakoveralgoritmen (IKKE forveksle dem med fremover-bakover-algoritmen).

2. Avkodingsproblem

   • Avkodingsproblem svarer på spørsmålet: Gitt en sekvens av symboler (dine observasjoner) og en modell, hva er den mest sannsynlige sekvensen av tilstander som produserte sekvensen.
   • For dekoding bruker vi Viterbi-algoritmen .

3. Treningsproblem

   • Treningsproblemer svarer på spørsmålet: Gitt en modellstruktur og et sett med sekvenser, finn den modellen som passer best til dataene .
   • For dette problemet kan vi bruke følgende 3 algoritmer:
     1. MLE (maksimal sannsynlighetsestimering)
     2. Viterbi-trening (IKKE forveksle med Viterbi-dekoding)
     3. Baum Welch = fremover-bakover-algoritme

For å oppsummere bruker du Viterbi-algoritmen for avkodingsproblem og Baum Welch / Forover-bakover når du trener modellen din på et sett med sekvenser.

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

For hver sekvens i treningssettet med sekvenser.

1. Beregn fremover sannsynligheter med fremoveralgoritmen
2. Beregn bakover sannsynligheter med bakover algoritmen
3. Beregn bidragene til den nåværende sekvensen til overgangene til modellen, beregne bidragene til den nåværende sekvensen til utslippssannsynlighetene til modellen.
4. Beregn de nye modellparametrene (startsannsynligheter, overgangssannsynligheter, utslippssannsynligheter )
5. Beregn ny logg sannsynlighet for modellen
6. Stopp når endringen i logg sannsynligheten er mindre enn en gitt terskel eller når et maksimalt antall iterasjoner er passert.

Hvis du trenger en full beskrivelse av ligningene for Viterbi-dekoding og treningsalgoritmen, gi meg beskjed, og jeg kan peke deg i riktig retning.

Kommentarer

• Hei . Hvis vi lagrer banen, under evaluering ved hjelp av fremoveralgoritme, gjør den bruk av Viterbi-algoritme i avkoding overflødig?

Jeg synes disse to følgende lysbildene fra {2} er veldig bra å plassere fremover -backward og Viterbi algoritmer blant alle andre typiske algoritmer som brukes med HMM:

Merknader :

• $ x $ er det observerte utslippet (e), $ \ pi $ er parametrene til HMM.
• bane = en sekvens av utslipp
• dekoding = slutning
• learning = training = parameterestimering
• Noen papirer (f.eks. {1}) hevder at Baum – Welch er det samme som fremover-bakover-algoritme, men Jeg agr ee med Masterfool og Wikipedia: Baum – Welch er en forventnings-maksimeringsalgoritme som bruker fremover-bakover-algoritmen. De to illustrasjonene skiller også Baum – Welch fra fremover – bakover-algoritmen.

Referanser:

• {1} Lember, Jüri og Alexey Koloydenko. «Den justerte Viterbi-treningen for 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 falskt på ett punkt: Baum -Welch er en forventnings-maksimaliseringsalgoritme, som brukes til å trene parametere for en HMM. Den bruker algoritmen forover-bakover under hver iterasjon. Den fremover-bakover-algoritmen er egentlig bare en kombinasjon av algoritmene forover og bakover: en fremover-passering, en bakover-passering. For seg selv brukes ikke fremover-bakover-algoritmen til å trene en HMM «s parametere, men bare for utjevning: beregning av marginal sannsynligheten for en sekvens av tilstander.

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

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

@ Yaroslav Bulatov hadde et presist svar. Jeg vil legge til et eksempel på det for å fortelle forskjeller mellom fremover og Viterbi-algoritmer.

Anta at vi har denne HMM (fra Wikipedia HMM-side). Merk at modellen allerede er gitt, så det er ingen læring fra dataoppgaven her.

Anta at våre data er en lengde 4 sekvens. (Walk, Shop, Walk, Clean). To algoritmer vil gi forskjellige ting.

• Fremover-bakover-algoritme vil gi probabi lity av hver skjulte tilstand . Her er et eksempel. Merk, hver kolonne i tabellen summerer seg til $ 1 $.

• Viterbi-algoritmen vil gi mest sannsynlige sekvens av skjulte tilstander . Her er et eksempel. Merk at det er også en sannsynlighet knyttet til denne skjulte tilstandssekvensen. Denne sekvensen har maks. over alle andre sekvenser (f.eks. $ 2 ^ 4 = 16 $ sekvenser fra alle Sunny til alle Rainy).

Her er noen R kode for demoen

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