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

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

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

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

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

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

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

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

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

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

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

1.[math]a_i(1) = \pi_i \cdot b_i(O_1) [/math].

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

Источники

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

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