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

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

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

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

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

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

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

Пусть существует скрытая марковская модель (СММ) с пространством состояний , где — количество возможных различных состояний сети. При этом состояния, которые принимает сеть, невидимы для наблюдения. Обозначим через состояние сети в момент . На выходе сети в момент появляется видимое для наблюдения значение , где — число возможных различных наблюдаемых значений на выходе. Пусть — начальная вероятность нахождения сети в состоянии , а — вероятности перехода сети из состояния в состояние .

Пусть на выходе сети наблюдается последовательность . Тогда наиболее вероятная последовательность состояний сети для наблюдаемой последовательности может быть определена с помощью следующих рекуррентных соотношений:[2]

Здесь  — это вероятность наиболее вероятной последовательности состояний, соответствующей первым наблюдаемым значениям, завершающейся в состоянии . Путь Витерби может быть найден при помощи указателей, запоминающих, какое состояние появлялось во втором уравнении. Пусть  — функция, которая возвращает значение , использованное для подсчета , если , или если . Тогда

Здесь мы используем стандартное определение arg max.
Сложность этого алгоритма равна .

Примечания

[править | править код]
  1. 29 Apr 2005, G. David Forney Jr: The Viterbi Algorithm: A Personal History. Дата обращения: 10 января 2012. Архивировано 2 июня 2016 года.
  2. Xing E, slide 11, URL: http://www.cs.cmu.edu/~epxing/Class/10708-07/schedule.html Архивная копия от 18 января 2015 на Wayback Machine