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

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

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

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

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