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

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

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

Алгоритм был предложен Эндрю Витерби в 1967 году как алгоритм декодирования свёрточного кода, передаваемого по сетям с наличием шума. Алгоритм получил широкое применение в декодировании свёрточных кодов мобильных телефонов стандартов 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$ для наблюдаемой последовательности может быть определена с помощью следующих рекуррентных соотношений:

$\begin{array}{ccc}{V}_{1,k}& =& \mathrm{P}(y_1|k)\cdot {\pi }_k\\ V_{t,k}& =& \underset{x\in S}{\max }\left(\mathrm{P}\right(y_t|k)\cdot a_{x,k}\cdot V_{t-1,x})\end{array}$

Здесь $V_{t,k}$ — это вероятность наиболее вероятной последовательности состояний, соответствующей первым $t$ наблюдаемым значениям, завершающейся в состоянии $k$. Путь Витерби может быть найден при помощи указателей, запоминающих, какое состояние $x$ появлялось во втором уравнении. Пусть $\mathrm{P}\mathrm{t}\mathrm{r}(k,t)$ — функция, которая возвращает значение $x$, использованное для подсчета $V_{t,k}$, если $t>1$, или $k$ если $t=1$. Тогда

$\begin{array}{ccc}{x}_T& =& \arg \max {\mathrm{\backslash limits}}_{x\in S}(V_{T,x})\\ x_{t-1}& =& \mathrm{P}\mathrm{t}\mathrm{r}(x_t,t)\end{array}$

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

См. также

• EM-алгоритм
• Скрытая марковская модель