Изменения

Пусть дана скрытая Марковская модель <tex>\lambda = \{\bold{S}, \bold{\Sigma}, \bold{\Pi}, \bold{A}, \bold{B}\}</tex>, где <tex>\bold{S} = \{s_1, ..'''Алгоритм "Вперед-Назад"''' (англ., s_n\}</tex> - состояния, <tex>\bold''forward–backward algorithm'') {\Sigma} = \{\omega_1, ..., \omega_m\}</tex> - возможные события, <tex>\bold{\Pi}</tex> -- начальные вероятности}} алгоритм, позволяющий найти в [[Скрытые Марковские модели|скрытой Марковской модели]] вероятность попадания в состояние <tex>\bold{A} = \{a_{ij}\}s_i</tex> -- матрица переходов, а на <tex>\bold{B} = \{b_{ik}\}t</tex> -- вероятность наблюдения события ом шаге при последовательности наблюдений <tex>\omega_kO</tex> после перехода в состояние и (скрытой) последовательности состояний <tex>s_iX</tex>.

== Вычисление ==Пусть дана скрытая Марковская модель <tex>\lambda = \{S, \Omega, \Pi, A, B\}</tex>, где <tex>S = \{s_1,\ldots, s_n\}</tex> {{---}} состояния, <tex>\Omega = \{\omega_1,\ldots, \omega_m\}</tex> {{---}} возможные события, <tex>\Pi = \{\pi_1,\ldots, \pi_n\}</tex> {{---}} начальные вероятности, <tex>A = \{a_{ij}\}</tex> {{---}} матрица переходов, а <tex>B = \{b_{i\omega_k}\}</tex> {{---}} вероятность наблюдения события <tex>\omega_k</tex> после перехода в состояние <tex>s_i</tex>.За <tex>T</tex> шагов в этой модели получилась последовательность наблюдений <tex>O_{1,T} = {o_1, ...\ldots, o_T}</tex>.

Алгоритм "вперед-назад" позволяет найти в скрытой Марковской модели вероятность попадания в состояние <tex>s_i</tex> на <tex>t</tex>-ом шагу, при последовательности наблюдений <tex>O = \{o_1 , ..., o_T\}</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 dpi="180">\alpha_{i}(t) \overset{def}{=} P(O_{1, t-1} | \mid X_t = i) \\\beta_i(t) \overset{def}{=} P(O_{t,T} | \mid X_t = 1i)</tex>

Нам требуется найти <tex>P(X_t = i | \mid O) = P(X_t = i | \mid 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 \mid O_{1,t-1} \cap O_{t,T}) =</tex> <tex dpi="180160">\dfrac{P(X_t = i | \mid O_{1,t-1}) \cdot P(X_t = i \mid O_{t,T})}{P(O)}</tex> <tex>=</tex> <tex dpi="160">\dfrac{\alpha_{i}(t) \cdot \beta_{i}(t)}{P(O) }</tex> === Проход вперед ===Заметим, что в <tex>\{\alpha_s(1)\}</tex> нужно считать равной <tex>\pi_s b_{so_1}</tex>, как вероятность получить первое событие из начального распределения. Для следующих <tex>t</tex> можно вычислить <tex>\alpha_s(t)</tex> рекуррентно: <tex>\propto alpha_{s}(t) = P(O_{1, t} \mid X_t = i | s_i) = \\= \displaystyle\sum\limits_{j \in S} P(O_{1, t} \mid X_t = s \cap X_{t-1} = j) = \\= \displaystyle\sum\limits_{j \in S} P(O_{1,t-1}\mid X_{t-1} = j) \cdot P(X_t = s \mid X_{t-1} = j) \cdot P(O_t = o_t \mid 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 - 1)</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} \mid X_t = s) = \\= \displaystyle\sum\limits_{j \in S} P(O_{t+1,T} \mid X_{t+1} = j) \cdot P(X_{t+1} = j \mid X_t = s) \cdot P(o_{t+1} \mid X_t = s) = \\= \displaystyle\sum\limits_{j \in S} \beta_j(t+1) \cdot a_{sj} \cdot b_{jo_{t+1}}</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>P(X_t = s \mid O) = P(X_t = s \mid O_{1,t-1} \cap O_{t,T}) =</tex> <tex dpi="160">\dfrac{P(X_t = s \mid O_{1 | ,t-1}) \cdot P(X_t = s \mid O_{t,T}) }{P(O)}</tex> <tex>=</tex> <tex dpi= "160">\dfrac{\alpha_{s}(t) \cdot \beta_{s}(t)}{P(O)}</tex> <tex>=</tex> <tex>=</tex> <tex dpi="160">\dfrac{\alpha_s(t)\cdot \beta_s(t)}{\sum_{i\in S}\alpha_s(t)\cdot \beta_s(t)}</tex> == Пример ==[[Файл:HMM-Forward-Backward-Example.png|thumb|right|Пример СММ]]Пусть ваша жизнь не удалась и вам пришлось работать охранником в холле офисного здания. Каждое утро вы наблюдали за тем, как один и тот же мужчина либо приносил, либо не приносил зонтик в зависимости от погоды. Увлекаясь статистикой, вы выяснили, что за день погода может поменяться с вероятностью <tex>0.3</tex>; если на улице идет дождь, то мужчина приносит зонтик с вероятностью <tex>0.9</tex>, а если солнечно {{---}} то с вероятностью <tex>0.2</tex> (пример справа). Но вот вас переводят смотреть за камерами наблюдения: теперь вы не можете наблюдать за погодой, но каждый день видите того мужчину. За рабочую неделю вы заметили, что он не принес зонтик лишь в среду. С какой вероятностью во вторник шел дождь? По вышесказанному, <tex>P(X_2 = Rain \mid \{umbrella, umbrella, no, umbrella, umbrella\}) = </tex>  <tex>=</tex> <tex dpi="160">\dfrac{\alpha_{Rain}(2) \cdot \beta_{Rain}(2)}{\sum_{i\in \{Rain, Sun\}}\alpha_i(2)\cdot \beta_i(2)}</tex> <tex>=</tex> <tex dpi="160">\dfrac{\alpha_{Rain}(2)\cdot \beta_{Rain}(2)}{\alpha_{Rain}(t2)\cdot \beta_{Rain}(2) + \alpha_{Sun}(2)\cdot \beta_{Sun}(2)}</tex><tex>\approx 0.820</tex>. Итак, с вероятностью <tex>\approx 82\%</tex> во вторник шел дождь. == Псевдокод == <font color=darkgreen> // fwd, bkw {{---}} матрицы размера |S|*T, которым во время работы присваиваются промежуточные результаты alpha и beta // probabilities {{---}} матрица размера |S|*T, в которую заносится ответ // S - массив состояний, П - массив начальных вероятностей, O - последовательность наблюдений </font> '''fun''' alpha(s: '''int''', t: '''int'''): '''int''' '''if''' (s, t) '''in''' fwd '''return''' fwd[s, t] f = 0 '''for''' j '''in''' S f += alpha(j, t - 1) * transitionProbability[j, s] f *= emitProbability[s, observations[t]] fwd[s, t] = f '''return''' fwd[s, t] '''fun''' beta(s: '''int''', t: '''int'''): '''int''' '''if''' (s, t) '''in''' bkw '''return''' bkw[s, t] b = 0 '''for''' j '''in''' S b += beta(j, t + 1) * transitionProbability[s, j] * emitProbability[j, O[t + 1]] bkw[s, t] = b '''return''' bkw[s, t] '''fun''' forward_backward(): '''for''' s '''in''' S fwd[s, 1] = emitProbability[s, observations[1]] * П[s] bkw[s, observations.length - 1] = 1 chainProbability = 0 '''for''' j '''in''' S chainProbability += alpha(j, 1) * beta(j, 1) '''for''' s '''in''' S '''for''' t '''in''' [1, T] probabilities[s, t] = (alpha(s, t) * beta(s, t)) / chainProbability == См. также == *[[Скрытые Марковские модели]]*[[Алгоритм Баума-Велша]]*[[Алгоритм Витерби]] == Источники информации ==* [[wikipedia:Forward–backward_algorithm|Wikipedia {{---}} Forward–backward algorithm]]* [http://web.cecs.pdx.edu/~mperkows/JUNE1a/010.Intorduction-to-HMM.ppt Forward/Backward Algorithms for Hidden Markov Models]* [http://faculty.washington.edu/fxia/courses/LING572/forward_backward.ppt Forward-backward algorithm, Fei Xia, University of Washington] [[Категория: Дискретная математика и алгоритмы]][[Категория: Марковские цепи]]