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

Шаблон:Чистить

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

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

1. $~t$-ая скрытая переменная при известной (t-1)-ой переменной, независима от всех предыдущих $~(t-1)$ переменных, то есть $~P(O_{t}|Q_{t-1},O_{t-1},...,Q_{1},O_{1})=P(Q_{t}|Q_{t-1})$;
2. $~t$-ое известное наблюдение зависит только о $~i$-го состояния, то есть не зависит от времени, $~P(O_{t}|Q_{t},O_{1},...,Q_{1},O_{1})=P(Q_{t}|Q_{t})$.

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

$~Q_{t}$ — это дискретная случайная переменная, принимающая одно из $~N$ значений $~(1..N)$. Будем полагать, что данная модель Маркова, определенная как $~P(Q_{t}|Q_{t-1})$, однородна по времени, то есть независима от $~t$. Тогда можно задать $~P(Q_{t}|Q_{t-1})$ как независящую от времени стохастическую матрицу перемещений $~A=\{a_{ij}\}=p(Q_{t}=j|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_{i}(o_{i})=p_{j}(O_{t}=o_{t}|Q_{t}=j)$. ($~B=\{b_{ij}\}$ — это матрица L на N). Заданная последовательность наблюдений O выражается как $~O=(O_{1}=o1,...,O_{T}=o_{T})$.

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

Алгоритм

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

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

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

Определим $~\alpha _{i}(t)=p(O_{1}=o_{1},\ldots ,O_{t}=o_{t},~Q_{t}=i|\lambda )$, что является вероятностью получения заданной последовательности $~o_{1},\ldots ,o_{t}$ для состояния $~i$ в момент времени $~t$.

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

1. $\alpha _{i}(t)=\pi _{i}\cdot b_{i}(O_{i})$,
2. $\alpha _{j}(t+1)=b_{j}(O_{t+1})\sum _{i=1}^{N}{\alpha _{i}(t)\cdot a_{ij}}$.

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

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

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

1. $~\beta _{i}(T)=1$;
2. $~\beta _{i}(t)=\sum _{j=1}^{N}{\beta _{j}(t+1)a_{ij}b_{j}(O_{t+1})}$.

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

• $~\gamma _{i}(t)\equiv p(Q_{t}=i|O,\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|O,\lambda )={\frac {\alpha _{i}(t)a_{ij}\beta _{j}(t+1)b_{j}(o_{t+1})}{\sum _{i=1}^{N}{\sum _{j=1}^{N}{\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 {\sum _{t=1}^{T-1}{\xi _{ij}(t)}}{\sum _{t=1}^{T-1}{\gamma _{i}(t)}}}$,
• $~{\bar {b}}_{i}(k)={\frac {\sum _{t=1}^{T}{\delta _{O_{t},o_{k}}\gamma _{i}(t)}}{\sum _{t=1}^{T}{\gamma _{i}(t)}}}$.

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

Источники

1. The Baum–Welch algorithm for estimating a Hidden Markov Model
2. Baum-Welch Algorithm