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

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

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

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

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

Алгоритм

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

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

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

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

${\displaystyle {\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 .
Сложность этого алгоритма равна ${\displaystyle O(T\times \left|{S}\right|^{2})}$ .

См. также

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

Примечания