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

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

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

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

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

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

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

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

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

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

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

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

Пример

За основу взят пример из книги Russel & Norvig 2003 стр 540. Просмотрим следующую последовательность наблюдений (зонтик, зонтик, нет зонтика, зонтик, зонтик). Предположим что вероятность дождя, составляют 90 %, если зонтик наблюдается, и 10 %, если зонтик не наблюдается. Вероятность же отсутствия дождя 20 % и 80 % соответственно. Кроме того, предположим, что вероятность, что погода останется — 70 %, и 30 %, что погода изменится. Следующие матрицы взятые из «мира» зонтиков описывают численно, вышеупомянутые наблюдения ${𝐎}_{\mathrm{𝟏}}=\left(\begin{array}{cc}0.9& 0.0\\ 0.0& 0.2\end{array}\right){𝐎}_{\mathrm{𝟐}}=\left(\begin{array}{cc}0.9& 0.0\\ 0.0& 0.2\end{array}\right){𝐎}_{\mathrm{𝟑}}=\left(\begin{array}{cc}0.1& 0.0\\ 0.0& 0.8\end{array}\right){𝐎}_{\mathrm{𝟒}}=\left(\begin{array}{cc}0.9& 0.0\\ 0.0& 0.2\end{array}\right){𝐎}_{\mathrm{𝟓}}=\left(\begin{array}{cc}0.9& 0.0\\ 0.0& 0.2\end{array}\right)𝐓=\left(\begin{array}{cc}0.7& 0.3\\ 0.3& 0.7\end{array}\right){𝐓}^{𝐓}=\left(\begin{array}{cc}0.7& 0.3\\ 0.3& 0.7\end{array}\right)$

Прежде, чем мы начнём вычислять прямые вероятности, мы должны описать две специальные переменные, первую прямую вероятность и k+2 обратную вероятность. Первая прямая вероятность в t=0 определена предшествующей из случайной переменной. k+2 обратная вероятность определена «истинной» матрицей. Поэтому следует:

${𝐟}_{\mathrm{𝟏}\mathbf{:}\mathrm{𝟎}}=\left(\begin{array}{c}0.5\\ 0.5\end{array}\right)$

${𝐛}_{𝐤\mathbf{+}\mathrm{𝟐}\mathbf{:}𝐭}=\left(\begin{array}{c}1.0\\ 1.0\end{array}\right)$

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

${𝐟}_{\mathrm{𝟏}\mathbf{:}\mathrm{𝟏}}=\alpha \left(\begin{array}{cc}0.9& 0.0\\ 0.0& 0.2\end{array}\right)\left(\begin{array}{cc}0.7& 0.3\\ 0.3& 0.7\end{array}\right)\left(\begin{array}{c}0.5000\\ 0.5000\end{array}\right)=\alpha \left(\begin{array}{c}0.4500\\ 0.1000\end{array}\right)=\left(\begin{array}{c}0.8182\\ 0.1818\end{array}\right)$

${𝐟}_{\mathrm{𝟏}\mathbf{:}\mathrm{𝟐}}=\alpha \left(\begin{array}{cc}0.9& 0.0\\ 0.0& 0.2\end{array}\right)\left(\begin{array}{cc}0.7& 0.3\\ 0.3& 0.7\end{array}\right)\left(\begin{array}{c}0.8182\\ 0.1818\end{array}\right)=\alpha \left(\begin{array}{c}0.5645\\ 0.0745\end{array}\right)=\left(\begin{array}{c}0.8834\\ 0.1165\end{array}\right)$

${𝐟}_{\mathrm{𝟏}\mathbf{:}\mathrm{𝟑}}=\alpha \left(\begin{array}{cc}0.1& 0.0\\ 0.0& 0.8\end{array}\right)\left(\begin{array}{cc}0.7& 0.3\\ 0.3& 0.7\end{array}\right)\left(\begin{array}{c}0.8834\\ 0.1165\end{array}\right)=\alpha \left(\begin{array}{c}0.0653\\ 0.2772\end{array}\right)=\left(\begin{array}{c}0.1906\\ 0.8093\end{array}\right)$

${𝐟}_{\mathrm{𝟏}\mathbf{:}\mathrm{𝟒}}=\alpha \left(\begin{array}{cc}0.9& 0.0\\ 0.0& 0.2\end{array}\right)\left(\begin{array}{cc}0.7& 0.3\\ 0.3& 0.7\end{array}\right)\left(\begin{array}{c}0.1906\\ 0.8093\end{array}\right)=\alpha \left(\begin{array}{c}0.3386\\ 0.1247\end{array}\right)=\left(\begin{array}{c}0.7308\\ 0.2691\end{array}\right)$

${𝐟}_{\mathrm{𝟏}\mathbf{:}\mathrm{𝟓}}=\alpha \left(\begin{array}{cc}0.9& 0.0\\ 0.0& 0.2\end{array}\right)\left(\begin{array}{cc}0.7& 0.3\\ 0.3& 0.7\end{array}\right)\left(\begin{array}{c}0.7308\\ 0.2691\end{array}\right)=\alpha \left(\begin{array}{c}0.5331\\ 0.0815\end{array}\right)=\left(\begin{array}{c}0.8673\\ 0.1326\end{array}\right)$

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

${𝐛}_{\mathrm{𝟓}\mathbf{:}\mathrm{𝟓}}=\left(\begin{array}{cc}0.7& 0.3\\ 0.3& 0.7\end{array}\right)\left(\begin{array}{cc}0.9& 0.0\\ 0.0& 0.2\end{array}\right)\left(\begin{array}{c}1.0000\\ 1.0000\end{array}\right)=\left(\begin{array}{c}0.5984\\ 0.0543\end{array}\right)=\left(\begin{array}{c}0.9168\\ 0.0831\end{array}\right)$

${𝐛}_{\mathrm{𝟒}\mathbf{:}\mathrm{𝟓}}=\left(\begin{array}{cc}0.7& 0.3\\ 0.3& 0.7\end{array}\right)\left(\begin{array}{cc}0.9& 0.0\\ 0.0& 0.2\end{array}\right)\left(\begin{array}{c}0.9168\\ 0.0831\end{array}\right)=\left(\begin{array}{c}0.7308\\ 0.2691\end{array}\right)=\left(\begin{array}{c}0.8593\\ 0.1407\end{array}\right)$

${𝐛}_{\mathrm{𝟑}\mathbf{:}\mathrm{𝟓}}=\left(\begin{array}{cc}0.7& 0.3\\ 0.3& 0.7\end{array}\right)\left(\begin{array}{cc}0.1& 0.0\\ 0.0& 0.8\end{array}\right)\left(\begin{array}{c}0.8593\\ 0.1407\end{array}\right)=\left(\begin{array}{c}0.0178\\ 0.0845\end{array}\right)=\left(\begin{array}{c}0.1739\\ 0.8260\end{array}\right)$

${𝐛}_{\mathrm{𝟐}\mathbf{:}\mathrm{𝟓}}=\left(\begin{array}{cc}0.7& 0.3\\ 0.3& 0.7\end{array}\right)\left(\begin{array}{cc}0.9& 0.0\\ 0.0& 0.2\end{array}\right)\left(\begin{array}{c}0.1739\\ 0.8260\end{array}\right)=\left(\begin{array}{c}0.1405\\ 0.0189\end{array}\right)=\left(\begin{array}{c}0.8814\\ 0.1185\end{array}\right)$

${𝐛}_{\mathrm{𝟏}\mathbf{:}\mathrm{𝟓}}=\left(\begin{array}{cc}0.7& 0.3\\ 0.3& 0.7\end{array}\right)\left(\begin{array}{cc}0.9& 0.0\\ 0.0& 0.2\end{array}\right)\left(\begin{array}{c}0.8814\\ 0.1185\end{array}\right)=\left(\begin{array}{c}0.4600\\ 0.0462\end{array}\right)=\left(\begin{array}{c}0.9087\\ 0.0912\end{array}\right)$

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

$𝐬{𝐯}_{\mathrm{𝟓}}=\alpha \left(\begin{array}{c}1.0000\\ 1.0000\end{array}\right)\times \left(\begin{array}{c}0.8673\\ 0.1326\end{array}\right)=\alpha \left(\begin{array}{c}0.8673\\ 0.1326\end{array}\right)=\left(\begin{array}{c}0.8673\\ 0.1326\end{array}\right)$

$𝐬{𝐯}_{\mathrm{𝟒}}=\alpha \left(\begin{array}{c}0.9168\\ 0.0831\end{array}\right)\times \left(\begin{array}{c}0.7308\\ 0.2691\end{array}\right)=\alpha \left(\begin{array}{c}0.6699\\ 0.0223\end{array}\right)=\left(\begin{array}{c}0.9677\\ 0.0322\end{array}\right)$

$𝐬{𝐯}_{\mathrm{𝟑}}=\alpha \left(\begin{array}{c}0.8593\\ 0.1407\end{array}\right)\times \left(\begin{array}{c}0.1906\\ 0.8093\end{array}\right)=\alpha \left(\begin{array}{c}0.1637\\ 0.1138\end{array}\right)=\left(\begin{array}{c}0.5899\\ 0.4101\end{array}\right)$

$𝐬{𝐯}_{\mathrm{𝟐}}=\alpha \left(\begin{array}{c}0.1739\\ 0.8260\end{array}\right)\times \left(\begin{array}{c}0.8834\\ 0.1165\end{array}\right)=\alpha \left(\begin{array}{c}0.1536\\ 0.0962\end{array}\right)=\left(\begin{array}{c}0.6148\\ 0.3852\end{array}\right)$

$𝐬{𝐯}_{\mathrm{𝟏}}=\alpha \left(\begin{array}{c}0.8814\\ 0.1185\end{array}\right)\times \left(\begin{array}{c}0.8182\\ 0.1818\end{array}\right)=\alpha \left(\begin{array}{c}0.7211\\ 0.0215\end{array}\right)=\left(\begin{array}{c}0.9710\\ 0.0289\end{array}\right)$

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