Изменения

Пусть дана скрытая Марковская модель <tex>\lambda = \{\bold{S}, \bold{\Sigma}, \bold{\Pi}, \bold{A}, \bold{B}\}</tex>, где <tex>\bold{S} = \{s_1, ..., s_n\}</tex> -- состояния, <tex>\bold{\Sigma} = \{\omega_1, ..., \omega_m\}</tex> -- возможные события, <tex>\bold{\Pi} = \{\pi_1, ..., \pi_n\}</tex> -- начальные вероятности, <tex>\bold{A} = \{a_{ij}\}</tex> -- матрица переходов, а <tex>\bold{B} = \{b_{iki\omega_k}\}</tex> -- вероятность наблюдения события <tex>\omega_k</tex> после перехода в состояние <tex>s_i</tex>.

Алгоритм "вперед-назад" позволяет найти в скрытой Марковской модели вероятность попадания в состояние <tex>s_i</tex> на <tex>t</tex>-ом шаге при последовательности наблюдений <tex>O</tex> и (скрытой) последовательности состояний <tex>X</tex>.=== Вычисление ===

\beta_i(t) \overset{def}{=} P(O_{t,T} | X_t = 1i)</tex>

Нам требуется найти <tex>P(X_t = i | O) = P(X_t = i | O_{1,t-1} \cap O_{t,T})</tex>. Поскольку будущее Марковской цепи не зависит от прошлого, мы можем утверждать, что вероятность того, что мы будем наблюдать события <tex>O_{t,nT}</tex> не зависит от того, что в прошлом мы наблюдали последовательность <tex>O_{1,t-1}</tex>, и, следовательно:

<tex>P(X_t = i | O_{1,t-1} \cap O_{t,T}) = \propto frac{P(X_t = i | O_{1,t-1}) \cdot P(X_t = i | O_{t,T}) }{P(O)} = \frac{\alpha_{i}(t) \cdot \beta_{i}(t)}{P(O)}</tex>

[[КатегорияСледующие <tex>t</tex> посчитаем рекуррентно:Дискретная математика и алгоритмы]][[Категория: Марковские цепи ]]<tex>\alpha_{i}(t+1) = P(O_{1, t} | X_{t+1} = i) = \\= \displaystyle\sum\limits_{j}P(O_{1, t} \cap X_t = j \cap X_t+1 = i) = \\= \displaystyle\sum\limits_{j}P(O_{1, t-1} \cap X_t = j)\cdot P(o_t \cap X_{t+1} = i | O_{1, t-1} \cap X_t = j) = \\= \displaystyle\sum\limits_{j}P(O_{1, t-1} \cap X_t = j)\cdot P(o_t \cap X_{t+1} = i | X_t = j) = \\= \displaystyle\sum\limits_{j}P(O_{1, t-1} \cap X_t = j)\cdot P(X_{t+1} = i | X_{t} = j) \cdot P(o_t | X_{t+1} = i) = \\= \displaystyle\sum\limits_{j}\alpha_j(t)a_{ji}b_{io_t}</tex> Итак, вероятность попасть в состояние <tex>s_i</tex> на </tex>t+1</tex>-ом шаге, учитывая, что после перехода произойдет событие <tex>o_t</tex> будет равна вероятности быть в состоянии <tex>s_j</tex> на <tex>t</tex>-ом шаге, умноженной на вероятность перейти из состояния <tex>s_j</tex> в <tex>s_i</tex>, произведя событие <tex>o_t</tex>