Алгоритм "Вперед-Назад" — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 49 промежуточных версий 8 участников)
Строка 1: Строка 1:
=== Общие сведения ===
+
'''Алгоритм "Вперед-Назад"''' (англ. ''forward–backward algorithm'') {{---}} алгоритм, позволяющий найти в [[Скрытые Марковские модели|скрытой Марковской модели]] вероятность попадания в состояние <tex>s_i</tex> на <tex>t</tex>-ом шаге при последовательности наблюдений <tex>O</tex> и (скрытой) последовательности состояний <tex>X</tex>.
Алгоритм "вперед-назад" позволяет найти чему будет равна вероятность попадания в состояние <tex>s_i</tex> на <tex>t</tex>-ом шагу, при последовательности наблюдений <tex>O = {o_1 , ..., o_T}</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>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} \mid X_t = i) \\
 +
\beta_i(t) \overset{def}{=} P(O_{t,T} \mid X_t = i)</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,T}</tex> не зависит от того, что в прошлом мы наблюдали последовательность <tex>O_{1,t-1}</tex>, и, следовательно:
 +
 
 +
<tex>P(X_t = i \mid O_{1,t-1} \cap O_{t,T}) =</tex> <tex dpi="160">\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>\alpha_{s}(t) = P(O_{1, t} \mid X_t = 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}(2)\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]
 +
 
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Марковские цепи]]

Текущая версия на 19:35, 4 сентября 2022

Алгоритм "Вперед-Назад" (англ. forward–backward algorithm) — алгоритм, позволяющий найти в скрытой Марковской модели вероятность попадания в состояние [math]s_i[/math] на [math]t[/math]-ом шаге при последовательности наблюдений [math]O[/math] и (скрытой) последовательности состояний [math]X[/math].

Вычисление

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

Пусть в момент [math]t[/math] мы оказались в состоянии [math]i[/math]: [math]X_t = i[/math]. Назовем [math]\alpha_{i}(t)[/math] вероятность того, что при этом во время переходов образовалась последовательность наблюдений [math]O_{1,t-1}[/math], а [math]\beta_{i}(t)[/math] — вероятность того, что после этого состояния мы будем наблюдать последовательность наблюдений [math]O_{t,T}[/math]:

[math]\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 = i)[/math]

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

[math]P(X_t = i \mid O_{1,t-1} \cap O_{t,T}) =[/math] [math]\dfrac{P(X_t = i \mid O_{1,t-1}) \cdot P(X_t = i \mid O_{t,T})}{P(O)}[/math] [math]=[/math] [math]\dfrac{\alpha_{i}(t) \cdot \beta_{i}(t)}{P(O)}[/math]

Проход вперед

Заметим, что в [math]\{\alpha_s(1)\}[/math] нужно считать равной [math]\pi_s b_{so_1}[/math], как вероятность получить первое событие из начального распределения.

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

[math]\alpha_{s}(t) = P(O_{1, t} \mid X_t = 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}[/math]

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

Проход назад

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

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

[math]\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}}[/math]

Сглаживание вероятности

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

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

[math]P(X_t = s \mid O) = P(X_t = s \mid O_{1,t-1} \cap O_{t,T}) =[/math] [math]\dfrac{P(X_t = s \mid O_{1,t-1}) \cdot P(X_t = s \mid O_{t,T})}{P(O)}[/math] [math]=[/math] [math]\dfrac{\alpha_{s}(t) \cdot \beta_{s}(t)}{P(O)}[/math] [math]=[/math]

[math]=[/math] [math]\dfrac{\alpha_s(t)\cdot \beta_s(t)}{\sum_{i \in S}\alpha_s(t)\cdot \beta_s(t)}[/math]

Пример

Пример СММ

Пусть ваша жизнь не удалась и вам пришлось работать охранником в холле офисного здания. Каждое утро вы наблюдали за тем, как один и тот же мужчина либо приносил, либо не приносил зонтик в зависимости от погоды. Увлекаясь статистикой, вы выяснили, что за день погода может поменяться с вероятностью [math]0.3[/math]; если на улице идет дождь, то мужчина приносит зонтик с вероятностью [math]0.9[/math], а если солнечно — то с вероятностью [math]0.2[/math] (пример справа).

Но вот вас переводят смотреть за камерами наблюдения: теперь вы не можете наблюдать за погодой, но каждый день видите того мужчину. За рабочую неделю вы заметили, что он не принес зонтик лишь в среду. С какой вероятностью во вторник шел дождь?

По вышесказанному, [math]P(X_2 = Rain \mid \{umbrella, umbrella, no, umbrella, umbrella\}) = [/math]

[math]=[/math] [math]\dfrac{\alpha_{Rain}(2)\cdot \beta_{Rain}(2)}{\sum_{i \in \{Rain, Sun\}}\alpha_i(2)\cdot \beta_i(2)}[/math] [math]=[/math] [math]\dfrac{\alpha_{Rain}(2)\cdot \beta_{Rain}(2)}{\alpha_{Rain}(2)\cdot \beta_{Rain}(2) + \alpha_{Sun}(2)\cdot \beta_{Sun}(2)}[/math] [math]\approx 0.820[/math].

Итак, с вероятностью [math]\approx 82\%[/math] во вторник шел дождь.

Псевдокод

// fwd, bkw — матрицы размера |S|*T, которым во время работы присваиваются промежуточные результаты alpha и beta 
// probabilities — матрица размера |S|*T, в которую заносится ответ
// S - массив состояний, П - массив начальных вероятностей, O - последовательность наблюдений  
  
  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

См. также

Источники информации