QuantAlgos

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

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

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

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