Algoritmul Viterbi

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 23 aprilie 2017; verificările necesită 7 modificări .

Algoritmul Viterbi este un algoritm pentru găsirea celei mai potrivite liste de stări (numită calea Viterbi ), care, în contextul lanțurilor Markov, obține cea mai probabilă succesiune de evenimente care au avut loc.

Este un algoritm de programare dinamică . Este folosit în algoritmul de decodare convoluțional Viterbi .

Algoritmul a fost propus de Andrew Viterbi în 1967 ca algoritm pentru decodarea unui cod convoluțional transmis prin rețele cu zgomot. [1] Algoritmul a fost utilizat pe scară largă în decodarea codurilor convoluționale ale telefoanelor mobile GSM și CDMA , modemurilor dial-up și rețelelor fără fir 802.11 . De asemenea, este utilizat pe scară largă în recunoașterea vorbirii , sinteza vorbirii , lingvistică computațională și bioinformatică . De exemplu, în recunoașterea vorbirii, un semnal sonor este perceput ca o succesiune de evenimente, iar o linie de text este „sensul ascuns” al semnalului acustic. Algoritmul Viterbi găsește cea mai probabilă linie de text pentru un semnal dat.

Algoritmul face mai multe ipoteze:

evenimentele observabile și ascunse trebuie să fie o secvență. Secvența este cel mai adesea ordonată în funcție de timp.
cele două secvenţe trebuie aliniate: fiecare eveniment observabil trebuie să corespundă exact unui eveniment ascuns
calculul secvenței ascunse cele mai probabile până la momentul t trebuie să depindă numai de evenimentul observat la momentul t , și secvența cea mai probabilă până la momentul t − 1.

Algoritm

Să existe un model Markov ascuns (HMM) cu spațiu de stare , unde este numărul de stări diferite posibile ale rețelei. În același timp, stările pe care le acceptă rețeaua sunt invizibile pentru observație. Indicați prin starea rețelei în acest moment . La ieșirea rețelei , valoarea vizibilă pentru observare apare în momentul de față , unde este numărul de valori diferite observate posibile la ieșire. Fie probabilitatea inițială ca rețeaua să fie în stare și fie probabilitățile tranziției rețelei de la stare la stare . ${\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$

Să fie observată secvența la ieșirea rețelei . Apoi, cea mai probabilă secvență de stări de rețea pentru secvența observată poate fi determinată folosind următoarele relații recursive: [2] $y_{1},\dots ,y_{T}$ $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}}

Aici , este probabilitatea secvenței celei mai probabile de stări corespunzătoare primelor valori observate, care se termină în starea . Calea Viterbi poate fi găsită folosind pointeri pentru a reține care stare a apărut în a doua ecuație. Fie o funcție care returnează valoarea folosită pentru a calcula dacă , sau dacă . Apoi $V_{t,k)$ $t$ $k$ $X$ $\mathrm {Ptr} (k,t)$ $X$ $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}}

Aici folosim definiția standard a arg max .
Complexitatea acestui algoritm este . $O(T\times \left|{S}\right|^{2})$

Vezi și

Note

↑ 29 apr 2005, G. David Forney Jr: The Viterbi Algorithm: A Personal History . Consultat la 10 ianuarie 2012. Arhivat din original pe 2 iunie 2016. (nedefinit)
↑ Xing E, slide 11, URL: http://www.cs.cmu.edu/~epxing/Class/10708-07/schedule.html Arhivat la 18 ianuarie 2015 la Wayback Machine