Viterbi-algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 23. huhtikuuta 2017 tarkistetusta versiosta . tarkastukset vaativat 7 muokkausta .

Viterbi-algoritmi on algoritmi sopivimman tilaluettelon löytämiseksi (kutsutaan Viterbi-poluksi ), joka Markov-ketjujen yhteydessä saa todennäköisimmän tapahtuneen tapahtumasarjan.

Se on dynaaminen ohjelmointialgoritmi . Sitä käytetään Viterbi-konvoluutiodekoodausalgoritmissa .

Algoritmia ehdotti Andrew Viterbi vuonna 1967 algoritmiksi verkkojen kautta lähetetyn konvoluutiokoodin dekoodaamiseksi kohinalla. [1] Algoritmia on käytetty laajalti GSM- ja CDMA -matkapuhelinten, puhelinmodeemien ja langattomien 802.11 - verkkojen konvoluutiokoodien dekoodaamiseen . Sitä käytetään myös laajasti puheentunnistuksessa , puhesynteesissä , laskennallisessa lingvistiikassa ja bioinformatiikassa . Esimerkiksi puheentunnistuksessa äänisignaali havaitaan tapahtumien sarjana ja tekstirivi on akustisen signaalin "piilotettu merkitys". Viterbi-algoritmi löytää todennäköisimmän tekstirivin annetulle signaalille.

Algoritmi tekee useita oletuksia:

havaittavien ja piilotettujen tapahtumien on oltava sarja. Sarja järjestetään useimmiten ajan mukaan.
kahden sekvenssin on oltava kohdakkain: jokaisen havaittavan tapahtuman on vastattava täsmälleen yhtä piilotettua tapahtumaa
Todennäköisimmän piilotetun sekvenssin laskennan ajanhetkeen t asti tulee riippua vain havaitusta tapahtumasta hetkellä t ja todennäköisimmän sekvenssin ajanhetkeen t - 1 asti.

Algoritmi

Olkoon piilotettu Markovin malli (HMM) tilaavaruudella , jossa on mahdollisten eri verkkotilojen lukumäärä. Samalla tilat, jotka verkko hyväksyy, ovat näkymättömiä havainnolle. Merkitään verkon senhetkisellä tilalla . Verkon lähdössä näkyy tällä hetkellä havainnointiin näkyvä arvo , jossa on mahdollisten erilaisten havaittujen arvojen määrä lähdössä. Olkoon alkutodennäköisyys sille, että verkko on tilassa , ja olkoon verkon siirtymisen todennäköisyydet tilasta tilaan . ${\displaystyle S=\{s_{1},s_{2},\dots ,s_{K}\))$ $K$ $x_t$ $t$ $t$ ${\displaystyle y_{t}\in O=\{o_{1},o_{2},\dots ,o_{N}\))$ $N$ $\pi _{i}$ $i$ $a_{i,j}$ $i$ $j$

Tarkastellaan sekvenssiä verkon lähdössä . Sitten havaitun sekvenssin todennäköisin verkkotilojen sarja voidaan määrittää käyttämällä seuraavia rekursiivisia suhteita: [2] $y_{1},\dots ,y_{T}$ ${\displaystyle x_{1},\dots ,x_{T))$

{\begin{array}{rcl}V_{1,k}&=&\mathrm {P} {\big (}y_{1}\ |\ k{\big )}\cdot \pi _{ k}\\V_{t,k}&=&\max _{x\in S}\left(\mathrm {P} {\big (}y_{t}\ |\ k{\big )}\cdot a_{x,k}\cdot V_{t-1,x}\right)\end{array}}

Tässä on todennäköisimmän ensimmäisiä havaittuja arvoja vastaavien tilojen sarjan todennäköisyys, joka päättyy tilaan . Viterbi-polku voidaan löytää käyttämällä osoittimia muistamaan, mikä tila esiintyi toisessa yhtälössä. Antaa olla funktio, joka palauttaa arvon , jota käytetään laskettaessa jos , tai jos . Sitten ${\displaystyle V_{t,k))$ $t$ $k$ $x$ $\mathrm {Ptr} (k,t)$ $x$ ${\displaystyle V_{t,k))$ $t>1$ $k$ $t = 1$

{\begin{array}{rcl}x_{T}&=&\arg \max \limits _{x\in S}(V_{T,x})\\x_{t-1}&= &\mathrm {Ptr} (x_{t},t)\end{array}}

Tässä käytetään vakiomääritelmää arg max .
Tämän algoritmin monimutkaisuus on . $O(T\times \left|{S}\right|^{2})$

Katso myös

Muistiinpanot

↑ 29. huhtikuuta 2005, G. David Forney Jr: The Viterbi Algorithm: A Personal History . Haettu 10. tammikuuta 2012. Arkistoitu alkuperäisestä 2. kesäkuuta 2016. (määrätön)
↑ Xing E, dia 11, URL: http://www.cs.cmu.edu/~epxing/Class/10708-07/schedule.html Arkistoitu 18. tammikuuta 2015 Wayback Machinessa