Вперед – обратный алгоритм

Эта статья включает в себя список ссылок , связанных материалов или внешних ссылок , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Апрель 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,\dots ,T\}}$${\displaystyle t}$${\displaystyle P(X_{t}\ |\ o_{1:t})}$${\displaystyle t}$${\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_{t}}$

Как указано выше, алгоритм состоит из трех шагов:

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

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

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

Прямые вероятности [ править ]

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

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

Усовершенствование общего алгоритма вперед-назад, называемого алгоритмом острова , использует меньшее использование памяти для более длительного времени работы, отнимая время и память. Кроме того, можно инвертировать модель процесса для получения пространственно- временного алгоритма, хотя инвертированный процесс может не существовать или быть плохо обусловленным . ^[3]${\displaystyle O(S^{2}T\log T)}$${\displaystyle O(S^{2}\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: result  : = result + (вероятность перехода от guessState к n заданный элемент наблюдения в sequenceIndex ) × Назад (n, sequenceIndex + 1) сохранить результат для ( guessState , sequenceIndex ) вернуть  результат

Пример Python [ править ]

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

состояния  =  ( 'Здоровый' ,  'Лихорадка' ) end_state  =  'E' наблюдения  =  ( 'нормальный' ,  'холодный' ,  'головокружительный' ) start_probability  =  { 'Здоровый' :  0,6 ,  'Лихорадка' :  0,4 } transition_probability  =  {  'Healthy'  :  { 'Healthy' :  0,69 ,  'Fever' :  0,3 ,  'E' :  0,01 },  'Fever'  :  { 'Healthy' :  0,4 ,  'Fever' :  0,59 ,  'E' :  0,01 } ,  } эмиссия_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  в  enumerate ( наблюдения ):  f_curr  =  { }  для  ст  в  состояниях :  если  я  ==  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 . добавить ( f_curr )  f_prev  =  f_curr p_fwd  =  sum ( f_curr [ k ]  *  trans_prob [ k ] [ end_st ]  для  k  в  состояниях ) # Обратная часть алгоритма  bkw  =  []  для  i ,  наблюдение_i_plus  в  перечислении ( обратное ( наблюдение [ 1 :]  +  ( None ,))):  b_curr  =  {}  для  st  в  состояниях :  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 . вставить ( 0 , b_curr )  b_prev  =  b_curr p_bkw  =  sum ( start_prob [ l ]  *  emm_prob [ l ] [ наблюдения [ 0 ]]  *  b_curr [ l ]  для  l  в  состояниях ) # Объединение двух частей  posterior  =  []  для  i  in  range ( len ( наблюдения )):  posterior . append ({ st :  fwd [ i ] [ st ]  *  bkw [ i ] [ st ]  /  p_fwd  для  st  в  состояниях }) 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.

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

Защиту  пример ():  возвращение  fwd_bkw ( наблюдения ,  состояние ,  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} { «Здоровый»: 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 и алгоритм вперед-назад)