Изменения

#Вычисление наиболее вероятной скрытой последовательности до момента <tex>\mathtt{t}</tex> зависит только от наблюдаемого события в этот момент времени и наиболее вероятной последовательности до момента <tex>\mathtt{t } - 1}</tex> (динамическое программирование).

#Пространство состояний <tex>\mathtt{S} =\{\mathtt{s_1},\mathtt{s_2} \ldots \mathtt{s_K}}\}</tex>#Последовательность наблюдений <tex>\mathtt{Y} =\{\mathtt{y_1},\mathtt{y_2} \ldots \mathtt{y_T}}\}</tex>

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

*<tex>\mathtt{V_{1,k}} = \mathrm{P}(\mathtt{y_1 } \mid \mathtt{k}) \cdot \pi_k}</tex>*<tex>\mathtt{V_{t,k}} = \max\limits_{\mathtt{x } \in \mathtt{S}}\left(\mathrm{P}(\mathtt{y_t } \mid \mathtt{k}) \cdot \mathtt{A_{x,k}} \cdot \mathtt{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},\mathtt{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\limits_mathtt{x } \in \mathtt{S}(: \mathtt{V_{T,x})}\leadsto \max</tex>*<tex>\mathtt{x_{t-1}} = \mathrm{Ptr}(\mathtt{x_t},\mathtt{t})}</tex>

'''Viterbi'''(<tex>\mathrm{Viterbi}(\mathtt {O}, \mathtt {S}, \mathtt {P} , \mathtt {Y}, \mathtt {A}, \mathtt {B})</tex>) '''for''' <tex>\mathtt{j} = 1</tex> '''to''' <tex>\mathtt {K}</tex> <tex>\mathtt{TState}[\mathtt{ij}, 1}] = \mathtt{P}[\mathtt{ij}] * \mathtt{B}[\mathtt{ij},} \mathtt{Y}[\mathtt{1}]]</tex> <tex>\mathtt{TIndex}[\mathtt{ij}, 1}] = 0</tex> '''for''' <tex>\mathtt{i} = 2</tex> '''to''' <tex>\mathtt {T}</tex> '''for''' <tex>\mathtt{j} = 1</tex> '''to''' <tex>\mathtt {K}</tex> <tex>\mathtt{TStateTIndex}[\mathtt{j}, \mathtt{i}]} = \max_{1 \leqslant \mathtt{k}\leqslant in \mathtt{K}} \limits : (\mathtt{TState}[\mathtt{k}, \mathtt{i } - 1] * \mathtt{A}[\mathtt{k}, \mathtt{j}] * \mathtt{B}[\mathtt{j}, \mathtt{Y}[\mathtt{i}]]})\leadsto \max</tex> <tex>\mathtt{TIndexTState}[\mathtt{j}, \mathtt{i}]} = \argmathtt{TState}[\max_mathtt{1 \leqslant TIndex}[\mathtt{kj}\leqslant , \mathtt{K}i} \limits (], \mathtt{TState[k, i } - 1] * \mathtt{A}[\mathtt{k}, \mathtt{j}] * \mathtt{B}[\mathtt{j}, \mathtt{Y}[i]]})</tex> ''<font color=green>// функция arg max() ищет максимум выражения в скобках и возвращает аргумент(в нашем случае <tex>\mathtt{ki}]]</tex>), при котором достигается этот максимум</font>'' <tex>\mathtt{X}[\mathtt{T}] = \arg\max_{1 \leqslant \mathtt{k}\leqslant \mathtt{K}} \limits (\mathtt{TState}[\mathtt{k}, \mathtt{T}])</tex>

<tex>\mathtt{X}[\mathtt{i } - 1}] = \mathtt{TIndex}[\mathtt{X}[\mathtt{i}], \mathtt{, i}]</tex>

Таким образом, алгоритму требуется <tex>\mathrm{O}(\mathtt{T}\times\left|{\mathtt{K}}\right|^2})</tex> времени.