Традиционное определение HMM исходит из неизменной поддержки Википедии, когда дело доходит до поиска новой темы:

Скрытая марковская модель (HMM) - это статистическая марковская модель, в которой моделируемая система считается марковским процессом с ненаблюдаемым (т. е. скрытые) состояния.

И снова определение марковской модели:

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

Приложение Hidden Markov Models включает в себя обучение с подкреплением и временное распознавание образов, такое как речь, почерк, распознавание жестов, тегирование части речи, отслеживание нот, частичные разряды и Биоинформатика.

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

Возьмем Лию. Леа - наш воображаемый друг, и в течение дня она делает одно из следующих четырех действий:

  • Рисование
  • Уборка дома
  • Езда на велосипеде
  • Покупка продуктов

Не так уж много жизни, не так ли? Но в любом случае это список того, что называется наблюдаемыми. А теперь предположим, что через четыре дня Леа делает следующее: красит, убирает, делает покупки, ездит на велосипеде.

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

Вот график нашего потенциального HMM:

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

  • Скрытые состояния S: в приведенном выше примере скрытыми состояниями являются солнечное и дождливое, и они сгруппированы в набор S.
  • Наблюдаемые O: покраска, уборка, покупки и велосипед. Они группируются в набор O.
  • Начальные вероятности 𝜋: матрица начальной вероятности состояния в момент времени t = 0. В этом случае вероятность того, что в первый день будет солнечно, равна 0,6, а вероятность того, что сейчас дождь, равна 0,4.
    𝜋 = | 0,6, 0,4 |
    Примечание: каждая строка следующих матриц должна давать в сумме 1, поскольку они представляют вероятность.
  • Вероятности перехода A: матрица, представляющая вероятность перехода в другое состояние с учетом текущего состояния. Например, если текущее состояние - солнечно, вероятность того, что следующий день будет солнечным, равна 0,8, тогда как вероятность того, что следующий день будет дождливым, равна 0,2.
    Аналогично, если сегодня дождливый день, вероятность того, что завтра будет дождливым также составляет 0,6, в то время как вероятность того, что завтра будет солнечно, равна 0,4.

  • Вероятности выбросов B: матрица, представляющая вероятность увидеть конкретную наблюдаемую при скрытом состоянии. Например, вероятность чистоты в солнечный день составляет 0,1, а вероятность чистоты в дождливый день - 0,45.

В более математических терминах мы бы описали свойства этой модели как таковые:

Это все очень приятно, но сразу же мы сталкиваемся с тремя проблемами:

  • Проблема правдоподобия
  • Проблема декодирования
  • Проблема обучения

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

Проблема 1 - Вероятность

Возьмем начальный пример активности Ли за четыре дня. Последовательность наблюдения следующая: покраска, чистка, покупка и велосипед.

Итак, какова вероятность того, что эта последовательность наблюдений O может быть получена из нашей HMM λ?

P(O|λ) = ???

Есть два метода, с помощью которых мы можем вычислить это: алгоритм прямого и обратный.

Прямой алгоритм

Алгоритм пересылки состоит из трех шагов:

  • Инициализация
  • Рекурсия
  • Прекращение

Инициализация

Вышеприведенное уравнение означает, что первая прямая переменная вычисляется путем умножения начальной вероятности состояния i на вероятность выброса b этого состояния при наблюдаемом O во время 1.

Как можно видеть, начальная прямая переменная состояния Sunny - это начальная вероятность появления Sunny, 0,6, умноженная на вероятность выброса от Sunny до наблюдаемой Paint, 0,4. Следовательно, 0,24.

В то время как начальная прямая переменная состояния Rainy - это начальная вероятность Rainy, 0,4, умноженная на вероятность эмиссии от Rainy до наблюдаемой Paint, 0,3. Следовательно, 0,12.

Рекурсия

Для t = 1, 2,…, T-1 мы используем уравнение рекурсии, которое определяет прямую переменную состояния j как произведение предыдущей прямой переменной состояние i, умноженное на вероятность перехода a между предыдущим состоянием i в состояние j, умноженное на выброс вероятность b от состояния j до наблюдаемого O.

Я знаю, что это жарко, но давайте взглянем на диаграмму ниже:

Здесь мы вычисляем прямую переменную состояния Sunny во время 2, суммируя результаты двух умножений:

  • Предыдущая прямая переменная предыдущего состояния Sunny, 0,24, умноженная на вероятность перехода из Sunny в Sunny, 0,8, умноженная на вероятность выброса из Sunny в Clean, 0,1.
    0,24 * 0,8 * 0,1 = 0,0192
  • Предыдущая прямая переменная предыдущего состояния Rainy, 0,12, умноженная на вероятность перехода из Rainy в Sunny, 0,4, умноженная на вероятность выброса из Sunny в Clean, 0,1.
    0,12 * 0,4 * 0,1 = 0,0048

Затем, в соответствии с приведенным выше уравнением, мы суммируем эти результаты и получаем нашу прямую переменную.

α = 0.0192 +0.0048 = 0.024

Точно так же для следующего шага у нас будет прямая переменная 0,054 для состояния Rainy:

И так до тех пор, пока у нас не будут все прямые переменные:

Прекращение

Это последнее уравнение говорит нам, что для определения вероятности последовательности наблюдений O, полученной из модели HMM λ, нам нужно просуммировать все прямые переменные в момент времени T, т. Е. все переменные каждого состояния в конце последовательности наблюдений. Следовательно, в нашем примере выше,

P(O|λ) = 0.0028512 + 0.0003048 = 0.003156

Обратный алгоритм

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

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

Инициализация

Это простое уравнение говорит нам, что в момент времени T (в конце последовательности наблюдений) обратные переменные каждого состояния равны 1. Вот и все.

Рекурсия

Приведенное выше уравнение говорит нам суммировать все умножения вероятности перехода из текущего состояния i в следующее состояние j, умноженное на вероятность излучения наблюдаемого O в момент t + 1 от следующего состояния j, умножается на обратную переменную следующего состояния j в момент t + 1.

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

Мы возвращаемся в прошлое. В момент времени T, когда последней наблюдаемой в последовательности наблюдений был Bike, обратные переменные были инициализированы как равные 1.

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

  • Вероятность перехода от солнечного состояния к солнечному, 0,8, умноженная на вероятность выброса велосипеда из солнечного состояния в момент t + 1, 0,3, умноженная на обратную переменную солнечного состояния во время t + 1, 1.
    0,8 * 0,3 * 1 = 0,24
  • Вероятность перехода из солнечного состояния в дождливый, 0,2, умноженная на вероятность выброса велосипеда из состояния дождя в момент t + 1, 0,05, умноженная на обратную переменную состояния солнечного света в момент t + 1, 1.
    0,2 * 0,05 * 1 = 0,01

Затем, в соответствии с приведенным выше уравнением, мы суммируем эти результаты и получаем обратную переменную.

β = 0.24 +0.01 = 0.25

Аналогично для состояния дождя:

Как и раньше, мы подведем итоги:

  • Вероятность перехода от дождя к солнечному, 0,4, умноженная на вероятность выброса из солнечного состояния в байк в момент t + 1, 0,3, умноженная на обратную переменную солнечного состояния во время t + 1 , 1.
    0,4 ​​* 0,3 * 1 = 0,12
  • Вероятность перехода из состояния дождя в состояние дождя, 0,6, умноженная на вероятность выброса из состояния дождя в состояние велосипеда в момент t + 1, 0,05, умноженное на обратную переменную состояния солнечного света во время t + 1 , 1.
    0,6 * 0,05 * 1 = 0,03

β = 0.12 +0.03 = 0.15

И так до тех пор, пока у нас не будут все обратные переменные:

Прекращение

Это уравнение требует, чтобы мы суммировали произведение начальной вероятности π состояния i, умноженное на вероятность выброса b наблюдаемого O в момент t = 1 из состояния i, умноженное на обратную переменную в момент t = 1 состояния i.

Поясним это на диаграмме ниже:

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

Согласно уравнению, мы суммируем следующие умножения:

  • Начальная вероятность π солнечного состояния, 0,6, умноженная на вероятность выброса из солнечного состояния в момент t = 1 до наблюдаемого состояния Paint, 0,4. , умноженное на обратную переменную состояния Sunny в момент времени t = 1, 0,0071.
    0,6 * 0,4 * 0,0071 = 0,001704
  • Начальная вероятность π состояния Rainy, 0,4, умноженная на вероятность выброса из состояния Rainy в момент времени t = 1 до наблюдаемой Paint, 0,3 , умноженное на обратную переменную состояния Rainy в момент времени t = 1, 0,0121.
    0,4 ​​* 0,3 * 0,0121 = 0,001452

P(O|λ) = 0.001704 + 0.001452 = 0.003156

И, как мы видим, результат такой же, как у прямого алгоритма.

Заключение и что дальше

Подводя итог тому, что мы узнали, мы можем сказать, что вероятность того, что Ли последние четыре дня рисовала, убиралась, ходила по магазинам и каталась на велосипеде, составляет 0,003156 с учетом модели HMM, которую мы для нее построили.

* Бонусный совет для разработчиков *

Я знаю, что эти вычисления довольно сложно выполнить вручную, и поэтому я также предлагаю вам поиграть с примером Lea на JavaScript. Я создал пакет npm под названием mary-markov, который решает все проблемы HMM с использованием требуемых алгоритмов.

Вы можете загрузить пакет npm здесь и посмотреть, как я написал код JavaScript здесь.

После того, как вы установили его с помощью npm install --save mary-markov, вы можете написать следующий код в своем файле index.js и запустить его. Это решит проблему правдоподобия путем вычисления прямого и обратного алгоритмов.

*********

Если вам удалось дочитать до этого момента, молодец! Это, безусловно, было непросто.

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

Так что держитесь, ребята!