1632
правки
Изменения
м
rollbackEdits.php mass rollback
*<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>
<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}[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{TIndex}[\mathtt{j}, \mathtt{i}] = \arg\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}]])</tex> ''<font color=green>// функция arg \leadsto \max() ищет максимум выражения в скобках и возвращает аргумент(в нашем случае <tex>\mathtt{k}</tex>), при котором достигается этот максимум</font>''
<tex>\mathtt{TState}[\mathtt{j}, \mathtt{i}] = \mathtt{TState}[\mathtt{TIndex}[\mathtt{j}, \mathtt{i}], \mathtt{i} - 1] * \mathtt{A}[\mathtt{k}, \mathtt{j}] * \mathtt{B}[\mathtt{j}, \mathtt{Y}[\mathtt{i}]]</tex>
<tex>\mathtt{X}[\mathtt{T}] = \arg\max_{1 \leqslant \mathtt{k}\leqslant \mathtt{K}} \limits (\mathtt{TState}[\mathtt{k}, \mathtt{T}])</tex>
