Русская Википедия:Алгоритм Витерби
Алгоритм Витерби — алгоритм поиска наиболее подходящего списка состояний (называемого путём Витерби), который в контексте цепей Маркова получает наиболее вероятную последовательность произошедших событий.
Является алгоритмом динамического программирования. Применяется в алгоритме свёрточного декодирования Витерби.
Алгоритм был предложен Эндрю Витерби в 1967 году как алгоритм декодирования свёрточного кода, передаваемого по сетям с наличием шума.[1] Алгоритм получил широкое применение в декодировании свёрточных кодов мобильных телефонов стандартов GSM и CDMA, dial-up модемах и беспроводных сетях стандарта 802.11. Также он широко используется в распознавании речи, синтезе речи, компьютерной лингвистике и биоинформатике. К примеру, при распознавании речи звуковой сигнал воспринимается как последовательность событий и строка текста есть «скрытый смысл» акустического сигнала. Алгоритм Витерби находит наиболее вероятную строку текста по данному сигналу.
Алгоритм делает несколько предположений:
- наблюдаемые и скрытые события должны быть последовательностью. Последовательность чаще всего упорядочена по времени.
- две последовательности должны быть выровнены: каждое наблюдаемое событие должно соответствовать ровно одному скрытому событию
- вычисление наиболее вероятной скрытой последовательности до момента t должно зависеть только от наблюдаемого события в момент времени t, и наиболее вероятной последовательности до момента t − 1.
Алгоритм
Пусть существует скрытая марковская модель (СММ) с пространством состояний <math>S=\{s_1,s_2,\dots,s_K\}</math>, где <math>K</math> — количество возможных различных состояний сети. При этом состояния, которые принимает сеть, невидимы для наблюдения. Обозначим через <math>x_t</math> состояние сети в момент <math>t</math>. На выходе сети в момент <math>t</math> появляется видимое для наблюдения значение <math>y_t \in O=\{o_1,o_2,\dots,o_N\}</math>, где <math>N</math> — число возможных различных наблюдаемых значений на выходе. Пусть <math>\pi_i</math> — начальная вероятность нахождения сети в состоянии <math>i</math>, а <math>a_{i,j}</math> — вероятности перехода сети из состояния <math>i</math> в состояние <math>j</math>.
Пусть на выходе сети наблюдается последовательность <math>y_1,\dots, y_T</math>. Тогда наиболее вероятная последовательность состояний сети <math>x_1,\dots,x_T</math> для наблюдаемой последовательности может быть определена с помощью следующих рекуррентных соотношений:[2]
- <math>
\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>V_{t,k}</math> — это вероятность наиболее вероятной последовательности состояний, соответствующей первым <math>t</math> наблюдаемым значениям, завершающейся в состоянии <math>k</math>. Путь Витерби может быть найден при помощи указателей, запоминающих, какое состояние <math>x</math> появлялось во втором уравнении. Пусть <math>\mathrm{Ptr}(k,t)</math> — функция, которая возвращает значение <math>x</math>, использованное для подсчета <math>V_{t,k}</math>, если <math>t > 1</math>, или <math>k</math> если <math>t=1</math>. Тогда
- <math>
\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>O(T\times\left|{S}\right|^2)</math>.
См. также
Примечания
- ↑ Шаблон:Cite web
- ↑ Xing E, slide 11, URL: http://www.cs.cmu.edu/~epxing/Class/10708-07/schedule.html Шаблон:Wayback
