uralpro личный блог

14 мая 2015, 13:34

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

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

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

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

Форвардный алгоритм позволяет эффективно рассчитать функцию вероятности p(O|λ). Форвардной переменной называется вероятность генерации моделью наблюдений до времени 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)$

где akj — вероятность перехода из состояния k в состояние j, и bj(ot)- вероятность генерации вектора параметров ot из состояния 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 ≤ N и $\alpha_1(t)=0$ для 1< t ≤ 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|λ) суммированием по всем возможным последовательностям состояний, но иногда предпочтительней аппроксимировать p(O|λ) вероятностью p^(O|λ) которая вычисляется для одной, наиболее вероятной последовательности. Для этого применяется алгоритм Витерби:

$\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_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≤ t ≤ 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|λ) может привести к ошибкам малой разрядности. Значение вероятности может быть таким маленьким, что компьютер не сможет рассчитать его верно. Вместо этого необходимо использовать вычисление натурального логарифма log(p(O|λ).

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

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

алгоритм модель Маркова математические модели

uralpro

Челябинск

457

4 790

с 19 июня 2014

17 Комментариев

Deleted Account
14 мая 2015, 14:11
Аффтырь, слишком примитивно это все. Все уже заработали по этой модели миллиарды. Давай напиши лучше про нелинейные неоднородные дифференциальные уравнения высших порядков.
+1
- Вестников (Витковский)
  14 мая 2015, 15:37
  Злой Инвестор, а я люблю в чужих карманах посчитать и помоделировать чужие скрытые состояния. И 90% здесь присутствующих любят.
  +2
- SergeyJu
  14 мая 2015, 16:45
  Злой Инвестор, во первых, не примитивно.
  Во вторых, не надо ля-ля про дифуры.
  В третьих, по слухам, на этом если кто и смог заработать, так это Ренессанс Текноложди.
  0
- Ivan
  14 мая 2015, 20:58
  Злой Инвестор, А если серьезно чем вам модель на основе марковских состояний так не нравится? Вы думаете, что модель должна быть проще?
  
  0
IliaM
14 мая 2015, 15:49
Еще-бы в excel это оформить
0
- SergeyJu
  14 мая 2015, 16:39
  IliaM, только если в VBA.
  0
Ivan
14 мая 2015, 20:48
Интересно, а какой алгроритм для оценки Скрытых марковских состояний точнее, быстрее? Витерби или еще какой?
И как определить скольк овобще состояний имеет модель(например цнновой ряд) На глаз опрделеять или есть какие-то рекомендации?
0
- uralpro
  14 мая 2015, 20:55
  Ivan, состояния определяются вашим алгоритмом. Можно так — восходящий тренд, боковик, нисходящий тренд. А можно и так: в этом режиме моя стратегия зарабатывает, а в этом — сливает
  0
  - Ivan
    14 мая 2015, 21:00
    uralpro, понятноно если состояния меняются довольно часто и с разной частотой.Например 1мин боковик 1мин тренд 5мин боковик 1мин тренд 2мин тренд 3минбоковик 1мин боковик 1мин тренд итд
    То что тогда делать? ну тоесть они в случайном порядке идут и с разной периодичностью? Почти как рендом волк
    0
    - uralpro
      14 мая 2015, 21:22
      Ivan, неважно какая продолжительность состояний, важна точность их определений. Если вы хотите ловить минутные тренды и модель позволяет это сделать, то можно вас поздравить — у вас будет высокочастотный алгоритм. Если вы не хотите так делать, что мешает детектировать тренды, например, на часовиках?
      0
      - Ivan
        14 мая 2015, 21:41
        uralpro, А как система опрделит тренд или флэт.КМожет ведь быть и такое, что система только определила, что это тренд, так он и закончится.
        Предположим у нас был сигнал (10 мин цена идет вверх- значит это тренд.А потом этот же сигнал перестанет работать.10 мин цена шла вверх, А дальше она не пойдет вверх, а наоборот боковик или вниз. Получается, что нужна какая-то оптимизация на истории.Мы берем нбеольшой промежуток веремени 10мин и по нему опрделеяем куда цена идет дальше.Если 10мин шло вверх-то тренд. Но как мне кажется у нас такая ситуацию не часто будет встречаться, а чаще будет угадайка, что произойдет если цена 10мин шла вверх? Исходя из исторических данных вряд ли это даст нам сигнал, Который с высокой вероятностью(70%, что цена после 10мин вверх и дальше еще 10-20мин будет идти вверх)
        0
        uralpro
        14 мая 2015, 21:48
        Ivan, конечно, запаздывание будет. На истории в любом случае необходимо тестировать и смотреть статистику. Определять тренды вообще не лучшая мысль для высокой частоты. Я указал направление в одном из ответов на ваш коммент, поверьте, это хорошая подсказка :)
        0
        Ivan
        14 мая 2015, 22:05
        uralpro, да спасибо, с вашими знаниями надо кандидатскую уже писать :-)
        0
        Ivan
        14 мая 2015, 22:12
        uralpro, а что вы делаете, если видите какую-то непонятную формулу в тексте, тройные интегралы, дифуры итд? Лезть по учебникам математики? Есть ли простые учебники по дифурам?
        0
        uralpro
        15 мая 2015, 06:22
        Ivan, в любом случае пытаюсь разобраться, что формула означает. Но в алгоритмах, как правило, применяются численные решения задач, поэтому достаточно подобрать правильную библиотеку
        0
        Ivan
        15 мая 2015, 10:47
        uralpro, понятно спасибо
        0
Ivan
14 мая 2015, 22:08
Тему уже подобрал Стохастические дифференциальные уравнения с пуассоновской составляющей для поиска Грааля
0