Алгоритм прямого и обратного хода (или алгоритм «прямого-обратного» хода) — метод вычисления апостериорных вероятностей последовательности состояний при наличии последовательности наблюдений. Иными словами, данный метод позволяет вычислить вероятность заданной последовательности наблюдений. Алгоритм применяется в трёх алгоритмах скрытых марковских моделей.
Краткий обзор Алгоритм включает три шага: вычисление прямых вероятностей вычисление обратных вероятностей вычисление сглаженных вероятностей
Этапы прямого и обратного хода иногда интерпретируются в терминах передачи сообщений, где роль сообщений играет последовательность наблюдений. Такая терминология обусловлена способом обработки последовательности: сначала алгоритм последовательно обрабатывает наблюдения от первого до последнего (прямой ход), а затем возвращается от последнего к первому (обратный ход). На каждом шаге вычисляются вероятности, которые затем используются для расчётов на следующем шаге. Во время обратного хода алгоритм выполняет вычисление сглаженных вероятностей. Сглаживание — это процесс вычисления распределения вероятностей скрытых переменных в предыдущих состояниях при наличии всех наблюдений вплоть до текущего момента. Этот шаг позволяет алгоритму учитывать всю историю наблюдений, что обеспечивает более точные оценки.
Формальное описание Далее будем рассматривать в качестве базовой матрицы эмпирическую матрицу вероятностных значений, а не распределения вероятности. Мы преобразовываем распределения вероятности, связанные с данной скрытой марковской моделью в матричный вид следующим образом. Матрица переходных вероятностей (для) данной случайной переменной , определенных для всех возможных состояний в скрытой марковской модели, задается матрицей . В этой матрице индекс строки i обозначает начальное состояние, а индекс столбца j — конечное состояние . Рассмотрим систему, для которой вероятность остаться в том же состоянии после каждого шага равна 70 %, а вероятность перейти к другому состоянию равна 30 %. Тогда матрица переходных вероятностей выглядит следующим образом:
Аналогично, вероятности наблюдений при заданных скрытых состояниях (так называемые свидетельства) представляются в виде матрицы наблюдений . Каждый диагональный элемент этой матрицы содержит вероятность наблюдения при условии нахождения в соответствующем состоянии в момент времени t. Отметим, что t обозначает номер наблюдений в последовательности наблюдений. Остальные элементы в матрице будут равны нулю. В рассматриваемом примере первое наблюдаемое свидетельство — «зонтик». Поэтому имеет вид:
На основе этого мы можем вычислить прямую вероятность для следующего шага. Пусть набор прямых вероятностей будет сохранён в векторе . Здесь означает, что вычисленные вероятности зависят от всех прямых вероятностей от до , включая текущий вектор вероятностей, которую обозначим как . Следовательно, равно произведению матрицы наблюдений, транспонированной матрицы переходов и вектора прямых вероятностей для следующего наблюдения. После этого получается вектор, который требует нормализации, то есть полученные значения должны быть поделены на сумму всех значений в векторе. Коэффициент нормализации обозначим как α. Вычисление прямых вероятностей задается формулой:
Аналогично вычисляется вектор обратных вероятностей , начиная с конца последовательности. Пусть конец последовательности будет описан индексом , принимающим значения от конца последовательности к началу. Поэтому движение от к и вычисления каждой обратной вероятности описываются следующей формулой:
Обратите внимание, что мы используем не транспонированную матрицу и что порядок элементов изменился. Также отметим, что в качестве окончательного результата мы не используем стандартное матричное произведение, а поэлементное. Эта операция умножает каждый элемент в одном векторе на соответствующий элемент в другом. Третий и последний шаг — это вычисление сглаженных вероятностей . Сглаженные вероятности вычисляются как поэлементное произведение. Формула имеет кид как
Ниже показан следующий пример.
Пример В основе данного примера лежит задача из книги С. Рассела и П. Норвига (2003, стр. 540). Рассмотрим следующую последовательность наблюдений: «зонтик», «зонтик», «нет зонтика», «зонтик», «зонтик». Предположим, что вероятность дождя составляет 90 %, если зонтик наблюдается, и 10 %, если зонтик не наблюдается. Вероятности отсутствия дождя составляют 20 % и 80 % соответственно. Кроме того, предположим, что вероятность того, что погода останется прежней, составляет 70 %, а вероятность того, что погода изменится, — 30 %. Следующие матрицы, взятые из задачи о «мире» зонтиков, численно описывают вышеописанные наблюдения:
Прежде чем мы начнём вычислять прямые вероятности, мы должны определить две специальные переменные: первую прямую вероятность и (k+2) -ю обратную вероятность. Первая прямая вероятность в t=0 задаётся априорным распределением случайной переменной. (k+2) -я обратная вероятность задаётся вектором из единиц. Таким образом, получаем:
Теперь, когда мы вычислили прямые вероятности, мы продолжаем вычислять обратные вероятности. Описанные ниже векторы мы получаем из формулы вычисления обратной вероятности, как описано выше.
Теперь, когда мы определили прямые вероятности, мы продолжаем вычислять обратные вероятности. Описанные ниже матрицы мы получаем из формулы нахождения обратной вероятности как описано выше.
Наконец мы вычислим сглаженные значения вероятностей. Упорядочение векторов производится по формуле вычисления сглаженных значений, описанной выше.
Простейшее решение этой проблемы — прямой перебор всех возможных последовательностей скрытых состояний и вычисление их совместных вероятностей с использованием матриц переходных вероятностей и наблюдений. Совместная вероятность последовательностей вычисляется путём перемножения соответствующих вероятностей. Вычислительная сложность такого подхода составляет O(TNT), где T — длина последовательности, а N — число состояний. Это вычислительно нецелесообразно, поскольку число возможных скрытых последовательностей состояний обычно чрезвычайно велико. Вычислительная сложность алгоритма прямого и обратного хода составляет O(N2T). Существуют улучшения алгоритма, позволяющие производить вычисления, требующие памяти постоянного размера. Кроме того, для растущего t разработаны алгоритмы эффективного вычисления f1:t+1 с помощью онлайн-сглаживания с фиксированным лагом, такие как алгоритм сглаживания с фиксированным лагом (FLS), описанный Расселом и Норвигом (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) Сглаживание Скрытые марковские модели
Категория:Динамическое программирование Категория:Обнаружение и устранение ошибок Категория:Машинное обучение