В последнем посте о скрытых марковских моделях (HMM) мы ни разу не решили проблему поиска наиболее вероятной последовательности используемых монет. Если вы не читали сообщение о HMM, я настоятельно рекомендую вам это сделать. Для тех из вас, кто этого не сделал, я обрисую проблему. Допустим, к вам подошел какой-то гуру и сказал вам взять монету из сумки (в сумке всего две монеты) и подбросить монету. Вы увидите либо голову, либо хвост. Затем вы кладете монету обратно в пакет и выполняете цикл еще 3 раза. Вы наблюдаете голову, хвост, хвост, голову. Гуру говорит, что даст вам миллион долларов, если вы угадаете последовательность. Гуру дает вам HMM. Поиск наиболее вероятной последовательности даст наилучшие шансы на победу, но как мы можем это найти? Как вы уже догадались из названия, мы можем использовать алгоритм Витерби.

Что такое алгоритм Витерби?

Алгоритм Витерби - это решение динамического программирования для поиска наиболее вероятной скрытой последовательности состояний. Если у нас есть набор состояний Q и набор наблюдений O, мы пытаемся найти последовательность состояний, которая максимизирует P (Q | O). По условной вероятности мы можем преобразовать P (Q | O) в P (Q, O) / P (O), но нет необходимости находить P (O), поскольку P (O) не относится к изменениям в последовательностях состояний . Мы можем просто найти последовательность состояний, которая максимизирует P (Q, O). Давайте углубимся в формулу для P (Q, O).

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

Итак, если бы мы хотели найти последовательность состояний для максимизации P (Q, O), вы могли бы представить, что это было бы довольно дорого, поскольку нам пришлось бы максимизировать P (Q, O) для всех возможных последовательностей состояний. Здесь на помощь приходит алгоритм Витерби. Алгоритм Витерби - это итеративный подход к поиску наиболее вероятной последовательности. Вместо того, чтобы находить наиболее вероятную последовательность скрытых состояний для всех наблюдений, мы просто хотим найти следующее наиболее вероятное скрытое состояние. Мы итеративно находим наиболее вероятные состояния, пока не закончим последовательность наблюдений.

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

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

Алгоритм Витерби состоит из трех шагов.

Шаг 1. Инициализация

Сначала мы создаем начальное состояние q *. Затем мы находим вероятности начальных состояний и наблюдений с учетом начальных состояний. В этом случае P (qi | q *) - это вероятность того, что начальным состоянием является qi.

Шаг 2. Индукция

Мы выполняем шаг индукции, когда t больше или равно 2 и меньше или равно T, где T - количество наблюдений + 1 (плюс 1 происходит от добавленного начального состояния). T представляет общее количество наблюдений.

Шаг 3. Прекращение действия

Пример

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

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

Из определения алгоритма нам нужно сначала инициализировать, прежде чем мы выполним шаг индукции.

Шаг инициализации

Здесь мы вычисляем вероятность наблюдения головы на монете 1 и головы на монете 2 на временном шаге 1. Вместо пользователя P (qi | q *) мы используем распределение начального состояния. Теперь, когда мы инициализировали функцию на временном шаге 1, мы можем начать шаг индукции.

Шаги индукции в момент времени t = 2

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

Я не хочу, чтобы расчеты забивали основную часть блога, поэтому я добавлю их в конец блога, если кто-то захочет взглянуть. После того, как мы закончили с вычислениями, мы обнаруживаем, что последовательность с максимальной вероятностью имеет вероятность около 1,2%. Это подводит нас к выводу, что, приложив все усилия, мы, скорее всего, не выиграем эту игру. Что касается наиболее вероятной последовательности, Coin 1, Coin 1, Coin 1, Coin 1. Такой уж неприятный способ решить проблему.

Вывод

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

Оставшиеся вычисления алгоритма Витерби