Скрытая марковская модель. Основы HMM, которые нужно знать

Мало знаний, большой вызов! Эта статья участвует в "Необходимые знания для программистов«Творческая деятельность.

Изучение скрытых марковских моделей рекомендуется прочитать в первую очередь«Лучшее введение в цепь Маркова для Xiaobai», мы знаем, что последовательность состояний в скрытой модели Маркова на самом деле является цепью Маркова.

Скрытая марковская модель (HMM) — это относительно классическая модель машинного обучения, которая широко используется в распознавании языков, обработке естественного языка, распознавании образов и других областях. С нынешним ростом глубокого обучения, особенно с популярностью моделей последовательностей нейронных сетей, таких как RNN и LSTM, статус HMM снизился. Однако, как и в случае с классической моделью, изучение модели HMM и соответствующего алгоритма очень полезно для нашей способности решать задачи моделирования и расширять идеи алгоритмов. В этой статье будут представлены основы модели HMM с целью получения предварительного понимания и понимания HMM после прочтения.

1. Для решения каких задач требуется модель HMM

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

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

Благодаря этим двум функциям эта проблема может быть решена с помощью модели HMM. Таких проблем в реальной жизни много. Например: "Сейчас я печатаю и пишу в блог. Серия символов, которые я набираю на клавиатуре, — это последовательность наблюдения, а абзац, который я на самом деле хочу написать, — это скрытая последовательность. Задача метода ввода — начать с наберите как можно больше серий символов.Угадайте, что я хочу написать, и поставьте вверху наиболее вероятные слова для моего выбора, что можно расценивать как модель НММ, возьмите еще одно, я с вами разговариваю, и Я произношу серию непрерывных звуков Это последовательность наблюдения, а фактическое предложение, которое я хочу выразить, является последовательностью состояний Задача вашего мозга состоит в том, чтобы судить о содержании того, что я, скорее всего, выскажу из этой серии непрерывных звуков .

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

2. Определение модели HMM

HMM模型会意图

Для модели HMM сначала мы предполагаем, что ? — это множество всех возможных скрытых состояний, а ? — множество всех возможных наблюдаемых состояний, а именно:

Q=\left\{ {}q_{1},q_{2},...,q_{N}\right\} ,V=\left\{ v_{1},v_{2,}...,v_{M}\right\}

где ? — количество возможных скрытых состояний, а ? — количество всех возможных наблюдаемых состояний.

Для последовательности длины ? ? — соответствующая последовательность состояний, ? — соответствующая последовательность наблюдения, а именно:

I=\left\{ {}i_{1},i_{2},...,i_{T}\right\} ,O=\left\{ o_{1},o_{2}...,o_{T}\right\}

Среди них любое скрытое состояние ??∈?, любое наблюдаемое состояние $O_{t}\in V$

Модель HMM делает два важных предположения:

1) Гипотеза однородной цепи Маркова. То есть скрытое состояние в любой момент времени зависит только от его предыдущего скрытого состояния. Конечно, это предположение немного экстремально, потому что очень часто одно из наших скрытых состояний зависит не только от предыдущего скрытого состояния, это могут быть первые два или первые три. Но преимущество этого предположения в том, что модель проста и ее легко решить. Если скрытое состояние в момент ? равно $i_{t}=q_{i}$ , скрытое состояние в момент времени ?+1 равно $i_{t+1}=q_{j}$ , то вероятность перехода состояния ГММ от момента времени ? к моменту времени ?+1 $a_{ij}$ Это может быть выражено как:

$a_{ij}=p\left( i_{t+1}=q_{j}\mid i_{t}=q_{t}\right)$

Таким образом, ??? может сформировать матрицу перехода состояний ? цепи Маркова:

$A=\left[ a_{ij}\right]_{N\times N}$

2) Допущение независимости от наблюдения. То есть наблюдаемое состояние в любой момент времени зависит только от скрытого состояния в текущий момент времени, что также является допущением для упрощения модели. Если скрытое состояние в момент ? равно $i_{t}=q_{j}$ , и соответствующее состояние наблюдения равно $O_{t}=V_{k}$ , то состояние наблюдения в этот момент $V_{k}$ в скрытом состоянии $Q_{j}$ Вероятность появления следующего

$b_{j}\left( k\right)$

, удовлетворять:

$b_{j}\left( k\right) =P\left( o_{t}=v_{k}\mid i_{t}=q_{j}\right)$

Таким образом, ??(?) может сформировать матрицу вероятности ?, сгенерированную состоянием наблюдения:

$B=\left[ b_{j}\left( k\right) \right]_{N\times M}$

В дополнение к этому нам нужен набор распределений вероятностей скрытых состояний в момент времени ?=1 $\Pi$ :

$\Pi =\left[ \text{π} \left( i\right) \right]_{N} \ \text{where} \text{π} \left( i\right) =P\left( i_{ 1}=q_{i}\справа)$

Модель HMM, которую можно определить по начальному распределению вероятностей скрытого состояния $\Pi$ , матрица вероятности перехода состояния $A$ и матрица вероятности наблюдаемого состояния $B$ Принять решение. $\Pi$ , $A$ определить последовательность состояний, $B$ Определите последовательность наблюдения. Следовательно, модель HMM можно представить тройкой ? следующим образом: $\lambda =\left( A,B,\Pi \right)$

3. Экземпляр модели HMM

Ниже мы используем простой пример для описания абстрагированной выше модели HMM. Это модель коробки и мяча. Предположим, у нас есть 3 ящика, в каждом ящике есть красные и белые шары, количество шаров в этих трех ящиках равно:

Коробка	1	2	3
Количество красных шаров	5	4	7
Количество белых шаров	5	6	3

Вытащите шар из ящиков следующим образом, начиная с вероятности 0,2 для первого ящика, 0,4 для второго и 0,4 для третьего. После того, как с этой вероятностью шар вытащен один раз, его возвращают обратно. Затем переместитесь из текущего поля в следующее поле, чтобы нарисовать мяч. Правило такое: если коробка, в которой в данный момент вытягивается шарик, является первой коробкой, то с вероятностью 0,5 шарик останется в первой коробке и продолжит вытягиваться, перейти во вторую коробку с вероятностью 0,2, чтобы вытащить шарик , и перейти к третьему ящику с вероятностью 0,3.Ящик с шарами. Если текущим ящиком, в котором вытягивается шарик, является второй ящик, то вероятность 0,5 все еще остается во втором ящике, чтобы продолжить вытаскивать шарик, вероятность 0,3 — в первом ящике, чтобы вытащить шарик, и вероятность 0,2 — в первом ящике. третья коробка, чтобы нарисовать мяч мяч. Если текущим ящиком для розыгрыша является третий ящик, вероятность 0,5 останется в третьем ящике и продолжит вытягивать шарик, вероятность 0,2 перейдет в первый ящик, чтобы вытянуть шарик, а вероятность 0,3 будет вытянута во вторую коробку мяч. И так далее, пока не повторится трижды, чтобы получить последовательность наблюдений за цветом шарика:

$O=\left\{ \text{красный, белый, красный} \right\}$

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

$V=\left\{ \text{красный, белый} \right\} ,M=2$

Наш набор состояний:

$Q=\left\{ \text{поле 1, поле 2, поле 3} \право\}, N=3$

Длина последовательности наблюдения и последовательности состояний равна 3.

Распределение начального состояния: $\Pi =\left( 0.2,0.4,0.4\right)^{T}$

Матрица распределения вероятности перехода состояния:

$A=\begin{pmatrix}0.5&0.2&0.3\\ 0.3&0.5&0.2\\ 0.2&0.3&0.5\end{pmatrix}$

Матрица вероятности наблюдаемого состояния:

$B=\begin{pmatrix}0.5&0.5\\ 0.4&0.6\\ 0.7&0.3\end{pmatrix}$

4. Генерация последовательностей наблюдений HMM

Из примера в предыдущем разделе мы также можем абстрагироваться от процесса генерации последовательности наблюдений HMM.

На входе модель HMM $\lambda =\left( A,B,\Pi \right)$ , длина последовательности наблюдений ?

Результатом является последовательность наблюдений $O=\left\{ {}o_{1},o_{2},...,o_{T}\right\}$

Процесс генерации выглядит следующим образом:

Сгенерируйте скрытые состояния ?1 в соответствии с начальным распределением вероятностей состояний Π
for t from 1 to T
1. Распределение наблюдаемого состояния в соответствии со скрытым состоянием ?? $b_{i_{t}}\left( k\right)$ Создать состояние наблюдения $o_{t}$
2. Согласно распределению вероятности перехода скрытого состояния ?? $a_{i_{t}\ i_{t+1}}$ генерировать скрытое состояние $i_{t+1}$

все $o_{t}$ вместе образуют последовательность наблюдений $O=\left\{ {}o_{1},o_{2},...,o_{T}\right\}$

5. Три основные проблемы модели HMM

В модели HMM необходимо решить три классические проблемы:

Оцените вероятности последовательности наблюдений. То есть, учитывая модель ?=(?,?,Π) и последовательность наблюдений $O=\left\{ {}o_{1},o_{2},...,o_{T}\right\}$ , вычисляет вероятность ?(?|?) наблюдаемой последовательности ? в рамках модели ?. Решение этой задачи требует использования прямого-обратного алгоритма, который является простейшей из трех задач модели НММ.
Проблема изучения параметров модели. то есть заданная последовательность наблюдений $O=\left\{ {}o_{1},o_{2},...,o_{T}\right\}$ , оценивая параметры модели ?=(?,?,Π) для максимизации условной вероятности ?(?|?) последовательности наблюдений в модели. Решение этой задачи требует использования алгоритма Баума-Уэлча на основе алгоритма ЕМ, который является наиболее сложным из трех задач модели НММ.
Проблема предсказания, также известная как проблема декодирования. То есть, учитывая модель ?=(?,?,Π) и последовательность наблюдений $O=\left\{ {}o_{1},o_{2},...,o_{T}\right\}$ , для нахождения наиболее вероятной соответствующей последовательности состояний при условии заданной последовательности наблюдений.Решение этой задачи требует использования алгоритма Витерби, основанного на динамическом программировании. Эта задача является алгоритмом средней сложности среди трех задач модели HMM.

Основные ссылки статьи:

Ли Ханг, "Статистические методы обучения"
woo woo woo.cn блог на.com/pi этого человека/afraid/69…
Станция БМашинное обучение — серия выводов на доске