Алгоритм прямого-обратного хода

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

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

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

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

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

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

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

Прежде, чем мы начнём вычислять прямые вероятности, мы должны описать две специальные переменные, первую прямую вероятность и 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.0322\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(TN^{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)
• Сглаживание (недоступная ссылка)
• Скрытые марковские модели