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

Материал из Викиконспекты
Перейти к: навигация, поиск
(alpha 1)
Строка 3: Строка 3:
 
За <tex>T</tex> шагов в этой модели получилась последовательность наблюдений <tex>O_{1,T} = {o_1, ..., o_T}</tex>.
 
За <tex>T</tex> шагов в этой модели получилась последовательность наблюдений <tex>O_{1,T} = {o_1, ..., o_T}</tex>.
  
Алгоритм "вперед-назад" позволяет найти в скрытой Марковской модели вероятность попадания в состояние <tex>s_i</tex> на <tex>t</tex>-ом шагу, при последовательности наблюдений <tex>O = \{o_1 , ..., o_T\}</tex>.
+
Алгоритм "вперед-назад" позволяет найти в скрытой Марковской модели вероятность попадания в состояние <tex>s_i</tex> на <tex>t</tex>-ом шаге при последовательности наблюдений <tex>O</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>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} | X_t = i) \\
+
<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 = 1)</tex>
 
\beta_i(t) \overset{def}{=} P(O_{t,T} | X_t = 1)</tex>
  
 
Нам требуется найти <tex>P(X_t = i | O) = P(X_t = i | O_{1,t-1} \cap O_{t,T})</tex>. Поскольку будущее Марковской цепи не зависит от прошлого, мы можем утверждать, что вероятность того, что мы будем наблюдать события <tex>O_{t,n}</tex> не зависит от того, что в прошлом мы наблюдали последовательность <tex>O_{1,t-1}</tex>, и, следовательно:
 
Нам требуется найти <tex>P(X_t = i | O) = P(X_t = i | O_{1,t-1} \cap O_{t,T})</tex>. Поскольку будущее Марковской цепи не зависит от прошлого, мы можем утверждать, что вероятность того, что мы будем наблюдать события <tex>O_{t,n}</tex> не зависит от того, что в прошлом мы наблюдали последовательность <tex>O_{1,t-1}</tex>, и, следовательно:
  
<tex dpi="180">P(X_t = i | O) \propto P(X_t = i | O_{1,t-1}) \cdot P(X_t = 1 | O_{t,T}) = \alpha_{i}(t) \cdot \beta_{i}(t)</tex>
+
<tex>P(X_t = i | O_{1,t-1} \cap O_{t,T}) \propto P(X_t = i | O_{1,t-1}) \cdot P(X_t = i | O_{t,T}) = \alpha_{i}(t) \cdot \beta_{i}(t)</tex>
 +
 
 +
 
 +
[[Категория:Дискретная математика и алгоритмы]]
 +
[[Категория: Марковские цепи ]]

Версия 21:14, 13 января 2013

Пусть дана скрытая Марковская модель [math]\lambda = \{\bold{S}, \bold{\Sigma}, \bold{\Pi}, \bold{A}, \bold{B}\}[/math], где [math]\bold{S} = \{s_1, ..., s_n\}[/math] - состояния, [math]\bold{\Sigma} = \{\omega_1, ..., \omega_m\}[/math] - возможные события, [math]\bold{\Pi}[/math] -- начальные вероятности, [math]\bold{A} = \{a_{ij}\}[/math] -- матрица переходов, а [math]\bold{B} = \{b_{ik}\}[/math] -- вероятность наблюдения события [math]\omega_k[/math] после перехода в состояние [math]s_i[/math].

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

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

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

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