Алгоритм Витерби

Алгоритм Витерби — алгоритм поиска наиболее подходящего списка состояний (называемого путём Витерби), который в контексте цепей Маркова получает наиболее вероятную последовательность произошедших событий.

Является алгоритмом динамического программирования. Применяется в алгоритме свёрточного декодирования Витерби.

Алгоритм был предложен Эндрю Витерби в 1967 году как алгоритм декодирования свёрточного кода, передаваемого по сетям с наличием шума.[1] Алгоритм получил широкое применение в декодировании свёрточных кодов мобильных телефонов стандартов GSM и CDMA, dial-up модемах и беспроводных сетях стандарта 802.11. Также он широко используется в распознавании речи, синтезе речи, компьютерной лингвистике и биоинформатике. К примеру, при распознавании речи звуковой сигнал воспринимается как последовательность событий и строка текста есть «скрытый смысл» акустического сигнала. Алгоритм Витерби находит наиболее вероятную строку текста по данному сигналу.

Алгоритм делает несколько предположений:

наблюдаемые и скрытые события должны быть последовательностью. Последовательность чаще всего упорядочена по времени.
две последовательности должны быть выровнены: каждое наблюдаемое событие должно соответствовать ровно одному скрытому событию
вычисление наиболее вероятной скрытой последовательности до момента t должно зависеть только от наблюдаемого события в момент времени t, и наиболее вероятной последовательности до момента t − 1.

Алгоритм

Пусть существует скрытая марковская модель (СММ) с пространством состояний $S=\{s_{1},s_{2},\dots ,s_{K}\}$ , где $K$ — количество возможных различных состояний сети. При этом состояния, которые принимает сеть, невидимы для наблюдения. Обозначим через $x_{t}$ состояние сети в момент $t$ . На выходе сети в момент $t$ появляется видимое для наблюдения значение $y_{t}\in O=\{o_{1},o_{2},\dots ,o_{N}\}$ , где $N$ — число возможных различных наблюдаемых значений на выходе. Пусть $\pi _{i}$ — начальная вероятность нахождения сети в состоянии $i$ , а $a_{i,j}$ — вероятности перехода сети из состояния $i$ в состояние $j$ .

Пусть на выходе сети наблюдается последовательность $y_{1},\dots ,y_{T}$ . Тогда наиболее вероятная последовательность состояний сети $x_{1},\dots ,x_{T}$ для наблюдаемой последовательности может быть определена с помощью следующих рекуррентных соотношений:[2]

{\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}}

Здесь $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}}

Здесь мы используем стандартное определение arg max.
Сложность этого алгоритма равна $O(T\times \left|{S}\right|^{2})$ .

См. также

Примечания

29 Apr 2005, G. David Forney Jr: The Viterbi Algorithm: A Personal History
Xing E, slide 11, URL: http://www.cs.cmu.edu/~epxing/Class/10708-07/schedule.html

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] 29 Apr 2005, G. David Forney Jr: The Viterbi Algorithm: A Personal History

[2] Xing E, slide 11, URL: http://www.cs.cmu.edu/~epxing/Class/10708-07/schedule.html