Прихована марківська модель

Діаграма переходів у прихованій марківській моделі (приклад)
x - приховані стани
y - спостережувані результати
a - ймовірності переходів
b - ймовірність результату

Прихо́вана ма́рківська моде́ль (ПММ) — статистична модель, що імітує процес, схожого на марківський процес із невідомими параметрами. Завданням ПММ є визначення невідомих параметрів на основі спостережуваних. Отримані параметри може бути використано в подальшому аналізі, наприклад, для розпізнавання образів. ПММ може розглядатися як найпростіша Байєсова мережа довіри.

Перші нотатки про приховані марківські моделі опублікував Баум у 1960-х, і вже в 70-х їх вперше застосували для розпізнавання мови. З середини 1980-х ПММ застосовуються в аналізі біологічних послідовностей, зокрема ДНК. Основне застосування ПММ отримали в галузі розпізнавання мови, письма, рухів та біоінформатики. Крім того, ПММ застосовуються в криптоаналізі, машинному перекладі.

Приклад

Уявімо двох друзів, які обговорюють щовечора по телефону, що вони робили вдень. Ваш друг може робити лише три речі: гуляти в парку, ходити за покупками або прибирати в кімнаті. Його вибір ґрунтується лише на погоді, яка була в момент прийняття рішення. Ви нічого не знаєте про погоду в тому регіоні, де живе ваш друг, але ви можете, ґрунтуючись на його рішеннях, спробувати вгадати, якою вона була.

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

Структура прихованої марківської моделі

У звичайній марківській моделі стан видно спостерігачеві, тому ймовірності переходів - єдиний необхідний параметр. У прихованій марківській моделі ми можемо стежити лише за змінними, на які впливає цей стан. Кожен стан має ймовірнісний розподіл серед усіх можливих вихідних значень. Тому послідовність символів, згенерована ПММ, дає інформацію про послідовність станів.

Діаграма, подана нижче, показує загальну структуру ПММ. Овали - це змінні з випадковим значенням. Випадкова змінна $x(t)$ відповідає значенню прихованої змінної в момент часу $t$. Випадкова змінна $y(t)$ - це значення змінної, за якою ми спостерігаємо, в момент часу $t$. Стрілки на діаграмі символізують умовні залежності.

Із діаграми можна дізнатись, що значення прихованої змінної $x(t)$ (в момент часу $t$) залежить тільки від значення прихованої змінної $x(t-1)$ (в момент $t-1$). Це називається властивістю Маркова. Хоча в той же час значення змінної $y(t)$, за якою ми спостерігаємо, залежить лише від значення прихованої змінної $x(t)$ (в момент часу $t$).

Ймовірність спостерігати послідовність $Y=y(0), y(1),\dots,y(L-1)$ довжини $L$ дорівнює:

$P(Y)=\sum_{X}P(Y\mid X)P(X),$

тут сума пробігає по всіх можливих послідовностях прихованих вузлів $X=x(0), x(1), \dots, x(L-1).\,$ Метод підрахунку повним перебором значень $P(Y)$ — дуже трудомісткий для багатьох реальних задач внаслідок того, що кількість можливих послідовностей прихованих вузлів дуже велика. Але застосування процедури вперед-назад дозволяє істотно збільшити швидкість обчислень.

Загальний опис

Основні приховані марківські моделі можна описати за допомогою таких змінних:

• $N$ - кількість станів
• $T$ - кількість спостережень
• $\theta_{i=1 \dots N}$ - параметр для спостереження за зв'язками між станами
• $\phi_{i=1 \dots N, j=1 \dots N}$ - ймовірність переходу із стану $i$ до стану $j$
• $\boldsymbol\phi_{i=1 \dots N}$ - $N$-мірний вектор, що складається із $\phi_{i,1 \dots N}$
• $x_{t=1 \dots T}$ - стан спостереження за час $t$
• $y_{t=1 \dots T}$ - результат спостереження за час $t$
• $F(y|\theta)$ - функція розподілу ймовірності спостережень, параметризованих по θ

Базові алгоритми

Існують три основні задачі, пов'язані з ПММ:

• Алгоритм вперед-назад. Задано параметри моделі та послідовність, потрібно обчислити ймовірність появи заданої послідовності.
• Алгоритм Вітербі: Задано параметри моделі, необхідно визначити найпридатнішу послідовність прихованих вузлів, яка найточніше описує цю модель.
• Алгоритм Баума-Велша: Задано вхідну послідовність (послідовності) із дискретними значеннями, необхідно змоделювати відповідну ПММ на виході.

Посилання

• Три основні задачі ПММ (рос.)
• Сергій Ніколенко. Лекції № 6 і № 7 (слайди), присвячені прихованим марківським моделям, із курсу «Теорія ймовірності»