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

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

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

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

1. $t$$t$ -я скрытая переменная при известной $(t-<!--\; -\; -->1)$$(t-1)$ -ой переменной независима от всех предыдущих $(t-<!--\; -\; -->1)$$(t-1)$  переменных, то есть $P(Q_t\mid <!--\; \mid \; -->Q_{t-<!--\; -\; -->1},Y_{t-<!--\; -\; -->1},\dots <!--\; \dots \; -->,Q_1,Y_1)=P(Q_t\mid <!--\; \mid \; -->Q_{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$ -е известное наблюдение зависит только от $t$$t$ -го состояния, то есть не зависит от времени, $P(Y_t\mid <!--\; \mid \; -->Q_t,Q_{t-<!--\; -\; -->1},Y_{t-<!--\; -\; -->1},\dots <!--\; \dots \; -->,Q_1,Y_1)=P(Y_t\mid <!--\; \mid \; -->Q_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$$Q_{t}$  — это дискретная случайная переменная, принимающая одно из $N$$N$  значений $(1\dots <!--\; \dots \; -->N)$$(1\ldots N)$ . Будем полагать, что данная модель Маркова, определённая как $P(Q_t\mid <!--\; \mid \; -->Q_{t-<!--\; -\; -->1})$$P(Q_{t}\mid Q_{t-1})$ , однородна по времени, то есть независима от $t$$t$ . Тогда можно задать $P(Q_t\mid <!--\; \mid \; -->Q_{t-<!--\; -\; -->1})$$P(Q_{t}\mid Q_{t-1})$  как независящую от времени стохастическую матрицу перемещений $A=\{a_{ij}\}=p(Q_t=j\mid <!--\; \mid \; -->Q_{t-<!--\; -\; -->1}=i)$$A=\{a_{ij}\}=p(Q_{t}=j\mid Q_{t-1}=i)$ . Вероятности состояний в момент времени $t=1$$t=1$  определяется начальным распределением ${\mathrm{\pi <!--\; \pi \; -->}}_i=P(Q_1=i)$$\pi _{i}=P(Q_{1}=i)$ .

Будем считать, что мы в состоянии $j$$j$  в момент времени $t$$t$ , если $Q_t=j$$Q_{t}=j$ . Последовательность состояний выражается как $q=(q_1,\dots <!--\; \dots \; -->,q_T)$$q=(q_{1},\;\ldots ,\;q_{T})$ , где $q_t\in <!--\; \in \; -->\{1\dots <!--\; \dots \; -->N\}$$q_{t}\in \{1\ldots N\}$  является состоянием в момент $t$$t$ .

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

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

АлгоритмПравить

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

Алгоритм итеративно обновляет параметр $\mathrm{\lambda <!--\; \lambda \; -->}$$\lambda$  до схождения в одной точке.

Прямая процедураПравить

Обозначим через ${\mathrm{\alpha <!--\; \alpha \; -->}}_i(t)=p(Y_1=y_1,\dots <!--\; \dots \; -->,Y_t=y_t,Q_t=i\mid <!--\; \mid \; -->\mathrm{\lambda <!--\; \lambda \; -->})$$\alpha _{i}(t)=p(Y_{1}=y_{1},\;\ldots ,\;Y_{t}=y_{t},\;Q_{t}=i\mid \lambda )$  вероятность появления заданной последовательности $y_1,\dots <!--\; \dots \; -->,y_t$$y_{1},\;\ldots ,\;y_{t}$  для состояния $i$$i$  в момент времени $t$$t$ .

${\mathrm{\alpha <!--\; \alpha \; -->}}_i(t)$$\alpha _{i}(t)$  можно вычислить рекурсивно:

1. ${\mathrm{\alpha <!--\; \alpha \; -->}}_i(1)={\mathrm{\pi <!--\; \pi \; -->}}_i\cdot <!--\; \cdot \; -->b_i(y_1);$$\alpha _{i}(1)=\pi _{i}\cdot b_{i}(y_{1});$ 
2. ${\mathrm{\alpha <!--\; \alpha \; -->}}_j(t+1)=b_j(y_{t+1})\underset{i=1}{\overset{N}{\sum <!--\; \sum \; -->}}{\mathrm{\alpha <!--\; \alpha \; -->}}_i(t)\cdot <!--\; \cdot \; -->a_{ij}.$$\alpha _{j}(t+1)=b_{j}(y_{t+1})\sum _{i=1}^{N}{\alpha _{i}(t)\cdot a_{ij}}.$ 

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

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

Можно вычислить ${\mathrm{\beta <!--\; \beta \; -->}}_i(t)$$\beta _{i}(t)$ :

1. ${\mathrm{\beta <!--\; \beta \; -->}}_i(T)=p(Y_T=y_T\mid <!--\; \mid \; -->Q_t=i,\mathrm{\lambda <!--\; \lambda \; -->})=1;$$\beta _{i}(T)=p(Y_{T}=y_{T}\mid Q_{t}=i,\lambda )=1;$ 
2. ${\mathrm{\beta <!--\; \beta \; -->}}_i(t)=\underset{j=1}{\overset{N}{\sum <!--\; \sum \; -->}}{\mathrm{\beta <!--\; \beta \; -->}}_j(t+1)a_{ij}{b}_j(y_{t+1}).$$\beta _{i}(t)=\sum _{j=1}^{N}{\beta _{j}(t+1)a_{ij}b_{j}(y_{t+1})}.$ 

Используя $\mathrm{\alpha <!--\; \alpha \; -->}$$\alpha$  и $\mathrm{\beta <!--\; \beta \; -->}$$\beta$  можно вычислить следующие значения:

• ${\mathrm{\gamma <!--\; \gamma \; -->}}_i(t)\equiv <!--\; \equiv \; -->p(Q_t=i\mid <!--\; \mid \; -->y,\mathrm{\lambda <!--\; \lambda \; -->})=\frac{{\mathrm{\alpha <!--\; \alpha \; -->}}_i(t){\mathrm{\beta <!--\; \beta \; -->}}_i(t)}{\underset{j=1}{\overset{N}{\sum <!--\; \sum \; -->}}},$$\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)}},$ 
• ${\mathrm{\xi <!--\; \xi \; -->}}_{ij}(t)\equiv <!--\; \equiv \; -->p(Q_t=i,Q_{t+1}=j\mid <!--\; \mid \; -->y,\mathrm{\lambda <!--\; \lambda \; -->})=\frac{{\mathrm{\alpha <!--\; \alpha \; -->}}_i(t)a_{ij}{\mathrm{\beta <!--\; \beta \; -->}}_j(t+1)b_j(y_{t+1})}{\underset{i=1}{\overset{N}{\sum <!--\; \sum \; -->}}}.$$\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})}}.$ 

Имея $\mathrm{\gamma <!--\; \gamma \; -->}$$\gamma$  и $\mathrm{\xi <!--\; \xi \; -->}$$\xi$ , можно вычислить новые значения параметров модели:

• ${\stackrel{¯<!--\; ¯\; -->}{\mathrm{\pi <!--\; \pi \; -->}}}_i={\mathrm{\gamma <!--\; \gamma \; -->}}_i(1),$${\bar {\pi }}_{i}=\gamma _{i}(1),$ 
• ${\stackrel{¯<!--\; ¯\; -->}{a}}_{ij}=\frac{\underset{t=1}{\overset{T-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}}{{\mathrm{\xi <!--\; \xi \; -->}}_{ij}},$${\bar {a}}_{ij}={\frac {\displaystyle \sum _{t=1}^{T-1}\xi _{ij}(t)}{\displaystyle \sum _{t=1}^{T-1}\gamma _{i}(t)}},$ 
• ${\stackrel{¯<!--\; ¯\; -->}{b}}_i(o_k)=\frac{\underset{t=1}{\overset{T}{\sum <!--\; \sum \; -->}}}{{\mathrm{\delta <!--\; \delta \; -->}}_{y_t,o_k}}.$${\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^{\ast <!--\; \ast \; -->}(o_k)$$b_{i}^{*}(o_{k})$  ожидаемое количество значений наблюдаемой величины, равных $o_k$$o_{k}$  в состоянии $i$$i$  к общему количеству состояний $i$$i$ .

Используя новые значения $A$$A$ , $B$$B$  и $\mathrm{\pi <!--\; \pi \; -->}$$\pi$ , итерации продолжаются до схождения.

См. такжеПравить

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

ИсточникиПравить

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