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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

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

Алгоритм[править | править вики-текст]

Пусть у нас есть скрытая марковская модель с пространством состояний S, начальными вероятностями \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} &=& \mathrm{P}\big( y_t \ | \ k \big) \cdot \max_{x \in S} \left( 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_{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).


См. также[править | править вики-текст]

Примечания[править | править вики-текст]