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

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

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

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

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

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

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

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

Отметьте, что мы используем не транспонированную матрицу ${\displaystyle T}$ и что значение элементов изменилось. Также отметим, что в качестве окончательного результата мы не используем обычное матричное произведение, а поточечное. Эта операция умножает каждую переменную в одной матрице с соответствующей переменной в другой. Третий и конечный шаг — это вычисление сглаженных вероятностей ${\displaystyle {\mbox{sv}}_{\mathrm {k} }}$. Сглаженые вероятности полученные поточечным произведением Формула определена как ${\displaystyle {\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 %, что погода изменится. Следующие матрицы взятые из «мира» зонтиков описывают численно, вышеупомянутые наблюдения ${\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}}~~\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 обратная вероятность определена «истинной» матрицей. Поэтому следует:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Более простое решение этой проблемы — перебор всех возможных последовательностей наблюдаемых событий и скрытых состояний с их вероятностями, используя две матрицы перехода. Совместная вероятность двух последовательностей вычисляется путём умножения соответствующих вероятностей. У этого алгоритма есть временная сложность ${\displaystyle O(TN^{T})}$ где T — длина последовательностей, и N — число символов в алфавите состояний . Это затруднительно, поскольку число возможных скрытых последовательностей узла обычно чрезвычайно высоко. У алгоритма прямого-обратного хода временная сложность составляет ${\displaystyle O(N^{2}T)}$. Существуют улучшения алгоритма, позволяющие производить вычисления в области памяти постоянного размера. Кроме того, для растущего t разработаны алгоритмы эффективного вычисления ${\displaystyle {\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)
• Сглаживание (недоступная ссылка)
• Скрытые марковские модели