Jaký je rozdíl mezi algoritmy vpřed-vzad a Viterbi?

Trochu pozadí nejdříve to možná vyjasní trochu.

Když mluvíme o HMM (Hidden Markov Models), je třeba vzít v úvahu 3 problémy:

1. Problém s hodnocením

   • Problém s hodnocením odpovídá na otázku: jaká je pravděpodobnost, že určitý sled symbolů bude vytvořen konkrétním modelem?
   • Pro vyhodnocení používáme dva algoritmy: dopředný algoritmus nebo zpětný algoritmus (NEPOUŽÍVEJTE je s algoritmem dopředu-dozadu).

2. Problém s dekódováním

   • Problém s dekódováním odpovídá na otázku: Vzhledem k posloupnosti symbolů (vaše pozorování) a modelu, jaká je nejpravděpodobnější posloupnost stavů, které sekvenci vytvořily.
   • K dekódování používáme Viterbiho algoritmus .

3. Školicí problém

   • Školicí problém odpovídá na otázku: Vzhledem k modelové struktuře a sadě sekvencí najděte model, který nejlépe vyhovuje datům .
   • K tomuto problému můžeme použít následující 3 algoritmy:
     1. MLE (odhad maximální pravděpodobnosti)
     2. trénink Viterbi (NEPLATIT s dekódováním Viterbi)
     3. Baum Welch = algoritmus dopředu-dozadu

Abychom to shrnuli, použijeme pro Viterbiho algoritmus problém s dekódováním a Baum Welch / Forward-backward, když trénujete model na sadě sekvencí.

Baum Welch funguje následujícím způsobem.

Pro každou sekvenci v tréninkové sadě sekvencí.

1. Vypočítejte pravděpodobnosti dopředu pomocí algoritmu dopředu
2. Vypočítejte zpětné pravděpodobnosti pomocí algoritmu dozadu
3. Vypočítejte příspěvky aktuální sekvence k přechodům modelu, vypočítejte příspěvky aktuální sekvence k emisním pravděpodobnostem modelu.
4. Vypočítejte nové parametry modelu (pravděpodobnosti spuštění, pravděpodobnosti přechodu, pravděpodobnosti emisí) )
5. Vypočítejte nová logaritmická pravděpodobnost modelu
6. Zastavit, když je změna logaritmické pravděpodobnosti menší než zadaná prahová hodnota nebo když je předán maximální počet iterací.

Pokud potřebujete úplný popis rovnic pro Viterbiho dekódování a tréninkový algoritmus, dejte mi vědět a já vás mohu nasměrovat správným směrem.

Komentáře

• Ahoj . Pokud cestu během vyhodnocení pomocí dopředného algoritmu uložíme, učiní použití algoritmu Viterbi při dekódování nadbytečným?

Tyto dva následující snímky z {2} považuji za dobré umístit dopředu -backward a Viterbiho algoritmy mezi všemi ostatními typickými algoritmy používanými s HMM:

Poznámky :

• $ x $ jsou pozorované emise, $ \ pi $ jsou parametry HMM.
• path = posloupnost emisí
• dekódování = odvození
• učení = trénink = odhad parametrů
• Některé články (např. {1}) tvrdí, že Baum – Welch je stejný jako algoritmus vpřed – vzad, ale Agr ee s Masterfool a Wikipedia: Baum – Welch je algoritmus maximalizace očekávání, který používá algoritmus vpřed – vzad. Tyto dvě ilustrace také odlišují Baum – Welcha od algoritmu dopředu – dozadu.

Odkazy:

• {1} Lember, Jüri a Alexey Koloydenko. „Upravený výcvik Viterbi pro skryté Markovovy modely.“ Bernoulli 14, č. 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):

Moratova odpověď je v jednom bodě nepravdivá: Baum -Welch je algoritmus Expectation-Maximization, který se používá k trénování parametrů HMM. používá během každé iterace algoritmus dopředu-dozadu. Algoritmus dopředu a dozadu je ve skutečnosti jen kombinací algoritmů dopředu a dozadu: jeden dopředný průchod, jeden zpětný průchod. Samotný algoritmus dopředu a dozadu se nepoužívá k trénování parametrů HMM, ale pouze k vyhlazení: výpočtu mezních pravděpodobností posloupnosti stavů.

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

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

@Yaroslav Bulatov měl přesnou odpověď. Přidal bych jeden její příklad, abych řekl rozdíly mezi dopředu a dozadu a Viterbiho algoritmy.

Předpokládejme, že máme tento HMM (ze stránky HMM na Wikipedii). Model je již uveden, takže zde se nelze z datového úkolu učit.

Předpokládejme, že naše data jsou sekvence délky 4. (Walk, Shop, Walk, Clean). Dva algoritmy poskytnou různé věci.

• Algoritmus dopředu dozadu poskytne probabi množství jednotlivých skrytých stavů . Zde je příklad. Každý sloupec v tabulce má součet až 1 $.

• Algoritmus Viterbi poskytne nejpravděpodobnější posloupnost skrytých stavů . Zde je příklad. Všimněte si, že s touto sekvencí skrytého stavu je také spojena pravděpodobnost. Tato sekvence má max. přes všechny ostatní sekvence (např. $ 2 ^ 4 = 16 $ sekvence ze všech Sunny do všech Rainy).

Zde je několik R kód ukázky

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