Алгоритм Баума — Велша використовується в інформатиці та статистиці для знаходження невідомих параметрів прихованої марковської моделі (ПММ). Він використовує алгоритм прямого-зворотного ходу і є окремим випадком узагальненого EM-алгоритму.
Алгоритм Баума — Велша оцінки прихованої моделі Маркова
[ред. | ред. код]
Прихована модель Маркова — це імовірнісна модель множини випадкових змінних
. Змінні
— відомі дискретні спостереження, а
— «приховані» дискретні величини. В рамках прихованої моделі Маркова є два незалежних твердження, що забезпечують збіжність даного алгоритму:
— прихована змінна за відомих
змінних незалежна від усіх попередніх
змінних, тобто
;
-е відоме спостереження залежить тільки від
-го стану, тобто не залежить від часу,
.
Далі буде запропоновано алгоритм «припущень і максимізації» для пошуку максимальної ймовірнісної оцінки параметрів прихованої моделі Маркова за заданого набору спостережень. Цей алгоритм також відомий як алгоритм Баума — Велша.
— це дискретна випадкова змінна, що набуває одного з
значень
. Будемо вважати, що дана модель Маркова, визначена як
, однорідна за часом, тобто незалежна від
. Тоді можна задати
як незалежну від часу стохастичну матрицю переміщень
. Ймовірності станів у момент часу
визначаються початковим розподілом
.
Будемо вважати, що ми в стані
у момент часу
, якщо
. Послідовність станів виражається як
, де
є станом у момент
.
Спостереження
в момент часу
може мати одне з
можливих значень,
. Імовірність заданого вектора спостережень у момент часу
для стану
визначається як
(
— це матриця
на
). Послідовність спостережень
виражається як
.
Отже, ми можемо описати приховану модель Маркова за допомогою
. За заданого вектора спостережень
алгоритм Баума — Велша знаходить
.
максимізує ймовірність спостережень
.
Початкові дані:
з випадковими початковими умовами.
Алгоритм ітеративно оновлює параметр
до збігання в одній точці.
Позначимо через
ймовірність появи заданої послідовності
для стану
в момент часу
.
можна обчислити рекурсивно:
![{\displaystyle \alpha _{i}(1)=\pi _{i}\cdot b_{i}(y_{1});}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d67de25bf8cc692c6f0ed17c34150a6d2669e0ee)
![{\displaystyle \alpha _{j}(t+1)=b_{j}(y_{t+1})\sum _{i=1}^{N}{\alpha _{i}(t)\cdot a_{ij}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b6e6d3d58998ac327f19220364a719b888e6c3f9)
Дана процедура дозволяє обчислити
ймовірність кінцевої заданої послідовності
за умови, що ми почали з вихідного стану
, в момент часу
.
Можна обчислити
:
![{\displaystyle \beta _{i}(T)=p(Y_{T}=y_{T}\mid Q_{t}=i,\lambda )=1;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/76cd105ad421359df7281028e25063dcd834e064)
![{\displaystyle \beta _{i}(t)=\sum _{j=1}^{N}{\beta _{j}(t+1)a_{ij}b_{j}(y_{t+1})}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/963b7ba2aff88eff9e5d03db71a8b1c361171f0f)
Використовуючи
і
можна обчислити наступні значення:
![{\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)}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f21a70cc367204b618f89a42fc50e672c2e87e73)
![{\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})}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6fba1e43d5ef0ccc969879777b0af9e04e105c6a)
Маючи
і
, Можна обчислити нові значення параметрів моделі:
![{\displaystyle {\bar {\pi }}_{i}=\gamma _{i}(1),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/70241608ff045120eeedcc45fdfd460362809f9f)
![{\displaystyle {\bar {a}}_{ij}={\frac {\displaystyle \sum _{t=1}^{T-1}\xi _{ij}(t)}{\displaystyle \sum _{t=1}^{T-1}\gamma _{i}(t)}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b64bfa5f81202209b6afff34cc101f1254d9fb9f)
,
де
![{\displaystyle \delta _{y_{t},\;o_{k}}={\begin{cases}1&{\text{якщо }}y_{t}=o_{k},\\0&{\text{інакше}}\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b370d69c9495e57e93eb8e4f749a10acbe383c6e)
індикативна функція, і
очікувана кількість значень спостережуваної величини, рівних
в стані
до загальної кількості станів
.
Використовуючи нові значення
,
і
, ітерації продовжуються до збігання.