Алгоритм вперед-назад

алгоритм вперед-назад - это алгоритм вывода для скрытых марковских моделей, которые вычисляют задние маргиналы всех скрытых переменных состояния с учетом последовательности наблюдений / выбросов $o\; 1:\; T:\; =\; o\; 1,\dots ,\; o\; T\; \{\backslash \; displaystyle\; o\_\; \{1:\; T\}:\; =\; o\_\; \{1\},\; \backslash \; dots,\; o\_\; \{T\}\}$, т.е. вычисляет для всех скрытых переменных состояния $X\; t\; \in \; \{X\; 1,\dots ,\; XT\}\; \{\backslash \; displaystyle\; X\_\; \{t\}\; \backslash \; in\; \backslash \; \{X\_\; \{1\},\; \backslash \; dots,\; X\_\; \{T\}\; \backslash \}\}$, распределение $P\; (Икс\; t\; |\; о\; 1:\; T)\; \{\backslash \; Displaystyle\; P\; (X\_\; \{t\}\; \backslash \; |\; \backslash \; o\_\; \{1:\; T\})\}$. Эта задача логического вывода обычно называется сглаживанием. Алгоритм использует принцип динамического программирования для эффективного вычисления значений, необходимых для получения апостериорных маргинальных распределений за два прохода. Первый проход идет вперед во времени, а второй - назад; отсюда и название «алгоритм вперед-назад».

Термин "алгоритм вперед-назад" также используется для обозначения любого алгоритма, принадлежащего к общему классу алгоритмов, которые работают с моделями последовательности в прямом-обратном порядке. В этом смысле описания в оставшейся части этой статьи относятся только к одному конкретному экземпляру этого класса.

• 1 Обзор
• 2 Прямые вероятности
• 3 Обратные вероятности
• 4 Пример
• 5 Производительность
• 6 Псевдокод
• 7 Пример Python
• 8 См. Также
• 9 Ссылки
• 10 Внешние ссылки

На первом проходе алгоритм вперед-назад вычисляет набор прямых вероятностей, которые обеспечивают для всех $t\; \in \; \{1,\dots ,\; T\}\; \{\backslash \; displaystyle\; t\; \backslash \; in\; \backslash \; \{1,\; \backslash \; dots,\; T\; \backslash \}\}$, вероятность попасть в какое-либо конкретное состояние с учетом первого $t\; \{\backslash \; displaystyle\; t\}$наблюдения в последовательности, то есть $P\; (X\; t\; |\; o\; 1:\; t)\; \{\backslash \; displaystyle\; P\; (X\_\; \{t\}\; \backslash \; |\; \backslash \; o\_\; \{1:\; t\})\}$. Во втором проходе алгоритм вычисляет набор обратных вероятностей, которые обеспечивают вероятность наблюдения оставшихся наблюдений при любой начальной точке $t\; \{\backslash \; displaystyle\; t\}$, то есть $P\; (ot\; +\; 1:\; Т\; |\; Икс\; t)\; \{\backslash \; Displaystyle\; P\; (o\_\; \{t\; +\; 1:\; T\}\; \backslash \; |\; \backslash \; X\_\; \{t\})\}$. Затем эти два набора распределений вероятностей можно объединить для получения распределения по состояниям в любой конкретный момент времени с учетом всей последовательности наблюдений:

$P\; (X\; t\; |\; o\; 1:\; T)\; =\; P\; (X\; t\; |\; o\; 1:\; t,\; ot\; +\; 1:\; T)\; \propto \; п\; (ot\; +\; 1:\; T\; |\; X\; t)\; P\; (X\; t\; |\; o\; 1:\; t)\; \{\backslash \; displaystyle\; P\; (X\_\; \{t\}\; \backslash \; |\; \backslash \; o\_\; \{1:\; T\})\; =\; P\; (X\_\; \{t\}\; \backslash \; |\; \backslash \; o\_\; \{1:\; t\},\; o\_\; \{t\; +\; 1:\; T\})\; \backslash \; propto\; P\; (o\_\; \{t\; +\; 1:\; T\}\; \backslash \; |\; \backslash \; X\_\; \{t\})\; P\; (X\_\; \{t\; \}\; |\; o\_\; \{1:\; t\})\}$

Последний шаг следует из применения правила Байеса и условной независимости для $ot\; +\; 1:\; T\; \{\backslash \; displaystyle\; o\_\; \{t\; +\; 1:\; T\}\}$и $o\; 1:\; t\; \{\backslash \; displaystyle\; o\_\; \{1:\; t\}\}$с учетом $X\; t\; \{\backslash \; displaystyle\; X\_\; \{t\}\}$.

Как описано выше, алгоритм включает три этапа:

1. вычисление прямых вероятностей
2. вычисление обратных вероятностей
3. вычисление сглаженных значений.

прямое и Обратные шаги также могут называться «прямой проход сообщения» и «обратный проход сообщения» - эти термины связаны с передачей сообщения, используемой в целом распространение веры приближается. Для каждого отдельного наблюдения в последовательности вычисляются вероятности, которые будут использоваться для вычислений при следующем наблюдении. Шаг сглаживания можно рассчитать одновременно во время обратного прохода. Этот шаг позволяет алгоритму учитывать любые прошлые наблюдения за выходными данными для вычисления более точных результатов.

Алгоритм прямого-обратного можно использовать для поиска наиболее вероятного состояния в любой момент времени. Однако его нельзя использовать для поиска наиболее вероятной последовательности состояний (см. алгоритм Витерби ).

В нижеследующем описании будут использоваться матрицы значений вероятностей, а не распределения вероятностей, хотя в целом алгоритм прямого-обратного может применяться как к непрерывным, так и к дискретным вероятностным моделям.

Мы преобразуем распределения вероятностей, относящиеся к данной скрытой марковской модели, в матричную запись следующим образом. Вероятности перехода $P\; (X\; t\; \mid \; X\; t\; -\; 1)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{P\}\; (X\_\; \{t\}\; \backslash \; mid\; X\_\; \{t-1\})\}$данной случайной величины $X\; t\; \{\backslash \; displaystyle\; X\_\; \{t\}\}$, представляющий все возможные состояния в скрытой марковской модели, будет представлен матрицей $T\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{T\}\}$где индекс столбца $j\; \{\backslash \; displaystyle\; j\}$будет представлять целевое состояние, а индекс строки $i\; \{\backslash \; displaystyle\; i\}$представляет начальное состояние. Переход из состояния вектора-строки $\pi \; t\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{\backslash \; pi\; \_\; \{t\}\}\}$в состояние инкрементного вектора-строки $\pi \; t\; +\; 1\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{\backslash \; pi\; \_\; \{t\; +\; 1\}\}\}$записывается как $\pi \; t\; +\; 1\; =\; \pi \; t\; T\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{\backslash \; pi\; \_\; \{t\; +\; 1\}\}\; =\; \backslash \; mathbf\; \{\backslash \; pi\; \_\; \{t\}\}\; \backslash \; mathbf\; \{T\}\}$. В приведенном ниже примере представлена ​​система, в которой вероятность оставаться в том же состоянии после каждого шага составляет 70%, а вероятность перехода в другое состояние составляет 30%. Тогда матрица перехода имеет следующий вид:

$T\; =\; (0,7\; 0,3\; 0,3\; 0,7)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{T\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; 0,7\; 0,3\; \backslash \backslash \; 0,3\; 0,7\; \backslash \; end\; \{pmatrix\}\}\}$

В типичной марковской модели мы умножаем вектор состояния на эту матрицу, чтобы получить вероятности для последующего состояния. В скрытой марковской модели состояние неизвестно, и вместо этого мы наблюдаем события, связанные с возможными состояниями. Матрица событий в форме:

$B\; =\; (0,9\; 0,1\; 0,2\; 0,8)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{B\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; 0,9\; 0,1\; \backslash \backslash \; 0,2\; 0,8\; \backslash \; end\; \{pmatrix\}\}\}$

обеспечивает вероятности наблюдения событий в конкретном состоянии. В приведенном выше примере событие 1 будет наблюдаться в 90% случаев, если мы находимся в состоянии 1, в то время как событие 2 имеет 10% вероятность возникновения в этом состоянии. Напротив, событие 1 будет наблюдаться только в 20% случаев, если мы находимся в состоянии 2, а вероятность возникновения события 2 составляет 80%. Для произвольного вектора-строки, описывающего состояние системы ($\pi \; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{\backslash \; pi\}\}$), тогда вероятность наблюдения события j равна:

$P\; (O\; знак\; равно\; j)\; знак\; равно\; \sum \; я\; \pi \; я\; В\; я,\; j\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{P\}\; (O\; =\; j)\; =\; \backslash \; sum\; \_\; \{i\}\; \backslash \; pi\; \_\; \{i\}\; B\_\; \{i,\; j\}\}$

Это может быть представлен в матричной форме путем умножения вектора-строки состояния ($\pi \; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{\backslash \; pi\}\}$) на матрицу наблюдения ($O\; j\; =\; diag\; (B\; \ast ,\; oj)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{O\_\; \{j\}\}\; =\; \backslash \; mathrm\; \{diag\}\; (B\; \_\; \{*,\; o\_\; \{j\}\})\}$), содержащий только диагональные элементы. Каждая запись - это вероятность наблюдаемого события для каждого состояния. Продолжая приведенный выше пример, наблюдение за событием 1 будет:

$O\; 1\; =\; (0,9\; 0,0\; 0,0\; 0,2)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{O\_\; \{1\}\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; 0,9\; 0,0\; \backslash \backslash \; 0,0\; 0.2\; \backslash \; end\; \{pmatrix\}\}\}$

Это позволяет нам вычислить новый вектор состояния ненормализованных вероятностей $\pi \; \prime \; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{\backslash \; pi\; \text{'}\}\}$через правило Байеса, взвешивание по вероятности того, что каждый элемент $\pi \; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{\backslash \; pi\}\}$сгенерировал событие 1 как:

$\pi \; \prime \; =\; \pi \; O\; 1\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{\backslash \; pi\; \text{'}\}\; =\; \backslash \; mathbf\; \{\backslash \; pi\}\; \backslash \; mathbf\; \{O\_\; \{1\}\}\}$

Теперь мы можем сделать эту общую процедуру конкретной для нашей серии наблюдений. Предполагая вектор начального состояния $\pi \; 0\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{\backslash \; pi\}\; \_\; \{0\}\}$(который может быть оптимизирован как параметр путем повторения процедуры вперед-назад), мы начните с $f\; 0:\; 0\; =\; \pi \; 0\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{f\_\; \{0:\; 0\}\}\; =\; \backslash \; mathbf\; \{\backslash \; pi\}\; \_\; \{0\}\}$, затем обновите распределение состояний и взвешивание по вероятности первого наблюдения:

$f\; 0:\; 1\; =\; \pi \; 0\; TO\; o\; (1)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{f\_\; \{0:\; 1\}\}\; =\; \backslash \; mathbf\; \{\backslash \; pi\}\; \_\; \{0\}\; \backslash \; mathbf\; \{T\}\; \backslash \; mathbf\; \{O\_\; \{o\; (1)\}\}\}$

Этот процесс можно продолжить с дополнительными наблюдениями, используя:

$f\; 0:\; t\; =\; f\; 0:\; t\; -\; 1\; TO\; o\; (t)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{f\_\; \{0:\; t\}\}\; =\; \backslash \; mathbf\; \{f\_\; \{0:\; t-1\}\}\; \backslash \; mathbf\; \{T\}\; \backslash \; mathbf\; \{O\_\; \{o\; (t)\}\}\}$

Это значение является ненормализованным форвардом вектор вероятности. I-я запись этого вектора обеспечивает:

$f\; 0:\; t\; (i)\; =\; P\; (o\; 1,\; o\; 2,\dots ,\; ot,\; X\; t\; =\; xi\; |\; \pi \; 0)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{f\_\; \{0\; :\; t\}\}\; (i)\; =\; \backslash \; mathbf\; \{P\}\; (o\_\; \{1\},\; o\_\; \{2\},\; \backslash \; dots,\; o\_\; \{t\},\; X\_\; \{t\}\; =\; x\_\; \{i\}\; |\; \backslash \; mathbf\; \{\backslash \; pi\}\; \_\; \{\; 0\})\}$

Обычно мы нормализуем вектор вероятности на каждом шаге так, чтобы сумма его элементов равнялась 1. Таким образом, на каждом шаге вводится коэффициент масштабирования, такой что:

$f\; ^\; 0:\; t\; =\; ct\; -\; 1\; е\; ^\; 0:\; t\; -\; 1\; К\; o\; (t)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{\{\backslash \; hat\; \{f\}\}\; \_\; \{0:\; t\}\}\; =\; c\_\; \{t\}\; ^\; \{-\; 1\}\; \backslash \; \backslash \; mathbf\; \{\{\backslash \; hat\; \{\; f\}\}\; \_\; \{0:\; t-1\}\}\; \backslash \; mathbf\; \{T\}\; \backslash \; mathbf\; \{O\_\; \{o\; (t)\}\}\}$

где $f\; ^\; 0:\; t\; -\; 1\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{\{\; \backslash \; hat\; \{f\}\}\; \_\; \{0:\; t-1\}\}\}$представляет масштабированный вектор из предыдущего шага, а $ct\; \{\backslash \; displaystyle\; c\_\; \{t\}\}$представляет коэффициент масштабирования, который заставляет элементы результирующего вектора суммироваться до 1. Произведение коэффициентов масштабирования представляет собой полную вероятность наблюдения данных событий независимо от конечных состояний:

$P\; (o\; 1,\; o\; 2,\dots ,\; ot\; |\; \pi \; 0)\; =\; \prod \; s\; =\; 1\; tcs\; \{\backslash \; displayst\; yle\; \backslash \; mathbf\; \{P\}\; (o\_\; \{1\},\; o\_\; \{2\},\; \backslash \; dots,\; o\_\; \{t\}\; |\; \backslash \; mathbf\; \{\backslash \; pi\}\; \_\; \{0\})\; =\; \backslash \; prod\; \_\; \{s\; =\; 1\}\; ^\; \{t\}\; c\_\; \{s\}\}$

Это позволяет нам интерпретировать масштабированный вектор вероятности как:

$f\; ^\; 0:\; t\; (i)\; =\; f\; 0:\; t\; (i)\; \prod \; s\; =\; 1\; tcs\; =\; P\; (o\; 1,\; o\; 2,\dots ,\; Ot,\; X\; t\; =\; xi\; |\; \pi \; 0)\; п\; (о\; 1,\; о\; 2,\dots ,\; ot\; |\; \pi \; 0)\; =\; P\; (X\; t\; =\; xi\; |\; o\; 1,\; o\; 2,\dots ,\; ot,\; \pi \; 0)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{\{\backslash \; hat\; \{f\; \}\}\; \_\; \{0:\; t\}\}\; (i)\; =\; \{\backslash \; frac\; \{\backslash \; mathbf\; \{f\_\; \{0:\; t\}\}\; (i)\}\; \{\backslash \; prod\; \_\; \{s\; =\; 1\}\; ^\; \{t\}\; c\_\; \{s\}\}\}\; =\; \{\backslash \; frac\; \{\backslash \; mathbf\; \{P\}\; (o\_\; \{1\},\; o\_\; \{2\},\; \backslash \; dots,\; o\_\; \{t\},\; X\_\; \{t\}\; =\; x\_\; \{i\}\; |\; \backslash \; mathbf\; \{\backslash \; pi\}\; \_\; \{0\})\; \}\; \{\backslash \; mathbf\; \{P\}\; (o\_\; \{1\},\; o\_\; \{2\},\; \backslash \; dots,\; o\_\; \{t\}\; |\; \backslash \; mathbf\; \{\backslash \; pi\}\; \_\; \{0\})\}\}\; =\; \backslash \; mathbf\; \{P\}\; (X\_\; \{t\}\; =\; x\_\; \{i\}\; |\; o\_\; \{1\},\; o\_\; \{2\},\; \backslash \; dots,\; o\_\; \{t\},\; \backslash \; mathbf\; \{\backslash \; pi\}\; \_\; \{0\})\}$

Таким образом, мы находим, что произведение коэффициентов масштабирования дает нам с полной вероятностью для наблюдения данной последовательности до момента времени t и что масштабированный вектор вероятности дает нам вероятность нахождения в каждом состоянии в это время.

Подобная процедура может быть построена для поиска обратных вероятностей. Они предназначены для обеспечения вероятностей:

$bt:\; T\; (i)\; =\; P\; (ot\; +\; 1,\; ot\; +\; 2,\dots ,\; o\; T\; |\; X\; t\; =\; xi)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{b\_\; \{t:\; T\}\}\; (i)\; =\; \backslash \; mathbf\; \{P\}\; (o\_\; \{t\; +\; 1\},\; o\_\; \{t\; +\; 2\},\; \backslash \; dots,\; o\_\; \{T\}\; |\; X\_\; \{t\}\; =\; x\_\; \{i\})\}$

То есть мы теперь мы хотим предположить, что мы начинаем с определенного состояния ($X\; t\; =\; xi\; \{\backslash \; displaystyle\; X\_\; \{t\}\; =\; x\_\; \{i\}\}$), и теперь нас интересует вероятность наблюдения все будущие события из этого состояния. Поскольку исходное состояние считается заданным (т.е. априорная вероятность этого состояния = 100%), мы начинаем с:

$b\; T:\; T\; =\; [1\; 1\; 1\dots ]\; T\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{b\_\; \{T:\; T\}\}\; =\; [1\; \backslash \; 1\; \backslash \; 1\; \backslash \; \backslash \; dots]\; ^\; \{T\}\}$

Обратите внимание, что теперь мы используем вектор-столбец, в то время как прямые вероятности использовали векторы-строки. Затем мы можем работать в обратном направлении, используя:

$bt\; -\; 1:\; T\; =\; TO\; tbt:\; T\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{b\_\; \{t-1:\; T\}\}\; =\; \backslash \; mathbf\; \{T\}\; \backslash \; mathbf\; \{O\_\; \{t\}\}\; \backslash \; mathbf\; \{b\_\; \{t:\; T\}\}\}$

Хотя мы могли бы также нормализовать этот вектор, чтобы сумма его записей равнялась единице, обычно это не делается. Отмечая, что каждая запись содержит вероятность будущей последовательности событий с учетом конкретного начального состояния, нормализация этого вектора была бы эквивалентна применению теоремы Байеса для нахождения вероятности каждого начального состояния с учетом будущих событий (при условии единообразных априорных значений для вектора конечного состояния). Однако чаще для масштабирования этого вектора используются те же константы $c\; t\; \{\backslash \; displaystyle\; c\_\; \{t\}\}$, используемые в расчетах прямой вероятности. $b\; T:\; T\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{b\_\; \{T:\; T\}\}\}$не масштабируется, но в последующих операциях используется:

$b\; ^\; t\; -\; 1:\; T\; =\; ct\; -\; 1\; К\; tb\; ^\; t:\; T\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{\{\backslash \; hat\; \{b\}\}\; \_\; \{t-1:\; T\}\}\; =\; c\_\; \{t\}\; ^\; \{-\; 1\}\; \backslash \; mathbf\; \{T\}\; \backslash \; mathbf\; \{O\_\; \{t\}\; \}\; \backslash \; mathbf\; \{\{\backslash \; hat\; \{b\}\}\; \_\; \{t:\; T\}\}\}$

где $b\; ^\; t:\; T\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{\{\backslash \; hat\; \{b\}\}\; \_\; \{t:\; T\}\; \}\}$представляет предыдущий масштабированный вектор. Этот результат состоит в том, что масштабированный вектор вероятности связан с обратными вероятностями следующим образом:

$b\; ^\; t:\; T\; (i)\; =\; bt:\; T\; (i)\; \prod \; s\; =\; t\; +\; 1\; T\; cs\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{\{\backslash \; шляпа\; \{b\}\}\; \_\; \{t:\; T\}\}\; (i)\; =\; \{\backslash \; frac\; \{\backslash \; mathbf\; \{b\_\; \{t:\; T\}\}\; (i)\}\; \{\backslash \; prod\; \_\; \{s\; =\; t\; +\; 1\}\; ^\; \{T\}\; c\_\; \{s\}\}\}\}$

Это полезно, поскольку позволяет нам найти общую вероятность нахождения в каждом состоянии в заданный момент времени t путем умножения этих значений:

$\gamma \; t\; (i)\; =\; P\; (X\; t\; =\; xi\; |\; o\; 1,\; o\; 2,\dots ,\; o\; T,\; \pi \; 0)\; =\; P\; (o\; 1,\; o\; 2,\dots ,\; o\; T,\; X\; t\; =\; xi\; |\; \pi \; 0)\; P\; (o\; 1,\; o\; 2,\dots ,\; о\; T\; |\; \pi \; 0)\; знак\; равно\; е\; 0:\; T\; (я)\; \cdot \; bt:\; T\; (я)\; \prod \; s\; =\; 1\; T\; cs\; =\; f\; ^\; 0:\; t\; (я)\; \cdot \; b\; ^\; t:\; T\; (я)\; \{\backslash \; Displaystyle\; \backslash \; mathbf\; \{\backslash \; gamma\; \_\; \{t\}\}\; (i)\; =\; \backslash \; mathbf\; \{P\}\; (X\_\; \{t\}\; =\; x\_\; \{i\}\; |\; o\_\; \{1\},\; o\_\; \{2\},\; \backslash \; dots,\; o\_\; \{T\},\; \backslash \; mathbf\; \{\backslash \; pi\}\; \_\; \{0\})\; =\; \{\backslash \; frac\; \{\backslash \; mathbf\; \{P\}\; (o\_\; \{1\},\; o\_\; \{2\},\; \backslash \; dots,\; o\_\; \{T\},\; X\_\; \{t\}\; =\; x\_\; \{i\}\; |\; \backslash \; mathbf\; \{\backslash \; pi\}\; \_\; \{0\})\}\; \{\backslash \; mathbf\; \{P\}\; (o\_\; \{1\},\; o\_\; \{2\},\; \backslash \; dots,\; o\_\; \{T\}\; |\; \backslash \; mathbf\; \{\backslash \; pi\}\; \_\; \{0\})\}\}\; =\; \{\backslash \; frac\; \{\backslash \; mathbf\; \{f\_\; \{0:\; t\}\}\; (i)\; \backslash \; cdot\; \backslash \; mathbf\; \{b\_\; \{t:\; T\}\}\; (i)\}\; \{\backslash \; prod\; \_\; \{s\; =\; 1\}\; ^\; \{T\}\; c\_\; \{s\}\}\}\; =\; \backslash \; mathbf\; \{\{\backslash \; hat\; \{f\}\}\; \_\; \{0:\; t\}\}\; (i)\; \backslash \; cdot\; \backslash \; mathbf\; \{\{\backslash \; hat\; \{b\}\}\; \_\; \{t:\; T\}\}\; (i)\}$

Чтобы понять это, отметим, что $f\; 0:\; t\; (i)\; \cdot \; bt:\; T\; (i)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{f\_\; \{0:\; t\}\}\; (i)\; \backslash \; cdot\; \backslash \; mathbf\; \{b\_\; \{t:\; T\}\}\; (i)\}$обеспечивает вероятность наблюдения данных событий способом, который проходит через состояние $xi\; \{\backslash \; displaystyle\; x\_\; \{i\}\}$в момент времени t. Эта вероятность включает прямые вероятности, охватывающие все события до момента времени t, а также обратные вероятности, которые включают все будущие события. Это числитель, который мы ищем в нашем уравнении, и мы делим его на общую вероятность последовательности наблюдений для нормализации этого значения и извлекаем только вероятность того, что $X\; t\; =\; xi\; \{\backslash \; displaystyle\; X\_\; \{t\}\; =\; x\_\; \{\; i\}\}$. Эти значения иногда называют «сглаженными значениями», поскольку они объединяют прямую и обратную вероятности для вычисления окончательной вероятности.

Значения $\gamma \; t\; (i)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{\backslash \; gamma\; \_\; \{t\}\}\; (i)\}$, таким образом, обеспечивают вероятность нахождения в каждом состоянии в определенный момент времени. т. Таким образом, они полезны для определения наиболее вероятного состояния в любое время. Термин «наиболее вероятное состояние» несколько неоднозначен. Хотя наиболее вероятное состояние с наибольшей вероятностью будет правильным в данной точке, последовательность индивидуально вероятных состояний вряд ли будет наиболее вероятной последовательностью. Это связано с тем, что вероятности для каждой точки рассчитываются независимо друг от друга. Они не принимают во внимание вероятности перехода между состояниями, и, таким образом, можно получить состояния в два момента (t и t + 1), которые являются наиболее вероятными в эти моменты времени, но которые имеют очень небольшую вероятность возникновения вместе, т. Е. $п\; (Икс\; t\; =\; xi,\; X\; t\; +\; 1\; =\; xj)\; \ne \; P\; (X\; t\; =\; xi)\; P\; (X\; t\; +\; 1\; =\; xj)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{P\}\; (X\_\; \{t\}\; =\; x\_\; \{\; i\},\; X\_\; \{t\; +\; 1\}\; =\; x\_\; \{j\})\; \backslash \; neq\; \backslash \; mathbf\; \{P\}\; (X\_\; \{t\}\; =\; x\_\; \{i\})\; \backslash \; mathbf\; \{P\}\; (X\_\; \{t\; +\; 1\}\; =\; x\_\; \{j\})\}$. Наиболее вероятная последовательность состояний, которая произвела последовательность наблюдений, может быть найдена с помощью алгоритма Витерби.

В этом примере за основу взят зонтичный мир из Russell Norvig 2010 Глава 15 стр. 567, в которой мы хотели бы сделать вывод о погоде на основании наблюдения другого человека, несущего или не несущего зонтик. Мы предполагаем два возможных состояния погоды: состояние 1 = дождь, состояние 2 = без дождя. Мы предполагаем, что у погоды есть 70% шанс оставаться неизменной каждый день и 30% шанс измениться. Тогда вероятности перехода таковы:

$T\; =\; (0,7\; 0,3\; 0,3\; 0,7)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{T\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; 0,7\; 0,3\; \backslash \backslash \; 0,3\; 0,7\; \backslash \; end\; \{pmatrix\}\}\}$

Мы также предполагаем, что каждое состояние генерирует одно из двух возможных событий: событие 1 = зонтик, событие 2 = отсутствие зонтика. Условные вероятности их появления в каждом состоянии задаются матрицей вероятностей:

$B\; =\; (0,9\; 0,1\; 0,2\; 0,8)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{B\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; 0,9\; 0,1\; \backslash \backslash \; 0,2\; 0.8\; \backslash \; end\; \{pmatrix\}\}\}$

Затем мы наблюдаем следующую последовательность событий: {зонтик, зонтик, без зонта, зонтик, зонтик}, которые мы представим в наших расчетах как:

$O\; 1\; =\; (0.9\; 0,0\; 0,0\; 0,2)\; O\; 2\; =\; (0,9\; 0,0\; 0,0\; 0,2)\; O\; 3\; =\; (0,1\; 0,0\; 0,0\; 0,8)\; O\; 4\; =\; (0,9\; 0,0\; 0,0\; 0,2)\; O\; 5\; =\; (0,9\; 0,0\; 0,0\; 0,2)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{O\_\; \{1\}\; \}\; =\; \{\backslash \; begin\; \{pmatrix\}\; 0.9\; 0.0\; \backslash \backslash \; 0.0\; 0.2\; \backslash \; end\; \{pmatrix\}\}\; ~~\; \backslash \; mathbf\; \{O\_\; \{2\}\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; 0.9\; 0.0\; \backslash \backslash \; 0.0\; 0.\; 2\; \backslash \; end\; \{pmatrix\}\}\; ~~\; \backslash \; mathbf\; \{O\_\; \{3\}\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; 0.1\; 0.0\; \backslash \backslash \; 0.0\; 0.8\; \backslash \; end\; \{pmatrix\}\}\; ~~\; \backslash \; mathbf\; \{O\_\; \{4\}\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; 0,9\; 0,0\; \backslash \backslash \; 0,0\; 0,2\; \backslash \; end\; \{pmatrix\}\}\; ~~\; \backslash \; mathbf\; \{O\_\; \{5\}\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; 0,9\; и\; 0,0\; \backslash \backslash \; 0,0\; и\; 0,2\; \backslash \; end\; \{pmatrix\}\}\}$

Обратите внимание, что $O\; 3\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{O\_\; \{3\}\}\}$отличается от других из-за наблюдения «без зонтика».

При вычислении прямых вероятностей мы начинаем с:

$f\; 0:\; 0\; =\; (0,5\; 0,5)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{f\_\; \{0:\; 0\}\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; 0,5\; 0.\; 5\; \backslash \; end\; \{pmatrix\}\}\}$

, который является нашим предыдущим вектором состояния, указывающим, что мы не знаем, в каком состоянии находится погода до наших наблюдений. Хотя вектор состояния должен быть задан как вектор-строка, мы будем использовать транспонирование матрицы, чтобы было легче читать приведенные ниже вычисления. Наши вычисления записываются в виде:

$(f\; ^\; 0:\; t)\; T\; =\; ct\; -\; 1\; O\; t\; (T)\; T\; (f\; ^\; 0:\; t\; -\; 1)\; T\; \{\backslash \; displaystyle\; (\backslash \; mathbf\; \{\{\backslash \; hat)\; \{f\}\}\; \_\; \{0:\; t\}\})\; ^\; \{T\}\; =\; c\_\; \{t\}\; ^\; \{-\; 1\}\; \backslash \; mathbf\; \{O\_\; \{t\}\}\; (\backslash \; mathbf\; \{T\})\; ^\; \{T\}\; (\backslash \; mathbf\; \{\{\; \backslash \; hat\; \{f\}\}\; \_\; \{0:\; t-1\}\})\; ^\; \{T\}\}$

вместо:

$f\; ^\; 0:\; t\; =\; ct\; -\; 1\; f\; ^\; 0:\; t\; -\; 1\; TO\; t\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{\{\backslash \; hat\; \{f\}\}\; \_\; \{0:\; t\}\}\; =\; c\_\; \{t\}\; ^\; \{-\; 1\}\; \backslash \; mathbf\; \{\{\backslash \; hat\; \{f\}\}\; \_\; \{0:\; t-1\}\}\; \backslash \; mathbf\; \{\; T\}\; \backslash \; mathbf\; \{O\_\; \{t\}\}\}$

Обратите внимание, что матрица преобразования также транспонируется, но в нашем примере транспонирование равно исходной матрице. Выполнение этих вычислений и нормализация результатов дает:

$(f\; ^\; 0:\; 1)\; T\; =\; c\; 1\; -\; 1\; (0,9\; 0,0\; 0,0\; 0,2)\; (0,7\; 0,3\; 0,3\; 0,7)\; (0,5000\; 0,5000)\; =\; c\; 1\; -\; 1\; (0,4500\; 0,1000)\; =\; (0,8182\; 0,1818)\; \{\backslash \; displaystyle\; (\backslash \; mathbf\; \{\{\backslash \; hat\; \{f\}\}\; \_\; \{0:\; 1\}\})\; ^\; \{T\}\; =\; c\_\; \{1\}\; ^\; \{-\; 1\}\; \{\backslash \; begin\; \{pmatrix\}\; 0,9\; и\; 0.\; 0\; \backslash \backslash \; 0,0\; 0,2\; \backslash \; end\; \{pmatrix\}\}\; \{\backslash \; begin\; \{pmatrix\}\; 0,7\; 0,3\; \backslash \backslash \; 0,3\; 0,7\; \backslash \; end\; \{pmatrix\}\}\; \{\backslash \; begin\; \{pmatrix\}\; 0,5000\; \backslash \backslash \; 0,5000\; \backslash \; end\; \{pmatrix\}\; \}\; =\; c\_\; \{1\}\; ^\; \{-\; 1\}\; \{\backslash \; begin\; \{pmatrix\}\; 0,4500\; \backslash \backslash \; 0,1000\; \backslash \; end\; \{pmatrix\}\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; 0,8182\; \backslash \backslash \; 0,1818\; \backslash \; end\; \{pmatrix\}\}\}$

$(f\; ^\; 0:\; 2)\; T\; =\; c\; 2\; -\; 1\; (0,9\; 0,0\; 0,0\; 0,2)\; (0,7\; 0,3\; 0,3\; 0,7)\; (0,8182\; 0,1818)\; =\; c\; 2\; -\; 1\; (0,5645\; 0,0745)\; =\; (0,8834\; 0,1166)\; \{\backslash \; displaystyle\; (\backslash \; mathbf\; \{\{\backslash \; hat\; \{f\}\}\; \_\; \{0:\; 2\}\})\; ^\; \{T\}\; =\; c\_\; \{2\}\; ^\; \{-\; 1\}\; \{\backslash \; begin\; \{pmatrix\}\; 0.9\; 0.0\; \backslash \backslash \; 0.0\; 0.2\; \backslash \; end\; \{pmatrix\}\}\; \{\; \backslash \; begin\; \{pmatrix\}\; 0.7\; 0.3\; \backslash \backslash \; 0.3\; 0.7\; \backslash \; end\; \{pmatrix\}\}\; \{\backslash \; begin\; \{pmatrix\}\; 0.8182\; \backslash \backslash \; 0.1818\; \backslash \; end\; \{pmatrix\}\}\; =\; c\_\; \{2\}\; ^\; \{-\; 1\}\; \{\backslash \; begin\; \{pmatrix\}\; 0,5645\; \backslash \backslash \; 0,0745\; \backslash \; end\; \{pmatrix\}\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; 0,8834\; \backslash \backslash \; 0,1166\; \backslash \; end\; \{pmatrix\}\}\}$

$(f\; ^\; 0:\; 3)\; T\; =\; c\; 3\; -\; 1\; (0,1\; 0,0\; 0,0\; 0,8)\; (0,7\; 0,3\; 0,3\; 0,7)\; (0,8834\; 0,1166)\; =\; c\; 3\; -\; 1\; (0,0653\; 0,2772)\; =\; (0,1907\; 0,8093)\; \{\backslash \; displaystyle\; (\backslash \; mathbf\; \{\{\backslash \; hat\; \{f\}\}\; \_\; \{0:\; 3\}\})\; ^\; \{T\}\; =\; c\_\; \{3\; \}\; ^\; \{-\; 1\}\; \{\backslash \; begin\; \{pmatrix\}\; 0,1\; 0,0\; \backslash \backslash \; 0,0\; 0,8\; \backslash \; end\; \{pmatrix\}\}\; \{\backslash \; begin\; \{pmatrix\}\; 0,7\; 0,3\; \backslash \backslash \; 0,3\; 0,7\; \backslash \; end\; \{pmatrix\}\}\; \{\backslash \; begin\; \{pmatrix\}\; 0,8834\; \backslash \backslash \; 0,1166\; \backslash \; end\; \{pmatrix\}\}\; =\; c\_\; \{3\}\; ^\; \{-\; 1\}\; \{\backslash \; begin\; \{pmatrix\}\; 0,0653\; \backslash \backslash \; 0,2772\; \backslash \; end\; \{pmatrix\}\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; 0,1907\; \backslash \backslash \; 0.8093\; \backslash \; end\; \{pmatrix\}\}\}$

$(f\; ^\; 0:\; 4)\; T\; =\; c\; 4\; -\; 1\; (0,9\; 0,0\; 0,0\; 0,2)\; (0,7\; 0,3\; 0,3\; 0,7)\; (0,1907\; 0,8093)\; =\; c\; 4\; -\; 1\; (0,3386\; 0,1247)\; =\; (0,7308\; 0,2692)\; \{\backslash \; displaystyle\; (\backslash \; mathbf\; \{\{\backslash \; hat\; \{f\}\}\; \_\; \{0:\; 4\}\})\; ^\; \{T\}\; =\; c\_\; \{4\}\; ^\; \{-\; 1\}\; \{\backslash \; begin\; \{pmatrix\}\; 0,9\; 0.0\; \backslash \backslash \; 0,0\; 0,2\; \backslash \; end\; \{pmatrix\}\}\; \{\backslash \; begin\; \{pmatrix\}\; 0,7\; 0,3\; \backslash \backslash \; 0,3\; 0,7\; \backslash \; end\; \{pmatrix\}\}\; \{\backslash \; begin\; \{pmatrix\}\; 0,1907\; \backslash \backslash \; 0.8093\; \backslash \; end\; \{pmatrix\; \}\}\; =\; c\_\; \{4\}\; ^\; \{-\; 1\}\; \{\backslash \; begin\; \{pmatrix\}\; 0,3386\; \backslash \backslash \; 0,1247\; \backslash \; end\; \{pmatrix\}\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; 0,7308\; \backslash \backslash \; 0,2692\; \backslash \; end\; \{pmatrix\}\}\}$

$(\; f\; ^\; 0:\; 5)\; T\; =\; c\; 5-1\; (0,9\; 0,0\; 0,0\; 0,2)\; (0,7\; 0,3\; 0,3\; 0,7)\; (0,7308\; 0,2692)\; =\; c\; 5-1\; (0,5331\; 0,0815)\; =\; (0,8673\; 0,1327)\; \{\backslash \; displaystyle\; (\backslash \; mathbf\; \{\{\; \backslash \; hat\; \{f\}\}\; \_\; \{0:\; 5\}\})\; ^\; \{T\}\; =\; c\_\; \{5\}\; ^\; \{-\; 1\}\; \{\backslash \; begin\; \{pmatrix\}\; 0,9\; 0,0\; \backslash \backslash \; 0,0\; 0,2\; \backslash \; end\; \{pmatrix\}\}\; \{\backslash \; begin\; \{pmatrix\}\; 0,7\; 0,3\; \backslash \backslash \; 0,3\; 0,7\; \backslash \; end\; \{pmatrix\}\}\; \{\backslash \; begin\; \{pmatrix\}\; 0,7308\; \backslash \backslash \; 0,2692\; \backslash \; end\; \{pmatrix\}\}\; =\; c\_\; \{5\}\; ^\; \{-\; 1\}\; \{\backslash \; begin\; \{pmatrix\}\; 0,5331\; \backslash \; 0,0815\; \backslash \; end\; \{pmatrix\}\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; 0,8673\; \backslash \backslash \; 0,1327\; \backslash \; end\; \{\; pmatrix\}\}\}$

Для обратных вероятностей мы начинаем с:

$b\; 5:\; 5\; =\; (1.0\; 1.0)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{b\_\; \{5:\; 5\}\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; 1.0\; \backslash \backslash \; 1.0\; \backslash \; end\; \{pmatrix\}\}\}$

Затем мы можем вычислить (используя наблюдения в обратном порядке и нормализуя с разными константами):

$b\; ^\; 4:\; 5\; =\; \alpha \; (0,7\; 0,3\; 0,3\; 0,7)\; (0,9\; 0,0\; 0,0\; 0,2)\; (1,0000\; 1,0000)\; =\; \alpha \; (0,6900\; 0,4100)\; =\; (0,6273\; 0,3727)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{\{\backslash \; hat\; \{b\}\}\; \_\; \{4:\; 5\}\}\; =\; \backslash \; alpha\; \{\backslash \; begin\; \{pmatrix\}\; 0,7\; и\; 0.\; 3\; \backslash \backslash \; 0,3\; 0,7\; \backslash \; end\; \{pmatrix\}\}\; \{\backslash \; begin\; \{pmatrix\}\; 0,9\; 0,0\; \backslash \backslash \; 0,0\; 0,2\; \backslash \; end\; \{pmatrix\}\}\; \{\backslash \; begin\; \{pmatrix\}\; 1,0000\; \backslash \; 1,0000\; \backslash \; end\; \{pmatrix\}\; \}\; =\; \backslash \; alpha\; \{\backslash \; begin\; \{pmatrix\}\; 0,6900\; \backslash \backslash \; 0,4100\; \backslash \; end\; \{pmatrix\}\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; 0,6273\; \backslash \backslash \; 0,3727\; \backslash \; end\; \{pmatrix\}\}\}$

$b\; ^\; 3:\; 5\; =\; \alpha \; (0,7\; 0,3\; 0,3\; 0,7)\; (0,9\; 0,0\; 0,0\; 0,2)\; (0,6273\; 0,3727)\; =\; \alpha \; (0,4175\; 0,2215)\; =\; (0,6533\; 0,3467)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{\{\backslash \; hat\; \{b\}\}\; \_\; \{3:\; 5\}\}\; =\; \backslash \; alpha\; \{\backslash \; begin\; \{pmatrix\}\; 0,7\; и\; 0,3\; \backslash \backslash \; 0,3\; и\; 0,7\; \backslash \; end\; \{pmatrix\; \}\}\; \{\backslash \; begin\; \{pmatrix\}\; 0,9\; 0,0\; \backslash \backslash \; 0,0\; 0,2\; \backslash \; end\; \{pmatrix\}\}\; \{\backslash \; begin\; \{pmatrix\}\; 0,6273\; \backslash \; 0,3727\; \backslash \; end\; \{pmatrix\}\}\; =\; \backslash \; alpha\; \{\backslash \; begin\; \{pmatrix\}\; 0,4175\; \backslash \backslash \; 0,2215\; \backslash \; end\; \{pmatrix\}\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; 0,6533\; \backslash \backslash \; 0,3467\; \backslash \; end\; \{pmatrix\}\}\}$

$b\; ^\; 2:\; 5\; =\; \alpha \; (0,7\; 0,3\; 0,3\; 0,7)\; (0,1\; 0,0\; 0,0\; 0,8)\; (\; 0,6533\; 0,3467)\; =\; \alpha \; (0,1289\; 0,2138)\; =\; (0,3763\; 0,6237)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{\{\backslash \; hat\; \{b\}\}\; \_\; \{2:\; 5\}\}\; =\; \backslash \; alpha\; \{\backslash \; begin\; \{pmatrix\}\; 0,7\; и\; 0,3\; \backslash \backslash \; 0,3\; 0,7\; \backslash \; end\; \{pmatrix\}\}\; \{\backslash \; begin\; \{pmatrix\}\; 0,1\; 0,0\; \backslash \; 0,0\; 0,8\; \backslash \; end\; \{pmatrix\}\}\; \{\backslash \; begin\; \{pmatrix\}\; 0,6533\; \backslash \; 0,3467\; \backslash \; end\; \{pmatrix\}\}\; =\; \backslash \; alpha\; \{\backslash \; begin\; \{pmatrix\}\; 0,1289\; \backslash \; 0,2138\; \backslash \; end\; \{pmatrix\}\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; 0,3763\; \backslash \; 0,6237\; \backslash \; end\; \{pmatrix\}\}\}$

$b\; ^\; 1:\; 5\; =\; \alpha \; (0,7\; 0,3\; 0,3\; 0,7)\; (0,9\; 0,0\; 0,0\; 0,2)\; (0,3763\; 0,6237)\; =\; \alpha \; (0,2745\; 0,1889)\; =\; (0,5923\; 0,4077)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{\{\backslash \; hat\; \{b\}\}\; \_\; \{1:\; 5\}\}\; =\; \backslash \; alpha\; \{\backslash \; begin\; \{pmatrix\}\; 0,7\; и\; 0,3\; \backslash \backslash \; 0,3\; и\; 0,7\; \backslash \; end\; \{pmatrix\}\}\; \{\backslash \; begin\; \{pmatrix\}\; 0,9\; и\; 0,0\; \backslash \backslash \; 0,0\; и\; 0,2\; \backslash \; end\; \{pmatrix\}\}\; \{\backslash \; begin\; \{pmatrix\}\; 0,37\; 63\; \backslash \backslash \; 0,6237\; \backslash \; end\; \{pmatrix\}\}\; =\; \backslash \; alpha\; \{\backslash \; begin\; \{pmatrix\}\; 0,2745\; \backslash \backslash \; 0,1889\; \backslash \; end\; \{pmatrix\}\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; 0,5923\; \backslash \backslash \; 0,4077\; \backslash \; end\; \{pmatrix\}\}\}$

$b\; ^\; 0:\; 5\; =\; \alpha \; (0,7\; 0,3\; 0,3\; 0,7)\; (0,9\; 0,0\; 0,0\; 0,2)\; (0,5923\; 0,4077)\; =\; \alpha \; (0,3976\; 0,2170)\; =\; (0,6469\; 0,3531)\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{\{\backslash \; hat\; \{b\}\}\; \_\; \{0\; :\; 5\}\}\; =\; \backslash \; alpha\; \{\backslash \; begin\; \{pmatrix\}\; 0,7\; 0,3\; \backslash \backslash \; 0,3\; 0,7\; \backslash \; end\; \{pmatrix\}\}\; \{\backslash \; begin\; \{pmatrix\}\; 0,9\; 0,0\; \backslash \backslash \; 0,0\; 0,2\; \backslash \; end\; \{pmatrix\}\; \}\; \{\backslash \; begin\; \{pmatrix\}\; 0,5923\; \backslash \backslash \; 0,4077\; \backslash \; end\; \{pmatrix\}\}\; =\; \backslash \; alpha\; \{\backslash \; begin\; \{pmatrix\}\; 0,3976\; \backslash \backslash \; 0,2170\; \backslash \; end\; \{pmatrix\}\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; 0,6469\; \backslash \backslash \; 0,3531\; \backslash \; end\; \{\; pmatrix\}\}\}$

Наконец, мы вычислим сглаженные значения вероятности. Эти результаты также должны быть масштабированы так, чтобы сумма их записей равнялась 1, потому что мы не масштабировали обратные вероятности с помощью найденных ранее $c\; t\; \{\backslash \; displaystyle\; c\_\; \{t\}\}$. Таким образом, приведенные выше обратные векторы вероятности фактически представляют вероятность каждого состояния в момент времени t с учетом будущих наблюдений. Поскольку эти векторы пропорциональны реальным обратным вероятностям, результат необходимо дополнительно масштабировать.

$(\gamma \; 0)\; T\; =\; \alpha \; (0,5000\; 0,5000)\; \circ \; (0,6469\; 0,3531)\; =\; \alpha \; (0,3235\; 0,1765)\; =\; (0,6469\; 0,3531)\; \{\backslash \; displaystyle\; (\backslash \; mathbf\; \{\backslash \; gamma\; \_\; \{0\}\})\; ^\; \{T\}\; =\; \backslash \; alpha\; \{\backslash \; begin\; \{pmatrix\}\; 0,5000\; \backslash \backslash \; 0,5000\; \backslash \; end\; \{pmatrix\}\}\; \backslash \; circ\; \{\backslash \; begin\; \{pmatrix\}\; 0,6469\; \backslash \; 0,3531\; \backslash \; end\; \{pmatrix\}\}\; =\; \backslash \; alpha\; \{\backslash \; begin\; \{pmatrix\}\; 0,3235\; \backslash \backslash \; 0,1765\; \backslash \; end\; \{pmatrix\}\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; 0,6469\; \backslash \backslash \; 0,3531\; \backslash \; end\; \{pmatrix\}\}\}$

$(\gamma \; 1)\; T\; =\; \alpha \; (0,8182\; 0,1818)\; \circ \; (0,5923\; 0,4077)\; =\; \alpha \; (0,4846\; 0,0741)\; =\; (\; 0,8673\; 0,1327)\; \{\backslash \; displaystyle\; (\backslash \; mathbf\; \{\backslash \; gamma\; \_\; \{1\}\})\; ^\; \{T\}\; =\; \backslash \; alpha\; \{\backslash \; begin\; \{pmatrix\}\; 0,8182\; \backslash \backslash \; 0,1818\; \backslash \; end\; \{pmatrix\}\}\; \backslash \; circ\; \{\backslash \; begin\; \{pmatrix\}\; 0,5923\; \backslash \backslash \; 0,4077\; \backslash \; end\; \{pmatrix\}\}\; =\; \backslash \; alpha\; \{\backslash \; begin\; \{pmatrix\}\; 0,4846\; \backslash \backslash \; 0,0741\; \backslash \; end\; \{pmatrix\}\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; 0,8673\; \backslash \backslash \; 0,1327\; \backslash \; end\; \{pmatrix\}\}\}$

$(\; \gamma \; 2)\; T\; знак\; равно\; \alpha \; (0,8834\; 0,1166)\; \circ \; (0,3763\; 0,6237)\; =\; \alpha \; (0,3324\; 0,0728)\; =\; (0,8204\; 0,1796)\; \{\backslash \; displaystyle\; (\backslash \; mathbf\; \{\backslash \; gamma\; \_\; \{2\}\})\; ^\; \{T\}\; =\; \backslash \; alpha\; \{\backslash \; begin\; \{pmatrix\}\; 0.8834\; \backslash \backslash \; 0.1166\; \backslash \; end\; \{pmatrix\}\}\; \backslash \; circ\; \{\backslash \; begin\; \{pmatrix\}\; 0.3763\; \backslash \backslash \; 0.6237\; \backslash \; end\; \{pmatrix\}\}\; =\; \backslash \; alpha\; \{\backslash \; begin\; \{pmatrix\}\; 0.3324\; \backslash \backslash \; 0.0728\; \backslash \; end\; \{pmatrix\}\; \}\; =\; \{\backslash \; begin\; \{pmatrix\}\; 0.8204\; \backslash \backslash \; 0,1796\; \backslash \; end\; \{pmatrix\}\}\}$

$(\gamma \; 3)\; T\; =\; \alpha \; (0,1907\; 0,8093)\; \circ \; (0,6533\; 0,3467)\; =\; \alpha \; (0,1246\; 0,2806)\; =\; (0,3075\; 0,6925)\; \{\backslash \; displaystyle\; (\backslash \; mathbf\; \{\backslash \; гамма\; \_\; \{3\}\})\; ^\; \{T\}\; =\; \backslash \; alpha\; \{\backslash \; begin\; \{pmatrix\}\; 0,1907\; \backslash \backslash \; 0.8093\; \backslash \; end\; \{pmatrix\}\}\; \backslash \; circ\; \{\backslash \; begin\; \{pmatrix\}\; 0,6533\; \backslash \backslash \; 0,3467\; \backslash \; end\; \{pmatrix\}\}\; =\; \backslash \; альфа\; \{\backslash \; begin\; \{pmatrix\}\; 0,1246\; \backslash \; 0,2806\; \backslash \; end\; \{pmatrix\}\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; 0,3075\; \backslash \; 0,6925\; \backslash \; end\; \{pmatrix\}\}\}$

$(\gamma \; 4)\; T\; =\; \alpha \; (0,7308\; 0,2692)\; \circ \; (0,6273\; 0,3727)\; =\; \alpha \; (0,4584\; 0,1003)\; =\; (0,8204\; 0,1796)\; \{\backslash \; displaystyle\; (\backslash \; mathbf\; \{\backslash \; gamma\; \_\; \{4\}\})\; ^\; \{T\}\; =\; \backslash \; alpha\; \{\backslash \; begin\; \{pmatrix\}\; 0,7308\; \backslash \backslash \; 0,2692\; \backslash \; end\; \{\; pmatrix\}\}\; \backslash \; circ\; \{\backslash \; begin\; \{pmatrix\}\; 0,6273\; \backslash \backslash \; 0,3727\; \backslash \; end\; \{pmatrix\}\}\; =\; \backslash \; alpha\; \{\backslash \; begin\; \{pmatrix\}\; 0,4584\; \backslash \backslash \; 0,1003\; \backslash \; end\; \{pmatrix\}\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; 0,8204\; \backslash \backslash \; 0,1796\; \backslash \; end\; \{pmatrix\}\}\}$

$(\gamma \; 5)\; T\; =\; \alpha \; (0,8673\; 0,1327)\; \circ \; (1,0000\; 1,0000)\; =\; \alpha \; (0,8673\; 0,1327)\; =\; (0,8673\; 0,1327)\; \{\backslash \; displaystyle\; (\backslash \; mathbf\; \{\backslash \; gamma\; \_\; \{5)\; \}\})\; ^\; \{T\}\; =\; \backslash \; alpha\; \{\backslash \; begin\; \{pmatrix\}\; 0.8673\; \backslash \backslash \; 0.1327\; \backslash \; end\; \{pmatrix\}\}\; \backslash \; circ\; \{\backslash \; begin\; \{pmatrix\}\; 1.0000\; \backslash \backslash \; 1.0000\; \backslash \; end\; \{pmatrix\}\}\; =\; \backslash \; alpha\; \{\backslash \; begin\; \{pmatrix\}\; 0,8673\; \backslash \backslash \; 0,1327\; \backslash \; en\; d\; \{pmatrix\}\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; 0.8673\; \backslash \backslash \; 0.1327\; \backslash \; end\; \{pmatrix\}\}\}$

Обратите внимание, что значение $\gamma \; 0\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{\backslash \; gamma\; \_\; \{0\}\}\}$равно $b\; ^\; 0:\; 5\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{\{\backslash \; hat\; \{b\}\}\; \_\; \{0:\; 5\}\}\}$и что $\gamma \; 5\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{\backslash \; gamma\; \_\; \{5\}\}\}$равно $f\; ^\; 0:\; 5\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{\{\backslash \; hat\; \{f\}\}\; \_\; \{0:\; 5\; \}\}\}$. Это естественно, потому что и $f\; ^\; 0:\; 5\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{\{\backslash \; hat\; \{f\}\}\; \_\; \{0:\; 5\}\}\}$, и $b\; ^\; 0:\; 5\; \{\; \backslash \; displaystyle\; \backslash \; mathbf\; \{\{\backslash \; hat\; \{b\}\}\; \_\; \{0:\; 5\}\}\}$начинаются с единых априорных значений по векторам начального и конечного состояния (соответственно) и учитывают все наблюдения. Однако $\gamma \; 0\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{\backslash \; gamma\; \_\; \{0\}\}\}$будет равно только $b\; ^\; 0:\; 5\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{\{\backslash \; hat\; \{\; b\}\}\; \_\; \{0:\; 5\}\}\}$, когда наш вектор начального состояния представляет собой однородный априор (т. е. все записи равны). Если это не так, $b\; ^\; 0:\; 5\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{\{\backslash \; hat\; \{b\}\}\; \_\; \{0:\; 5\}\}\}$необходимо объединить с вектором начального состояния найти наиболее вероятное начальное состояние. Таким образом, мы находим, что прямых вероятностей самих по себе достаточно для расчета наиболее вероятного конечного состояния. Точно так же обратные вероятности могут быть объединены с вектором начального состояния, чтобы обеспечить наиболее вероятное начальное состояние с учетом наблюдений. Прямые и обратные вероятности нужно только объединить, чтобы вывести наиболее вероятные состояния между начальной и конечной точками.

Приведенные выше расчеты показывают, что наиболее вероятным состоянием погоды на каждый день, кроме третьего, был «дождь». Однако они говорят нам больше, поскольку теперь предоставляют способ количественной оценки вероятностей каждого состояния в разное время. Возможно, наиболее важным является то, что наше значение $\gamma \; 5\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{\backslash \; gamma\; \_\; \{5\}\}\}$количественно определяет наши знания вектора состояния в конце последовательности наблюдений. Затем мы можем использовать это, чтобы предсказать вероятность различных погодных условий завтра, а также вероятность наблюдения за зонтом.

Алгоритм прямого и обратного направления работает с временной сложностью $O\; (S\; 2\; T)\; \{\backslash \; displaystyle\; O\; (S\; ^\; \{2\}\; T)\}$в пространстве $O\; (ST)\; \{\backslash \; displaystyle\; O\; (ST)\}$, где $T\; \{\backslash \; displaystyle\; T\}$- длина временной последовательности, а $S\; \{\backslash \; displaystyle\; S\}$- количество символов в государственном алфавите. Алгоритм также может работать в постоянном пространстве с временной сложностью $O\; (S\; 2\; T\; 2)\; \{\backslash \; displaystyle\; O\; (S\; ^\; \{2\}\; T\; ^\; \{2\})\}$путем пересчета значений на каждом шаге.. Для сравнения, процедура грубой силы генерирует все возможные последовательности состояний $ST\; \{\backslash \; displaystyle\; S\; ^\; \{T\}\}$и вычисляет совместную вероятность каждой последовательности состояний с наблюдаемой серией событий, которая будет иметь временную сложность $O\; (T\; \cdot \; ST)\; \{\backslash \; displaystyle\; O\; (T\; \backslash \; cdot\; S\; ^\; \{T\})\}$. Грубая сила неразрешима для реалистичных задач, поскольку количество возможных последовательностей скрытых узлов обычно чрезвычайно велико.

Усовершенствованный алгоритм прямого и обратного направления, называемый островным алгоритмом, использует меньшее использование памяти для более длительного времени работы, принимая $O\; (S\; 2\; T\; log\; \; T)\; \{\; \backslash \; Displaystyle\; O\; (S\; ^\; \{2\}\; T\; \backslash \; log\; T)\}$время и $O\; (S\; 2\; log\; \; T)\; \{\backslash \; displaystyle\; O\; (S\; ^\; \{2\}\; \backslash \; log\; T)\}$память. Кроме того, можно инвертировать модель процесса, чтобы получить $O\; (S)\; \{\backslash \; displaystyle\; O\; (S)\}$пробел, $O\; (S\; 2\; T)\; \{\backslash \; displaystyle\; O\; (\; S\; ^\; \{2\}\; T)\}$временной алгоритм, хотя инвертированный процесс может не существовать или плохо обусловлен.

Кроме того, были разработаны алгоритмы для вычисления $f\; 0:\; t\; +\; 1\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{f\_\; \{0:\; t\; +\; 1\}\}\}$эффективно с помощью онлайн-сглаживания, такого как алгоритм сглаживания с фиксированной задержкой (FLS).

алгоритм forward_backward isinput: guessState int sequenceIndex output: result если sequenceIndex находится за концом последовательности, то return 1 if(guessState, sequenceIndex) был замечен до, затемreturn сохраненный результат result: = 0 для каждого соседнего состояния n: result: = result + (вероятность перехода от guessState к n данному элементу наблюдения в sequenceIndex) × Backward (n, sequenceIndex + 1) сохранить результат для (guessState, sequence Index) return result

Учитывая HMM (как и в алгоритме Витерби ), представленный на языке программирования Python :

States = ('Здоровый', 'Лихорадка') end_state = 'E' Наблюдения = ('нормальный', 'холодный', 'головокружительный') start_probability = {'Здоровый': 0,6, 'Лихорадка »: 0,4} transition_probability = { «Здоровый»: {«Здоровый»: 0,69, «Лихорадка»: 0,3, «E»: 0,01}, «Лихорадка»: {«Здоровый»: 0,4, «Лихорадка»: 0,59, «E»: 0,01},} selection_probability = {'Здоровый': {'нормальный': 0,5, 'холодный': 0,4, 'головокружительный': 0,1}, 'Лихорадка': {'нормальный': 0,1, 'холодный': 0,3, 'головокружительный': 0,6}, }

Мы можем написать реализацию алгоритма вперед-назад следующим образом:

def fwd_bkw (наблюдения, состояния, start_prob, trans_prob, emm_prob, end_st): "" "Алгоритм вперед-назад." "" # Вперед. часть алгоритма fwd = для i, наблюдение_i в перечислении (наблюдения): f_curr = {} для st в состояниях: if i == 0: # базовый вариант для прямой части prev_f_sum = start_prob [st] else: prev_f_sum = sum ( f_ prev [k] * trans_prob [k] [st] для k в состоянии) f_curr [st] = emm_prob [st] [Наблюдение_i] * prev_f_sum fwd.append (f_curr) f_prev = f_curr p_fwd = sum (f_curr [k] * trans_prob [k] [end_st] для k в состояниях) # Обратная часть алгоритма bkw = для i, наблюдение_i_plus в enumerate (обратное (наблюдение [1:] + (None,))): b_curr = {} для st in состояний: if i == 0: # базовый вариант для обратной части b_curr [st] = trans_prob [st] [end_st] else: b_curr [st] = sum (trans_prob [st] [l] * emm_prob [l] [Наблюдение_i_plus] * b_prev [l] для l в состояниях) bkw.insert (0, b_curr) b_prev = b_curr p_bkw = sum (start_prob [l] * emm_prob [l] [наблюдения [0]] * b_curr [l] для l в состояниях) # Объединение две части posterior = для i в диапазоне (len (наблюдения)): posterior.append ({st: fwd [i] [st] * bkw [i] [st] / p_fwd for st in states}) assert p_fwd == p_bkw return fwd, bkw, posterior

The function fwd_bkwtakes the following arguments: xis the sequence of observations, eg ['normal', 'cold', 'dizzy']; statesis the set of hidden states; a_0is the start probability; aare the transition probabilities; and eare the emission probabilities.

For simplicity of code, we assume that the observation sequence xis non-empty and that a[i][j]and e[i][j]is defined for all states i,j.

In the running example, the forward-backward algorithm is used as follows:

def example(): return fwd_bkw(observations, states, start_probability, transition_probability, emission_probability, end_state)

>>>for line in example():... print(*line)... {'Healthy': 0.3, 'Fever': 0.04000000000000001} {'Healthy': 0.0892, 'Fever': 0.03408} {'Healthy': 0.007518, 'Fever': 0.028120319999999997} {'Healthy': 0.0010418399999999998, 'Fever': 0.00109578} {'Healthy': 0.00249, 'Fever': 0.00394} {'Healthy': 0.01, 'Fever': 0.01} {'Healthy': 0.8770110375573259, 'Fever': 0.1229889624426741} {'Healthy': 0.623228030950954, 'Fever': 0.3767719690490461} {'Healthy': 0.2109527048413057, 'Fever': 0.7890472951586943}

• Baum–Welch algorithm
• Viterbi algorithm
• BCJR algorithm

• Lawrence R. Rabiner, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. Proceedings of the IEEE, 77 (2), p. 257–286, February 1989. 10.1109/5.18626
• Lawrence R. Rabiner, B. H. Juang (January 1986). "An introduction to hidden Markov models". IEEE ASSP Magazine: 4–15.
• Eugene Charniak (1993). Statistical Language Learning. Кембридж, Массачусетс: MIT Press. ISBN 978-0-262-53141-2.
• Stuart Russell and Peter Norvig (2010). Artificial Intelligence A Modern Approach 3rd Edition. Upper Saddle River, New Jersey: Pearson Education/Prentice-Hall. ISBN 978-0-13-604259-4.

• An interactive spreadsheet for teaching the forward–backward algorithm (spreadsheet and article with step-by-step walk-through)
• Tutorial of hidden Markov models including the forward–backward algorithm
• Collection of AI algorithms implemented in Java (including HMM and the forward–backward algorithm)