119
правок
Изменения
Нет описания правки
=== Проход вперед ===
Заметим, что в <tex>\{\alpha_s(1)\}</tex> нужно считать равной <tex>\pi_sb_{so_1}</tex>, так как на первом шаге распределение по определению будет равно начальномувероятность получить первое событие из начального распределения.
Для следующих <tex>t</tex> можно вычислить <tex>\alpha_s(t)</tex> рекуррентно:
= \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) = 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>
=== Псевдокод ===
fwd = {}
bkw = {}
for s in S:
fwd[s, 1] = emit_probability[s][observations[1]] * П[s]
bkw[s, len(observations) - 1] = 1
alpha(s, t):
if (s, t) in fwd: return fwd[s, t]
fwd[s, t] = emit_probability[s -> observations[t]] * sum([alpha(j, t-1) * transition_probability[j -> s] for j in S])
return fwd[s, t]
beta(s, t):
if (s, t) in bkw: return bkw[s, t]
bkw[s, t] = sum([beta(j, t+1) * transition_probability[s -> j] * emit_probability[j -> O[t]] for j in S])
return bkw[s, t]
forward_backward(s, t):
return (alpha(s, t)*beta(s, t)) / sum([alpha(j, t)*beta(j, t) for j in S])
