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

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

История

Скрытые_Марковские_модели(HMMs) и алгоритм Баума-Велша впервые были описаны в заметках Леонарда Баума и его сверстников в конце 1960х. Одно из первых основных приложений на основе HMMs было использовано в области обработки речи. В 1980х HMMs стало эффективным инструментом в анализе биологических систем и информации, особенно в генном анализе.

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

Пусть [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].

Обратная процедура

Данная процедура позволяет вычислить вероятность конечной заданной последовательности [math]o_{t + 1}, ..., o_T[/math] при условии, что мы начали из исходного состояния [math]i[/math], в момент времени [math]t[/math].

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

1.[math]\beta_i(T) = 1[/math];

2. [math]\beta_i(t) = \displaystyle\sum^N_{j = 1}\beta_j(t + 1)a_{ij}b_j(O_{t + 1})[/math].

Обновление переменных

Определим временные переменные:

[math]\gamma_i(t) = p(Q_t=i\mid O,\;\lambda)=\frac{\alpha_i(t)\beta_i(t)}{\displaystyle\sum^N_{j=1}\alpha_j(t)\beta_j(t)}[/math]

[math]\xi_{ij}(t) = p(Q_t=i,\;Q_{t+1}=j\mid O,\;\lambda)=\frac{\alpha_i(t)a_{ij}\beta_j(t+1)b_j(o_{t+1})}{\displaystyle\sum^N_{i=1}\displaystyle\sum^N_{j=1}\alpha_i(t)a_{ij}\beta_j(t+1)b_j(O_{t+1})}[/math].

Имея [math]\gamma[/math] и [math]\xi[/math], можно определить:

[math]\bar\pi_i=\gamma_i(1)[/math],

[math]\bar{a}_{ij}=\frac{\displaystyle\sum^{T-1}_{t=1}\xi_{ij}(t)}{\displaystyle\sum^{T-1}_{t=1}\gamma_i(t)}[/math],

[math]\bar{b}_i(k)=\frac{\displaystyle\sum^T_{t=1}\delta_{O_t,\;o_k}\gamma_i(t)}{\displaystyle\sum^T_{t=1}\gamma_i(t)}[/math].

Используя новые переменные [math] A, B, \pi[/math] итерации продолжаются до схождения.

Источники

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

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

3. http://en.wikipedia.org/wiki/Baum%E2%80%93Welch_algorithm