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

Алгоритм Баума — Велша використовується в інформатиці та статистиці для знаходження невідомих параметрів прихованої марковської моделі (ПММ). Він використовує алгоритм прямого-зворотного ходу і є окремим випадком узагальненого EM-алгоритму.

Алгоритм Баума — Велша оцінки прихованої моделі Маркова

Прихована модель Маркова — це імовірнісна модель множини випадкових змінних $\{Y_1,\dots ,Y_t,Q_1,\dots ,Q_t\}$. Змінні $Y_t$ — відомі дискретні спостереження, а $Q_t$ — «приховані» дискретні величини. В рамках прихованої моделі Маркова є два незалежних твердження, що забезпечують збіжність даного алгоритму:

1. $t$ — прихована змінна за відомих $(t-1)$ змінних незалежна від усіх попередніх $(t-1)$ змінних, тобто $P(Q_t\mid Q_{t-1},Y_{t-1},\dots ,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},\dots ,Q_1,Y_1)=P(Y_t\mid Q_t)$ .

Далі буде запропоновано алгоритм «припущень і максимізації» для пошуку максимальної ймовірнісної оцінки параметрів прихованої моделі Маркова за заданого набору спостережень. Цей алгоритм також відомий як алгоритм Баума — Велша.

$Q_t$ — це дискретна випадкова змінна, що набуває одного з $N$ значень $(1\dots 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,\dots ,q_T)$, де $q_t\in \{1\dots N\}$ є станом у момент $t$.

Спостереження $Y_t$ в момент часу $t$ може мати одне з $L$ можливих значень, $y_t\in \{o_1,\dots ,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,\dots ,y_T)$ .

Отже, ми можемо описати приховану модель Маркова за допомогою $\lambda =(A,B,\pi )$. За заданого вектора спостережень $y$ алгоритм Баума — Велша знаходить ${\lambda }^{*}=arg\underset{\lambda }{\max }P(y\mid \lambda )$ . ${\lambda }^{*}$ максимізує ймовірність спостережень $y$.

Алгоритм

Початкові дані: $\lambda =(A,B,\pi )$ з випадковими початковими умовами.

Алгоритм ітеративно оновлює параметр $\lambda$ до збігання в одній точці.

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

Позначимо через ${\alpha }_i(t)=p(Y_1=y_1,\dots ,Y_t=y_t,Q_t=i\mid \lambda )$ ймовірність появи заданої послідовності $y_1,\dots ,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},\dots ,Y_T=y_T\mid Q_t=i,\lambda )$ ймовірність кінцевої заданої послідовності $y_{t+1},\dots ,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)}{\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})}{\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i(t)a_{ij}{\beta }_j(t+1)b_j(y_{t+1})}.$

Маючи $\gamma$ і $\xi$, Можна обчислити нові значення параметрів моделі:

• ${\overline{\pi }}_i={\gamma }_i(1),$
• ${\overline{a}}_{ij}=\frac{\sum _{t=1}^{T-1}{\xi }_{ij}(t)}{\sum _{t=1}^{T-1}{\gamma }_i(t)},$
• ${\overline{b}}_i(o_k)=\frac{\sum _{t=1}^T{\delta }_{y_t,o_k}{\gamma }_i(t)}{\sum _{t=1}^T{\gamma }_i(t)}.$ ,

де

${\delta }_{y_t,o_k}=\{\begin{array}{cc}1& \text{якщо }{y}_t=o_k,\\ 0& \text{інакше}\end{array}$

індикативна функція, і $b_i^{*}(o_k)$ очікувана кількість значень спостережуваної величини, рівних $o_k$ в стані $i$ до загальної кількості станів $i$ .

Використовуючи нові значення $A$, $B$ і $\pi$, ітерації продовжуються до збігання.

Див. також

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

Джерела

• The Baum-Welch algorithm for estimating a Hidden Markov ModelШаблон:Ref-en
• Baum-Welch Algorithm Шаблон:WebarchiveШаблон:Ref-en
• Лекція С. Ніколенка «Приховані марковські моделі» Шаблон:WebarchiveШаблон:Ref-ru