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

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

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

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

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

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

$Q_t$ — это дискретная случайная переменная, принимающая одно из $N$ значений $(1\dots 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,\dots ,q_T)$, где $q_t\in \{1\dots N\}$ является состоянием в момент $t$.

Наблюдение $Y_t$ в момент времени $t$ может иметь одно из $L$ возможных значений, $y_t\in \{o_1,\dots ,o_L\}$. Вероятность заданного вектора наблюдений в момент времени $t$ для состояния $j$ определяется как $b_j(o_i)=P(Y_t=o_i\mid Q_t=j)$ ($B=\{b_{ij}\}$ — это матрица $L$ на $N$). Последовательность наблюдений $y$ выражается как $y=(y_1,\dots ,y_T)$.

Следовательно, мы можем описать скрытую модель Маркова с помощью $\lambda =(A,B,\pi )$. При заданном векторе наблюдений $y$ алгоритм Баума — Велша находит ${\lambda }^{\ast }=arg\underset{\lambda }{max}P(y\mid \lambda )$. ${\lambda }^{\ast }$ максимизирует вероятность наблюдений $y$.

Алгоритм

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

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

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

Обозначим через ${\alpha }_i(t)=p(Y_1=y_1,\dots ,Y_t=y_t,Q_t=i\mid \lambda )$ вероятность появления заданной последовательности $y_1,\dots ,y_t$ для состояния $i$ в момент времени $t$.

${\alpha }_i(t)$ можно вычислить рекурсивно:

1. ${\alpha }_i(1)={\pi }_i\cdot b_i(y_1);$
2. ${\alpha }_j(t+1)=b_j(y_{t+1})\sum _{i=1}^N{\alpha }_i(t)\cdot a_{ij}.$

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

Данная процедура позволяет вычислить ${\beta }_i(t)=p(Y_{t+1}=y_{t+1},\dots ,Y_T=y_T\mid Q_t=i,\lambda )$ вероятность конечной заданной последовательности $y_{t+1},\dots ,y_T$ при условии, что мы начали из исходного состояния $i$, в момент времени $t$.

Можно вычислить ${\beta }_i(t)$:

1. ${\beta }_i(T)=p(Y_T=y_T\mid Q_t=i,\lambda )=1;$
2. ${\beta }_i(t)=\sum _{j=1}^N{\beta }_j(t+1)a_{ij}{b}_j(y_{t+1}).$

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

• ${\gamma }_i(t)\equiv p(Q_t=i\mid y,\lambda )=\frac{{\alpha }_i(t){\beta }_i(t)}{\sum _{j=1}^N{\alpha }_j(t){\beta }_j(t)},$
• ${\xi }_{ij}(t)\equiv p(Q_t=i,Q_{t+1}=j\mid y,\lambda )=\frac{{\alpha }_i(t)a_{ij}{\beta }_j(t+1)b_j(y_{t+1})}{\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i(t)a_{ij}{\beta }_j(t+1)b_j(y_{t+1})}.$

Имея $\gamma$ и $\xi$, можно вычислить новые значения параметров модели:

• ${\overline{\pi }}_i={\gamma }_i(1),$
• ${\overline{a}}_{ij}=\frac{\sum _{t=1}^{T-1}{\xi }_{ij}(t)}{\sum _{t=1}^{T-1}{\gamma }_i(t)},$
• ${\overline{b}}_i(o_k)=\frac{\sum _{t=1}^T{\delta }_{y_t,o_k}{\gamma }_i(t)}{\sum _{t=1}^T{\gamma }_i(t)}.$,

где

${\delta }_{y_t,o_k}=\{\begin{array}{cc}1& \text{если }{y}_t=o_k,\\ 0& \text{иначе}\end{array}$

индикативная функция, и $b_i^{\ast }(o_k)$ ожидаемое количество значений наблюдаемой величины, равных $o_k$ в состоянии $i$ к общему количеству состояний $i$.

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

См. также

• Алгоритм Витерби

Источники

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