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

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

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

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

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

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

где akj — вероятность перехода из состояния k  в состояние j, и bj(ot)- вероятность генерации вектора параметров ot из состояния t.

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

для 1< j ≤ N идля 1< t ≤ T

2. Рекурсия.

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

… для j=2,3,....,N−1

................

3. Решение.

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

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

, где X — наиболее вероятная последовательность состояний.

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

, где — лучший путь/последовательность состояний.

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

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

для 1< j < N и для 1≤ t ≤ T

2. Рекурсия.

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

… для j=2,3,...,N−1

....................

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

3. Решение.

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

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

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

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

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

Другие стратегии, применяемые в алгоритмической торговле и биржевых роботах смотрите в моем блоге и на сайте.