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

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

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

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

1. $t$-я скрытая переменная при известной $(t-1)$-ой переменной независима от всех предыдущих $(t-1)$ переменных, то есть $P(Q_{t}\mid Q_{t-1},\;Y_{t-1},\;\ldots ,\;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},\;\ldots ,\;Q_{1},\;Y_{1})=P(Y_{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$.

Наблюдение $Y_{t}$ в момент времени $t$ может иметь одно из $L$ возможных значений, $y_{t}\in \{o_{1},\;\ldots ,\;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},\;\ldots ,\;y_{T})$.

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

Алгоритм

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

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

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

Обозначим через $\alpha _{i}(t)=p(Y_{1}=y_{1},\;\ldots ,\;Y_{t}=y_{t},\;Q_{t}=i\mid \lambda )$ вероятность появления заданной последовательности $y_{1},\;\ldots ,\;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},\ldots ,Y_{T}=y_{T}\mid Q_{t}=i,\lambda )$ вероятность конечной заданной последовательности $y_{t+1},\;\ldots ,\;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)}{\displaystyle \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})}{\displaystyle \sum _{i=1}^{N}\displaystyle \sum _{j=1}^{N}\alpha _{i}(t)a_{ij}\beta _{j}(t+1)b_{j}(y_{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}(o_{k})={\frac {\displaystyle \sum _{t=1}^{T}\delta _{y_{t},\;o_{k}}\gamma _{i}(t)}{\displaystyle \sum _{t=1}^{T}\gamma _{i}(t)}}.$,

где

$\delta _{y_{t},\;o_{k}}={\begin{cases}1&{\text{если }}y_{t}=o_{k},\\0&{\text{иначе}}\end{cases}}$

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

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

См. также

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

Источники

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