Просмотр исходного текста страницы Алгоритм "Вперед-Назад"

Пусть дана скрытая Марковская модель <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_{i\omega_k}\}</tex> -- вероятность наблюдения события <tex>\omega_k</tex> после перехода в состояние <tex>s_i</tex>.

За <tex>T</tex> шагов в этой модели получилась последовательность наблюдений <tex>O_{1,T} = {o_1, ..., o_T}</tex>.

Алгоритм "вперед-назад" позволяет найти в скрытой Марковской модели вероятность попадания в состояние <tex>s_i</tex> на <tex>t</tex>-ом шаге при последовательности наблюдений <tex>O</tex> и (скрытой) последовательности состояний <tex>X</tex>.
== Вычисление ==
Пусть в момент <tex>t</tex> мы оказались в состоянии <tex>i</tex>: <tex>X_t = i</tex>. Назовем <tex>\alpha_{i}(t)</tex> вероятность того, что при этом во время переходов образовалась последовательность наблюдений <tex>O_{1,t-1}</tex>, а <tex>\beta_{i}(t)</tex> — вероятность того, что после этого состояния мы будем наблюдать последовательность наблюдений <tex>O_{t,T}</tex>:

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

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

<tex>P(X_t = i | O_{1,t-1} \cap O_{t,T}) = \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>\{\alpha_s(1)\}</tex> нужно считать равной <tex>\pi_s</tex>, так как на первом шаге распределение по определению будет равно начальному.

Для следующих <tex>t</tex> можно вычислить <tex>\alpha_s(t)</tex>  рекуррентно:

<tex>\alpha_{s}(t) = P(O_{1, t} | X_t = s_i) = \\
= \displaystyle\sum\limits_{j \in S} P(O_{1, t} | X_t = s \cap X_{t-1} = j) = \\
= \displaystyle\sum\limits_{j \in S} P(O_{1, t-1} | X_{t-1} = j) \cdot P(X_t = s | X_{t-1} = j) \cdot P(O_t = o_t | X_t = s) = \\
= \displaystyle\sum\limits_{j \in S} \alpha_{j}(t-1) \cdot a_{js} \cdot b_{so_t} = \\
= b_{so_t} \cdot \displaystyle\sum\limits_{j \in S} \alpha_{j}(t-1) \cdot a_{js}</tex>

Итак, вероятность попасть в состояние <tex>s</tex> на <tex>t</tex>-ом шаге, учитывая, что после перехода произойдет событие <tex>o_t</tex> будет равна вероятности быть в состоянии <tex>j</tex> на <tex>t</tex>-ом шаге, умноженной на вероятность перейти из состояния <tex>j</tex> в <tex>s</tex>, произведя событие <tex>o_t</tex> для всех <tex>j \in S</tex>.

=== Проход назад ===
Аналогично, <tex>\beta_s(T+1) = 1</tex>, так как произвольная цепочка наблюдений будет произведена, какими бы ни были состояния.

Предыдущие <tex>\beta_s(t)</tex> считаются рекуррентно:

<tex>\beta_s(t) = P(O_{t, T} | X_t = s) = \\
= \displaystyle\sum\limits_{j \in S} P(O_{t+1,T} | X_{t+1} = j) \cdot P(X_{t+1} = j | X_t = s) \cdot P(o_t | X_t = s) = \\
= \displaystyle\sum\limits_{j \in S} \beta_j(t+1) \cdot a_{sj} \cdot b_{jo_t}</tex>

=== Сглаживание вероятности ===
Итак, для произвольного состояния <tex>s</tex> в произвольный шаг <tex>t</tex> теперь известна вероятность того, что на пути к нему была произведена последовательность <tex>O_{1,t}</tex> и вероятность того, что после него будет произведена последовательность <tex>O_{t+1,T}</tex>. Чтобы найти вероятность того, что будет произведена цепочка событий, найти <tex>P(O)</tex>, нужно просуммировать произведение обеих вероятностей для всех состояний при произвольном шаге t: <tex>P(O) = \sum_{s \in S} \alpha_s(t)\beta_s(t)</tex>.

Теперь найдем вероятность того, что в момент <tex>t</tex> цепь будет в состоянии <tex>s</tex>:

<tex dpi="180">P(X_t = s | O_{1,t-1} \cap O_{t,T}) = \frac{P(X_t = s | O_{1,t-1}) \cdot P(X_t = s | O_{t,T})}{P(O)} = \frac{\alpha_{s}(t) \cdot \beta_{s}(t)}{P(O)} = \\
= \frac{\alpha_s(t)\cdot \beta_s(t)}{\sum_{i \in S}\alpha_s(t)\cdot \beta_s(t)}</tex>