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

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

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

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

Ответы

Ответ 1

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

equation 1, где equation 2

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

Equation 3

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

LAWRENCE R. RABINER, учебное пособие по Скрытые марковские модели и избранные Приложения в распознавании речи

Ответ 2

Короче говоря:

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

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

Ответ 3

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

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