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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Алгоритм Баума — Велша используется в информатике и статистике для нахождения неизвестных параметров скрытой марковской модели (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 определяется начальным распределением \pi_i=P(Q_1=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). \lambda максимизирует вероятность наблюдений O.

Алгоритм[править | править вики-текст]

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

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

Прямая процедура[править | править вики-текст]

Определим \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.

\alpha_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_{t+1},\;\ldots,\;o_T при условии, что мы начали из исходного состояния i, в момент времени t.

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

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

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

  • \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})}.

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

  • \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 и \pi, итерации продолжаются до схождения.

Источники[править | править вики-текст]

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