Алгоритм Витерби для прогнозирования с помощью HMM - Часть 3 серии HMM

Как получить наилучшую скрытую цепочку состояний из всех возможных способов?

Отказ от ответственности: это то, что я узнал о HMM за последние несколько дней и написал в потоке, который, на мой взгляд, легче понять, и это определенно не систематический способ, который может предложить вам учебник. Учебники всегда являются нашими друзьями, они дают полный и структурированный способ обучения, а материалы представлены без потери общности, но я надеюсь, что моя статья может помочь вам преодолеть некоторые узкие места на вашем пути. Удачи!

Часть 1: Архитектура скрытой марковской модели
Часть 2: Алгоритм обучения HMM: алгоритм Баума-Велча
Часть 3: Алгоритм прогнозирования с помощью обученного алгоритма HMM: Viterbi

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

Как и алгоритм Баума-Велча, наш алгоритм обучения, алгоритм Витерби также является подходом динамического программирования. Напоминаем, что динамическое программирование - это подход, при котором вы будете повторно использовать вычисленный результат в следующем вычислении, а действие повторного использования экономит время! Более того, это действительно естественный выбор для HMM, возьмите простой HMM в качестве примера, в котором любое состояние зависит от своего первого предыдущего состояния. Это утверждение, однако, не означает, что нет никакого эффекта от остальных предыдущих состояний к текущему, но все их эффекты поглощаются первым предыдущим состоянием, и это первое предыдущее состояние становится единственным фактором, который вам нужен. учитывать при переходе в следующее состояние.

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

Алгоритм Витерби

Цель алгоритма Витерби - сделать вывод на основе обученной модели и некоторых наблюдаемых данных. Он работает, задавая вопрос: учитывая обученные матрицы параметров и данные, каков выбор состояний, при которых совместная вероятность достигает максимума? Другими словами, какой выбор наиболее вероятен с учетом данных и обученной модели? Это утверждение можно представить в виде следующей формулы, и, очевидно, ответ зависит от данных!

Чтобы найти лучший набор состояний, используется следующая рекурсивная формула. Я рекомендую это видео на YouTube и это видео на YouTube за их отклонение.

Подставим вместо k = 1,2,3, чтобы мы могли легко понять эту рекурсию.

Первая формула - это начальная функция mu, которая приводит к распределению вероятностей для различного начального состояния с учетом исходных наблюдаемых данных. Здесь мы не ограничиваем себя каким-либо из этих начальных состояний, но мы определяем это в следующей формуле.

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

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

Шаг 0 состоит в том, чтобы просто перечислить все возможные состояния в момент времени 0 и их соответствующие значения вероятности, и мы не решаем, какое состояние выбрано на этом этапе.

На шаге 1 мы перебираем все возможные первые состояния (состояние в момент времени = 1) и определяем их соответствующее наилучшее начальное состояние (состояние в момент времени = 0), как показано на приведенных выше графиках. Затем мы повторяем ту же процедуру и завершаем шаг 2.

Теперь мы начинаем видеть некоторые пути. Например, если мы завершим вывод на шаге 2, то наиболее вероятным конечным состоянием будет состояние = 1, а остальные предыдущие состояния можно будет отследить с помощью стрелок, которые представляют собой состояние 2 в момент времени 0, состояние 1. в момент времени 1 и состояние 1 во время 2. Второй вероятный путь - 3–2–3, а наименее вероятный путь - 2–1–2. Очень маловероятно, что путь начинается с состояния 1.

Резюме

Алгоритм Витерби - это эффективный способ сделать вывод или предсказание скрытых состояний при условии, что параметры модели оптимизированы и с учетом наблюдаемых данных. Лучше всего визуализировать решетку, чтобы узнать, как выбирается путь от временного шага к следующему. На этом заканчивается введение в серию «Скрытые марковские модели».