Care este diferența dintre algoritmii înainte-înapoi și algoritmii Viterbi?

Mai întâi un pic de fundal, poate clarifică lucrurile un pic.

Când vorbim despre HMM-uri (modele ascunse Markov), în general, trebuie luate în considerare 3 probleme:

1. Problema de evaluare

   • Problema de evaluare răspunde la întrebarea: care este probabilitatea ca o anumită secvență de simboluri să fie produsă de un anumit model?
   • Pentru evaluare, utilizăm doi algoritmi: algoritmul înainte sau algoritmul invers (NU le confundați cu algoritmul înainte-înapoi).

2. Problemă de decodare

   • Problema de decodare răspunde la întrebarea: Având în vedere o secvență de simboluri (observațiile dvs.) și un model, care este cea mai probabilă secvență de stări care a produs secvența.
   • Pentru decodare folosim algoritmul Viterbi .

3. Problemă de antrenament

   • Problemă de antrenament răspunde la întrebarea: Având în vedere o structură de model și un set de secvențe, găsiți modelul care se potrivește cel mai bine cu datele .
   • Pentru această problemă putem folosi următorii 3 algoritmi:
     1. MLE (estimare maximă a probabilității)
     2. Instruire Viterbi (NU confundați cu decodarea Viterbi)
     3. Baum Welch = algoritm înainte-înapoi

Pentru a rezuma, utilizați algoritmul Viterbi pentru problemă de decodare și Baum Welch / Forward-backward când vă antrenați modelul pe un set de secvențe.

Baum Welch funcționează în felul următor.

Pentru fiecare secvență din setul de secvențe de antrenament.

1. Calculați probabilitățile înainte cu algoritmul direct
2. Calculați probabilitățile înapoi cu algoritmul înapoi
3. Calculați contribuțiile secvenței curente la tranzițiile modelului, calculați contribuțiile secvenței curente la probabilitățile de emisie ale modelului.
4. Calculați noii parametri ai modelului (probabilități de pornire, probabilități de tranziție, probabilități de emisie) )
5. Calculați noua probabilitate a jurnalului modelului
6. Opriți-vă când modificarea probabilității jurnalului este mai mică decât un prag dat sau când este trecut un număr maxim de iterații.

Dacă aveți nevoie o descriere completă a ecuațiilor pentru decodarea Viterbi și a algoritmului de antrenament anunțați-mă și vă pot indica în direcția corectă.

Comentarii

• Bună ziua . Dacă salvăm calea, în timpul evaluării folosind algoritmul de redirecționare, utilizează algoritmul Viterbi în decodarea redundantă?

Înainte-înapoi oferă o probabilitate marginală pentru fiecare stare individuală , Viterbi oferă probabilitatea secvenței de stări cea mai probabilă. De exemplu, dacă sarcina dvs. HMM este de a prezice vremea însorită față de cea ploioasă pentru fiecare zi, Forward Backward vă va spune probabilitatea ca acesta să fie „însorit” pentru fiecare zi, Viterbi va da secvența cea mai probabilă de zile însorite / ploioase, probabilitatea acestei secvențe.

Consider că aceste două diapozitive următoare din {2} sunt foarte bune pentru a situa înainte -înapoi și algoritmi Viterbi printre toți ceilalți algoritmi tipici utilizați cu HMM:

Note :

• $ x $ reprezintă emisiile observate, $ \ pi $ sunt parametrii HMM.
• cale = o succesiune de emisii
• decodare = inferență
• învățare = instruire = estimarea parametrilor
• Unele lucrări (de exemplu, {1}) susțin că Baum – Welch este același cu algoritmul înainte-înapoi, dar Eu agr Cu Masterfool și Wikipedia: Baum – Welch este un algoritm de maximizare a așteptărilor care folosește algoritmul înainte-înapoi. Cele două ilustrații disting, de asemenea, Baum-Welch de algoritmul înainte-înapoi.

Referințe:

• {1} Lember, Jüri și Alexey Koloydenko. „Antrenamentul Viterbi ajustat pentru modelele ascunse Markov.” 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):

Răspunsul lui Morat este fals într-un punct: Baum -Welch este un algoritm de așteptare-maximizare, folosit pentru a instrui parametrii unui HMM. folosește algoritmul înainte-înapoi în timpul fiecărei iterații. Algoritmul înainte-înapoi este într-adevăr doar o combinație a algoritmilor înainte și înapoi: o trecere înainte, o trecere înapoi. Singur, algoritmul înainte-înapoi nu este utilizat pentru instruirea parametrilor unui HMM, ci doar pentru netezire: calculând probabilitățile marginale ale unei secvențe de stări.

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

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

@Yaroslav Bulatov a avut un răspuns precis. Aș adăuga un exemplu pentru a spune diferențele dintre algoritmii înainte-înapoi și algoritmii Viterbi.

Să presupunem că avem acest HMM (din pagina HMM Wikipedia). Notă, modelul este deja dat, deci nu există nicio învățare din sarcina de date aici.

Să presupunem că datele noastre sunt o secvență de lungime 4. (Walk, Shop, Walk, Clean). Doi algoritmi vor da lucruri diferite.

• Algoritmul invers înapoi va da probabi litatea fiecărei stări ascunse . Iată un exemplu. Rețineți, fiecare coloană din tabel însumează până la $ 1.

• Algoritmul Viterbi va da cea mai probabilă secvență de stări ascunse . Iată un exemplu. Rețineți, există, de asemenea, o probabilitate asociată cu această secvență de stare ascunsă. Această secvență are prob max. peste toate celelalte secvențe (de exemplu, $ 2 ^ 4 = 16 $ secvențe de la toate Sunny la toate Rainy).

Iată câteva R cod pentru demonstrație

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