Viterbi algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 23 april 2017; kontroller kräver 7 redigeringar .

Viterbi-algoritmen är en algoritm för att hitta den mest lämpliga listan över tillstånd (kallad Viterbi-banan ), som, i samband med Markov-kedjor, erhåller den mest sannolika sekvensen av händelser som har inträffat.

Det är en dynamisk programmeringsalgoritm . Den används i Viterbi faltningsavkodningsalgoritmen .

Algoritmen föreslogs av Andrew Viterbi 1967 som en algoritm för att avkoda en faltningskod som sänds över nätverk med brus. [1] Algoritmen har använts i stor utsträckning vid avkodning av faltningskoder för GSM- och CDMA -mobiltelefoner, uppringda modem och trådlösa 802.11 -nätverk . Det används också i stor utsträckning inom taligenkänning , talsyntes , datorlingvistik och bioinformatik . Till exempel, vid taligenkänning, uppfattas en ljudsignal som ett händelseförlopp och en textrad är den akustiska signalens "dolda betydelse". Viterbi-algoritmen hittar den mest sannolika textraden för en given signal.

Algoritmen gör flera antaganden:

observerbara och dolda händelser måste vara en sekvens. Sekvensen är oftast ordnad efter tid.
de två sekvenserna måste anpassas: varje observerbar händelse måste motsvara exakt en dold händelse
beräkningen av den mest sannolika dolda sekvensen fram till tidpunkten t måste endast bero på den observerade händelsen vid tidpunkten t , och den mest sannolika sekvensen fram till tiden t − 1.

Algoritm

Låt det finnas en dold Markov-modell (HMM) med tillståndsutrymme , där är antalet möjliga olika nätverkstillstånd. Samtidigt är de tillstånd som nätverket accepterar osynliga för observation. Ange med nätverkets status för tillfället . Vid utgången av nätverket visas det värde som är synligt för observation för tillfället , där är antalet möjliga olika observerade värden vid utgången. Låt vara den initiala sannolikheten för att nätverket är i tillståndet , och låt vara sannolikheten för nätverksövergången från stat till stat . ${\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$

Låt sekvensen observeras vid utgången av nätverket . Sedan kan den mest sannolika sekvensen av nätverkstillstånd för den observerade sekvensen bestämmas med hjälp av följande rekursiva relationer: [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}}

Här är sannolikheten för den mest sannolika sekvensen av tillstånd som motsvarar de första observerade värdena, som slutar på tillståndet . Viterbi-banan kan hittas genom att använda pekare för att komma ihåg vilket tillstånd som dök upp i den andra ekvationen. Låta vara en funktion som returnerar värdet som används för att beräkna if , eller if . Sedan ${\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}}

Här använder vi standarddefinitionen av arg max .
Komplexiteten i denna algoritm är . $O(T\times \left|{S}\right|^{2})$

Se även

Anteckningar

↑ 29 april 2005, G. David Forney Jr: Viterbi-algoritmen: En personlig historia . Hämtad 10 januari 2012. Arkiverad från originalet 2 juni 2016. (obestämd)
↑ Xing E, bild 11, URL: http://www.cs.cmu.edu/~epxing/Class/10708-07/schedule.html Arkiverad 18 januari 2015 på Wayback Machine