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

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

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

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

  1.  — прихована змінна за відомих змінних незалежна від усіх попередніх змінних, тобто ;
  2. -е відоме спостереження залежить тільки від -го стану, тобто не залежить від часу, .

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

 — це дискретна випадкова змінна, що набуває одного з значень . Будемо вважати, що дана модель Маркова, визначена як , однорідна за часом, тобто незалежна від . Тоді можна задати як незалежну від часу стохастичну матрицю переміщень . Ймовірності станів у момент часу визначаються початковим розподілом .

Будемо вважати, що ми в стані у момент часу , якщо . Послідовність станів виражається як , де є станом у момент .

Спостереження в момент часу може мати одне з можливих значень, . Імовірність заданого вектора спостережень у момент часу для стану визначається як ( — це матриця на ). Послідовність спостережень виражається як .

Отже, ми можемо описати приховану модель Маркова за допомогою . За заданого вектора спостережень алгоритм Баума — Велша знаходить . максимізує ймовірність спостережень .

Алгоритм

Початкові дані: з випадковими початковими умовами.

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

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

Позначимо через ймовірність появи заданої послідовності для стану в момент часу .

можна обчислити рекурсивно:

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

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

Можна обчислити  :

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

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

  • ,

де

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

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

Див. також

Джерела

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