Markov&HMM | UnderSkyAi

Это 17-й день моего участия в августовском испытании обновлений. Ознакомьтесь с подробностями мероприятия: Испытание августовского обновления

Markov

Модель Маркова отличается от моделей регрессии и классификации, которые имеют дело с независимыми выборочными данными.Данные временного ряда, то есть данные с отношениями временного ряда между выборками. Основная идея Маркова: «Текущее состояние связано только с состоянием в предыдущий момент и не имеет ничего общего с состоянием любого другого момента до». Лично я считаю, что это самая большая проблема Маркова, почему — в конце статьи. Давайте рассмотрим пример, чтобы подробно объяснить марковскую модель.

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

Теперь вы хотите знать, в каком состоянии он находится в n-й день, ест, играет или спит? Какова вероятность возникновения этих состояний?

Сначала сделайте предположение, предполагая, что его ежедневный переход состояния имеет фиксированную вероятность. Например, если мы играем сегодня, вероятность поесть завтра равна 0,6, вероятность поспать завтра равна 0,3, а вероятность продолжить игру завтра равна 0,1, то мы можем построить следующую матрицу

Эта матрицаМатрица вероятности перехода состояния $P$ , и этопостоянный, то есть матрица вероятности перехода состояния в первый день такая же, как матрица вероятности перехода состояния во второй день и каждый последующий день.

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

Чтобы привести очень простой пример, предположим, что вероятность того, что этот человек будет есть, играть и спать 1 октября, равна $S_1=(0.6, 0.2, 0.2)$ ,Так

Вектор распределения состояний на 2 октября $S_2=S_1 * P = (0.22, 0.4, 0.38)$

Вектор распределения штатов на 3 октября $S_3=S_2 * P=(0.236,0.496,0.268)$ (Смотри, следуй $S_1$ ничего просто $S_2$ Связанный)

Вектор распределения штатов на 4 октября $S_4=S_3 * P$ (Смотрите, просто следуйте $S_3$ Связанный)

Вектор распределения состояний за октябрь n $S_n=S_{n-1}*P$ (Смотрите, он следует только за состоянием перед ним $S_{n-1}$ Связанный)

Вот вам и простой марковский контент. Наконец, подведем итоги, собственно, если вы хотите вычислить состояние n-го момента $S_n$ , нужно только рассчитать $S_1*P^n$ Просто

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

Предположим, мы делим путь поровну на 5 моментов (синие точки на рисунке). Мы можем подумать о процессе принятия решений этой женщиной: она, должно быть, хотела пойти домой, как только вышла из торгового центра, и у нее уже была идея в сердце.длиннаяпланирование. Что, если Марков сделал предсказания? Марковская модель рассматривает это каккороткий срокОно думает, что этот человек вдруг захотел уйти домой только в начале зеленой точки Марков не знает и ему все равно, что вы думаете до этого, потому что, по его мнению, самое главное — это состояние предыдущего момента .

Лично я думаю, что у Маркова в любом случае большие проблемы с данными временных рядов. Это также то, что я обнаружил, когда писал статью.Первоначально в статье планировалось использовать модель Маркова, но позже она была изменена на модель, которая может предсказывать долгосрочные тренды + стратегия коррекции Маркова. Если вам интересно, вы можете прочитать мою статьюбумага

HMM (скрытая марковская модель)

Скрытый значит невидимый. Заимствуем фразу: «Когда пакетик с маслом в лапше быстрого приготовления затвердевает, отаку знает, что приближается зима». Сезон (зима) здесь является скрытой переменной, отаку (наблюдатель) не выходит на улицу, поэтому он не может видеть погоду, он может видеть только приправу для лапши быстрого приготовления (наблюдаемый результат). В дополнение к требованию фиксированной вероятности перехода между самими скрытыми состояниями, HMM также требует отношения фиксированной вероятности между последовательностью наблюдения и последовательностью скрытых состояний.

Предполагать $Q$ множество всех возможных (скрытых) состояний, $V$ множество всех возможных наблюдений:

Q=\{q_1, q_2, ..., q_N\}, V=\{v_1,v_2,...,v_M\}

в, $N$ число возможных состояний, $M$ число возможных наблюдений.

$I$ длина $T$ последовательность состояний, $O$ – соответствующая последовательность наблюдений:

I=(i_1, i_2, ..., i_T), O=(o_1, o_2, ..., o_T)

$A$ - (скрытая) матрица вероятности перехода состояния:

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

в,

a_{ij}=P(i_{t+1}=q_j\mid i_t=q_i),\ \ \ \ i,j=1, 2, ..., N

выражено на данный момент $t$ в состоянии $q_i$ состояние, на данный момент $t+1$ переход в состояние $q_j$ Вероятность. Например, сейчас зима, а вероятность перехода на весну, осень и лето в следующий момент

$B$ матрица наблюдения:

B=[b_j(k)]_{N\times M}

в,

b_j(k)=P(o_t=v_k\mid i_t=q_j),\ \ \ \ k=1,2,...,M;\ \ j=1,2,...,N

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

$\pi$ – вектор вероятности начального состояния:

\pi =(\pi_i)

в,

\pi_i = P(i_1=q_i),\ \ \ \ i=1,2,...,N

время для шоу $t=1$ в состоянии $q_i$ Вероятность. Например, вероятность четырех сезонов весны, лета, осени и зимы в начале

Скрытая марковская модель по вектору вероятности начального состояния $\pi$ , матрица вероятности перехода состояния $A$ и матрица вероятности наблюдения $B$ Принять решение. $\pi$ и $A$ определить последовательность состояний, $B$ Определите последовательность наблюдения. Так скрытая марковская модель $\lambda$ может быть представлено троичной записью, т.е.

\lambda=(A,B, \pi)

$A,B,\pi$ три элемента, называемые скрытыми марковскими моделями

Матрица вероятности перехода состояния $A$ с вектором вероятности начального состояния $\pi$ Выявлены скрытые цепи Маркова, генерирующие ненаблюдаемые последовательности состояний. Матрица вероятности наблюдения B определяет, как наблюдения генерируются из состояний, а комбинация с последовательностью состояний определяет, как генерируется последовательность наблюдений.

Из определения скрытая марковская модель делает два основных предположения:

Однородная гипотеза Маркова. То есть предполагается, что скрытая цепь Маркова в любой момент времени $t$ Состояние $t$ Не имеет значения:

P(i_t\mid i_{t-1},o_{t-1},...,i_1,o_1)={P(i_t\mid i_{t-1})},\ \ \ \ t=1,2,...,T

Допущение наблюдательной независимости. То есть предполагается, что наблюдение в любой момент времени зависит только от состояния цепи Маркова в этот момент и не имеет ничего общего с другими наблюдениями и состояниями:
$P(o_t\mid i_T,o_T,i_{T-1},o_{T-1},...,i_{t+1},o_{t+1},i_t,i_{t-1},o_{t-1},...,i_1,o_1)=P(o_t\mid i_t)$

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

Рассмотрим пример скрытой марковской модели.

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

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

Последовательность наблюдений за цветом мяча формируется следующим образом:

В начале случайным образом выберите 1 ящик из 4 ящиков с равной вероятностью, случайным образом вытащите из этого ящика шарик, запишите его цвет и положите обратно.
Затем случайным образом переносите из текущего ящика в следующий ящик, по правилу: если текущий ящик — ящик 1, то следующий ящик должен быть ящиком 2; если текущий ящик — 2 или 3, то переносите влево и вправо. с вероятностью 0,4 и 0,6 ящик соответственно; если текущий ящик 4, то остаться в ящике 4 или перейти в ящик 3 с вероятностью 0,5
Определив переданный ящик, вытащите из ящика случайным образом шар, запишите его цвет и положите обратно.
Таким образом, повторите 5 раз, чтобы получить последовательность наблюдений за цветом мяча.
$O=(\текст{красный},\текст{красный},белый,белый,красный)$

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

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

Блоки соответствуют состояниям, а набор состояний:

Q=\{Коробка 1, Коробка 2, Коробка 3, Коробка 4\}, \ \ \ \ N=4

Цвет шарика соответствует наблюдению. И этот набор наблюдений:

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

Последовательность состояний и длина последовательности наблюдений $T=5$

Начальное распределение вероятностей

\pi = (0.25, 0.25, 0.25, 0.25)^T

Распределение вероятности перехода состояния

A = \begin{bmatrix} {0}&{1}&{0}&{0}\\ {0.4}&{0}&{0.6}&{0}\\ {0}&{0.4}&{0}&{0.6}\\ {0}&{0}&{0.5}&{0.5}\\ \end{bmatrix}

Наблюдаемое распределение вероятностей

B = \begin{bmatrix} {0.5}&{0.5}\\ {0.3}&{0.7}\\ {0.6}&{0.4}\\ {0.8}&{0.8}\\ \end{bmatrix}

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

Согласно определению скрытой марковской модели длина $T$ Последовательность наблюдения за $O={o_1,o_2,...,o_T}$ Процесс генерации описывается следующим образом:

Вход: скрытая марковская модель $\lambda=(A,B,\pi)$ , длина последовательности наблюдений $T$

Выход: последовательность наблюдений $O=(o_1,o_2,...,o_T)$

По начальному распределению состояний $\pi$ производить состояние $i_1$
сделать $t=1$
По статусу $i_1$ Наблюдаемое распределение вероятностей $b_{i_t}(k)$ генерировать $o_t$
По статусу $i_t$ Распределение вероятности перехода состояния $\{a_{i_ti_{t+1}}\}$ производить состояние $i_{t+1},i_{t+1}=1,2,...,N$
сделать $t=t+1$ ;если $t<T$ , перейти к шагу 3, если нет, завершить

3 основные проблемы скрытых марковских моделей (курсив)

Есть 3 основные проблемы со скрытыми марковскими моделями:

Проблема расчета вероятности. данная модель $\lambda=(A,B,\pi)$ и последовательность наблюдения $O=(o_1,o_2,...,o_T)$ , рассчитанный в модели $\lambda$ нижняя последовательность наблюдений $O$ вероятность возникновения $P(O\mid \lambda)$
проблемы с обучением. известная последовательность наблюдений $O=(o_1,o_2,...,o_T)$ , расчетная модель $\lambda=(A,B,\pi)$ такие, что наблюдаемая вероятность последовательности в этой модели $P(O\mid \lambda)$ максимум. То есть использовать метод оценки максимального правдоподобия для оценки параметров
Проблема предсказания, также известная как проблема декодирования. известная модель $\lambda=(A,B,\pi)$ и последовательность наблюдения $O=(o_1,o_2,...,o_T)$ , найти условие для заданной последовательности наблюдений $P(I\mid O)$ самая большая последовательность состояний $I=(i_1,i_2,...,i_T)$ . То есть, учитывая последовательность наблюдений, найдите наиболее вероятную соответствующую последовательность состояний.

Вероятностный метод расчета HMM

Нижеследующее в основном вводит расчет вероятности последовательности наблюдения. $P(O\mid \lambda)$ прямой и обратный алгоритмы. Сначала введите метод прямого расчета, который концептуально возможен, но невозможен с точки зрения вычислений.

1. Метод прямого расчета

данная модель $\lambda=(A,B,\pi)$ и последовательность наблюдения $O=(o_1,o_2,...,o_T)$ , вычислить последовательность наблюдений $O$ вероятность возникновения $P(O\mid \lambda)$ . Самый прямой метод — расчет непосредственно по формуле вероятности. Перечисляя все возможные длины как $T$ последовательность состояний $I=(i_1,i_2,...,i_T)$ , найти каждую последовательность состояний $I$ с последовательностью наблюдения $O=(o_1,o_2,...,o_T)$ совместная вероятность $P(O,I\mid \lambda)$ , а затем, просуммировав все возможные последовательности состояний, получим $P(O\mid \lambda)$

последовательность состояний $I=(i_1,i_2,...,i_T)$ Вероятность

P(I\mid \lambda) = \pi_{i_1}a_{i_1i_2}a_{i_2i_3}···a_{i_{T-1}i_T}

для фиксированной последовательности состояний $I=(i_1,i_2,...,i_T)$ , последовательность наблюдения $O=(o_1,o_2,...,o_T)$ Вероятность

P(O\mid I,\lambda)=b_{i_1}(o_1)b_{i_2}(o_2)···b_{i_t}(o_T)

Тогда для всех возможных последовательностей состояний $I$ Суммируем, получаем последовательность наблюдений $O$ Вероятность $P(O\mid \lambda)$ ,Сейчас

\begin{aligned} P(O\mid \lambda)&=\sum_I P(O\mid I,\lambda)P(I\mid \lambda)\\ &=\sum_{i_1,i_2,..,i_T}\pi_{i_1}b_{i_1}(o_1)a_{i_1i_2}b_{i_2}(o_2)···a_{i_{T-1}i_T}b_{i_T}(o_T) \end{aligned}

Однако приведенная выше формула очень требовательна к вычислительным ресурсам, а временная сложность составляет $O(TN^T)$ порядок, этот алгоритм не выполним

Ниже описано, как рассчитать вероятность последовательности наблюдений. $P(O\mid \lambda)$ Эффективный алгоритм для: вперед-назад алгоритм

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

Сначала определите форвардную вероятность. Учитывая скрытую марковскую модель $\lambda$ , определено на данный момент $t$ Часть последовательности наблюдений $o_1,o_2,...,o_t$ и статус $q_i$ Вероятность - это прямая вероятность, обозначаемая как

\alpha_t(i)=P(o_1,o_2,...,o_t,i_t=q_i\mid \lambda)

Перспективную вероятность можно найти рекурсивно $\alpha_t(i)$ и вероятность последовательности наблюдений $P(O\mid \lambda)$

Вход: скрытая марковская модель $\lambda$ , последовательность наблюдения $O$

Выход: вероятность последовательности наблюдений $P(O\mid \lambda)$

(1) Начальное значение

\alpha_1(i)=\pi_ib_i(o_1),\ \ \ \ i=1,2,...,N

(2) Рекурсия, да $t=1,2,...,T-1$

\alpha_{t+1}(i)=\bigg [\sum_{j=1}^N \alpha_t(j)a_{ji}\bigg ]b_i(o_{t+1}),\ \ \ \ i=1,2,...,N

(3) Прекращение

P(O\mid \lambda)=\sum_{i=1}^N \alpha_T(i)

Форвардный алгоритм, шаг (1) инициализирует форвардную вероятность, которая является состоянием в начальный момент $i_1=q_i$ и наблюдения $o_1$ совместная вероятность . Шаг (2) представляет собой рекуррентную формулу форвардной вероятности, рассчитанную до момента $t+1$ Часть последовательности наблюдений $o_1,o_2,...,o_t,o_{t+1}$ и на данный момент $t+1$ в состоянии $q_i$ Форвардная вероятность , как показано на следующем рисунке

В квадратных скобках формулы шага (2), поскольку $\alpha_t(j)$ пора $t$ наблюдаемый $o_1,o_2,...,o_t$ и на данный момент $t$ в состоянии $q_j$ форвардная вероятность , то произведение $\alpha_t(j)a_{ji}$ вовремя $t$ наблюдаемый $o_1,o_2,...,o_t$ и на данный момент $t$ в состоянии $q_j$ и на данный момент $t+1$ достичь состояния $q_i$ совместная вероятность . для этого продукта во время $t$ все возможное $N$ состояния $q_j$ сумме, получается, что на данный момент $t$ наблюдается как $o_1,o_2,...,o_t$ и на данный момент $t+1$ в состоянии $q_i$ совместная вероятность . Значения в квадратных скобках и наблюдаемые вероятности $b_i(o_{t+1})$ Продукт точно соответствует моменту $t+1$ наблюдаемый $o_1,o_2,...,o_t,o_{t+1}$ и на данный момент $t+1$ в состоянии $q_i$ Форвардная вероятность $\alpha_{t+1}(i)$ . Шаг (3) дает $P(O\mid \lambda)$ формула расчета. так как

\alpha_T(i)=P(o_1,o_2,...,o_T,i_T=q_i\mid \lambda)

так

P(O\mid \lambda)=\sum_{i=1}^N\alpha_T(i)

В качестве примера рассмотрим модель коробки и мяча. $\lambda=(A,B,\pi)$ , набор состояний $Q=\{1,2,3\}$ , набор наблюдений $V=\{красный, белый\}$

A = \begin{bmatrix} {0.5}&{0.2}&{0.3}\\ {0.3}&{0.5}&{0.2}\\ {0.2}&{0.3}&{0.5}\\ \end{bmatrix},\ \ \ \ B= \begin{bmatrix} {0.5}&{0.5}\\ {0.4}&{0.6}\\ {0.7}&{0.3} \end{bmatrix},\ \ \ \ \pi= \begin{bmatrix} {0.2}\\ {0.4}\\ {0.4} \end{bmatrix}

Предполагать $T=3,O=(красный,белый,красный)$ , попробуйте прямой алгоритм для вычисления $P(O\mid \lambda)$

**Решение:** По прямому алгоритму

(1) Рассчитать начальное значение

\alpha_1(1)=\pi_1 b_1(o_1)=0.10\\ \alpha_1(2)=\pi_2 b_2(o_1)=0.16\\ \alpha_1(3)=\pi_3b_3(o_1)=0.28

(2) Рекурсивный расчет

\begin{aligned} &\alpha_2(1)=\bigg [\sum_{i=1}^3\alpha_1(i)a_{i1}\bigg ]b_1(o_2)=0.154\times 0.5=0.077\\ &\alpha_2(2)=\bigg [\sum_{i=1}^3\alpha_1(i)a_{i2}\bigg ]b_2(o_2)=0.184\times 0.6=0.1104\\ &\alpha_2(3)=\bigg [\sum_{i=1}^3\alpha_1(i)a_{i3}\bigg ]b_3(o_2)=0.202\times 0.3=0.0606\\ &\alpha_3(1)=\bigg [\sum_{i=2}^3\alpha_1(i)a_{i3}\bigg ]b_1(o_3)=0.04187\\ &\alpha_3(2)=\bigg [\sum_{i=2}^3\alpha_1(i)a_{i3}\bigg ]b_2(o_3)=0.03551\\ &\alpha_3(3)=\bigg [\sum_{i=2}^3\alpha_1(i)a_{i3}\bigg ]b_3(o_3)=0.05284\\ \end{aligned}

(3) Прекращение

P(O\mid \lambda)=\sum_{i=1}^3\alpha_3(i)=0.13022

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

Учитывая скрытую марковскую модель $\lambda$ , определяя момент $t$ Статус $q_i$ состояние, от $t+1$ прибыть $T$ Частичная последовательность наблюдения $o_{t+1},o_{t+2},...,o_T$ Вероятность - это обратная вероятность, обозначаемая как

\beta_t(i)=P(o_{t+1},o_{t+2},...,o_T\mid i_t=q_i,\lambda)

Обратная вероятность может быть получена рекурсией $\beta_t(i)$ вероятность последовательности наблюдений $P(O\mid \lambda)$

Вход: скрытая марковская модель $\lambda$ , последовательность наблюдения $O$

Выход: вероятность последовательности наблюдений $P(O\mid \lambda)$

(1)

\beta_t(i)=1, \ \ i=1,2,...,N

(2 пары $t=T-1,T-2,...,1$

\beta_t(i)=\sum_{j=1}^N a_{ij}b_j(o_{t+1})\beta_{t+1}(j),\ \ i=1,2,...,N

(3)

P(O\mid \lambda)=\sum_{i=1}^N \pi_i b_i(o_1)\beta_1(i)

Шаг (1) Инициализировать обратную вероятность для всех состояний в последний момент $q_i$ Регулирование $\beta_t(i)=1$ . Шаг (2) представляет собой рекурсивную формулу обратной вероятности. Как показано ниже

Для расчета на данный момент $t$ Статус $q_i$ время в условиях $t+1$ Последующая последовательность наблюдений $o_{t+1},o_{t+2},...,o_T$ Обратная вероятность $\beta_t(i)$ , просто рассмотрите момент $t+1$ все возможное $N$ состояния $q_j$ Вероятность перехода (т.е. $a_{ij}$ срок), и наблюдения в этом состоянии $o_{t+1}$ Наблюдаемая вероятность (т.е. $b_j(o_{t+1})$ пункт), то рассмотрим состояние $q_j$ Обратная вероятность последующей последовательности наблюдений (т. $\beta_{t+1}(j)$ пункт). Шаг (3) Поиск $P(O\mid \lambda)$ Идея та же, что и в шаге (2), только начальная вероятность $\pi_i$ Альтернативные вероятности перехода

Используя определения прямой вероятности и обратной вероятности, вероятность последовательности наблюдений может быть $P(O\mid \lambda)$ написано в унисон

P(O\mid \lambda)=\sum_{i=1}^N\sum_{j=1}^N\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j),\ \ t = 1,2,...,T-1