Изменения

Перейти к: навигация, поиск

Алгоритм Витерби

3 байта убрано, 10:31, 18 мая 2018
Алгоритм
*<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} = \mathtt{x} \in \mathtt{S} : \mathtt{V_{T,x}} \rightarrow leadsto \max</tex>
*<tex>\mathtt{x_{t-1}} = \mathrm{Ptr}(\mathtt{x_t},\mathtt{t})</tex>
Анонимный участник

Навигация