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

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

Алгоритм Баума — Велша используется в информатике и статистике для нахождения неизвестных параметров скрытой марковской модели (HMM). Он использует алгоритм «вперёд-назад» и является частным случаем обобщённого EM-алгоритма.

Алгоритм Баума — Велша оценки скрытой модели Маркова

Скрытая модель Маркова — это вероятностная модель множества случайных переменных $\{O_1,\;\ldots,\;O_t,\;Q_1,\;\ldots,\;Q_t\}$. Переменные O_t — известные дискретные наблюдения, а Q_t — «скрытые» дискретные величины. В рамках скрытой модели Маркова есть два независимых утверждения, обеспечивающих сходимость данного алгоритма:

1. t-я скрытая переменная при известной (t − 1)-ой переменной, независима от всех предыдущих (t − 1) переменных, то есть $P(Q_t\mid Q_{t-1},\;O_{t-1},\;\ldots,\;Q_1,\;O_1)=P(Q_t\mid Q_{t-1})$;
2. t-е известное наблюдение зависит только от t-го состояния, то есть не зависит от времени, $P(O_t\mid Q_t,\;Q_{t-1},\;O_{t-1},\;\ldots,\;Q_1,\;O_1)=P(O_t\mid Q_t)$.

Далее будет предложен алгоритм «предположений и максимизаций» для поиска максимальной вероятностной оценки параметров скрытой модели Маркова при заданном наборе наблюдений. Этот алгоритм так же известен как алгоритм Баума — Велша.

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

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

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

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

Алгоритм

Исходные данные: $\lambda=(A,\;B,\;\pi)$ со случайными начальными условиями.

Алгоритм итеративно обновляет параметр λ до схождения в одной точке.

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

Определим $\alpha_i(t)=p(O_1=o_1,\;\ldots,\;O_t=o_t,\;Q_t=i\mid\lambda)$, что является вероятностью получения заданной последовательности $o_1,\;\ldots,\;o_t$ для состояния i в момент времени t.

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

1. $\alpha_i(1)=\pi_i\cdot b_i(O_1);$
2. $\alpha_j(t+1)=b_j(O_{t+1})\sum^N_{i=1}{\alpha_i(t)\cdot a_{ij}}.$

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

Данная процедура позволяет вычислить вероятность конечной заданной последовательности $o_1,\;\ldots,\;o_t$ при условии, что мы начали из исходного состояния i, в момент времени t.

Можно вычислить β_i(t):

1. β_i(T) = 1;
2. $\beta_i(t)=\sum^N_{j=1}{\beta_j(t+1)a_{ij}b_j(O_{t+1})}.$

Используя α и β можно вычислить следующие значения:

• $\gamma_i(t)\equiv 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)},$
• $\xi_{ij}(t)\equiv 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})}.$

Имея γ и ξ, можно определить:

• $\bar\pi_i=\gamma_i(1),$
• $\bar{a}_{ij}=\frac{\displaystyle\sum^{T-1}_{t=1}\xi_{ij}(t)}{\displaystyle\sum^{T-1}_{t=1}\gamma_i(t)},$
• $\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)}.$

Используя новые значения A, B и π, итерации продолжаются до схождения.

Источники

1. The Baum-Welch algorithm for estimating a Hidden Markov Model
2. Baum-Welch Algorithm
3. Лекции С.Николенко по скрытым марковским моделям