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

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Алгоритм вперёд-назад»)
Перейти к: навигация, поиск

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

Краткий обзор[править | править вики-текст]

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

  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}

Прежде, чем мы начнём вычислять прямые вероятности, мы должны описать две специальные переменные, первую прямую вероятность и 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

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]