Марковські ланцюги: матриця переходів, стаціонарний розподіл і PageRank

Марковська властивість, матриця переходів і зміна розподілу на моделі погоди, стаціонарний розподіл і ергодична теорема, Марковів аналіз голосних на поемі Махи «Máj», PageRank і генерування тексту.

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

Серія Основи ШІ Частина 38 з 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 тем

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

Продовжує частини Умовна ймовірність і теорема Баєса та Лінійна алгебра для машинного навчання.

1. Процес без пам’яті

Означення — марковський ланцюг

Послідовність випадкових величин X₀, X₁, X₂, … зі значеннями у скінченній множині станів S є марковським ланцюгом, якщо для всіх t і всіх станів виконується марковська властивість

P(X_t+1 = j | X_t = i, X_t−1, …, X₀) = P(X_t+1 = j | X_t = i).

Якщо ця ймовірність не залежить від t, ланцюг однорідний.

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

P(X₀ = x₀, …, X_T = x_T) = π₀(x₀) · ∏_t=1^T P(x_t | x_t−1)

P(X₀ = x₀, …)

ймовірність того, що ланцюг пройде саме цю послідовність станів

π₀(x₀)

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

∏_t=1^T

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

P(x_t | x_t−1)

ймовірність переходу за один крок, тобто елемент матриці переходів у рядку x_t−1 і стовпці x_t — завдяки марковській властивості залежить лише від попереднього стану, а не від усієї історії; без неї тут стояло б P(x_t | x₀, …, x_t−1)

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

Означення — матриця переходів

Однорідний ланцюг з n станами задається матрицею переходів P = (p_ij), де p_ij = P(X_t+1 = j | X_t = i). Матриця стохастична: p_ij ≥ 0 і сума кожного рядка дорівнює 1.

Іграшкова модель погоди з трьома станами: після сонячного дня з імовірністю 0,6 знову сонячно, 0,3 хмарно і 0,1 дощ; після хмарного 0,3 / 0,4 / 0,3; після дощового 0,2 / 0,4 / 0,4. У вигляді графа:

Та сама інформація у вигляді матриці — рядок означає сьогоднішню погоду, стовпець завтрашню:

Приклад — ймовірність однієї траєкторії

Сьогодні сонячно (π₀ = (1; 0; 0)). Яка ймовірність того, що наступні три дні будуть сонячно, хмарно, дощ? За формулою для траєкторії

P = 1 · p_{сонячно→сонячно} · p_{сонячно→хмарно} · p_{хмарно→дощ} = 1 · 0,6 · 0,3 · 0,3 = 0,054.

Тобто 5,4 %. Сума за всіма 3³ = 27 можливими трійками днів дорівнює 1 — саме тому, що сума кожного рядка матриці дорівнює 1.

3. Як змінюється розподіл

Теорема — розподіл після n кроків

Якщо π_t — вектор-рядок розподілу X_t, то π_t+1 = π_t P, а отже π_t = π₀ P^t. Елемент (i, j) матриці Pⁿ — це ймовірність переходу з i в j за n кроків.

π_t+1(j) = ∑_i π_t(i) · p_ij

π_t+1(j)

ймовірність, що завтра буде стан j — одна компонента нового вектора-рядка

∑_i

сума за всіма сьогоднішніми станами — в j можна прийти звідки завгодно, і ці шляхи взаємно виключають один одного, тож їхні ймовірності додаються (формула повної ймовірності)

π_t(i)

наскільки ймовірно, що сьогодні ми в i — вага шляху через i

p_ij

ймовірність переходу з i в j — завдяки марковській властивості досить знати лише сьогоднішній стан

Приклад — розподіл на післязавтра

Завтра (після сонячного сьогодні) π₁ = (0,6; 0,3; 0,1). Для післязавтра покомпонентно — стовпець матриці, помножений на вектор π₁:

• сонячно: 0,6 · 0,6 + 0,3 · 0,3 + 0,1 · 0,2 = 0,36 + 0,09 + 0,02 = 0,47,
• хмарно: 0,6 · 0,3 + 0,3 · 0,4 + 0,1 · 0,4 = 0,18 + 0,12 + 0,04 = 0,34,
• дощ: 0,6 · 0,1 + 0,3 · 0,3 + 0,1 · 0,4 = 0,06 + 0,09 + 0,04 = 0,19.

Сума знову дорівнює 1. Через три дні тим самим способом вийде (0,422; 0,353; 0,225).

Цікава річ: приблизно через тиждень уже байдуже, світить сьогодні сонце чи йде дощ. Обидва розподіли сходяться до однакових значень і далі не змінюються. Ланцюг «забув», звідки почав.

Теорема — як швидко ланцюг забуває

Якщо матриця P з n станами має n різних власних значень 1 = λ₁, λ₂, …, λ_n і |λ_k| < 1 для k ≥ 2, то кожен початковий розподіл розкладається за лівими власними векторами і

π_t = π + a₂λ₂^tu₂ + … + a_nλ_n^tu_n,

де π — стаціонарний розподіл. Відхилення від π, отже, спадає як |λ₂|^t, де λ₂ — друге за абсолютною величиною власне значення.

π_t ≈ π + a₂u₂ · λ₂^t

π_t

розподіл через t днів

π

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

a₂u₂

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

λ₂^t

щодня відхилення множиться на λ₂ — це швидкість забування; решта членів із меншими |λ| зникають ще швидше, тому їх можна відкинути

Приклад — власні значення матриці погоди

Сума власних значень — це слід матриці, 0,6 + 0,4 + 0,4 = 1,4, а їхній добуток — визначник, який дорівнює 0,01. Одне власне значення дорівнює 1 (сума кожного рядка дорівнює 1), тож два інші задовольняють λ₂ + λ₃ = 0,4 і λ₂λ₃ = 0,01. Це корені рівняння λ² − 0,4λ + 0,01 = 0:

λ_2,3 = 0,2 ± √0,03 = (2 ± √3)/10, тобто λ₂ ≈ 0,373 і λ₃ ≈ 0,027.

Відхилення ймовірності сонячної погоди від стаціонарного значення 0,393 за сонячного старту через 3, 4, 5 днів становить 0,0286; 0,0107; 0,0040 — щодня воно множиться приблизно на 0,373. Через тиждень воно 0,0006, а за дощового старту −0,0005: обидва початки відрізняються лише в четвертому знаку після коми. До сотої відхилення зменшиться за ln 0,01 / ln 0,373 ≈ 4,7 дня.

4. Стаціонарний розподіл

Означення — стаціонарний розподіл

Розподіл π стаціонарний, якщо π P = π — тобто π є лівим власним вектором матриці P з власним значенням 1.

Означення — незвідний і аперіодичний ланцюг

Позначмо p_ij⁽ⁿ⁾ елемент (i, j) матриці Pⁿ, тобто ймовірність переходу з i в j за n кроків.

• Ланцюг незвідний, якщо для кожних двох станів i, j існує n ≥ 1 з p_ij⁽ⁿ⁾ > 0.
• Період стану i — це d(i) = НСД{n ≥ 1 : p_ii⁽ⁿ⁾ > 0} — найбільший спільний дільник довжин усіх шляхів, які повертаються в i. Якщо d(i) = 1, стан аперіодичний; у незвідному ланцюгу всі стани мають однаковий період.

Погода є і тим, і іншим одразу: усі елементи P додатні (досить n = 1) і p_ii > 0, тож повернення можливе за 1 крок і період дорівнює 1. Натомість ланцюг із двома станами, який регулярно їх чергує (p₁₂ = p₂₁ = 1), незвідний, але має період 2: π₀P^t для старту (1; 0) безкінечно перескакує між (1; 0) і (0; 1), хоча стаціонарний розподіл (½; ½) існує.

Теорема — ергодична теорема для скінченних ланцюгів

Якщо скінченний ланцюг незвідний (з кожного стану можна потрапити в кожен) і аперіодичний, він має єдиний стаціонарний розподіл π і для кожного початкового розподілу π₀ P^t → π. Крім того, частка часу, яку ланцюг проводить у стані j, з імовірністю 1 прямує до π_j, а середній час повернення в j дорівнює 1/π_j.

Для нашої моделі стаціонарний розподіл виходить точно (24/61; 22/61; 15/61) ≈ (0,393; 0,361; 0,246): у довгостроковій перспективі сонячно 39 % днів, хмарно 36 %, а дощ іде у 25 %. Після дощового дня наступного дощу чекаємо в середньому 1/0,246 ≈ 4,07 дня.

Приклад — стаціонарний розподіл погоди вручну

Шукаємо π = (a; b; c) з πP = π. За стовпцями матриці:

• a = 0,6a + 0,3b + 0,2c, тобто 4a = 3b + 2c,
• b = 0,3a + 0,4b + 0,4c,
• c = 0,1a + 0,3b + 0,4c, тобто 6c = a + 3b.

Рівняння залежні (додавши всі три, отримаємо a + b + c = a + b + c), тож середнє відкинемо. З третього a = 6c − 3b, після підстановки в перше 24c − 12b = 3b + 2c, тобто b = 22c/15 і a = 6c − 66c/15 = 24c/15. Відношення a : b : c = 24 : 22 : 15, і умова a + b + c = 1 дає

π = (24/61; 22/61; 15/61) ≈ (0,393; 0,361; 0,246).

Середній час повернення до дощу 1/π_дощ = 61/15 ≈ 4,07 дня.

А симуляція одного випадкового перебігу показує ергодичну теорему в дії:

Симуляція щодня окремо розігрує наступний стан із рядка сьогоднішнього стану: випадкове число u з [0, 1) порівнюється з послідовними сумами рядка. Після сонячного дня u < 0,6 означає сонячно, 0,6 ≤ u < 0,9 хмарно, а решта дощ:

stav = сонячно
for den in 1 … N:
    u = випадкове число з [0, 1)
    j = 0
    while u ≥ P[stav][j]:          # віднімай імовірності, доки u не «впаде» в комірку
        u = u − P[stav][j]
        j = j + 1
    stav = j
    počet[stav] += 1
podíly = počet / N                 # за ергодичною теоремою → π

Сам стаціонарний розподіл можна обчислити без розігрування, повторним множенням на матрицю:

import numpy as np

P = np.array([[0.6, 0.3, 0.1],
              [0.3, 0.4, 0.3],
              [0.2, 0.4, 0.4]])

pi = np.ones(3) / 3
for _ in range(100):          # степеневий метод: π ← π P
    pi = pi @ P
print(pi.round(3))            # [0.393 0.361 0.246]

5. Марков, Онєгін і «Máj»

Марков пройшов перші 20 000 літер «Євгенія Онєгіна» і кожну позначив як голосну або приголосну. Голосних було 43,2 %. Якби літери йшли одна за одною незалежно, голосна після голосної траплялася б теж у 43,2 % випадків. Але Марков нарахував лише 12,8 %, тоді як після приголосної — 66,3 %. Літери одна від одної залежать — і все ж частка голосних у довгому тексті надійно збігається. Це був його доказ того, що закон великих чисел не потребує незалежності.

Повторімо це на першій строфі поеми Карела Гінека Махи «Máj» («Травень»; «Byl pozdní večer – první máj…»). Вона має 311 літер, голосних серед них 37,6 %. Оцінка матриці переходів із кількостей пар:

У строфі лише 6 пар голосних поспіль — чеська любить чергувати їх із приголосними ще більше, ніж російська. А стаціонарний розподіл цього ланцюга дає 37,7 % голосних: ланцюг, оцінений із тексту, «усталюється» практично на тій частці, яка в тексті справді є (різницю дають лише перша й остання літери).

p̂_ij = n_ij / ∑_k n_ik

p̂_ij

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

n_ij

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

∑_k n_ik

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

Приклад — кількості пар у першій строфі

311 літер дають 310 пар сусідніх літер. Голосна–голосна 6, голосна–приголосна 111, приголосна–голосна 111, приголосна–приголосна 82. Звідси

p̂_{гол→гол} = 6/117 = 0,051, p̂_{гол→пр} = 111/117 = 0,949, p̂_{пр→гол} = 111/193 = 0,575, p̂_пр→пр = 82/193 = 0,425.

Ланцюг із двома станами має стаціонарний розподіл, заданий простою формулою:

π_гол = p_{пр→гол} / (p_{гол→пр} + p_{пр→гол})

π_гол

довгострокова частка голосних

p_{пр→гол}

потік у голосні — що частіше з приголосної переходимо на голосну, то більше голосних

p_{гол→пр}

потік із голосних — що швидше від голосної йдемо далі, то менше їх

Приклад — «Máj» і «Онєгін» за формулою

«Máj»: π_гол = 0,575 / (0,949 + 0,575) = 0,377. Точніше: переходів голосна→приголосна і приголосна→голосна однаково (111), тож π_гол = (111/193) / (111/117 + 111/193) = 117/310. Справжня частка голосних — 117/311; відрізняється лише знаменник, бо остання літера строфи («r») жодної пари не починає.

«Онєгін»: з чисел Маркова (голосна після голосної 12,8 %, тобто голосна→приголосна 87,2 %; голосна після приголосної 66,3 %) виходить π_гол = 0,663 / (0,872 + 0,663) = 0,432 — точно ті 43,2 % голосних, які Марков нарахував безпосередньо.

6. PageRank: випадковий серфер

1998 року Сергій Брін і Ларрі Пейдж, засновники Google, запропонували, як упорядкувати вебсторінки за важливістю. Вони уявили собі серфера, який навмання клацає на посилання, і запитали: на яких сторінках він проводитиме найбільше часу?

Означення — PageRank

Сторінка i має k_i вихідних посилань. Випадковий серфер з імовірністю d (зазвичай 0,85) клацає на одне з посилань, вибране рівномірно випадково, інакше стрибає на будь-яку з N сторінок:

p_ij = (1 − d)/N + d/k_i, якщо i посилається на j, інакше (1 − d)/N.

PageRank — це стаціонарний розподіл цього ланцюга. Стрибки гарантують, що ланцюг незвідний і аперіодичний.

Найвище стоїть C (0,374), на яку посилається майже кожна сторінка. Цікавіша A: має єдине вхідне посилання, і все ж вона друга (0,342) — бо це посилання веде з C, а C більше нікуди не посилається. B, на яку посилається лише A, отримує половину ваги A (0,171). Сторінки D, E і F, які посилаються переважно одна на одну, лишаються біля 0,04. Справжній PageRank обчислював те саме для мільярдів сторінок, степеневим методом.

Рівняння π = πP, розписане для однієї сторінки, дає відомий вигляд PageRank:

PR(j) = (1 − d)/N + d ∑_i→j PR(i) / k_i

PR(j)

PageRank сторінки j — частка часу, яку на ній проведе серфер; сума за всіма сторінками дорівнює 1

(1 − d)/N

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

d

ймовірність, що серфер клацне на посилання, а не стрибне деінде, — 0,85 в оригінальній статті Бріна і Пейджа

∑_i→j

сума лише за сторінками, які посилаються на j — посилання є «голосом» за цільову сторінку

PR(i) / k_i

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

Приклад — перевірка A, B і C

Для N = 6 і d = 0,85 маємо (1 − d)/N = 0,025. До A веде лише посилання з C, яка має єдине посилання (k_C = 1); до B — лише з A, яка має два:

• PR(A) = 0,025 + 0,85 · 0,37351 / 1 = 0,34248,
• PR(B) = 0,025 + 0,85 · 0,34248 / 2 ≈ 0,1706,
• PR(C) = 0,025 + 0,85 · (PR(A)/2 + PR(B)/1 + PR(D)/2 + PR(E)/3 + PR(F)/1) = 0,025 + 0,85 · 0,41001 = 0,37351.

Значення, отримані степеневим методом, рівняння задовольняють — так видно, що ітерація завершилася.

PR = [1/N] * N                              # почни рівномірно
repeat:
    nové = [(1 − d)/N] * N                  # випадкові стрибки
    for i in stránky:
        if i не має посилань:               # глухий кут: стрибни будь-куди
            nové[j] += d · PR[i]/N  для всіх j
        else:
            for j in odkazy[i]:
                nové[j] += d · PR[i]/k_i
    PR = nové
until PR майже не змінюється

7. Ланцюги, текст і мовні моделі

Ланцюг, станами якого є літери, можна змусити генерувати. З пар літер у першій строфі «Máj» оцінимо, що йде після якої літери, а потім розігруємо. Ось так виглядає 90 символів:

lal kou lasvavzvný dnkyl plásnětičaskol dnou ta javu snáscezepráro pl h jin trů bo kylalav

Нісенітниця — але нісенітниця, яка «звучить по-чеськи»: чергує голосні й приголосні, має короткі слова і склади на кшталт «lás» чи «kol». Такий самий дослід 1948 року провів Клод Шеннон з англійською і показав, що з довшим контекстом (трійки літер, пари слів) текст виглядає дедалі природніше.

Приклад — рядок «l» біграмної моделі

Текст строфи переведемо в малі літери, а розділові знаки замінимо пробілом. Після літери «l» у ньому 31 раз іде ще якийсь символ: 13 разів пробіл, 7 разів «a», 6 разів «á», 2 рази «o» і по одному разу «i», «h», «u». За формулою оцінки, отже,

P(пробіл | l) = 13/31 ≈ 0,42, P(a | l) = 7/31 ≈ 0,23, P(á | l) = 6/31 ≈ 0,19, P(o | l) = 2/31 ≈ 0,06, а решта 1/31 ≈ 0,03.

Генерування потім робить те саме, що й симуляція погоди: з рядка поточного символу розігрує наступний символ. Після «l» слово найчастіше закінчується — «byl», «lhal», «kol», «bol».

Означення — n-грамна модель

N-грамна модель передбачає наступний символ за n − 1 попередніми: P(w_t | w_t−n+1, …, w_t−1). Це марковський ланцюг, станом якого є останні n − 1 символів.

Приклад — скільки станів має n-грамна модель

Зі словником із V символів n-грамна модель має |V|ⁿ⁻¹ станів і в кожному рядку |V| ймовірностей. Строфа «Máj» використовує 32 різні символи (літери і пробіл):

• біграми (n = 2): 32 стани, матриця 32 × 32 = 1 024 числа — більше, ніж у строфі символів, тож більшість із них виходить нульовою;
• триграми: 32² = 1 024 стани і понад 32 тисячі чисел — більшості пар літер у строфі взагалі немає, і їхні рядки лишаються порожніми;
• мовна модель зі словником 50 000 токенів і вікном 1 000 токенів: 50 000^1 000 ≈ 10^4 699 станів.

Тому довший контекст потребує або величезних даних, або моделі, яка не бере ймовірності з таблиці, а оцінює їх функцією — нейронною мережею.

8. Куди ведуть марковські ланцюги

• Приховані марковські моделі — що, як стану ми не бачимо, а бачимо лише його прояви? Цьому присвячена наступна частина.
• Марковські процеси прийняття рішень додають дії та винагороди: на них тримається навчання з підкріпленням.
• Методи Монте-Карло з марковськими ланцюгами (MCMC) будують ланцюг, стаціонарний розподіл якого — саме той, з якого ми хочемо брати вибірку, — зазвичай апостеріорний розподіл у баєсівській статистиці. Критерій Метрополіса з частини про імітацію відпалу — саме такий ланцюг.

9. Підсумок

• Марковський ланцюг не має пам’яті: наступний стан залежить лише від поточного. Його описує стохастична матриця переходів P.
• Розподіл змінюється множенням на матрицю, π_t = π₀ P^t.
• Незвідний аперіодичний ланцюг усталюється на єдиному стаціонарному розподілі π = π P незалежно від початку; для погоди (0,393; 0,361; 0,246).
• Марков показав залежність літер на «Онєгіні»; у «Máj» голосна йде після голосної лише в 5 % випадків.
• PageRank — стаціонарний розподіл випадкового серфера; n-грамні й сучасні мовні моделі — це марковські ланцюги з великим станом.

Хочете спробувати самі? Попросіть ШІ-агента побудувати словесну біграмну модель з усього «Máj» або з ваших власних електронних листів і генерувати з неї речення — а потім спробуйте триграми.

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