Viterbi algoritmus

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2017. április 23-án áttekintett verziótól ; az ellenőrzések 7 szerkesztést igényelnek .

A Viterbi algoritmus az állapotok legmegfelelőbb listájának megtalálására szolgáló algoritmus (úgynevezett Viterbi-útvonal ), amely a Markov-láncok kontextusában megkapja a bekövetkezett események legvalószínűbb sorozatát.

Ez egy dinamikus programozási algoritmus . A Viterbi konvolúciós dekódoló algoritmusban használatos .

Az algoritmust Andrew Viterbi javasolta 1967-ben, mint egy hálózatokon zajos konvolúciós kód dekódolására szolgáló algoritmust . [1] Az algoritmust széles körben használták GSM és CDMA mobiltelefonok, betárcsázós modemek és 802.11 vezeték nélküli hálózatok konvolúciós kódjainak dekódolására . Széles körben használják a beszédfelismerésben , beszédszintézisben , a számítógépes nyelvészetben és a bioinformatikában is . Például a beszédfelismerésben a hangjelzést események sorozataként érzékelik, és egy szövegsor az akusztikus jel "rejtett jelentése". A Viterbi algoritmus megkeresi az adott jel legvalószínűbb szövegsorát.

Az algoritmus több feltételezést is megfogalmaz:

a megfigyelhető és rejtett eseményeknek sorozatnak kell lenniük. A sorrendet leggyakrabban idő szerint rendezik.
a két sorozatot egymáshoz kell igazítani: minden megfigyelhető eseménynek pontosan egy rejtett eseménynek kell megfelelnie
a legvalószínűbb rejtett sorozat kiszámítása t időpontig csak a t időpontban megfigyelt eseménytől , a legvalószínűbb sorozat pedig t - 1 időpontig függhet.

Algoritmus

Legyen egy rejtett Markov-modell (HMM) állapottérrel , ahol a lehetséges különböző hálózati állapotok száma. Ugyanakkor a hálózat által elfogadott állapotok láthatatlanok a megfigyelés számára. Jelölje a hálózat pillanatnyi állapotával . A hálózat kimenetén pillanatnyilag a megfigyelésre látható érték jelenik meg , ahol a kimeneten a lehetséges különböző megfigyelt értékek száma. Legyen a kezdeti valószínűsége annak, hogy a hálózat állapotba kerül , és legyen a hálózat állapotból állapotba való átmenetének valószínűsége . ${\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}$ $én$ $a_{i,j}$ $én$ $j$

Figyeljük meg a sorozatot a hálózat kimenetén . Ezután a következő rekurzív relációk segítségével meghatározható a megfigyelt sorozat hálózati állapotainak legvalószínűbb sorozata : [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}}

Itt az első megfigyelt értékeknek megfelelő állapotok legvalószínűbb sorozatának valószínűsége , amely állapotra végződik . A Viterbi útvonalat mutatók segítségével találhatjuk meg, hogy megjegyezzük, melyik állapot jelent meg a második egyenletben. Legyen egy függvény, amely az if , vagy if kiszámításához használt értéket adja vissza . Akkor ${\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{tömb}}

Itt az arg max szabvány definícióját használjuk .
Ennek az algoritmusnak a bonyolultsága . $O(T\times \left|{S}\right|^{2})$

Lásd még

Jegyzetek

↑ 2005. április 29., G. David Forney Jr.: The Viterbi Algorithm: A Personal History . Letöltve: 2012. január 10. Az eredetiből archiválva : 2016. június 2.. (határozatlan)
↑ Xing E, 11. dia, URL: http://www.cs.cmu.edu/~epxing/Class/10708-07/schedule.html Archiválva : 2015. január 18. a Wayback Machine -nél