Изменения

#Пространство наблюдений <tex>\mathtt{O =\{o_1,o_2 \ldots o_N\}}</tex>#Пространство состояний <tex>\mathtt{S =\{s_1,s_2 \ldots s_K\}}</tex>#Последовательность наблюдений <tex>\mathtt{Y =\{y_1,y_2 \ldots y_T\}}</tex>#Матрица <tex>\mathtt{A}</tex> переходов из <tex>\mathtt{i}</tex>-того состояния в <tex>\mathtt{j}</tex>-ое, размером <tex>\mathtt{K \times K}</tex> #Матрица эмиссии <tex> \mathtt{B }</tex> размера <tex>\mathtt{K \times N}</tex>, которая определяет вероятность наблюдения <tex>\mathtt{o_j}</tex> из состояния <tex>\mathtt{s_i}</tex>#Массив начальных вероятностей <tex>\mathtt{\pi}</tex> размером <tex>\mathtt{K}</tex>, показывающий вероятность того, что начальное состояние <tex>\mathtt{s_i}</tex>

<tex>\mathtt{X =\{x_1,x_2 \ldots x_T\}}</tex> {{---}} последовательность состояний, которые привели к последовательности наблюдений <tex>\mathtt{Y}</tex>.

Создадим две матрицы <tex>\mathtt{TState}</tex> и <tex>\mathtt{TIndex}</tex> размером <tex>\mathtt{K \times T}</tex>. Каждый элемент <tex>\mathtt{TState}[\mathtt{i,j}]</tex> содержит вероятность того, что на <tex>\mathtt{j}</tex>-ом шаге мы находимся в состоянии <tex>\mathtt{s_i}</tex>. Каждый элемент <tex>\mathtt{TIndex}[\mathtt{i,j}]</tex> содержит индекс наиболее вероятного состояния на <tex>{\mathtt{j-1}}</tex>-ом шаге.

'''Шаг 1.''' Заполним первый столбец матриц <tex>\mathtt{TState}</tex> на основании начального распределения, и <tex>\mathtt{TIndex}</tex> нулями.

'''Шаг 2.''' Последовательно заполняем следующие столбцы матриц <tex>\mathtt{TState}</tex> и <tex>\mathtt{TIndex}</tex>, используя матрицы вероятностей эмиссий и переходов.

'''Шаг 3.''' Рассматривая максимальные значения в столбцах матрицы <tex>\mathtt{TIndex}</tex>, начиная с последнего столбца, выдаем ответ.

*<tex>\mathtt{V_{1,k} = \mathrm{P}(\mathtt{y_1 \mid k}) \cdot \pi_k}</tex>*<tex>\mathtt{V_{t,k} = \max_{x \in S} \left( \mathrm{P}( \mathtt{y_t \mid k}) \cdot A_{x,k} \cdot V_{t-1,x}\right)}</tex>Где <tex>\mathtt{V_{t,k}}</tex> это вероятность наиболее вероятной последовательностельностипоследовательности, которая ответственна за первые <tex>\mathtt{t}</tex> наблюдений, у которых <tex>\mathtt{k}</tex> является завершающим состоянием. Путь Витерби может быть получен сохранением обратных указателей, которые помнят какое состояние было использовано во втором равенстве. Пусть <tex>\mathrm{Ptr}(\mathtt{k,t})</tex> {{---}} функция, которая возвращает значение <tex>\mathtt{x}</tex>, использованное для подсчета <tex>\mathtt{V_{t,k}}</tex> если <tex>\mathtt{t > 1}</tex>, или <tex>\mathtt{k}</tex> если <tex>\mathtt{t=1}</tex>. Тогда:*<tex>\mathtt{x_T = \arg\max_{x \in S} (V_{T,x})}</tex>*<tex>\mathtt{x_{t-1} = \mathrm{Ptr}(x_t,t)}</tex>