Wat is het verschil tussen de vooruit-achteruit- en Viterbi-algoritmen?

Eerst een beetje achtergrond, misschien maakt het dingen duidelijk een beetje.

Als we het hebben over HMMs (Hidden Markov-modellen), zijn er over het algemeen 3 problemen waarmee rekening moet worden gehouden:

1. Evaluatieprobleem

   • Evaluatieprobleem beantwoordt de vraag: wat is de kans dat een bepaalde reeks symbolen wordt geproduceerd door een bepaald model?
   • Voor evaluatie gebruiken we twee algoritmen: het vooruit-algoritme of het achteruit-algoritme (verwar ze NIET met het vooruit-achteruit-algoritme).

2. Decoderingsprobleem

   • Decoderingsprobleem beantwoordt de vraag: Gegeven een reeks symbolen (uw waarnemingen) en een model, wat is de meest waarschijnlijke reeks toestanden die de reeks produceerde.
   • Voor het decoderen gebruiken we het Viterbi-algoritme .

3. Trainingsprobleem

   • Trainingsprobleem beantwoordt de vraag: Gegeven een modelstructuur en een reeks sequenties, zoek het model dat het beste bij de gegevens past .
   • Voor dit probleem kunnen we de volgende 3 algoritmen gebruiken:
     1. MLE (maximale waarschijnlijkheidsschatting)
     2. Viterbi-training (NIET verwarren met Viterbi-decodering)
     3. Baum Welch = vooruit-achteruit-algoritme

Samenvattend gebruikt u het Viterbi-algoritme voor de decoderingsprobleem en Baum Welch / Vooruit-achteruit wanneer u uw model traint op een reeks reeksen.

Baum Welch werkt op de volgende manier.

Voor elke reeks in de trainingsreeks met reeksen.

1. Bereken voorwaartse kansen met het voorwaartse algoritme
2. Bereken achterwaartse kansen met het achterwaartse algoritme
3. Bereken de bijdragen van de huidige reeks aan de overgangen van het model, bereken de bijdragen van de huidige reeks aan de emissiekansen van het model.
4. Bereken de nieuwe modelparameters (startkansen, overgangskansen, emissiekansen )
5. Bereken de nieuwe log-waarschijnlijkheid van het model
6. Stop wanneer de verandering in log-waarschijnlijkheid kleiner is dan een bepaalde drempel of wanneer een maximum aantal iteraties is verstreken.

Als u een volledige beschrijving van de vergelijkingen voor Viterbi-decodering en het trainingsalgoritme, laat het me weten en ik kan je in de goede richting wijzen.

Opmerkingen

• Hallo . Als we het pad opslaan tijdens evaluatie met behulp van een voorwaarts algoritme, maakt het dan het gebruik van het Viterbi-algoritme bij het decoderen overbodig?

Ik vind deze twee volgende dias van {2} echt goed om de voorwaartse -backward en Viterbi-algoritmen naast alle andere typische algoritmen die worden gebruikt met HMM:

Opmerkingen :

• $ x $ is de waargenomen emissie (s), $ \ pi $ zijn de parameters van de HMM.
• pad = een opeenvolging van emissies
• decodering = inferentie
• leren = training = parameterschatting
• Sommige artikelen (bijv. {1}) beweren dat Baum-Welch hetzelfde is als een vooruit-achteruit algoritme, maar Ik agr ee met Masterfool en Wikipedia: Baum-Welch is een verwachtingsmaximalisatie-algoritme dat het vooruit-achteruit-algoritme gebruikt. De twee illustraties onderscheiden Baum-Welch ook van het vooruit-achteruit-algoritme.

Referenties:

• {1} Lember, Jüri en Alexey Koloydenko. “De aangepaste Viterbi-training voor verborgen Markov-modellen.” Bernoulli 14, nee. 1 (2008): 180-206.
• {2} 6.047 / 6.878 Computational Biology: Genomes, Networks, Evolution (Fall 2012) Lezing 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 antwoord is op één punt fout: Baum -Welch is een verwachtingsmaximalisatie-algoritme, dat wordt gebruikt om de parameters van een HMM te trainen. Het gebruikt het vooruit-achteruit-algoritme tijdens elke iteratie. Het vooruit-achteruit-algoritme is eigenlijk slechts een combinatie van de voorwaartse en achterwaartse algoritmen: één voorwaartse pas, één achterwaartse pas. Op zichzelf wordt het vooruit-achteruit-algoritme niet gebruikt voor het trainen van de parameters van een HMM, maar alleen voor het afvlakken: het berekenen van de marginale waarschijnlijkheden van een reeks toestanden.

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

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

@Yaroslav Bulatov had een precies antwoord. Ik zou er een voorbeeld van willen toevoegen om de verschillen tussen vooruit-achteruit- en Viterbi-algoritmen.

Stel dat we een deze HMM hebben (van Wikipedia HMM-pagina). Opmerking: het model is al gegeven, dus hier wordt niet geleerd van de gegevenstaak.

Stel dat onze gegevens een reeks van lengte 4 hebben. (Walk, Shop, Walk, Clean). Twee algoritmen geven verschillende dingen.

• Vooruit achteruit algoritme geeft de probabi lity van elke verborgen toestand . Hier is een voorbeeld. Let op: elke kolom in de tabel is $ 1 $.

• Het Viterbi-algoritme geeft de meest waarschijnlijke opeenvolging van verborgen toestanden . Hier is een voorbeeld. Merk op dat er ook een waarschijnlijkheid is verbonden aan deze verborgen toestandsvolgorde. Deze reeks heeft max. Prob. over alle andere reeksen (bijv. $ 2 ^ 4 = 16 $ reeksen van alle Sunny tot alle Rainy).

Hier is wat R code voor de 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))