Алгоритм Баума — Велша використовується в інформатиці та статистиці для знаходження невідомих параметрів прихованої марковської моделі (ПММ). Він використовує алгоритм прямого-зворотного ходу і є окремим випадком узагальненого EM-алгоритму.
Алгоритм Баума — Велша оцінки прихованої моделі Маркова
Прихована модель Маркова — це імовірнісна модель множини випадкових змінних
. Змінні
— відомі дискретні спостереження, а
— «приховані» дискретні величини. В рамках прихованої моделі Маркова є два незалежних твердження, що забезпечують збіжність даного алгоритму:
-
— прихована змінна за відомих
змінних незалежна від усіх попередніх
змінних, тобто
;
-
-е відоме спостереження залежить тільки від
-го стану, тобто не залежить від часу,
.
Далі буде запропоновано алгоритм «припущень і максимізації» для пошуку максимальної ймовірнісної оцінки параметрів прихованої моделі Маркова за заданого набору спостережень. Цей алгоритм також відомий як алгоритм Баума — Велша.
— це дискретна випадкова змінна, що набуває одного з
значень
. Будемо вважати, що дана модель Маркова, визначена як
, однорідна за часом, тобто незалежна від
. Тоді можна задати
як незалежну від часу стохастичну матрицю переміщень
. Ймовірності станів у момент часу
визначаються початковим розподілом
.
Будемо вважати, що ми в стані
у момент часу
, якщо
. Послідовність станів виражається як
, де
є станом у момент
.
Спостереження
в момент часу
може мати одне з
можливих значень,
. Імовірність заданого вектора спостережень у момент часу
для стану
визначається як
(
— це матриця
на
). Послідовність спостережень
виражається як
.
Отже, ми можемо описати приховану модель Маркова за допомогою
. За заданого вектора спостережень
алгоритм Баума — Велша знаходить
.
максимізує ймовірність спостережень
.
Алгоритм
Початкові дані:
з випадковими початковими умовами.
Алгоритм ітеративно оновлює параметр
до збігання в одній точці.
Пряма процедура
Позначимо через
ймовірність появи заданої послідовності
для стану
в момент часу
.
можна обчислити рекурсивно:


Зворотна процедура
Дана процедура дозволяє обчислити
ймовірність кінцевої заданої послідовності
за умови, що ми почали з вихідного стану
, в момент часу
.
Можна обчислити
:


Використовуючи
і
можна обчислити наступні значення:


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


-
,
де

індикативна функція, і
очікувана кількість значень спостережуваної величини, рівних
в стані
до загальної кількості станів
.
Використовуючи нові значення
,
і
, ітерації продовжуються до збігання.
Див. також
Джерела