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

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

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

Прихована модель Маркова — це імовірнісна модель множини випадкових змінних ${\displaystyle \{Y_{1},\;\ldots ,\;Y_{t},\;Q_{1},\;\ldots ,\;Q_{t}\}}$. Змінні ${\displaystyle Y_{t}}$ — відомі дискретні спостереження, а ${\displaystyle Q_{t}}$ — «приховані» дискретні величини. В рамках прихованої моделі Маркова є два незалежних твердження, що забезпечують збіжність даного алгоритму:

1. ${\displaystyle t}$ — прихована змінна за відомих ${\displaystyle (t-1)}$ змінних незалежна від усіх попередніх ${\displaystyle (t-1)}$ змінних, тобто ${\displaystyle P(Q_{t}\mid Q_{t-1},\;Y_{t-1},\;\ldots ,\;Q_{1},\;Y_{1})=P(Q_{t}\mid Q_{t-1})}$ ;
2. ${\displaystyle t}$-е відоме спостереження залежить тільки від ${\displaystyle t}$-го стану, тобто не залежить від часу, ${\displaystyle P(Y_{t}\mid Q_{t},\;Q_{t-1},\;Y_{t-1},\;\ldots ,\;Q_{1},\;Y_{1})=P(Y_{t}\mid Q_{t})}$ .

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

${\displaystyle Q_{t}}$ — це дискретна випадкова змінна, що набуває одного з ${\displaystyle N}$ значень ${\displaystyle (1\ldots N)}$. Будемо вважати, що дана модель Маркова, визначена як ${\displaystyle P(Q_{t}\mid Q_{t-1})}$, однорідна за часом, тобто незалежна від ${\displaystyle t}$. Тоді можна задати ${\displaystyle P(Q_{t}\mid Q_{t-1})}$ як незалежну від часу стохастичну матрицю переміщень ${\displaystyle A=\{a_{ij}\}=p(Q_{t}=j\mid Q_{t-1}=i)}$ . Ймовірності станів у момент часу ${\displaystyle t=1}$ визначаються початковим розподілом ${\displaystyle \pi _{i}=P(Q_{1}=i)}$.

Будемо вважати, що ми в стані ${\displaystyle j}$ у момент часу ${\displaystyle t}$, якщо ${\displaystyle Q_{t}=j}$. Послідовність станів виражається як ${\displaystyle q=(q_{1},\;\ldots ,\;q_{T})}$, де ${\displaystyle q_{t}\in \{1\ldots N\}}$ є станом у момент ${\displaystyle t}$.

Спостереження ${\displaystyle Y_{t}}$ в момент часу ${\displaystyle t}$ може мати одне з ${\displaystyle L}$ можливих значень, ${\displaystyle y_{t}\in \{o_{1},\;\ldots ,\;o_{L}\}}$. Імовірність заданого вектора спостережень у момент часу ${\displaystyle t}$ для стану ${\displaystyle j}$ визначається як ${\displaystyle b_{j}(o_{i})=P(Y_{t}=o_{i}\mid Q_{t}=j)}$ (${\displaystyle B=\{b_{ij}\}}$ — це матриця ${\displaystyle L}$ на ${\displaystyle N}$). Послідовність спостережень ${\displaystyle y}$ виражається як ${\displaystyle y=(y_{1},\;\ldots ,\;y_{T})}$ .

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

Алгоритм

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

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

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

Позначимо через ${\displaystyle \alpha _{i}(t)=p(Y_{1}=y_{1},\;\ldots ,\;Y_{t}=y_{t},\;Q_{t}=i\mid \lambda )}$ ймовірність появи заданої послідовності ${\displaystyle y_{1},\;\ldots ,\;y_{t}}$ для стану ${\displaystyle i}$ в момент часу ${\displaystyle t}$.

${\displaystyle \alpha _{i}(t)}$ можна обчислити рекурсивно:

1. ${\displaystyle \alpha _{i}(1)=\pi _{i}\cdot b_{i}(y_{1});}$
2. ${\displaystyle \alpha _{j}(t+1)=b_{j}(y_{t+1})\sum _{i=1}^{N}{\alpha _{i}(t)\cdot a_{ij}}.}$

Зворотна процедура

Дана процедура дозволяє обчислити ${\displaystyle \beta _{i}(t)=p(Y_{t+1}=y_{t+1},\ldots ,Y_{T}=y_{T}\mid Q_{t}=i,\lambda )}$ ймовірність кінцевої заданої послідовності ${\displaystyle y_{t+1},\;\ldots ,\;y_{T}}$ за умови, що ми почали з вихідного стану ${\displaystyle i}$, в момент часу ${\displaystyle t}$.

Можна обчислити ${\displaystyle \beta _{i}(t)}$ :

1. ${\displaystyle \beta _{i}(T)=p(Y_{T}=y_{T}\mid Q_{t}=i,\lambda )=1;}$
2. ${\displaystyle \beta _{i}(t)=\sum _{j=1}^{N}{\beta _{j}(t+1)a_{ij}b_{j}(y_{t+1})}.}$

Використовуючи ${\displaystyle \alpha }$ і ${\displaystyle \beta }$ можна обчислити наступні значення:

• ${\displaystyle \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)}},}$
• ${\displaystyle \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})}}.}$

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

• ${\displaystyle {\bar {\pi }}_{i}=\gamma _{i}(1),}$
• ${\displaystyle {\bar {a}}_{ij}={\frac {\displaystyle \sum _{t=1}^{T-1}\xi _{ij}(t)}{\displaystyle \sum _{t=1}^{T-1}\gamma _{i}(t)}},}$
• ${\displaystyle {\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)}}.}$ ,

де

${\displaystyle \delta _{y_{t},\;o_{k}}={\begin{cases}1&{\text{якщо }}y_{t}=o_{k},\\0&{\text{інакше}}\end{cases}}}$

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

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

Див. також

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

Джерела

• (англ.)
• Baum-Welch Algorithm [ 29 січня 2020 у Wayback Machine.](англ.)
• Лекція С. Ніколенка «Приховані марковські моделі» [ 23 вересня 2020 у Wayback Machine.](рос.)