Mitä eroa on eteenpäin-taaksepäin ja Viterbi-algoritmeilla?

Hieman taustaa ensin, ehkä se selvittää asiat vähän.

Kun puhutaan HMM: istä (piilotetut Markov-mallit), on yleensä otettava huomioon kolme ongelmaa:

1. Arviointiongelma

   • Arviointiongelma vastaa kysymykseen: mikä on todennäköisyys, että tietty malli tuottaa tietyn symbolisekvenssin?
   • Arvioinnissa käytämme kahta algoritmia: eteenpäin-algoritmi tai taaksepäin-algoritmi (ÄLÄ sekoita niitä eteenpäin-taaksepäin-algoritmiin).

2. Dekoodausongelma

   • Dekoodausongelma vastaa kysymykseen: Annetaan symbolisekvenssi (havainnot) ja malli, mikä on todennäköisin tilasekvenssi, joka tuotti sekvenssin.
   • Dekoodauksessa käytämme Viterbi-algoritmia .

3. Harjoitusongelma

   • Harjoitusongelma vastaa kysymykseen: Kun otetaan huomioon mallirakenne ja sarja sarjaa, etsi malli, joka parhaiten sopii tietoihin .
   • Tätä ongelmaa varten voidaan käyttää seuraavia 3 algoritmia:
     1. MLE (suurin todennäköisyysarvio)
     2. Viterbi-koulutus (ÄLÄ sekoita Viterbi-dekoodaukseen)
     3. Baum Welch = eteenpäin-taaksepäin-algoritmi

Yhteenvetona voit käyttää Viterbi-algoritmia dekoodausongelma ja Baum Welch / eteenpäin-taaksepäin, kun koulutat malliasi sarjaan.

Baum Welch toimii seuraavalla tavalla.

Jokaiselle jaksolle harjoitusjaksosarjassa.

1. Laske eteenpäin tulevaisuuden todennäköisyydet eteenpäin-algoritmilla
2. Laske taaksepäin-todennäköisyydet taaksepäin-algoritmilla
3. Laske nykyisen sekvenssin vaikutukset mallin siirtymiin, laske nykyisen sekvenssin vaikutukset mallin emissiotodennäköisyyksiin.
4. Laske uudet malliparametrit (aloitustodennäköisyydet, siirtymätodennäköisyydet, päästötodennäköisyydet )
5. Laske mallin uusi lokitodennäköisyys
6. Pysäytä, kun lokitodennäköisyyden muutos on pienempi kuin annettu kynnys tai kun enimmäismäärä iteraatioita on kulunut.

Tarvittaessa täydellinen kuvaus Viterbi-dekoodauksen yhtälöistä ja harjoitusalgoritmista kerro minulle ja voin osoittaa sinut oikeaan suuntaan.

Kommentit

• Hei . Jos tallennamme polun eteenpäin tulevaa algoritmia käyttävän arvioinnin aikana, tekeekö se Viterbi-algoritmin käyttöä dekoodauksessa turhaa?

Minusta nämä kaksi seuraavaa {2} diaa ovat todella hyviä sijoittamaan eteenpäin -backward- ja Viterbi-algoritmit kaikkien muiden HMM: n kanssa käytettyjen tyypillisten algoritmien joukossa:

Huomautuksia :

• $ x $ on havaittuja päästöjä, $ \ pi $ ovat HMM: n parametreja.
• path = päästöjen sarja
• dekoodaus = päättely
• oppiminen = harjoittelu = parametriarviointi
• Jotkut artikkelit (esim. {1}) väittävät, että Baum – Welch on sama kuin eteenpäin-taaksepäin-algoritmi, mutta I agr ee Masterfoolin ja Wikipedian kanssa: Baum – Welch on odotusten maksimoinnin algoritmi, joka käyttää eteenpäin-taaksepäin-algoritmia. Nämä kaksi kuvaa erottavat myös Baum – Welchin eteenpäin-taaksepäin-algoritmista.

Viitteet:

• {1} Lember, Jüri ja Alexey Koloydenko. ”Mukautettu Viterbi-koulutus piilotetuille Markov-malleille.” Bernoulli 14, nro. 1 (2008): 180-206.
• {2} 6.047 / 6.878 Laskennallinen biologia: genomit, verkostot, evoluutio (syksy 2012) Luento 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):

Moratin vastaus on väärä yhdessä pisteessä: Baum -Welch on odotusten maksimoinnin algoritmi, jota käytetään HMM: n parametrien kouluttamiseen. Se käyttää eteenpäin-taaksepäin-algoritmia jokaisen iteraation aikana. Eteenpäin-taaksepäin-algoritmi on todellakin vain yhdistelmä eteen- ja taaksepäin-algoritmeja: yksi eteenpäin, yksi taaksepäin. Yksinään eteenpäin-taaksepäin-algoritmia ei käytetä HMM-parametrien kouluttamiseen, vaan vain tasoittamiseen: tilasekvenssin marginaalisten todennäköisyyksien laskemiseen.

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

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

@Jaroslav Bulatovilla oli tarkka vastaus. Lisään yhden esimerkin siitä kertoakseni eroja eteenpäin-taaksepäin ja Viterbi-algoritmien välillä.

Oletetaan, että meillä on tämä HMM (Wikipedia HMM -sivulta). Huomaa, että malli on jo annettu, joten tässä ei ole oppimista datatehtävästä.

Oletetaan, että tietomme ovat pituudeltaan 4 sarjaa. (Walk, Shop, Walk, Clean). Kaksi algoritmia antaa erilaisia asioita.

• Eteenpäin-taaksepäin-algoritmi antaa -probabin jokaisen piilotetun tilan . Tässä on esimerkki. Huomaa, että taulukon kukin sarake on summa $ 1 $.

• Viterbi-algoritmi antaa todennäköisimmän piilotilojen järjestyksen . Tässä on esimerkki. Huomaa, että tähän piilotettuun sekvenssiin liittyy myös todennäköisyys. Tällä sekvenssillä on max prob. kaikkien muiden jaksojen yli (esim. $ 2 ^ 4 = 16 $ sekvenssit kaikista Sunny kaikista Rainy).

Tässä on joitain R esittelykoodi

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