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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 10 промежуточных версий 5 участников)
Строка 7: Строка 7:
 
Пусть в момент <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>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) \\
+
<tex>\alpha_{i}(t) \overset{def}{=} P(O_{1, t-1} \mid X_t = i) \\
\beta_i(t) \overset{def}{=} P(O_{t,T} | X_t = i)</tex>
+
\beta_i(t) \overset{def}{=} P(O_{t,T} \mid 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 \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 | O_{1,t-1} \cap O_{t,T}) =</tex> <tex dpi="160">\frac{P(X_t = i | O_{1,t-1}) \cdot P(X_t = i | O_{t,T})}{P(O)}</tex> <tex>=</tex> <tex dpi="160">\frac{\alpha_{i}(t) \cdot \beta_{i}(t)}{P(O)}</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>
  
 
=== Проход вперед ===
 
=== Проход вперед ===
Строка 19: Строка 19:
 
Для следующих <tex>t</tex> можно вычислить <tex>\alpha_s(t)</tex>  рекуррентно:
 
Для следующих <tex>t</tex> можно вычислить <tex>\alpha_s(t)</tex>  рекуррентно:
  
<tex>\alpha_{s}(t) = P(O_{1, t} | X_t = s_i) = \\
+
<tex>\alpha_{s}(t) = P(O_{1, t} \mid 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} \mid 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} 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} = \\
 
= \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>
 
= b_{so_t} \cdot \displaystyle\sum\limits_{j \in S} \alpha_{j}(t-1) \cdot a_{js}</tex>
Строка 32: Строка 32:
 
Предыдущие <tex>\beta_s(t)</tex> считаются рекуррентно:
 
Предыдущие <tex>\beta_s(t)</tex> считаются рекуррентно:
  
<tex>\beta_s(t) = P(O_{t, T} | X_t = s) = \\
+
<tex>\beta_s(t) = P(O_{t, T} \mid 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+1} | 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>
 
= \displaystyle\sum\limits_{j \in S} \beta_j(t+1) \cdot a_{sj} \cdot b_{jo_{t+1}}</tex>
  
Строка 41: Строка 41:
 
Теперь найдем вероятность того, что в момент <tex>t</tex> цепь будет в состоянии <tex>s</tex>:
 
Теперь найдем вероятность того, что в момент <tex>t</tex> цепь будет в состоянии <tex>s</tex>:
  
<tex>P(X_t = s | O) = P(X_t = s | O_{1,t-1} \cap O_{t,T}) =</tex> <tex dpi="160">\frac{P(X_t = s | O_{1,t-1}) \cdot P(X_t = s | O_{t,T})}{P(O)}</tex> <tex>=</tex> <tex dpi="160">\frac{\alpha_{s}(t) \cdot \beta_{s}(t)}{P(O)}</tex> <tex>=</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">\frac{\alpha_s(t)\cdot \beta_s(t)}{\sum_{i \in S}\alpha_s(t)\cdot \beta_s(t)}</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>
  
 
== Пример ==
 
== Пример ==
Строка 51: Строка 51:
 
Но вот вас переводят смотреть за камерами наблюдения: теперь вы не можете наблюдать за погодой, но каждый день видите того мужчину. За рабочую неделю вы заметили, что он не принес зонтик лишь в среду. С какой вероятностью во вторник шел дождь?
 
Но вот вас переводят смотреть за камерами наблюдения: теперь вы не можете наблюдать за погодой, но каждый день видите того мужчину. За рабочую неделю вы заметили, что он не принес зонтик лишь в среду. С какой вероятностью во вторник шел дождь?
  
По вышесказанному, <tex>P(X_2 = Rain | \{umbrella, umbrella, no, umbrella, umbrella\}) =</tex> <tex dpi="160">\frac{\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">\frac{\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>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> во вторник шел дождь.
 
Итак, с вероятностью <tex>\approx 82\%</tex> во вторник шел дождь.
Строка 63: Строка 65:
 
    
 
    
 
   '''fun''' alpha(s: '''int''', t: '''int'''): '''int'''
 
   '''fun''' alpha(s: '''int''', t: '''int'''): '''int'''
      '''if''' (s, t) '''in''' fwd
+
      '''if''' (s, t) '''in''' fwd
          '''return''' fwd[s, t]
+
          '''return''' fwd[s, t]
      f = 0
+
      f = 0
      '''for''' j '''in''' S
+
      '''for''' j '''in''' S
          f += alpha(j, t - 1) * transitionProbability[j][s]
+
          f += alpha(j, t - 1) * transitionProbability[j, s]
      f *= emitProbability[s][observations[t]]
+
      f *= emitProbability[s, observations[t]]
      fwd[s, t] = f
+
      fwd[s, t] = f
      '''return''' fwd[s, t]
+
      '''return''' fwd[s, t]
 
        
 
        
   '''fun''' beta(s: '''int''', t: '''int'''): int
+
   '''fun''' beta(s: '''int''', t: '''int'''): '''int'''
      '''if''' (s, t) '''in''' bkw
+
      '''if''' (s, t) '''in''' bkw
          '''return''' bkw[s, t]
+
          '''return''' bkw[s, t]
      b = 0
+
      b = 0
      '''for''' j '''in''' S
+
      '''for''' j '''in''' S
          b += beta(j, t + 1) * transitionProbability[s][j] * emitProbability[j][O[t + 1]]
+
          b += beta(j, t + 1) * transitionProbability[s, j] * emitProbability[j, O[t + 1]]
      bkw[s, t] = b
+
      bkw[s, t] = b
      '''return''' bkw[s, t]
+
      '''return''' bkw[s, t]
 
        
 
        
 
   '''fun''' forward_backward():
 
   '''fun''' forward_backward():
      '''for''' s '''in''' S
+
      '''for''' s '''in''' S
          fwd[s, 1] = emitProbability[s][observations[1]] * П[s]
+
          fwd[s, 1] = emitProbability[s, observations[1]] * П[s]
          bkw[s, observations.length - 1] = 1
+
          bkw[s, observations.length - 1] = 1
      chainProbability = 0
+
      chainProbability = 0
      '''for''' j '''in''' S
+
      '''for''' j '''in''' S
          chainProbability += alpha(j, 1) * beta(j, 1)
+
          chainProbability += alpha(j, 1) * beta(j, 1)
      '''for''' s '''in''' S
+
      '''for''' s '''in''' S
          '''for''' t '''in''' [1, T]
+
          '''for''' t '''in''' [1, T]
              probabilities[s, t] = (alpha(s, t) * beta(s, t)) / chainProbability
+
              probabilities[s, t] = (alpha(s, t) * beta(s, t)) / chainProbability
  
 
== См. также ==
 
== См. также ==

Текущая версия на 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

См. также

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