Приховані марковські моделі: алгоритм Вітербі й нечесне казино

Прихована марковська модель, три задачі за Рабінером, алгоритм прямого ходу, алгоритм Вітербі, апостеріорне декодування й алгоритм Баума–Велша — на казино, яке час від часу потай підміняє кубик фальшивим.

14 хвилин Matěj Žalmánek 2026-10-15

Серія Основи ШІ Частина 39 з 52

1. Мапа штучного інтелекту: що є що і як усе це пов’язано
2. Коротка історія штучного інтелекту: від Тюрінга до мовних моделей
3. Дані, модель, тренування, інференс: основні поняття на одному прикладі
4. Як читати математичний запис: символи, індекси, суми та квантори
5. Множини й відношення: конструктор, з якого складаються означення в ШІ
6. Функції й відображення: чому кожна модель у ШІ — це функція
7. Логіка й доведення: правила, за якими міркують у ШІ
8. Графи й дерева: структура, на якій тримаються пошук і нейронні мережі
9. Лінійна алгебра для машинного навчання: вектори, матриці й чому ШІ передусім множить
10. Похідні, градієнт і правило ланцюжка: як модель дізнається, у якому напрямку вчитися
11. Градієнтний спуск: як навчається модель
12. Що таке ймовірність: від кидка кубика до аксіом Колмогорова
13. Умовна ймовірність і теорема Баєса: як змінити оцінку, коли дізнаєтеся щось нове
14. Випадкова величина і функція розподілу: одна функція, яка каже про розподіл усе
15. Функція щільності та функція маси ймовірності: чому неперервна величина має в точці ймовірність нуль
16. Математичне сподівання, дисперсія і коваріація: де лежить розподіл, наскільки він широкий і що з чим пов’язано
17. Огляд розподілів ймовірностей: Бернуллі, біноміальний, Пуассона, рівномірний, нормальний і експоненційний
18. Закон великих чисел і центральна гранична теорема: чому середні поводяться так передбачувано
19. Статистика й оцінювання параметрів: максимальна правдоподібність, MAP і довірчі інтервали
20. Теорія інформації: ентропія, перехресна ентропія і KL-дивергенція — звідки беруться функції втрат
21. Пошук у просторі станів: BFS, DFS, UCS і A* з анімаціями
22. Ігри та суперник: мінімакс, альфа-бета відсікання і Monte Carlo tree search
23. Задоволення обмежень: бектрекінг, поширення обмежень і AC-3 на судоку та мапі чеських країв
24. Логіка й системи, засновані на знаннях: пряме і зворотне виведення, резолюція та експертні системи
25. Планування: STRIPS, світ кубиків, евристики з релаксації та планування в AI-агентах
26. Локальний пошук та імітація відпалу: комівояжер через обласні центри Чехії
27. Генетичні алгоритми: популяція, схрещування, мутація і добір на рюкзаку для походу
28. Еволюційні стратегії і генетичне програмування: від правила однієї п’ятої до закону Кеплера
29. Оптимізація мурашиною колонією: як феромоновий слід знаходить короткий шлях
30. Оптимізація роєм частинок: інерція, власний досвід і досвід рою
31. Нейроеволюція: еволюція ваг і форми нейронних мереж та алгоритм NEAT
32. Нечіткі множини й функції належності: як записати «трохи тепло»
33. Нечітка логіка та ймовірність: чому «трохи тепло» не означає «імовірно тепло»
34. Нечітка логіка: t-норми, імплікації та правила ЯКЩО–ТО
35. Нечітке керування: Мамдані та Суґено від вентилятора до маятника на візку
36. Нечітка кластеризація: алгоритм fuzzy c-means і точки між кластерами
37. Нейро-нечіткі системи (ANFIS): нечіткі правила, які навчаються з даних
38. Марковські ланцюги: матриця переходів, стаціонарний розподіл і PageRank
39. Приховані марковські моделі: алгоритм Вітербі й нечесне казино
40. Байєсівські мережі: чому трава мокра і що з цього випливає для дощувача
41. Фільтр Калмана: як за неточними вимірюваннями оцінити, де авто і як швидко воно їде
42. Види машинного навчання: з учителем, без учителя, з частковим залученням учителя та інші
43. Промпти, контекст і RAG: як дати моделі правильну інформацію
44. Варіаційні автокодувальники (VAE): нові зображення з неперервного латентного простору
45. Генеративні змагальні мережі (GAN): фальшувальник проти детектива
46. Дифузійні моделі: як із чистого шуму постає зображення
47. Марковські процеси ухвалення рішень: стани, дії, винагороди й рівняння Беллмана
48. Q-навчання і DQN: як навчитися цінності дій — від таблиці до нейронної мережі
49. Policy gradient і PPO: навчання безпосередньо політики
50. Як працює ШІ-агент: мовна модель у циклі з інструментами
51. Програмування з AI-агентами: завдання, тести й перевірка
52. Оцінювання і безпека систем ШІ: як вимірювати і як стежити

Повна програма серії Готово: 52 з 83 тем

У минулій частині ми стан ланцюга бачили: сьогодні сонячно, завтра дощ. Але часто бачимо лише його прояви. Мікрофон уловлює звукову хвилю, а не слово, яке її створило. Секвенатор читає літери ДНК, а не те, де починається ген. А в казино ми бачимо, що випало, а не яким кубиком кидає круп’є. Приховані марковські моделі — це ланцюги, стани яких ми не бачимо, — і алгоритми, якими все одно можна з’ясувати, що відбувається всередині. Десятиліттями на них трималося розпізнавання мовлення.

Продовжує частину Марковські ланцюги.

1. Нечесне казино

Класичний підручниковий приклад (Durbin та ін., 1998): круп’є кидає або чесний кубик, або фальшивий, на якому шістка випадає з ймовірністю 1/2, а решта чисел — з 1/10. Після кожного кидка з ймовірністю 0,05 він міняє чесний кубик на фальшивий і з ймовірністю 0,1 фальшивий назад на чесний. Заміни ми не бачимо. Бачимо лише ряд чисел — у нашому досліді 300 кидків, які починаються так:

163665521623524236522511663566613666222461626262162666626516…

Питаємо: чи тут грають чесно? А якщо ні, то коли саме в грі був фальшивий кубик?

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

Означення — прихована марковська модель

Прихована марковська модель (HMM) λ = (π, A, B) має приховані стани 1, …, N і спостережувані символи 1, …, M:

• приховані стани X₁, X₂, … утворюють марковський ланцюг із початковим розподілом π і матрицею переходів A, a_ij = P(X_t+1 = j | X_t = i);
• у кожен момент стан X_t = i породжує спостереження O_t за ймовірностями емісії b_i(o) = P(O_t = o | X_t = i), незалежно від усього іншого.

З означення випливає, наскільки ймовірна одна конкретна «історія»: послідовність кубиків x = (x₁, …, x_T) разом із кидками O = (O₁, …, O_T).

P(x, O | λ) = π_x1 b_x1(O₁) · ∏_t=2^T a_{xt−1 xt} b_xt(O_t)

π_x1

перший кубик не має попередника, з якого на нього перейшли б, — його ймовірність дає початковий розподіл

a_{xt−1 xt}

кожен наступний кубик залежить лише від попереднього (марковська властивість), тож на кожен крок досить одного числа з матриці A

b_xt(O_t)

кидок залежить лише від кубика, яким саме кидають, — беремо ймовірність числа, яке справді випало

∏_t=2^T

загалом множилися б ймовірності, обумовлені всім минулим (ланцюгове правило); обидва припущення незалежності з означення скорочують їх до цих локальних чисел, і тому ціле — простий добуток

Приклад — дві історії перших трьох кидків

Наш ряд починається кидками 1, 6, 3. Позначмо Ч чесний і Ф фальшивий кубик. Історія «тричі фальшивий»:

P(ФФФ, 1, 6, 3) = 0,5 · 0,1 · 0,9 · 0,5 · 0,9 · 0,1 = 0,002025,

історія «тричі чесний»:

P(ЧЧЧ, 1, 6, 3) = 0,5 · ¹/₆ · 0,95 · ¹/₆ · 0,95 · ¹/₆ = 0,002089.

Чесна історія виходить трохи ймовірнішою: шістка на фальшивому кубику хоч і отримує 0,5 замість ¹/₆, зате одиниця і трійка лише 0,1 замість ¹/₆. (У симуляції при цьому всі три кидки робили фальшивим кубиком — із трьох кидків цього не розпізнати.)

Лоуренс Рабінер у знаменитому огляді 1989 року звів те, що можна робити з такою моделлю, до трьох задач: оцінювання (наскільки ймовірний спостережений ряд?), декодування (які приховані стани найімовірніше за ним стояли?) і навчання (які параметри має модель, коли ми знаємо лише спостереження?). На кожну існує елегантний алгоритм.

3. Наскільки ймовірний ряд: алгоритм прямого ходу

Ймовірність спостереженого ряду — це сума за всіма можливими послідовностями прихованих станів. Для 300 кидків і двох кубиків їх 2³⁰⁰ ≈ 2 · 10⁹⁰ — більше, ніж атомів у Всесвіті. Підсумувати це напряму не вийде. Але марковська властивість дозволяє рахувати поступово.

Приклад — ймовірність трьох кидків як сума за всіма історіями

Ймовірність спостереження — це сума спільної ймовірності за всіма можливими історіями: P(O | λ) = ∑_x P(x, O | λ). Для кидків 1, 6, 3 їх 2³ = 8:

Історія	P(x, O)
ЧЧЧ	0,002089
ЧЧФ	0,000066
ЧФЧ	0,000035
ЧФФ	0,000188
ФЧЧ	0,000132
ФЧФ	0,000004
ФФЧ	0,000375
ФФФ	0,002025
сума	0,004913

Кожна історія коштує 2T − 1 = 5 множень, разом 8 · 5 = 40. Для T кидків це (2T − 1) · 2^T — для 300 кидків неймовірно багато.

Алгоритм — алгоритм прямого ходу

Позначмо α_t(j) = P(O₁, …, O_t, X_t = j). Тоді

α₁(j) = π_j b_j(O₁),   α_t+1(j) = [∑_i α_t(i) a_ij] b_j(O_t+1),   P(O | λ) = ∑_j α_T(j).

Обчислення триває O(N² T) замість O(N^T). Щоб числа не зникли в машинному нулі, α_t на кожному кроці нормалізують і підсумовують логарифми нормалізаційних сталих.

α_t+1(j) = ∑_i α_t(i) a_ij · b_j(O_t+1)

α_t(i)

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

a_ij

крок ланцюга з i в j; завдяки марковській властивості неважливо, як ми потрапили в i

∑_i

ми не знаємо, яким кубиком кидали минулого разу, а в j можна потрапити з будь-якого — тому підсумовуємо за всіма можливостями (історії є попарно несумісними подіями)

b_j(O_t+1)

новий кидок кубик j мусить справді породити; він не залежить від i, тож його можна винести за суму

Приклад — алгоритм прямого ходу на кидках 1, 6, 3

Старт: α₁(Ч) = 0,5 · ¹/₆ = 0,0833, α₁(Ф) = 0,5 · 0,1 = 0,0500. Другий кидок — шістка:

α₂(Ч) = (0,0833 · 0,95 + 0,0500 · 0,1) · ¹/₆ = 0,0140,
α₂(Ф) = (0,0833 · 0,05 + 0,0500 · 0,9) · 0,5 = 0,0246.

t	кидок	αt(Ч)	αt(Ф)	сума = P(O1, …, Ot)	ct
1	1	0,0833	0,0500	0,133333	0,1333
2	6	0,0140	0,0246	0,038611	0,2896
3	3	0,0026	0,0023	0,004913	0,1273

Сума в останньому рядку — це точно сума восьми історій із попереднього прикладу, тільки замість 40 множень вистачило 2 + 2 · 6 = 14. Останній стовпець c_t = P(O_t | O₁, …, O_t−1) — це нормалізаційна стала з масштабування: наскільки ймовірним був кидок t з огляду на попередні. Їхній добуток дорівнює P(O | λ), тож log P(O | λ) = ∑_t log c_t.

Навіщо логарифми? Для 3 000 кидків P(O | λ) виходить близько 10^−2 278, а найменше додатне число, яке комп’ютер може зберегти у звичайній подвійній точності (IEEE 754), — приблизно 4,9 · 10⁻³²⁴. Без масштабування α зникло б у машинному нулі.

def dopredu(hody, pi, A, B):
    alfa = pi * B[:, hody[0]]
    logP = 0.0
    for t in range(len(hody)):
        if t > 0:
            alfa = (alfa @ A) * B[:, hody[t]]       # сума за i, потім емісія
        c = alfa.sum()                              # c_t = P(O_t | O_1, …, O_t−1)
        alfa = alfa / c                             # масштабування: α_t тепер дає в сумі 1
        logP += np.log(c)
    return logP                                     # log P(O | λ)

Для наших 300 кидків виходить P(кидки | модель казино) ≈ 10^−230,03. Якби весь час грали чесно, ймовірність була б (1/6)³⁰⁰ ≈ 10^−233,45. Модель з епізодичним фальшивим кубиком пояснює спостережені кидки приблизно у 2 600 разів краще — сильний доказ, що тут шахраюють, хоча жоден окремий кидок шахрайства не видає.

Означення — відношення правдоподібностей (коефіцієнт Баєса)

Для двох моделей M₁, M₂ і даних O коефіцієнт Баєса — це K = P(O | M₁) / P(O | M₂). З теореми Баєса (записаної для обох моделей і поділеної) випливає:

P(M₁ | O) / P(M₂ | O) = P(O | M₁) / P(O | M₂) · P(M₁) / P(M₂)

P(M₁ | O) / P(M₂ | O)

відношення шансів після спостереження — те, що нас цікавить: наскільки більше ми віримо в шахрайство, ніж у чесну гру, коли кидки вже бачили

P(O | M₁) / P(O | M₂)

коефіцієнт Баєса — єдине місце, через яке у формулу входять дані; обидві правдоподібності обчислює алгоритм прямого ходу. Знаменник P(O) з теореми Баєса при діленні скорочується, тому його не треба знати

P(M₁) / P(M₂)

відношення шансів заздалегідь — хто заздалегідь довіряє казино, тому потрібен сильніший доказ; дані його лише домножують

Обчислення. log₁₀ K = −230,03 − (−233,45) = 3,42 (з незаокруглених значень 3,413), тобто K ≈ 10^3,413 ≈ 2 590, після округлення 2 600. Хто заздалегідь вважав шахрайство і чесну гру однаково ймовірними, після 300 кидків має шанси приблизно 2 600 : 1 на користь шахрайства. За поширеною шкалою Касса і Рафтері (1995) коефіцієнт Баєса понад 150 — «дуже сильний» доказ.

4. Коли шахраювали: алгоритм Вітербі

Алгоритм — алгоритм Вітербі (1967)

Шукаємо найімовірнішу послідовність станів argmax_x P(x, O | λ). Позначмо δ_t(j) ймовірність найкращого шляху, який у момент t закінчується в стані j:

δ₁(j) = π_j b_j(O₁),   δ_t+1(j) = max_i [δ_t(i) a_ij] · b_j(O_t+1),

і для кожного δ_t+1(j) запам’ятай, з якого i він прийшов. Наприкінці вибери найкращий стан і за запам’ятованими посиланнями йди назад. Обчислюють у логарифмах; час знову O(N² T).

δ_t+1(j) = max_i δ_t(i) a_ij · b_j(O_t+1),   ψ_t+1(j) = argmax_i δ_t(i) a_ij

δ_t(i)

ймовірність найкращої історії, яка в момент t закінчується кубиком i; гірші історії до i нам уже не потрібні — якби найкращий повний шлях ішов через i, він продовжився б найкращою з них

a_ij

ціна переходу з i в j; мале a_ЧФ = 0,05 — причина, чому Вітербі не хоче перемикатися через одну шістку

max_i, ψ_t+1(j)

на відміну від алгоритму прямого ходу ми не підсумовуємо, а вибираємо найкращого попередника — хочемо один шлях, а не ймовірність усіх; ψ пам’ятає, хто переміг (у ґратці бурштинові стрілки), щоб шлях наприкінці можна було відновити у зворотному порядку

b_j(O_t+1)

наскільки добре кубик j пояснює новий кидок — так само, як в α

На дванадцяти кидках видно, як Вітербі ухвалює рішення. Перші шість кидків (5, 2, 2, 5, 1, 1) виглядають чесно. Потім випадають дві шістки поспіль і ще дві трохи далі — і найкращий шлях перемикається на фальшивий кубик. Насправді круп’є замінив кубик лише на чотири кидки пізніше; дві шістки поспіль випадають і на чесному кубику.

Приклад — Вітербі крок за кроком на кидках 1, 6, 3

Старт такий самий, як для α: δ₁(Ч) = 0,0833, δ₁(Ф) = 0,0500. Для шістки в другому кидку:

δ₂(Ч) = max(0,0833 · 0,95; 0,0500 · 0,1) · ¹/₆ = 0,0792 · ¹/₆ = 0,0132   (переміг Ч),
δ₂(Ф) = max(0,0833 · 0,05; 0,0500 · 0,9) · 0,5 = 0,0450 · 0,5 = 0,0225   (переміг Ф).

t	кидок	δt(Ч)	ψt(Ч)	δt(Ф)	ψt(Ф)
1	1	0,083333	—	0,050000	—
2	6	0,013194	Ч	0,022500	Ф
3	3	0,002089	Ч	0,002025	Ф

Наприкінці перемагає Ч (0,002089 > 0,002025), і у зворотному порядку за посиланнями ψ виходить шлях ЧЧЧ — точно та історія з першого прикладу, яка була найімовірнішою з усіх восьми. Проте алгоритм прямого ходу для третього кидка дає P(Ф | O₁, O₂, O₃) = 0,002283 / 0,004913 = 0,465. Найкращий шлях і найімовірніший стан тут збігаються (Ч), але «перемога» тісна, і трьох кидків для певності не досить. Загалом вони збігатися не мусять — до цього ми повернемося в апостеріорному декодуванні.

import numpy as np

def viterbi(hody, pi, A, B):
    T, N = len(hody), len(pi)
    delta = np.log(pi) + np.log(B[:, hody[0]])
    odkud = np.zeros((T, N), dtype=int)
    for t in range(1, T):
        kandidati = delta[:, None] + np.log(A)       # з кожного i в кожне j
        odkud[t] = kandidati.argmax(axis=0)
        delta = kandidati.max(axis=0) + np.log(B[:, hody[t]])
    cesta = [int(delta.argmax())]
    for t in range(T - 1, 0, -1):                     # назад за переможними посиланнями
        cesta.append(odkud[t][cesta[-1]])
    return cesta[::-1]

5. Усі 300 кидків

Фальшивий кубик був у грі 88 разів, у дев’яти відрізках. Вітербі позначив як фальшиві 62 кидки, з них 56 правильно, і загалом визначив кубик правильно для 87,3 % кидків. Довгі відрізки шахрайства він знайшов, а короткі пропустив або злив докупи — замість дев’яти відрізків бачить два. На короткому відрізку просто не випадає досить шісток, щоб це було варте «дорогої» заміни кубика (ймовірність заміни лише 0,05).

Означення — апостеріорна ймовірність стану

Алгоритм прямого-зворотного ходу додатково обчислює β_t(i) = P(O_t+1, …, O_T | X_t = i) з кінця і з обох отримує γ_t(i) = P(X_t = i | O) ∝ α_t(i) β_t(i).

γ_t(i) = α_t(i) · β_t(i) / P(O | λ),   β_t(i) = ∑_j a_ij b_j(O_t+1) β_t+1(j),   β_T(i) = 1

γ_t(i)

ймовірність того, що в момент t у грі був кубик i, коли ми знаємо усі кидки — для фальшивого кубика це червона крива на рисунку

α_t(i)

докази з минулого: кидки від 1 до t і стан i в момент t

β_t(i)

докази з майбутнього: наскільки добре стан i пояснює кидки від t + 1 до T. Обчислюється з кінця тим самим трюком, що й α, — один крок ланцюга, емісія, решта майбутнього. Множити α і β можна, бо за відомого стану X_t минулі й майбутні кидки незалежні

P(O | λ)

добуток α·β — це спільна ймовірність P(X_t = i, O); діленням на ймовірність усіх кидків робимо з неї умовну. Це те саме число, яке дав алгоритм прямого ходу, і ∑_i α_t(i) β_t(i) = P(O | λ) для кожного t

Приклад — другий кидок: що додає майбутнє

Залишмося з кидками 1, 6, 3 і запитаймо про другий кидок (шістку). Зворотний крок від β₃ = 1 з третім кидком (трійкою):

β₂(Ч) = 0,95 · ¹/₆ + 0,05 · 0,1 = 0,1633,   β₂(Ф) = 0,1 · ¹/₆ + 0,9 · 0,1 = 0,1067.

γ₂(Ф) = 0,024583 · 0,106667 / 0,004913 = 0,534.

Якби ми знали лише перші два кидки, було б P(Ф | O₁, O₂) = α₂(Ф) / (α₂(Ч) + α₂(Ф)) = 0,637. Трійка, що випала потім, на фальшивому кубику менш імовірна, тож підозру щодо другого кидка вона заднім числом знижує до 0,534.

Означення — апостеріорне декодування і точність

Апостеріорне декодування в кожен момент окремо вибирає x̂_t = argmax_i γ_t(i). Точність декодування x̂ щодо справжніх станів x — це частка збігів (1/T) ∑_t [x̂_t = x_t], де [·] дорівнює 1, коли твердження справджується, інакше 0.

Апостеріорне декодування максимізує очікувану кількість правильно визначених кидків, Вітербі — ймовірність того, що правильний увесь шлях одразу. Тому апостеріорна послідовність може містити й перехід, який у моделі має ймовірність нуль, — у казино такого немає, але загалом це може статися.

Якби ми для кожного кидка вибрали кубик із більшою апостеріорною ймовірністю, влучили б у 87,7 % — трохи більше, ніж Вітербі (263 кидки з 300 проти 262, різниця в один кидок). (Вітербі шукає найкращий увесь шлях, апостеріорне декодування — найкращу оцінку кожного кидка окремо; це не одне й те саме.) І обережно з однією симуляцією: у дванадцяти різних дослідах точність алгоритму Вітербі коливалася від 73,3 до 90,0 %, у середньому 83,4 %. Залежно від того, які довгі відрізки шахрайства створить випадок.

6. Навчання: алгоритм Баума–Велша

Досі ми параметри казино знали. А якщо ми знаємо лише, що кубиків два, а все інше треба вичитати з кидків?

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

Це алгоритм EM (Baum та ін., близько 1970 року). Повторюй:

1. крок E: з поточними параметрами обчисли алгоритмом прямого-зворотного ходу γ_t(i) і очікувані кількості переходів ξ_t(i, j) = P(X_t = i, X_t+1 = j | O);
2. крок M: нове a_ij = ∑_t ξ_t(i, j) / ∑_t γ_t(i), нове b_i(o) = частка γ у моменти, коли випало o.

Правдоподібність P(O | λ) не спадає в жодній ітерації; алгоритм збігається до локального максимуму.

Очікувана кількість переходів обчислюється з тих самих α і β, що й γ, тільки між них вставляється один крок ланцюга:

ξ_t(i, j) = α_t(i) a_ij b_j(O_t+1) β_t+1(j) / P(O | λ)

α_t(i)

кидки до моменту t і кубик i в момент t — лівий кінець переходу

a_ij

сам перехід i → j, частоту якого ми оцінюємо

b_j(O_t+1)

кидок t + 1 мусить породити новий кубик j

β_t+1(j)

решта кидків від t + 2 далі, пояснена з кубика j, — правий кінець переходу

P(O | λ)

діленням зі спільної ймовірності «перехід і всі кидки» робимо умовну «перехід, коли ми знаємо кидки»

â_ij = ∑_t=1^T−1 ξ_t(i, j) / ∑_t=1^T−1 γ_t(i)

â_ij

нова оцінка ймовірності переходу — відносна частота, ніби ми рахували рисочки

∑ ξ_t(i, j)

очікувана кількість переходів i → j; замість «перейшли чи ні» (1 або 0) підсумовуємо ймовірності, бо стани ми не бачимо

∑ γ_t(i)

очікувана кількість виходів зі стану i; підсумовують лише до T − 1, бо з останнього стану вже жоден перехід не веде. Завдяки цьому рядок нової матриці дає в сумі 1

повторюй (у нас 100 разів):
    α, β, P(O) ← алгоритм прямого-зворотного ходу з поточними π, A, B
    # крок E: м’які кількості
    для кожних t, i:          γ[t][i]    ← α[t][i] · β[t][i] / P(O)
    для кожних t < T, i, j:   ξ[t][i][j] ← α[t][i] · a[i][j] · b[j](O[t+1]) · β[t+1][j] / P(O)
    # крок M: відносні частоти
    π[i]    ← γ[1][i]
    a[i][j] ← ∑_{t<T} ξ[t][i][j] / ∑_{t<T} γ[t][i]
    b[i](o) ← ∑_{t: O[t]=o} γ[t][i] / ∑_t γ[t][i]

Ми почали з поганої оцінки: кубики майже не відрізняються й міняються часто. З 300 кидків алгоритм Баума–Велша дійшов до моделі, яка майже не міняє кубики і фальшивому кубику дає шістку лише з ймовірністю 0,39 — для надійної оцінки 300 кидків замало. З 3 000 кидків (інша симуляція того самого казино) він уже вийшов дуже близько до істини:

Чому 300 кидків не вистачає, показує правдоподібність. За 100 ітерацій на наших 300 кидках вона зросла з 10^−231,26 до 10^−227,14 — а це більше, ніж 10^−230,03 справжньої моделі казино. Отже, навчена модель пояснює саме ці кидки краще за істину: вона пристосувалася й до випадкових коливань конкретних даних. Оцінка максимальної правдоподібності наближається до істини лише зі зростанням обсягу даних.

7. Приховані марковські моделі на практиці

• Розпізнавання мовлення. Від вісімдесятих років до приходу глибоких мереж близько 2010 року майже всі системи трималися на HMM: приховані стани — це частини звуків мовлення, спостереження — короткі відрізки звукового спектра, а Вітербі шукає найімовірнішу послідовність слів.
• Мова. Визначення частин мови: прихований стан — це частина мови, спостереження — слово. «Стать» може бути іменником, а «стати» — дієсловом, і вони різняться лише однією літерою; а слово «мати» буває і іменником, і дієсловом — вирішує контекст.
• Біоінформатика. Пошук генів у ДНК (кодувальні й некодувальні ділянки — приховані стани) або профільні HMM для родин білків у базі даних Pfam.
• Неперервні стани. Коли прихований стан — це не «кубик A чи B», а положення і швидкість, замість HMM використовують фільтр Калмана — він має в плані серії власну частину.

8. Підсумок

• Прихована марковська модель — це марковський ланцюг прихованих станів, з яких ми бачимо лише емісії; її визначають π, A і B.
• Алгоритм прямого ходу обчислює ймовірність спостереження за час O(N²T) замість суми за 2³⁰⁰ шляхами; казино з шахрайством пояснює наші кидки приблизно у 2 600 разів краще, ніж чесна гра.
• Алгоритм Вітербі знаходить найімовірніший шлях прихованих станів динамічним програмуванням — у нашій симуляції він визначив кубик правильно для 87,3 % кидків, але короткі відрізки пропустив.
• Алгоритм прямого-зворотного ходу дає апостеріорну ймовірність стану в кожен момент.
• Алгоритм Баума–Велша навчається параметрів лише зі спостережень — але йому потрібно досить даних: 300 кидків не вистачило, 3 000 — так.

Хочете спробувати самі? Доручіть ШІ-агенту навчити HMM із двома станами на щоденних прибутковостях фондового індексу — і подивіться, чи він сам знайде «спокійні» й «бурхливі» періоди ринку.

Маєте іншу думку? Напишіть на support@coden-app.com.