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

Алгоритм Баума — Велша використовується в інформатиці та статистиці для знаходження невідомих параметрів прихованої марковської моделі (ПММ). Він використовує алгоритм прямого-зворотного ходу і є окремим випадком узагальненого 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 [Архівовано 29 січня 2020 у Wayback Machine.](англ.)
• Лекція С. Ніколенка «Приховані марковські моделі» [Архівовано 23 вересня 2020 у Wayback Machine.](рос.)