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

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

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

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

$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})$ ;
$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)$ можно вычислить рекурсивно:

$\alpha _{i}(1)=\pi _{i}\cdot b_{i}(y_{1});$
$\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)$ :

$\beta _{i}(T)=p(Y_{T}=y_{T}\mid Q_{t}=i,\lambda )=1;$
$\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$ , итерации продолжаются до схождения.

См. также

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

Источники

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.