T-61.281 Luonnollisen kielen tilastollinen käsittely
Vastaukset 6, ti 2.3.2004, 8:30-10:00 Markov-ketjut ja kätketyt Markov-mallit, Versio 1.0
Sovelletaan ylläolevaan kaavaan Markov-oletusta, että nykyinen tila
riippuu vain edellisestä tilasta, muttei sitä aikaisemmista:
Ylläolevan yhtälön pyörittämiseen käytettiin ensiksi todennäköisyyslaskun kaavaa . Sitten huomattiin että . Edellisen yhtällön nimittäjässä ja osoittajassa on samankaltainen termi. Kevennetään hieman merkintöjä ja esitetään sama asia funktion avulla:
Tarkastellaanpa, miten tämä eteenpäin-todennäköisyys oikein voidaan laskea.
Lähtöpäivä
Ensimmäinen päivä
Toinen päivä
Kolmas päivä
Nyt olemme saaneet lasketuksi tehtävän ratkaisuun tarvittavat suureet.
Sijoitetaan luvut kaavaan:
Viterbi: Ensimmäinen päivä
Viterbi: Toinen päivä
Laskettaessa huomataan, että kahdesta paikkaa (tilat 1 ja 3) päästään yhtä todennäköisesti tilaan 3. Tässä tapauksessa paras paluureitti ratkaistiin arpomalla näiden kahden välillä ja tulokseksi saatiin 3.
Viterbi: Kolmas päivä
Valmiista hilasta voidaan hakea todennäköisin tilasekvenssi: aloitetaan kaikkein todennäköisimmästä lopputilasta ja seurataan nuolia alkuun päin. Nyt siis näyttäisi siltä, että aurinkoisen lähtöpäivän jälkeen Turussa on ollut aurinkoista, pilvistä ja taasen aurinkoista.
Yhteenveto: mitä eroa eteenpäin-algoritmilla ja Viterbi-haulla
Eteenpäin-algoritmi hakee oikean todennäköisyyden kullekin tilasekvenssille. Sen avulla ei kuitenkaan pysty hakemaan parasta polkua hilasta.
Viterbi-haulla tilatodennäköisyydet ovat vain approksimaatioita. Tätä algorimia kuitenkin käytetään paljon juuri sen takia, että sillä pysytytään löytämään paras polku.
Laskennallisesti algoritmit ovat yhtä raskaita, eteenpäin-algoritmin summaus on vain Viterbi-haussa vaihtunut maksimoinniksi.