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

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

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

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

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

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

Алгоритм

Пусть существует скрытая марковская модель (СММ) с пространством состояний [math]\displaystyle{ S=\{s_1,s_2,\dots,s_K\} }[/math], где [math]\displaystyle{ K }[/math] — количество возможных различных состояний сети. При этом состояния, которые принимает сеть, невидимы для наблюдения. Обозначим через [math]\displaystyle{ x_t }[/math] состояние сети в момент [math]\displaystyle{ t }[/math]. На выходе сети в момент [math]\displaystyle{ t }[/math] появляется видимое для наблюдения значение [math]\displaystyle{ y_t \in O=\{o_1,o_2,\dots,o_N\} }[/math], где [math]\displaystyle{ N }[/math] — число возможных различных наблюдаемых значений на выходе. Пусть [math]\displaystyle{ \pi_i }[/math] — начальная вероятность нахождения сети в состоянии [math]\displaystyle{ i }[/math], а [math]\displaystyle{ a_{i,j} }[/math] — вероятности перехода сети из состояния [math]\displaystyle{ i }[/math] в состояние [math]\displaystyle{ j }[/math].

Пусть на выходе сети наблюдается последовательность [math]\displaystyle{ y_1,\dots, y_T }[/math]. Тогда наиболее вероятная последовательность состояний сети [math]\displaystyle{ x_1,\dots,x_T }[/math] для наблюдаемой последовательности может быть определена с помощью следующих рекуррентных соотношений:

[math]\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} }[/math]

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

[math]\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} }[/math]

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

См. также

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