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

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

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

Обзор

На первом проходе алгоритм вперед-назад вычисляет набор прямых вероятностей, которые обеспечивают для всех $t\in \{1,\dots ,T\}$, вероятность оказаться в каком-либо конкретном состоянии при первом $t$ наблюдения в последовательности, т.е. $P(X_{t}\ |\ o_{1:t})$. На втором проходе алгоритм вычисляет набор обратных вероятностей, которые обеспечивают вероятность наблюдения оставшихся наблюдений с учетом любой начальной точки. $t$, то есть $P(o_{t+1:T}\ |\ X_{t})$. Эти два набора распределений вероятностей затем можно объединить, чтобы получить распределение по состояниям в любой конкретный момент времени с учетом всей последовательности наблюдений:

$P(X_{t}\ |\ o_{1:T})=P(X_{t}\ |\ o_{1:t},o_{t+1:T})\propto P(o_{t+1:T}\ |\ X_{t})P(X_{t}|o_{1:t})$

Последний шаг следует из применения правила Байеса и независимости условной $o_{t+1:T}$ и $o_{1:t}$ данный $X_{t}$.

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

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

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

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

Форвардные вероятности

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

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

$\mathbf {T} ={\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}$

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

$\mathbf {B} ={\begin{pmatrix}0.9&0.1\\0.2&0.8\end{pmatrix}}$

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

$\mathbf {P} (O=j)=\sum _{i}\pi _{i}B_{i,j}$

Вероятность данного состояния, приводящего к наблюдаемому событию j, может быть представлена ​​в матричной форме путем умножения вектора-строки состояния ( $\mathbf {\pi }$) с матрицей наблюдения ( $\mathbf {O_{j}} =\mathrm {diag} (B_{*,o_{j}})$), содержащий только диагональные элементы. Продолжая приведенный выше пример, матрица наблюдения для события 1 будет выглядеть следующим образом:

$\mathbf {O_{1}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}$

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

$\mathbf {\pi '} =\mathbf {\pi } \mathbf {O_{1}}$

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

$\mathbf {f_{0:1}} =\mathbf {\pi } _{0}\mathbf {T} \mathbf {O_{o_{1}}}$

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

$\mathbf {f_{0:t}} =\mathbf {f_{0:t-1}} \mathbf {T} \mathbf {O_{o_{t}}}$

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

$\mathbf {f_{0:t}} (i)=\mathbf {P} (o_{1},o_{2},\dots ,o_{t},X_{t}=x_{i}|\mathbf {\pi } _{0})$

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

$\mathbf {{\hat {f}}_{0:t}} =c_{t}^{-1}\ \mathbf {{\hat {f}}_{0:t-1}} \mathbf {T} \mathbf {O_{o_{t}}}$

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

$\mathbf {P} (o_{1},o_{2},\dots ,o_{t}|\mathbf {\pi } _{0})=\prod _{s=1}^{t}c_{s}$

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

$\mathbf {{\hat {f}}_{0:t}} (i)={\frac {\mathbf {f_{0:t}} (i)}{\prod _{s=1}^{t}c_{s}}}={\frac {\mathbf {P} (o_{1},o_{2},\dots ,o_{t},X_{t}=x_{i}|\mathbf {\pi } _{0})}{\mathbf {P} (o_{1},o_{2},\dots ,o_{t}|\mathbf {\pi } _{0})}}=\mathbf {P} (X_{t}=x_{i}|o_{1},o_{2},\dots ,o_{t},\mathbf {\pi } _{0})$

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

Обратная вероятность

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

$\mathbf {b_{t:T}} (i)=\mathbf {P} (o_{t+1},o_{t+2},\dots ,o_{T}|X_{t}=x_{i})$

То есть теперь мы хотим предположить, что начинаем в определенном состоянии ( $X_{t}=x_{i}$), и нас теперь интересует вероятность наблюдения всех будущих событий из этого состояния. Поскольку начальное состояние предполагается заданным (т.е. априорная вероятность этого состояния = 100%), начнем с:

$\mathbf {b_{T:T}} =[1\ 1\ 1\ \dots ]^{T}$

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

$\mathbf {b_{t-1:T}} =\mathbf {T} \mathbf {O_{t}} \mathbf {b_{t:T}}$

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

$\mathbf {{\hat {b}}_{t-1:T}} =c_{t}^{-1}\mathbf {T} \mathbf {O_{t}} \mathbf {{\hat {b}}_{t:T}}$

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

$\mathbf {{\hat {b}}_{t:T}} (i)={\frac {\mathbf {b_{t:T}} (i)}{\prod _{s=t+1}^{T}c_{s}}}$

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

$\mathbf {\gamma _{t}} (i)=\mathbf {P} (X_{t}=x_{i}|o_{1},o_{2},\dots ,o_{T},\mathbf {\pi } _{0})={\frac {\mathbf {P} (o_{1},o_{2},\dots ,o_{T},X_{t}=x_{i}|\mathbf {\pi } _{0})}{\mathbf {P} (o_{1},o_{2},\dots ,o_{T}|\mathbf {\pi } _{0})}}={\frac {\mathbf {f_{0:t}} (i)\cdot \mathbf {b_{t:T}} (i)}{\prod _{s=1}^{T}c_{s}}}=\mathbf {{\hat {f}}_{0:t}} (i)\cdot \mathbf {{\hat {b}}_{t:T}} (i)$

Чтобы понять это, заметим, что $\mathbf {f_{0:t}} (i)\cdot \mathbf {b_{t:T}} (i)$ обеспечивает вероятность наблюдения данных событий способом, проходящим через состояние $x_{i}$ во время т. Эта вероятность включает в себя прямые вероятности, охватывающие все события до момента времени t, а также обратные вероятности, которые включают все будущие события. Это числитель, который мы ищем в нашем уравнении, и мы делим его на общую вероятность последовательности наблюдений, чтобы нормализовать это значение и извлечь только вероятность того, что $X_{t}=x_{i}$. Эти значения иногда называют «сглаженными значениями», поскольку они объединяют прямую и обратную вероятности для вычисления окончательной вероятности.

Ценности $\mathbf {\gamma _{t}} (i)$ таким образом, обеспечьте вероятность пребывания в каждом состоянии в момент времени t. По существу, они полезны для определения наиболее вероятного состояния в любой момент времени. Термин «наиболее вероятное состояние» несколько неоднозначен. Хотя наиболее вероятное состояние с наибольшей вероятностью будет правильным в данной точке, последовательность индивидуально возможных состояний вряд ли будет наиболее вероятной последовательностью. Это связано с тем, что вероятности для каждой точки рассчитываются независимо друг от друга. Они не учитывают вероятности перехода между состояниями, и, таким образом, в два момента времени (t и t+1) можно получить состояния, которые наиболее вероятны в эти моменты времени, но вероятность возникновения которых вместе очень мала, т.е. $\mathbf {P} (X_{t}=x_{i},X_{t+1}=x_{j})\neq \mathbf {P} (X_{t}=x_{i})\mathbf {P} (X_{t+1}=x_{j})$. Наиболее вероятную последовательность состояний, породившую последовательность наблюдений, можно найти с помощью алгоритма Витерби .

Пример

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

$\mathbf {T} ={\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}$

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

$\mathbf {B} ={\begin{pmatrix}0.9&0.1\\0.2&0.8\end{pmatrix}}$

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

$\mathbf {O_{1}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}~~\mathbf {O_{2}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}~~\mathbf {O_{3}} ={\begin{pmatrix}0.1&0.0\\0.0&0.8\end{pmatrix}}~~\mathbf {O_{4}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}~~\mathbf {O_{5}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}$

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

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

$\mathbf {f_{0:0}} ={\begin{pmatrix}0.5&0.5\end{pmatrix}}$

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

$(\mathbf {{\hat {f}}_{0:t}} )^{T}=c_{t}^{-1}\mathbf {O_{t}} (\mathbf {T} )^{T}(\mathbf {{\hat {f}}_{0:t-1}} )^{T}$

вместо:

$\mathbf {{\hat {f}}_{0:t}} =c_{t}^{-1}\mathbf {{\hat {f}}_{0:t-1}} \mathbf {T} \mathbf {O_{t}}$

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

$(\mathbf {{\hat {f}}_{0:1}} )^{T}=c_{1}^{-1}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.5000\\0.5000\end{pmatrix}}=c_{1}^{-1}{\begin{pmatrix}0.4500\\0.1000\end{pmatrix}}={\begin{pmatrix}0.8182\\0.1818\end{pmatrix}}$

$(\mathbf {{\hat {f}}_{0:2}} )^{T}=c_{2}^{-1}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.8182\\0.1818\end{pmatrix}}=c_{2}^{-1}{\begin{pmatrix}0.5645\\0.0745\end{pmatrix}}={\begin{pmatrix}0.8834\\0.1166\end{pmatrix}}$

$(\mathbf {{\hat {f}}_{0:3}} )^{T}=c_{3}^{-1}{\begin{pmatrix}0.1&0.0\\0.0&0.8\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.8834\\0.1166\end{pmatrix}}=c_{3}^{-1}{\begin{pmatrix}0.0653\\0.2772\end{pmatrix}}={\begin{pmatrix}0.1907\\0.8093\end{pmatrix}}$

$(\mathbf {{\hat {f}}_{0:4}} )^{T}=c_{4}^{-1}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.1907\\0.8093\end{pmatrix}}=c_{4}^{-1}{\begin{pmatrix}0.3386\\0.1247\end{pmatrix}}={\begin{pmatrix}0.7308\\0.2692\end{pmatrix}}$

$(\mathbf {{\hat {f}}_{0:5}} )^{T}=c_{5}^{-1}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.7308\\0.2692\end{pmatrix}}=c_{5}^{-1}{\begin{pmatrix}0.5331\\0.0815\end{pmatrix}}={\begin{pmatrix}0.8673\\0.1327\end{pmatrix}}$

Что касается обратных вероятностей, мы начнем с:

$\mathbf {b_{5:5}} ={\begin{pmatrix}1.0\\1.0\end{pmatrix}}$

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

$\mathbf {{\hat {b}}_{4:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}1.0000\\1.0000\end{pmatrix}}=\alpha {\begin{pmatrix}0.6900\\0.4100\end{pmatrix}}={\begin{pmatrix}0.6273\\0.3727\end{pmatrix}}$

$\mathbf {{\hat {b}}_{3:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.6273\\0.3727\end{pmatrix}}=\alpha {\begin{pmatrix}0.4175\\0.2215\end{pmatrix}}={\begin{pmatrix}0.6533\\0.3467\end{pmatrix}}$

$\mathbf {{\hat {b}}_{2:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.1&0.0\\0.0&0.8\end{pmatrix}}{\begin{pmatrix}0.6533\\0.3467\end{pmatrix}}=\alpha {\begin{pmatrix}0.1289\\0.2138\end{pmatrix}}={\begin{pmatrix}0.3763\\0.6237\end{pmatrix}}$

$\mathbf {{\hat {b}}_{1:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.3763\\0.6237\end{pmatrix}}=\alpha {\begin{pmatrix}0.2745\\0.1889\end{pmatrix}}={\begin{pmatrix}0.5923\\0.4077\end{pmatrix}}$

$\mathbf {{\hat {b}}_{0:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.5923\\0.4077\end{pmatrix}}=\alpha {\begin{pmatrix}0.3976\\0.2170\end{pmatrix}}={\begin{pmatrix}0.6469\\0.3531\end{pmatrix}}$

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

$(\mathbf {\gamma _{0}} )^{T}=\alpha {\begin{pmatrix}0.5000\\0.5000\end{pmatrix}}\circ {\begin{pmatrix}0.6469\\0.3531\end{pmatrix}}=\alpha {\begin{pmatrix}0.3235\\0.1765\end{pmatrix}}={\begin{pmatrix}0.6469\\0.3531\end{pmatrix}}$

$(\mathbf {\gamma _{1}} )^{T}=\alpha {\begin{pmatrix}0.8182\\0.1818\end{pmatrix}}\circ {\begin{pmatrix}0.5923\\0.4077\end{pmatrix}}=\alpha {\begin{pmatrix}0.4846\\0.0741\end{pmatrix}}={\begin{pmatrix}0.8673\\0.1327\end{pmatrix}}$

$(\mathbf {\gamma _{2}} )^{T}=\alpha {\begin{pmatrix}0.8834\\0.1166\end{pmatrix}}\circ {\begin{pmatrix}0.3763\\0.6237\end{pmatrix}}=\alpha {\begin{pmatrix}0.3324\\0.0728\end{pmatrix}}={\begin{pmatrix}0.8204\\0.1796\end{pmatrix}}$

$(\mathbf {\gamma _{3}} )^{T}=\alpha {\begin{pmatrix}0.1907\\0.8093\end{pmatrix}}\circ {\begin{pmatrix}0.6533\\0.3467\end{pmatrix}}=\alpha {\begin{pmatrix}0.1246\\0.2806\end{pmatrix}}={\begin{pmatrix}0.3075\\0.6925\end{pmatrix}}$

$(\mathbf {\gamma _{4}} )^{T}=\alpha {\begin{pmatrix}0.7308\\0.2692\end{pmatrix}}\circ {\begin{pmatrix}0.6273\\0.3727\end{pmatrix}}=\alpha {\begin{pmatrix}0.4584\\0.1003\end{pmatrix}}={\begin{pmatrix}0.8204\\0.1796\end{pmatrix}}$

$(\mathbf {\gamma _{5}} )^{T}=\alpha {\begin{pmatrix}0.8673\\0.1327\end{pmatrix}}\circ {\begin{pmatrix}1.0000\\1.0000\end{pmatrix}}=\alpha {\begin{pmatrix}0.8673\\0.1327\end{pmatrix}}={\begin{pmatrix}0.8673\\0.1327\end{pmatrix}}$

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

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

Производительность

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

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

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

Псевдокод

algorithm forward_backward is
    input: guessState
           int sequenceIndex
    output: result

    if sequenceIndex is past the end of the sequence then
        return 1
    if (guessState, sequenceIndex) has been seen before then
        return saved result

    result := 0

    for each neighboring state n:
        result := result + (transition probability from guessState to 
                            n given observation element at sequenceIndex)
                            × Backward(n, sequenceIndex + 1)

    save result for (guessState, sequenceIndex)

    return result

Пример Python

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

states = ('Healthy', 'Fever')
end_state = 'E'
 
observations = ('normal', 'cold', 'dizzy')
 
start_probability = {'Healthy': 0.6, 'Fever': 0.4}
 
transition_probability = {
   'Healthy' : {'Healthy': 0.69, 'Fever': 0.3, 'E': 0.01},
   'Fever' : {'Healthy': 0.4, 'Fever': 0.59, 'E': 0.01},
   }
 
emission_probability = {
   'Healthy' : {'normal': 0.5, 'cold': 0.4, 'dizzy': 0.1},
   'Fever' : {'normal': 0.1, 'cold': 0.3, 'dizzy': 0.6},
   }

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

def fwd_bkw(observations, states, start_prob, trans_prob, emm_prob, end_st):
    """Forward–backward algorithm."""
    # Forward part of the algorithm
    fwd = []
    for i, observation_i in enumerate(observations):
        f_curr = {}
        for st in states:
            if i == 0:
                # base case for the forward part
                prev_f_sum = start_prob[st]
            else:
                prev_f_sum = sum(f_prev[k] * trans_prob[k][st] for k in states)

            f_curr[st] = emm_prob[st][observation_i] * prev_f_sum

        fwd.append(f_curr)
        f_prev = f_curr

    p_fwd = sum(f_curr[k] * trans_prob[k][end_st] for k in states)

    # Backward part of the algorithm
    bkw = []
    for i, observation_i_plus in enumerate(reversed(observations[1:] + (None,))):
        b_curr = {}
        for st in states:
            if i == 0:
                # base case for backward part
                b_curr[st] = trans_prob[st][end_st]
            else:
                b_curr[st] = sum(trans_prob[st][l] * emm_prob[l][observation_i_plus] * b_prev[l] for l in states)

        bkw.insert(0,b_curr)
        b_prev = b_curr

    p_bkw = sum(start_prob[l] * emm_prob[l][observations[0]] * b_curr[l] for l in states)

    # Merging the two parts
    posterior = []
    for i in range(len(observations)):
        posterior.append({st: fwd[i][st] * bkw[i][st] / p_fwd for st in states})

    assert p_fwd == p_bkw
    return fwd, bkw, posterior

Функция fwd_bkw принимает следующие аргументы: x - это последовательность наблюдений, например ['normal', 'cold', 'dizzy']; states – набор скрытых состояний; a_0 – вероятность старта; a – вероятности перехода; и e – вероятности выбросов.

Для простоты кода мы предполагаем, что последовательность наблюдений x непусто и что a[i][j] и e[i][j] определяется для всех состояний i,j.

В работающем примере алгоритм вперед-назад используется следующим образом:

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}

См. также

• Алгоритм Баума – Уэлча
• Алгоритм Витерби
• Алгоритм BCJR

Ссылки

• Лоуренс Р. Рабинер , Учебное пособие по скрытым марковским моделям и избранным приложениям в распознавании речи. Труды IEEE , 77 (2), с. 257–286, февраль 1989 г. 10.1109/5.18626.
• Лоуренс Р. Рабинер, Б. Х. Хуанг (январь 1986 г.). «Введение в скрытые модели Маркова». Журнал IEEE ASSP : 4–15.
• Евгений Чарняк (1993). Статистическое изучение языка . Кембридж, Массачусетс: MIT Press. ISBN  978-0-262-53141-2 .
• Стюарт Рассел и Питер Норвиг (2010). Искусственный интеллект: современный подход, 3-е издание . Река Аппер-Сэддл, Нью-Джерси: Pearson Education/Prentice-Hall. ISBN  978-0-13-604259-4 .

Внешние ссылки

• Интерактивная таблица для обучения алгоритму «вперед-назад» (таблица и статья с пошаговым описанием)
• Учебное пособие по скрытым марковским моделям, включая алгоритм вперед-назад.
• Коллекция алгоритмов ИИ, реализованных на Java (включая HMM и алгоритм вперед-назад)