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

Тарас Тріщук · листопад 2026 · Інфографіка | English

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

Усі числа на постері порахував той самий код, що працює в калькуляторі нижче; їх не переписано з рисунка. Приклад і поділ на три задачі взято з Appendix A книги Jurafsky & Martin; коментарі й практичні нотатки мої.

trishchuk.com / learn
Інфографіка

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

Відновіть приховану послідовність (погоду, частини мови, фонеми) за тим, що можна спостерігати. Одна модель, три задачі, три алгоритми динамічного програмування.

HCHHHCCHHHHOTCOLD
Порції морозива за кожен день (кульки) і погода, яку з них виводить алгоритм Вітербі (підсвічений шлях). Бурштиновий це спека, блакитний це холод.

Марковське припущення

P(qi | q1 … qi−1) = P(qi | qi−1)

Наступний стан залежить лише від поточного, а не від історії.

Незалежність виходів

P(oi | q1 … qT, o1 … oT) = P(oi | qi)

Спостереження залежить лише від прихованого стану, який його породив.

Ланцюг Маркова: стани, які видно

Ланцюг погоди, Fig. A.1a з книги

.1.3.1.1.3.1.8.6.6 COLDHOTWARM

Матриця переходів A

з ↓ / у →HOTCOLDWARM
HOT.6.1.3
COLD.1.8.1
WARM.3.1.6

Кожен рядок у сумі дає 1. Початковий розподіл: π = [.1, .7, .2].

Той самий ланцюг, дві послідовності

  • hot hot hot hot .0216
  • cold hot cold hot .0007

hot-hot-hot-hot приблизно у 31 раз імовірніша за cold-hot-cold-hot: погода «липка», і важка діагональ A саме це й кодує.

До чого він прийде? πA = π

  • після 0 кроків 10 70 20
  • після 1 кроків 19 59 22
  • після 2 кроків 24 51 25
  • після 3 кроків 27 46 27
  • після 5 кроків 30 39 30
  • після 10 кроків 33 34 33

Стартуйте з π і застосовуйте A знову і знову. A симетрична, тож її стовпці теж сумуються до 1, і рівномірний розподіл є стаціонарним: у довгостроковій перспективі кожен стан отримує ⅓. Стаціонарний розподіл задовольняє πA = π.

Прихована марковська модель: додаємо шар, якого не видно

Задача Айзнера з морозивом, Fig. A.2

.5.4 .5.6 π .2π .8 CCOLDHHOT P(o | C).51.42.13 P(o | H).21.42.43

Приховано: чи був день холодним (C) чи спекотним (H). Спостерігаємо: скільки порцій морозива (1, 2 чи 3) з’їв Джейсон. За щоденником треба вгадати погоду.

Переходи A

CH
C.5.5
H.4.6

Емісії B

123
C.5.4.1
H.2.4.4

Старт π

CH
π.2.8
Q
N прихованих станів (тут C, H)
A
матриця переходів, рядки в сумі дають 1
B
ймовірності емісії, P(o | стан)
π
початковий розподіл станів
O
T спостережень, по одному на крок

Одна модель, три задачі

Задача 1
Σ

Правдоподібність

Наскільки імовірний цей щоденник за моделлю?

P(O | λ)
Алгоритм Forward
O(N²T), один прохід
Задача 2
max

Декодування

Яка послідовність погоди пояснює його найкраще?

найкраща Q
Алгоритм Вітербі
O(N²T) за часом, O(NT) пам’ять
Задача 3
E → M

Навчання

Які A і B роблять щоденник найімовірнішим?

A, B
Forward-Backward (Баум–Велш)
O(N²T) на ітерацію

Forward: сума за всіма шляхами без їх перебору

Спостереження 3 1 3 (Джейсон з’їв 3, потім 1, потім 3 порції)

α₁(H) .32 α₁(C) .02 α₂(H) .0404 α₂(C) .069 α₃(H) .0235 α₃(C) .005066 o₁ = 3 o₂ = 1 o₃ = 3
αt(j) = NΣi=1 αt−1(i) · aij · bj(ot)

Кожна клітинка αₜ(j) це ймовірність побачити перші t спостережень і опинитися в стані j. Її будують із попереднього стовпця: множать на перехід, додають вхідні шляхи, множать на емісію.

Старт: α1(j) = πj · bj(o1)   Кінець: P(O | λ) = Σ αT(i)

Значення Forward αt(j)
t=1 o=3t=2 o=1t=3 o=3
H.32.0404.0235
C.02.069.005066
Повна правдоподібність P(O | λ) = .028562 Збігається із сумою перебору нижче.

Чому б просто не перебрати?

Усі 2³ = 8 прихованих шляхів для 3 1 3 зі спільною ймовірністю P(O, Q)

  1. HCH .0128
  2. HHH .009216
  3. HCC .0032
  4. HHC .001536
  5. CCH .001
  6. CHH .00048
  7. CCC .00025
  8. CHC .00008
Їхня сума і є правдоподібність Σ = .028562
1020 шляхів для перебору NT
2 000 кроків Forward N²·T

N = 10 станів, T = 20 кроків

Тут N = 2, T = 3: 8 шляхів проти 12 кроків. На такому розмірі різниця непомітна, а на реальних розмірах астрономічна.

Вітербі: та сама ґратка, але max замість суми

Лишаємо лише найкращий шлях у кожну клітинку й пам’ятаємо, звідки він

v₁(H) .32 v₁(C) .02 v₂(H) .0384 v₂(C) .064 v₃(H) .0128 v₃(C) .0032 o₁ = 3 o₂ = 1 o₃ = 3
vt(j) = maxi vt−1(i) · aij · bj(ot)
btt(j) = argmaxi vt−1(i) · aij · bj(ot)

Замініть суму на максимум і збережіть вказівник назад для кожної клітинки. Наприкінці оберіть найкращу останню клітинку й ідіть за вказівниками назад.

Значення Вітербі vt(j)
t=1 o=3t=2 o=1t=3 o=3
H.32.0384←H.0128←C
C.02.064←H.0032←C
Найкращий шлях HCH p = .0128 Другий за якістю: H H H = .009216

Інтуїція підказує «3 порції ⇒ спека, тобто H H H». Але на другий день Джейсон з’їв лише одну, а це набагато імовірніше в холодний день (.5 проти .2), і ланцюг недостатньо «липкий», щоб це перекрити. Найкращий шлях провалюється в холод: H C H.

Навчання: Forward-Backward (Баум–Велш)

Немає розмітки? Вгадайте A і B, пом’яко порахуйте, що з цього випливає, переоцініть і повторіть

Зворотна ймовірність: що буде після t

βt(i) = NΣj=1 aij · bj(ot+1) · βt+1(j)

γ: наскільки імовірно, що в день t був стан j?

γt(j) = αt(j) βt(j) / P(O | λ)

ξ: наскільки імовірний перехід i → j у момент t?

ξt(i, j) = αt(i) aij bj(ot+1) βt+1(j) / P(O | λ)

M-крок: переоцінка

âij = Σt ξt(i, j) / ΣtΣk ξt(i, k)
b̂j(vk) = Σt: ot=vk γt(j) / Σt γt(j)
  1. E-крок порахувати γ і ξ за поточними A, B (потрібні α і β)
  2. M-крок перерахувати A і B за очікуваними лічильниками
  3. ↻ повторювати, доки правдоподібність не перестане зростати
Апостеріорні ймовірності станів для 3 1 3 γt(j)
t=1 o=3t=2 o=1t=3 o=3
H.937.396.823
C.0634.604.177

Приклад: ξ₁(H→C) = .5602  ·  β3 = [1, 1], β2 = [.25, .28]

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

Ключові властивості

  • Перший порядок: пам’ять в один крок. Довша пам’ять означає більший простір станів.
  • Генеративна: моделює P(O, Q). Дискримінативні родичі (CRF) моделюють P(Q | O) напряму.
  • Геометричні тривалості: перебування d кроків у стані i має ймовірність aᵢᵢ^(d−1) · (1 − aᵢᵢ).
  • Вітербі ≠ апостеріорний: найкращий спільний шлях не те саме, що argmax γ на кожному кроці.

Застосування

  • Розмітка частин мови: теги приховані, слова спостерігаються.
  • Розпізнавання мовлення: стани субфонем, акустичні кадри як спостереження.
  • Біоінформатика: пошук генів, профільні HMM; родич вирівнювання послідовностей.
  • Зв’язок: Вітербі (1967) спершу декодував згорткові коди.
  • Ще: прив’язка GPS до карти, розпізнавання активності, зміна режимів у фінансах.

На практиці

  • Втрата значущості: добутки багатьох ймовірностей зникають. Для Вітербі беріть логарифми; для Forward log-sum-exp або масштабування на кожному кроці.
  • Локальні оптимуми: EM не зменшує правдоподібність, але може застрягти. Розумно ініціалізуйте, перезапускайте випадково, занулюйте неможливі переходи.
  • Нульові лічильники: небачена емісія отримує 0 і вбиває шлях. Згладжуйте B.
  • Чесно обирайте N: більше станів завжди підганяє краще. Перевіряйте на відкладених даних.
Тарас Тріщук За Jurafsky & Martin, SLP3, Appendix A trishchuk.com/learn

↓ Завантажити постер як PNG

Спробуйте самі

Введіть кількість порцій морозива (1, 2 або 3 на день, до 30 днів) і подивіться, як той самий код Forward і Вітербі з постера обробляє вашу послідовність.

Forward αt(j)
день 1 o = 3день 2 o = 1день 3 o = 3
H.32.0404.0235
C.02.069.005066
Вітербі vt(j)
день 1 o = 3день 2 o = 1день 3 o = 3
H.32.0384.0128
C.02.064.0032
Правдоподібність P(O | λ)
.028562
Найкращий прихований шлях
HCH
її ймовірність
.0128

Модель: HMM Айзнера зверху. Дуже малі значення показано як ×10⁻ⁿ.

Джерела та що читати далі