В чем разница между алгоритмом "вперед-назад" и алгоритмом Витерби?

Question

В чем разница между алгоритмом прямого-обратного хода на n-граммовой модели и алгоритмом Витерби на скрытой марковской модели (HMM)?

Когда я рассматриваю реализацию этих двух алгоритмов, я обнаружил только то, что вероятность транзакции исходит из разных вероятностных моделей.

Есть ли разница между этими двумя алгоритмами?

Answer 1

Алгоритм "Вперед-Назад" объединяет шаг вперед и шаг назад, чтобы получить вероятность нахождения в каждом состоянии в определенное время. Выполнение этого для всех временных шагов может, следовательно, дать нам последовательность наиболее вероятных состояний в каждый момент времени (хотя не гарантируется, что она является действительной последовательностью, поскольку она рассматривает индивидуальное состояние на каждом шаге, и может случиться так, что вероятность p(q_i -> q_j)=0 в модели перехода), другими словами:

, где

С другой стороны, алгоритм Витерби находит наиболее вероятную последовательность состояний при заданной последовательности наблюдения, максимизируя другой критерий оптимальности:

Я предлагаю вам обратиться к этой известной статье для подробного объяснения (см. Проблему № 2):

ЛОУРЕНС Р. РАБИНЕР, Учебное пособие по скрытым марковским моделям и избранным приложениям в распознавании речи

Answer 2

Кратко говоря:

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

Витерби используется для нахождения наиболее вероятной последовательности событий. Это будет смотреть на каждую последовательность и просто выбрать последовательность, которая наиболее вероятна.

Answer 3

Взгляните на страницы 262 - 264 статьи Рабинера, и все должно стать ясно. Вот прямо цитируемый ответ - из этой статьи - на ваш вопрос:

"... Следует отметить, что алгоритм Витерби аналогичен (за исключением этапа обратного отслеживания) в реализации прямому вычислению алгоритма прямого-обратного (Уравнения 19-21). Основным отличием является максимизация в (Уравнение 33a) по предыдущим состояниям, который используется вместо процедуры суммирования в (Уравнение 20)."