Пусть [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] итерации продолжаются до схождения.
