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

Алгоритм Баума — Велша використовується в інформатиці та статистиці для знаходження невідомих параметрів прихованої марковської моделі (ПММ). Він використовує алгоритм прямого-зворотного ходу і є окремим випадком узагальненого 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$ , ітерації продовжуються до збігання.

Див. також

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

Джерела

The Baum-Welch algorithm for estimating a Hidden Markov Model(англ.)
Baum-Welch Algorithm(англ.)
Лекція С. Ніколенка «Приховані марковські моделі»(рос.)

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