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

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

Связать^?

На эту статью не ссылаются другие статьи Википедии.

Пожалуйста, воспользуйтесь подсказкой и установите ссылки в соответствии с принятыми рекомендациями.

Эта статья или раздел нуждается в переработке.

Пожалуйста, улучшите её в соответствии с правилами написания статей.

Содержание

1 Алгоритм Баума-Велша оценки скрытой модели Маркова
2 Алгоритм
- 2.1 Прямая процедура
- 2.2 Обратная процедура
3 Источники

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

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

$~t$ -я скрытая переменная при известной (t-1)-ой переменной, независима от всех предыдущих $~(t-1)$ переменных, то есть $~P(O_t|Q_{t-1},O_{t-1},...,Q_1,O_1) = P(Q_t|Q_{t-1})$ ;
$~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)$ можно вычислить рекурсивно:

$\alpha_i(t)=\pi_i \cdot b_i(O_i)$ ,
$\alpha_j(t+1)=b_j(O_{t+1})\sum^{N}_{i=1}{\alpha_i(t)\cdot a_{ij}}$ .

[править] Обратная процедура

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

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

$~\beta_i(T)=1$ ;
$~\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|O,\lambda)=\frac{\alpha_i(t)\beta_i(t)}{\sum^{N}_{j=1}\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^{N}_{i=1}{\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{\sum^{T-1}_{t=1}{\xi_{ij}(t)}}{\sum^{T-1}_{t=1} {\gamma_i(t)}}$ ,
$~\bar{b}_i(k)=\frac{\sum^{T}_{t=1}{\delta_{O_t,o_k}\gamma_i(t)}}{\sum^{T}_{t=1}{\gamma_i(t)}}$ .