Прямой-обратный алгоритм

Эта статья включает список ссылок , связанных чтений или внешних ссылок , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . Пожалуйста, помогите улучшить эту статью, введя более точные цитаты. ( Апрель 2018 г. ) ( Узнайте, как и когда удалять это сообщение )

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

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

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

${\displaystyle 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})}$

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

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

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

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

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

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

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

${\displaystyle \mathbf {T} ={\begin{pmatrix}0,7&0,3\\0,3&0,7\end{pmatrix}}}$

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

${\displaystyle \mathbf {B} ={\begin{pmatrix}0,9&0,1\\0,2&0,8\end{pmatrix}}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \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, а масштабированный вектор вероятности дает нам вероятность нахождения в каждом состоянии в этот момент времени.

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \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)}$

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

Таким образом, значения предоставляют вероятность нахождения в каждом состоянии в момент времени t. Как таковые, они полезны для определения наиболее вероятного состояния в любой момент времени. Термин «наиболее вероятное состояние» несколько двусмыслен. В то время как наиболее вероятное состояние с наибольшей вероятностью будет правильным в данной точке, последовательность индивидуально вероятных состояний вряд ли будет наиболее вероятной последовательностью. Это происходит потому, что вероятности для каждой точки вычисляются независимо друг от друга. Они не учитывают вероятности перехода между состояниями, и, таким образом, возможно получить состояния в два момента (t и t+1), которые оба наиболее вероятны в эти моменты времени, но которые имеют очень малую вероятность возникнуть вместе, т. е . Наиболее вероятную последовательность состояний, которая создала последовательность наблюдения, можно найти с помощью алгоритма Витерби .${\displaystyle \mathbf {\gamma _{t}} (i)}$${\displaystyle \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%-ный шанс измениться. Тогда вероятности перехода таковы:

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

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

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

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

${\displaystyle \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}}}$

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

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

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

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

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

вместо:

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

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

${\displaystyle (\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}}}$

${\displaystyle (\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}}}$

${\displaystyle (\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}}}$

${\displaystyle (\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}}}$

${\displaystyle (\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}}}$

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

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

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

${\displaystyle \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}}}$

${\displaystyle \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}}}$

${\displaystyle \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}}}$

${\displaystyle \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}}}$

${\displaystyle \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, поскольку мы не масштабировали обратные вероятности с помощью найденных ранее. Векторы обратной вероятности выше, таким образом, фактически представляют вероятность каждого состояния в момент времени t с учетом будущих наблюдений. Поскольку эти векторы пропорциональны фактическим обратным вероятностям, результат должен быть масштабирован дополнительно.${\displaystyle c_{t}}$

${\displaystyle (\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}}}$

${\displaystyle (\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}}}$

${\displaystyle (\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}}}$

${\displaystyle (\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}}}$

${\displaystyle (\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}}}$

${\displaystyle (\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}}}$

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

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

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

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

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

алгоритм forward_backward имеет  входные данные: guessState int sequenceIndex  вывод:  результат если  sequenceIndex находится за пределами конца последовательности, то  вернуть 1, если ( guessState , sequenceIndex ) был замечен ранее , то  вернуть сохраненный результат результат  := 0 для каждого соседнего состояния n: результат  := результат + (вероятность перехода из guessState в n задан элемент наблюдения в sequenceIndex ) × Назад(n, ИндексПоследовательности + 1) сохранить результат для ( guessState , sequenceIndex ) вернуть  результат

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

состояния  =  ( 'Здоров' ,  'Лихорадка' ) конечное_состояние  =  'E' наблюдения  =  ( 'нормально' ,  'холодно' ,  'головокружение' ) start_probability  =  { 'Здоров' :  0,6 ,  'Лихорадка' :  0,4 } transition_probability  =  {  'Здоров'  :  { 'Здоров' :  0,69 ,  'Лихорадка' :  0,3 ,  'E' :  0,01 },  'Лихорадка'  :  { 'Здоров' :  0,4 ,  'Лихорадка' :  0,59 ,  'E' :  0,01 },  } emit_probability  =  {  'Здоров'  :  { 'нормально' :  0,5 ,  'простуда' :  0,4 ,  'головокружение' :  0,1 },  'Лихорадка'  :  { 'нормально' :  0,1 ,  'простуда' :  0,3 ,  'головокружение' :  0,6 },  }

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

def  fwd_bkw ( observations ,  states ,  start_prob ,  trans_prob ,  emm_prob ,  end_st ): """Алгоритм вперед–назад.""" # Прямая часть алгоритма fwd = [] for i , observation_i in enumerate ( observations ): f_curr = {} for st in states : if i == 0 : # базовый случай для прямой части 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 ][ наблюдение_i ]  *  prev_f_sum вперед.append ( f_curr ) f_prev = f_curr​​    p_fwd  =  сумма ( f_curr [ k ]  *  trans_prob [ k ][ end_st ]  для  k  в  состояниях ) # Обратная часть алгоритма  bkw  =  []  for  i ,  observation_i_plus  in  enumerate ( reversed ( observations [ 1 :]  +  ( None ,))):  b_curr  =  {}  for  st  in  states :  if  i  ==  0 :  # базовый случай для обратной части  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.вставить ( 0 , b_curr ) b_prev = b_curr​​    p_bkw  =  сумма ( start_prob [ l ]  *  emm_prob [ l ][ observations [ 0 ]]  *  b_curr [ l ]  для  l  в  состояниях ) # Объединение двух частей  posterior  =  []  for  i  in  range ( len ( observations )):  posterior . append ({ st :  fwd [ i ][ st ]  *  bkw [ i ][ st ]  /  p_fwd  for  st  in  states }) утверждать  p_fwd  ==  p_bkw  возвращать  вперед ,  назад ,  апостериор

Функция 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 ( наблюдения ,  состояния ,  начальная_вероятность ,  переходная_вероятность ,  эмиссионная_вероятность ,  конечное_состояние )

>>> для  строки  в  примере (): ...  вывести ( * строка ) ... {'Здорово': 0,3, 'Лихорадка': 0,040000000000000001} {'Здорово': 0,0892, 'Лихорадка': 0,03408} {'Здорово': 0,007518, 'Лихорадка': 0,028120319999999997} {'Здорово': 0,0010418399999999998, 'Лихорадка': 0,00109578} {'Здорово': 0,00249, 'Лихорадка': 0,00394} {'Здорово': 0,01, 'Лихорадка': 0,01} {'Здорово': 0,8770110375573259, 'Лихорадка': 0,1229889624426741} {'Здорово': 0,623228030950954, 'Лихорадка': 0,3767719690490461} {'Здорово': 0,2109527048413057, 'Лихорадка': 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 и алгоритм «вперед-назад»)