62
правки
Изменения
→Алгоритм
Наиболее вероятная последовательность скрытых состояний получается следующими реккурентными соотношениями:
*<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} max\left(\mathrm{P}(\mathtt{y_t \mid k}) \cdot A_{x,k} \cdot V_{t-1,x}\right), {x \in S} }</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} max (V_{T,x}), {x \in S}}</tex>
*<tex>\mathtt{x_{t-1} = \mathrm{Ptr}(x_t,t)}</tex>
