Алгоритм Баула-Вэлша

Алгоритм Баула-Вэлша — алгоритм для нахождения неизвестных параметров скрытой Марковской модели. Использует алгоритм прямого-обратного хода.

Описание алгоритма

Пусть $Q_t$ - это дискретная случайная переменная, принимающая одно из $N$ значений $(1..N)$. Будем полагать, что данная модель Маркова, определенная как $P(Q_t | Q_{t - 1})$ однородна по времени, то есть независима от $t$. Тогда можно задать $P(Q_t | Q_{t - 1})$ как независящую от времени стохастическую матрицу перемещений $A = \{a_{ij}\} = p(Q_t = j | Q_{t - 1} = i)$. Особый случай для времени $t = 1$ определяется начальным распределением $\pi_i = P(Q_1 = i)$.

Будем считать, что мы в состоянии $j$ в момент времени $t$, если $Q_t = j$. Последовательность заданных состояний определяется как $q = (q_1, ..., q_T)$, где $q_t \in \{ 1..N\}$ является состоянием в момент времени $t$.

Наблюдение может иметь одно из $L$ возможных значений, $Q_t \in \{o_1, ..., o_L\}$. Вероятность заданного вектора наблюдений в момент времени $t$ для состояния $j$ определяется как $b_j(o_t) = P(O_t = o_t | Q_t = j)( B = \{ b_{ij}\}$ - это матрица $L$ на $N)$. Заданная последовательность наблюдений $O$ выражается как $O = (O_1 = o_1, ..., O_T = o_T)$.

Следовательно, мы можем описать скрытую модель Маркова с помощью $\lambda = (A, B, \pi)$. При заданном векторе наблюдений $O$ алгоритм Баума-Велша находит $\lambda^*=\max_\lambda P(O\mid\lambda)$. $\lambda$ максимизирует вероятность наблюдений $O$.

Исходные данные: $\lambda = (A, B, \pi)$ со случайными начальными условиями. Алгоритм итеративно обновляет параметр $\lambda$ до схождения в одной точке.

Прямая процедура

$a_i(t) = p(O_1 = o_1, ..., O_t = o_t, Q_t = _i | \lambda$, что является вероятностью получения заданной последовательности $\{ o_1, ..., o_t\}$ для состояния $i$ в момент времени $t$.

$a_i(t)$ можно вычислить рекурсивно:

1.$a_i(1) = \pi_i \cdot b_i(O_1)$.

2.$a_j(t + 1) = b_j(O_{t + 1})\displaystyle\sum^N_{i=1}a_i(t) \cdot a_{ij}$.

Источники

1. https://ru.wikipedia.org/wiki/Алгоритм_Баума_-_Велша

2. http://logic.pdmi.ras.ru/~sergey/teaching/asr/notes-09-hmm.pdf