Алгоритм "Вперед-Назад" - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:35:47Z

rollbackEdits.php mass rollback

185.220.100.254 в 04:14, 1 сентября 2022

2022-09-01T04:14:43Z

77.234.212.37: /* Псевдокод */

2018-03-15T07:18:59Z

‎Псевдокод

Ponomarev: /* Псевдокод */

2018-03-11T18:40:25Z

‎Псевдокод

81.24.126.202: /* Псевдокод */

2018-03-11T16:18:48Z

‎Псевдокод

94.19.239.249 в 11:29, 8 марта 2018

2018-03-08T11:29:33Z

94.19.239.249: /* Пример */

2018-03-08T11:16:59Z

‎Пример

94.19.239.249: /* Пример */

2018-03-08T11:13:01Z

‎Пример

94.19.239.249: /* Проход назад */

2018-03-08T11:08:49Z

‎Проход назад

94.19.239.249: /* Вычисление */

2018-03-08T11:08:00Z

‎Вычисление

← Предыдущая		Версия 16:35, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	'''Алгоритм "Вперед-Назад"''' (англ. ''forward–backward algorithm'') {{---}} алгоритм, позволяющий найти в [[Скрытые Марковские модели\|скрытой Марковской модели]] вероятность попадания в состояние <tex>s_i</tex> на <tex>t</tex>-ом шаге при последовательности наблюдений <tex>O</tex> и (скрытой) последовательности состояний <tex>X</tex>.		'''Алгоритм "Вперед-Назад"''' (англ. ''forward–backward algorithm'') {{---}} алгоритм, позволяющий найти в [[Скрытые Марковские модели\|скрытой Марковской модели]] вероятность попадания в состояние <tex>s_i</tex> на <tex>t</tex>-ом шаге при последовательности наблюдений <tex>O</tex> и (скрытой) последовательности состояний <tex>X</tex>.

← Предыдущая		Версия 04:14, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	'''Алгоритм "Вперед-Назад"''' (англ. ''forward–backward algorithm'') {{---}} алгоритм, позволяющий найти в [[Скрытые Марковские модели\|скрытой Марковской модели]] вероятность попадания в состояние <tex>s_i</tex> на <tex>t</tex>-ом шаге при последовательности наблюдений <tex>O</tex> и (скрытой) последовательности состояний <tex>X</tex>.		'''Алгоритм "Вперед-Назад"''' (англ. ''forward–backward algorithm'') {{---}} алгоритм, позволяющий найти в [[Скрытые Марковские модели\|скрытой Марковской модели]] вероятность попадания в состояние <tex>s_i</tex> на <tex>t</tex>-ом шаге при последовательности наблюдений <tex>O</tex> и (скрытой) последовательности состояний <tex>X</tex>.

@@ Строка 65: / Строка 65: @@
     '''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'''
-      '''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():
-      '''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
 == См. также ==

@@ Строка 69: / Строка 69: @@
        f = 0
        '''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
        '''return''' fwd[s, t]
@@ Строка 79: / Строка 79: @@
        b = 0
        '''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
        '''return''' bkw[s, t]
@@ Строка 85: / Строка 85: @@
     '''fun''' forward_backward():
        '''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
        chainProbability = 0

@@ Строка 74: / Строка 74: @@
        '''return''' fwd[s, t]
-    '''fun''' beta(s: '''int''', t: '''int'''): int
+    '''fun''' beta(s: '''int''', t: '''int'''): '''int'''
        '''if''' (s, t) '''in''' bkw
            '''return''' bkw[s, t]

@@ Строка 19: / Строка 19: @@
 Для следующих <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} \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) = \\
@@ Строка 41: / Строка 41: @@
 Теперь найдем вероятность того, что в момент <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 | 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>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>

@@ Строка 51: / Строка 51: @@
 Но вот вас переводят смотреть за камерами наблюдения: теперь вы не можете наблюдать за погодой, но каждый день видите того мужчину. За рабочую неделю вы заметили, что он не принес зонтик лишь в среду. С какой вероятностью во вторник шел дождь?
-По вышесказанному, <tex>P(X_2 = Rain  \mid \{umbrella, umbrella, no, umbrella, umbrella\}) =</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>P(X_2 = Rain  \mid \{umbrella, umbrella, no, umbrella, umbrella\}) = </tex>
 Итак, с вероятностью <tex>\approx 82\%</tex> во вторник шел дождь.

@@ Строка 33: / Строка 33: @@
 <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 \mid X_t = s) \cdot P(o_{t+1} \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>

@@ Строка 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>\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">\dfrac{P(X_t = i | O_{1,t-1}) \cdot P(X_t = i | O_{t,T})}{P(O)}</tex> <tex>=</tex> <tex dpi="160">\dfrac{\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>
 === Проход вперед ===
@@ Строка 20: / Строка 20: @@
 <tex>\alpha_{s}(t) = P(O_{1, t} | 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} = \\
 = 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) = 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} | 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>
@@ Строка 41: / Строка 41: @@
 Теперь найдем вероятность того, что в момент <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">\dfrac{P(X_t = s | O_{1,t-1}) \cdot P(X_t = s | 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>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 | 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>