Яндекс.Метрика
ГлавнаяМатематические модели › Модель скрытых состояний Маркова. Часть 2

Модель скрытых состояний Маркова. Часть 2

hmm-training-outline-1024x889

В предыдущей статье мы говорили об эффективных алгоритмах, необходимых для вычисления вероятностей и стат. распределений модели Маркова, которыми являются форвардный алгоритм и алгоритм Витерби. Форвардный алгоритм вычисляет вероятность данных полученных моделью по всем возможным последовательностям состояний. Алгоритм Витерби вычисляет вероятность данных полученных моделью по одной, наиболее вероятной, последовательности.

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

Форвардный алгоритм.

Форвардный алгоритм позволяет эффективно рассчитать функцию вероятности p(O|\lambda). Форвардной переменной называется вероятность генерации моделью наблюдений до времени t, и состояние j в момент времени t определяется как:

\alpha_j(t)=p(o_1,...,o_t,x(t)=j|\lambda)

Это выражение вычисляется рекурсивно через форвардную переменную в момент времени t-1 , находясь в состоянии k, и затем вычисляется состояние j  в момент времени t:

\alpha_j(t)=p(o_1,...,o_t,x(t-1)=k,x(t)=j|\lambda)=\alpha_k(t-1)a_{kj}b_j(o_t)

где a_{kj} - вероятность перехода из состояния k  в состояние j, и b_j(o_t) - вероятность генерации вектора параметров o_t из состояния t.

\alpha_j(t)=\sum_{k=1}^N p(o_1,...,o_t,x(t-1)=k,x(t)=j|\lambda)

1. Инициализация алгоритма.

\alpha_1(0)=1,\alpha_j(0)=0 для  1<j\leq N и \alpha_1(t)=0 для 1<t\leq T

2. Рекурсия.

Для t=1,2,...,T

.........для j=2,3,....,N-1

................\alpha_j(t)=b_j(o_t)[\sum_{k=1}^{N-1}\alpha_k(t-1)a_{kj}]

3. Решение.

p(O|\lambda)=\sum_{k=2}^{N-1}\alpha_k(T)a_{kN}

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

Форвардный алгоритм находит p(O|\lambda) суммированием по всем возможным последовательностям состояний, но иногда предпочтительней аппроксимировать p(O|\lambda) вероятностью \hat{p}(O|\lambda) которая вычисляется для одной, наиболее вероятной последовательности. Для этого применяется алгоритм Витерби:

\hat{p}(O|\lambda)=\max_X[p(O,X|\lambda)], где X - наиболее вероятная последовательность состояний.

Вероятность лучшего  пути длиной t по модели Маркова, заканчивающегося состоянием j определяется как:

\phi_j(t)=\max_{X^{t-1}}[p(o_1,...,o_t, x(t)=j|\lambda)], где X^{t-1} - лучший путь/последовательность состояний.

Форвардная переменная \phi также может быть вычислена рекурсивно:

\phi_j(t)=\max_i[\phi_i(t-1)a_{ij}b_j(o_t)]

1. Инициализация алгоритма.

\phi_1(0)=1,\phi_j(0)=0 для 1<j<N и \phi_1(t)=0 для 1\leq t\leq T

2. Рекурсия.

Для t=1,2,...,T

...........для j=2,3,...,N-1

.....................\phi_j(t)=\max_{1\leq k<N}[\phi_k(t-1)a_{kj}]b_j(o_t)

...................................сохранить предыдущее значение pred(j,t)=k

3. Решение.

p(O,X|\lambda)=\max_{1\leq k<N}\phi_k(T)a_{kN}

сохранить предыдущее значение pred(N,T)=k.

Наилучший путь находится путем следования по сохранненым значениям в обратном порядке по pred(j,t).

Ошибки малой разрядности

Прямое вычисление p(O|\lambda) может привести к ошибкам малой разрядности. Значение вероятности может быть таким маленьким, что компьютер не сможет рассчитать его верно. Вместо этого необходимо использовать вычисление натурального логарифма log(p(O|\lambda).

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

4 Комментарии[ Ваш комментарий ]

  1. Спасибо за интересные переводы и исследования. А можно вас попросить еще и на сайт www.long-short.ru  кросспосты делать? 

Сообщение

Обратите внимание: вы можете использоватьHTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>