62
правки
Изменения
Нет описания правки
|definition='''Путь Витерби''' (англ. ''Viterbi path'') {{---}} наиболее правдоподобная (наиболее вероятная) последовательность скрытых состояний.
}}
'''Предположения, которые делает алгоритм:'''
#Скрытые и наблюдаемые события должны быть последовательностью, которая чаще всего упорядочена по времени.
#Каждое скрытое событие должно соответствовать только одному наблюдаемому.
#Вычисление наиболее вероятной скрытой последовательности до момента <tex>t</tex> зависит только от наблюдаемого события в этот момент времени и наиболее вероятной последовательности до момента <tex>t − 1</tex> (динамическое программирование).
== Алгоритм ==
'''Входные данные:'''
Пусть задано пространство наблюдений <tex>O =\{o_1,o_2 \ldots o_N\}</tex>, пространство состояний <tex>S =\{s_1,s_2 \ldots s_K\}</tex>, последовательность наблюдений <tex>Y =\{y_1,y_2 \ldots y_T\}</tex>, матрица <tex>A</tex> переходов из <tex>i</tex>-того состояния в <tex>j</tex>-ое, размером <tex>K \times K</tex>, матрица эмиссии <tex> B </tex> размера <tex>K \times N</tex>, которая определяет вероятность наблюдения <tex>o_j</tex> из состояния <tex>s_i</tex>, массив начальных вероятностей <tex>\pi</tex> размером <tex>K</tex>, показывающий вероятность того, что начальное состояние <tex>s_i</tex>. Путь <tex>X =\{x_1,x_2 \ldots x_T\}</tex> {{---}} последовательность состояний, которые привели к последовательности наблюдений <tex>Y</tex>.
Создадим две матрицы <tex>TState</tex> и <tex>TIndex</tex> размером <tex>K \times T</tex>. Каждый элемент <tex>TState[i,j]</tex> содержит вероятность того, что на <tex>j</tex>-ом шаге мы находимся в состоянии <tex>s_i</tex>. Каждый элемент <tex>TIndex[i,j]</tex> содержит индекс наиболее вероятного состояния на <tex>{j-1}</tex>-ом шаге.
'''Доказательство корректности:'''
Наиболее вероятная последовательность скрытых состояний получается следующими реккурентными соотношениями: <tex>#Скрытые и наблюдаемые события должны быть последовательностьюV_{1, которая чаще всего упорядочена по времени.k} = \mathrm{P}(y_1 \mid k) \cdot \pi_k \\#V_{t,k} = \max_{x \in S} \left( \mathrm{P}( y_t \mid k) \cdot a_{x,k} \cdot V_{t-1,x}\right) \\#Каждое скрытое событие должно соответствовать только одному наблюдаемому.x_T = \arg\max_{x \in S} (V_{T,x}) \\#Вычисление наиболее вероятной скрытой последовательности до момента x_{t-1} = \mathrm{Ptr}(x_t,t)</tex>Где <tex>V_{t,k}</tex> зависит только от наблюдаемого события в этот момент времени и это вероятность наиболее вероятной последовательности до момента последовательностельности, которая ответственна за первые <tex>t − 1</tex> (динамическое программирование)наблюдений, у которых <tex>k</tex> является завершающим состоянием.
== Псевдокод ==
