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

Алгоритм «прямого-обратного» хода — алгоритм для вычисления апостериорных вероятностей последовательности состояний при наличии последовательности наблюдений. Иначе говоря, алгоритм, вычисляющий вероятность специфической последовательности наблюдений. Алгоритм применяется в трёх алгоритмах скрытых Марковских моделей.

Краткий обзор

Алгоритм включает три шага:

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

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

Формальное описание

Далее будем рассматривать в качестве базовой матрицы эмпирическую матрицу вероятностных значений, а не распределения вероятности. Мы преобразовываем распределения вероятности, связанные с данной скрытой Марковской моделью в матричный вид следующим образом. Матрицей переходных вероятностей $~P(\mbox{X}_\mathrm{t}|\mbox{X}_\mathrm{t-1})$ (для) данной случайной переменной$~\mbox{X}_\mathrm{t}$, представляющего все возможные состояния в скрытой марковской модели будет представлена матрицей $~T$. В этой матрице индекс строки, i, обозначает начальное состояние, а индекс столбца, j, обозначает конечное состояние . Например, в примере ниже $~T$ была определена как: $~T=\begin{pmatrix} 0.7 & 0.3 \\ 0.3 & 0.7 \end{pmatrix}$

Точно так же мы представим вероятности новых состояний для данных наблюдаемых состояний, заданных как свидетельств, в матрице наблюдений $~\mbox{O}_\mathrm{t}$, где каждый диагональный элемент содержит вероятность нового состояния, учитывая наблюдаемое состояния в момент t. Отметим, что t указывает специфическое наблюдение в последовательности наблюдений. Все другие элементы в матрице будут нулями. В примере описанный ниже первое наблюдаемое доказательство $~(t=1)$ — «зонтик». Поэтому $~\mbox{O}_\mathrm{1}$ был бы определен как: $~O_1=\begin{pmatrix} 0.9 & 0.0 \\ 0.0 & 0.2 \end{pmatrix}$

Исходя из этого описания мы можем вычислить следующую прямую вероятность. Пусть набор прямых вероятностей будет сохранён в еще одной матрице $~\mbox{f}_\mathrm{1:t+1}$. Где $~1:t+1$ указывает, вычисленные вероятности зависят от всех прямых вероятностей от $~1$ до $~t+1$ включая текущию матричную вероятность, которую мы опишем как $~\mbox{f}_\mathrm{1:t}$. Следовательно, $~\mbox{f}_\mathrm{1:t+1}$ равно произведение транспонированой матрицы с текущими прямыми вероятностями и матрицей наблюдения для следующего свидетельства в потоке наблюдения. После этого получается матрица которая требует нормализации, то есть полученные значения должны быть разделены на сумму всех значений в матрице. Коэффициент нормализации задан α. Вычисление прямых вероятностей описано формулой: $~\mbox{f}_\mathrm{1:t+1}=\alpha\mbox{O}_\mathrm{t+1}T^T \mbox{f}_\mathrm{1:t}$

Можем представить вычисление обратной вероятности $~\mbox{b}_\mathrm{k+1:t}$, который начинается в конце последовательности аналогичным способом. Пусть конец последовательности будет описан индексом $~k$, начинающийся с 0. Поэтому выполнение от $~k$ к $~t=0$ и вычисляя каждую обратную вероятность может быть описано следующей формулой: $~\mbox{b}_\mathrm{k+1:t}=T\mbox{O}_\mathrm{k+1}\mbox{b}_\mathrm{k+2:t}$

Отметьте, что мы используем не транспонированную матрицу $~T$ и что значение элементов изменилось. Также отметим, что в качестве окончательного результата мы не используем обычное матричное произведение, а поточечное. Эта операция умножает каждую переменную в одной матрице с соответствующей переменной в другой. Третий и конечный шаг — это вычисление сглаженных вероятностей $~\mbox{sv}_\mathrm{k}$. Сглаженые вероятности полученные поточечным произведением Формула определена как $~\mbox{sv}_\mathrm{k}=\alpha\mbox{b}_\mathrm{k+1:t} \mbox{f}_\mathrm{1:k}$ Ниже показан следующий пример.

Пример

За основу взят пример из книги Russel & Norvig 2003 стр 540. Просмотрим следующую последовательность наблюдений (зонтик, зонтик, нет зонтика, зонтик, зонтик). Предположим что вероятность дождя, составляют 90 %, если зонтик наблюдается , и 10 %, если зонтик не наблюдается. Вероятность же отсутствия дождя 20% и 80% соответственно. Кроме того, предположим, что вероятность, что погода останется - 70 %, и 30 %, что погода изменится. Следующие матрицы взятые из «мира» зонтиков описывают численно, вышеупомянутые наблюдения $\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{T} = \begin{pmatrix} 0.7 & 0.3 \\ 0.3 & 0.7 \end{pmatrix}~~\mathbf{T^T} = \begin{pmatrix} 0.7 & 0.3 \\ 0.3 & 0.7 \end{pmatrix}$

Наблюдение $~\mbox{O}_\mathrm{3}$ отличается от наблюдения «нет зонтика». Прежде, чем мы начнём вычислять прямые вероятности, мы должны описать две специальные переменные, первую прямую вероятность и k+2 обратную вероятность. Первая прямая вероятность в t=0 определена предшествующей из случайной переменной. k+2 обратная вероятность определена «истинной» матрицей. Поэтому следует:

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

$\mathbf{b_{k+2:t}} = \begin{pmatrix} 1.0 \\ 1.0\end{pmatrix}$

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

$\mathbf{f_{1:1}} = \alpha\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}=\alpha\begin{pmatrix}0.4500 \\ 0.1000\end{pmatrix}=\begin{pmatrix}0.8182 \\ 0.1818 \end{pmatrix}$

$\mathbf{f_{1:2}} = \alpha\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}=\alpha\begin{pmatrix}0.5645 \\ 0.0745\end{pmatrix}=\begin{pmatrix}0.8834 \\ 0.1165 \end{pmatrix}$

$\mathbf{f_{1:3}} = \alpha\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.1165 \end{pmatrix}=\alpha\begin{pmatrix}0.0653 \\ 0.2772\end{pmatrix}=\begin{pmatrix}0.1906 \\ 0.8093 \end{pmatrix}$

$\mathbf{f_{1:4}} = \alpha\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.1906 \\ 0.8093 \end{pmatrix}=\alpha\begin{pmatrix}0.3386 \\ 0.1247\end{pmatrix}=\begin{pmatrix}0.7308 \\ 0.2691 \end{pmatrix}$

$\mathbf{f_{1:5}} = \alpha\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.2691 \end{pmatrix}=\alpha\begin{pmatrix}0.5331 \\ 0.0815\end{pmatrix}=\begin{pmatrix}0.8673 \\ 0.1326 \end{pmatrix}$

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

$\mathbf{b_{5:5}} = \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}=\begin{pmatrix}0.5984 \\ 0.0543\end{pmatrix}=\begin{pmatrix}0.9168 \\ 0.0831 \end{pmatrix}$

$\mathbf{b_{4:5}} = \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.9168 \\ 0.0831 \end{pmatrix}=\begin{pmatrix}0.7308 \\ 0.2691\end{pmatrix}=\begin{pmatrix}0.8593 \\ 0.1407 \end{pmatrix}$

$\mathbf{b_{3:5}} = \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.8593 \\ 0.1407 \end{pmatrix}=\begin{pmatrix}0.0178 \\ 0.0845\end{pmatrix}=\begin{pmatrix}0.1739 \\ 0.8260 \end{pmatrix}$

$\mathbf{b_{2:5}} = \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.1739 \\ 0.8260 \end{pmatrix}=\begin{pmatrix}0.1405 \\ 0.0189\end{pmatrix}=\begin{pmatrix}0.8814 \\ 0.1185 \end{pmatrix}$

$\mathbf{b_{1:5}} = \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.8814 \\ 0.1185 \end{pmatrix}=\begin{pmatrix}0.4600 \\ 0.0462\end{pmatrix}=\begin{pmatrix}0.9087 \\ 0.0912 \end{pmatrix}$

Наконец мы вычислим сглаженные значения вероятности. Упорядочение матриц следует за формулой вычисления сглаженых значений выше.

$\mathbf{sv_{5}} = \alpha\begin{pmatrix}1.0000 \\ 1.0000 \end{pmatrix}\times \begin{pmatrix}0.8673 \\ 0.1326 \end{pmatrix}=\alpha\begin{pmatrix}0.8673 \\ 0.1326 \end{pmatrix}=\begin{pmatrix}0.8673 \\ 0.1326 \end{pmatrix}$

$\mathbf{sv_{4}} = \alpha\begin{pmatrix}0.9168 \\ 0.0831 \end{pmatrix}\times \begin{pmatrix}0.7308 \\ 0.2691 \end{pmatrix}=\alpha\begin{pmatrix}0.6699 \\ 0.0223\end{pmatrix}=\begin{pmatrix}0.9677 \\ 0.322 \end{pmatrix}$

$\mathbf{sv_{3}} = \alpha\begin{pmatrix}0.8593 \\ 0.1407 \end{pmatrix}\times \begin{pmatrix}0.1906 \\ 0.8093 \end{pmatrix}=\alpha\begin{pmatrix}0.1637 \\ 0.1138\end{pmatrix}=\begin{pmatrix}0.5899 \\ 0.4101 \end{pmatrix}$

$\mathbf{sv_{2}} = \alpha\begin{pmatrix}0.1739 \\ 0.8260 \end{pmatrix}\times \begin{pmatrix}0.8834 \\ 0.1165 \end{pmatrix}=\alpha\begin{pmatrix}0.1536 \\ 0.0962\end{pmatrix}=\begin{pmatrix}0.6148 \\ 0.3852 \end{pmatrix}$

$\mathbf{sv_{1}} = \alpha\begin{pmatrix}0.8814 \\ 0.1185 \end{pmatrix}\times \begin{pmatrix}0.8182 \\ 0.1818 \end{pmatrix}=\alpha\begin{pmatrix}0.7211 \\ 0.0215\end{pmatrix}=\begin{pmatrix}0.9710 \\ 0.0289 \end{pmatrix}$

Более простое решение этой проблемы — перебор всех возможных последовательностей наблюдаемых событий и скрытых состояний с их вероятностями, используя две матрицы перехода. Совместная вероятность двух последовательностей вычисляется путём умножения соответствующих вероятностей. У этого алгоритма есть временная сложность $O(T N^T)$ где T — длина последовательностей, и N — число символов в алфавите состояний . Это затруднительно, поскольку число возможных скрытых последовательностей узла обычно чрезвычайно высоко. У алгоритма «вперёд назад» есть временная сложность $O (N^2 T)$. Много улучшений известны для алгоритма «Вперёд-назад», которые позволяют производить вычисления в области памяти постоянного размера. Кроме того, для растущего t разработаны алгоритмы эффективного вычисления $~\mbox{f}_\mathrm{1:t+1}$ с помощью он-лайн сглаживания с фиксированым лагом, такое как сглаживание (FLS) алгоритм Russel & Norvig 2003 стр 552.

Применение

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

Псевдокод

   ForwardBackward(guessState, sequenceIndex):
   if sequenceIndex is past the end of the sequence, return 1
   if (guessState, sequenceIndex) has been seen before, return saved result
   result = 0
   for each neighboring state n:
       result = result + (transition probability from guessState to n given observation element at sequenceIndex)*ForwardBackward(n, sequenceIndex+1)
   save result for (guessState, sequenceIndex)
   return result

См. также

• Алгоритм Баума-Велша
• Скрытая марковская модель
• Цепь Маркова

Ссылки

• 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)
• Сглаживание
• Скрытые марковские модели