Алгоритм Витерби - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:17:32Z

rollbackEdits.php mass rollback

185.86.148.90 в 05:44, 1 сентября 2022

2022-09-01T05:44:17Z

Breaker Zirconia: /* Псевдокод: i -> j; everywhere inside the first 'for' block */

2021-06-10T22:17:19Z

‎Псевдокод: i -> j; everywhere inside the first 'for' block

Breaker Zirconia: /* Псевдокод: j -> i; in the second like of the pseudocode */

2021-06-10T22:05:17Z

‎Псевдокод: j -> i; in the second like of the pseudocode

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

2018-05-18T07:36:22Z

‎Псевдокод

77.234.212.37: /* Алгоритм */

2018-05-18T07:31:06Z

‎Алгоритм

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

2018-05-18T07:29:47Z

‎Псевдокод

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

2018-05-18T07:28:46Z

‎Псевдокод

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

2018-05-17T21:27:28Z

‎Псевдокод

Tindarid: /* Алгоритм */

2018-05-17T21:22:55Z

‎Алгоритм

← Предыдущая		Версия 16:17, 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 Майкл Наки].
−	\|}
−
	== История ==		== История ==
	'''Алгоритм Витерби''' (англ. ''Viterbi algorithm'') был представлен в 1967 году для декодирования сверточных кодов, поступающих через зашумленный канал связи. В 1969 году Омура (Omura) показал, что основу алгоритма Витерби составляет оценка максимума правдоподобия, которая является популярным статистическим методом для создания статистической модели на основе данных и обеспечения оценки параметров модели (т.е. оценка неизвестного параметра максимизацией функции правдоподобия).		'''Алгоритм Витерби''' (англ. ''Viterbi algorithm'') был представлен в 1967 году для декодирования сверточных кодов, поступающих через зашумленный канал связи. В 1969 году Омура (Omura) показал, что основу алгоритма Витерби составляет оценка максимума правдоподобия, которая является популярным статистическим методом для создания статистической модели на основе данных и обеспечения оценки параметров модели (т.е. оценка неизвестного параметра максимизацией функции правдоподобия).

← Предыдущая		Версия 05:44, 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 Майкл Наки].
		+	\|}
		+
	== История ==		== История ==
	'''Алгоритм Витерби''' (англ. ''Viterbi algorithm'') был представлен в 1967 году для декодирования сверточных кодов, поступающих через зашумленный канал связи. В 1969 году Омура (Omura) показал, что основу алгоритма Витерби составляет оценка максимума правдоподобия, которая является популярным статистическим методом для создания статистической модели на основе данных и обеспечения оценки параметров модели (т.е. оценка неизвестного параметра максимизацией функции правдоподобия).		'''Алгоритм Витерби''' (англ. ''Viterbi algorithm'') был представлен в 1967 году для декодирования сверточных кодов, поступающих через зашумленный канал связи. В 1969 году Омура (Omura) показал, что основу алгоритма Витерби составляет оценка максимума правдоподобия, которая является популярным статистическим методом для создания статистической модели на основе данных и обеспечения оценки параметров модели (т.е. оценка неизвестного параметра максимизацией функции правдоподобия).

@@ Строка 56: / Строка 56: @@
 Функция возвращает вектор <tex>\mathtt{X}</tex> : последовательность номеров наиболее вероятных состояний, которые привели к данным наблюдениям.
      <tex>\mathrm{Viterbi}(\mathtt {O}, \mathtt {S},  \mathtt {P} , \mathtt {Y}, \mathtt {A}, \mathtt {B})</tex>
-         '''for''' <tex>\mathtt{i} = 1</tex> '''to''' <tex>\mathtt {K}</tex>
+         '''for''' <tex>\mathtt{j} = 1</tex> '''to''' <tex>\mathtt {K}</tex>
-             <tex>\mathtt{TState}[\mathtt{i}, 1] = \mathtt{P}[\mathtt{i}] * \mathtt{B}[\mathtt{i}, \mathtt{Y}[1]]</tex>
+             <tex>\mathtt{TState}[\mathtt{j}, 1] = \mathtt{P}[\mathtt{j}] * \mathtt{B}[\mathtt{j}, \mathtt{Y}[1]]</tex>
-             <tex>\mathtt{TIndex}[\mathtt{i}, 1] = 0</tex>
+             <tex>\mathtt{TIndex}[\mathtt{j}, 1] = 0</tex>
          '''for''' <tex>\mathtt{i} = 2</tex> '''to''' <tex>\mathtt {T}</tex>
              '''for''' <tex>\mathtt{j} = 1</tex> '''to''' <tex>\mathtt {K}</tex>

@@ Строка 56: / Строка 56: @@
 Функция возвращает вектор <tex>\mathtt{X}</tex> : последовательность номеров наиболее вероятных состояний, которые привели к данным наблюдениям.
      <tex>\mathrm{Viterbi}(\mathtt {O}, \mathtt {S},  \mathtt {P} , \mathtt {Y}, \mathtt {A}, \mathtt {B})</tex>
-         '''for''' <tex>\mathtt{j} = 1</tex> '''to''' <tex>\mathtt {K}</tex>
+         '''for''' <tex>\mathtt{i} = 1</tex> '''to''' <tex>\mathtt {K}</tex>
              <tex>\mathtt{TState}[\mathtt{i}, 1] = \mathtt{P}[\mathtt{i}] * \mathtt{B}[\mathtt{i}, \mathtt{Y}[1]]</tex>
              <tex>\mathtt{TIndex}[\mathtt{i}, 1] = 0</tex>

@@ Строка 61: / Строка 61: @@
          '''for''' <tex>\mathtt{i} = 2</tex> '''to''' <tex>\mathtt {T}</tex>
              '''for''' <tex>\mathtt{j} = 1</tex> '''to''' <tex>\mathtt {K}</tex>
-                 <tex>\mathtt{TIndex}[\mathtt{j}, \mathtt{i}] = \arg\max_{1 \leqslant \mathtt{k}\leqslant \mathtt{K}} \limits (\mathtt{TState}[\mathtt{k}, \mathtt{i} - 1] * \mathtt{A}[\mathtt{k}, \mathtt{j}] * \mathtt{B}[\mathtt{j}, \mathtt{Y}[\mathtt{i}]])</tex>
+                 <tex>\mathtt{TIndex}[\mathtt{j}, \mathtt{i}] = \mathtt{k} \in \mathtt{K} : (\mathtt{TState}[\mathtt{k}, \mathtt{i} - 1] * \mathtt{A}[\mathtt{k}, \mathtt{j}] * \mathtt{B}[\mathtt{j}, \mathtt{Y}[\mathtt{i}]]) \leadsto \max</tex>
                  <tex>\mathtt{TState}[\mathtt{j}, \mathtt{i}] = \mathtt{TState}[\mathtt{TIndex}[\mathtt{j}, \mathtt{i}], \mathtt{i} - 1] * \mathtt{A}[\mathtt{k}, \mathtt{j}] * \mathtt{B}[\mathtt{j}, \mathtt{Y}[\mathtt{i}]]</tex>
          <tex>\mathtt{X}[\mathtt{T}] = \arg\max_{1 \leqslant \mathtt{k}\leqslant \mathtt{K}} \limits (\mathtt{TState}[\mathtt{k}, \mathtt{T}])</tex>

@@ Строка 50: / Строка 50: @@
 *<tex>\mathtt{V_{t,k}} = \max\limits_{\mathtt{x} \in \mathtt{S}}\left(\mathrm{P}(\mathtt{y_t} \mid \mathtt{k}) \cdot \mathtt{A_{x,k}} \cdot \mathtt{V_{t-1,x}}\right)</tex>
 Где <tex>\mathtt{V_{t,k}}</tex> это вероятность наиболее вероятной последовательности, которая ответственна за первые <tex>\mathtt{t}</tex> наблюдений, у которых <tex>\mathtt{k}</tex> является завершающим состоянием. Путь Витерби может быть получен сохранением обратных указателей, которые помнят какое состояние было использовано во втором равенстве. Пусть <tex>\mathrm{Ptr}(\mathtt{k},\mathtt{t})</tex> {{---}} функция, которая возвращает значение <tex>\mathtt{x}</tex>, использованное для подсчета <tex>\mathtt{V_{t,k}}</tex> если <tex>\mathtt{t} > 1</tex>, или <tex>\mathtt{k}</tex> если <tex>\mathtt{t}=1</tex>.  Тогда:
-*<tex>\mathtt{x_T} = \mathtt{x} \in \mathtt{S} : \mathtt{V_{T,x}} \rightarrow \max</tex>
+*<tex>\mathtt{x_T} = \mathtt{x} \in \mathtt{S} : \mathtt{V_{T,x}} \leadsto \max</tex>
 *<tex>\mathtt{x_{t-1}} = \mathrm{Ptr}(\mathtt{x_t},\mathtt{t})</tex>