Łańcuchy Markowa: macierz przejścia, rozkład stacjonarny i PageRank

Własność Markowa, macierz przejścia i zmiana rozkładu na modelu pogody, rozkład stacjonarny i twierdzenie ergodyczne, analiza samogłosek Markowa na „Máju” Máchy, PageRank i generowanie tekstu.

13 minut Matěj Žalmánek 2026-10-15

Seria Podstawy AI Część 38 z 52

1. Mapa sztucznej inteligencji: co jest czym i jak to do siebie pasuje
2. Krótka historia sztucznej inteligencji: od Turinga do modeli językowych
3. Dane, model, trening, inferencja: podstawowe pojęcia na jednym przykładzie
4. Jak czytać zapis matematyczny: symbole, indeksy, sumy i kwantyfikatory
5. Zbiory i relacje: klocki, z których składają się definicje w AI
6. Funkcje i odwzorowania: dlaczego każdy model AI jest funkcją
7. Logika i dowody: reguły, według których rozumuje AI
8. Grafy i drzewa: struktura, na której opierają się przeszukiwanie i sieci neuronowe
9. Algebra liniowa dla uczenia maszynowego: wektory, macierze i dlaczego AI głównie mnoży
10. Pochodne, gradient i reguła łańcuchowa: jak model ustala, w którą stronę się uczyć
11. Spadek gradientu: jak uczy się model
12. Czym jest prawdopodobieństwo: od rzutu kostką do aksjomatów Kołmogorowa
13. Prawdopodobieństwo warunkowe i twierdzenie Bayesa: jak zmienić ocenę, gdy dowiesz się czegoś nowego
14. Zmienna losowa i dystrybuanta: jedna funkcja, która mówi o rozkładzie wszystko
15. Funkcja gęstości i funkcja prawdopodobieństwa: dlaczego zmienna ciągła ma w punkcie prawdopodobieństwo zero
16. Wartość oczekiwana, wariancja i kowariancja: gdzie leży rozkład, jak jest szeroki i co z czym się wiąże
17. Przegląd rozkładów prawdopodobieństwa: Bernoulliego, dwumianowy, Poissona, jednostajny, normalny i wykładniczy
18. Prawo wielkich liczb i centralne twierdzenie graniczne: dlaczego średnie zachowują się tak przewidywalnie
19. Statystyka i estymacja parametrów: największa wiarygodność, MAP i przedziały ufności
20. Teoria informacji: entropia, entropia krzyżowa i dywergencja KL — skąd się biorą funkcje straty
21. Przeszukiwanie przestrzeni stanów: BFS, DFS, UCS i A* z animacjami
22. Gry i przeciwnik: minimax, przycinanie alfa-beta i Monte Carlo tree search
23. Spełnianie ograniczeń: backtracking, propagacja ograniczeń i AC-3 na sudoku i mapie czeskich krajów
24. Logika i systemy z bazą wiedzy: wnioskowanie w przód i wstecz, rezolucja i systemy ekspertowe
25. Planowanie: STRIPS, świat klocków, heurystyki z relaksacji i planowanie w agentach AI
26. Przeszukiwanie lokalne i symulowane wyżarzanie: komiwojażer przez czeskie miasta wojewódzkie
27. Algorytmy genetyczne: populacja, krzyżowanie, mutacja i selekcja na plecaku na wycieczkę
28. Strategie ewolucyjne i programowanie genetyczne: od reguły jednej piątej do prawa Keplera
29. Optymalizacja kolonią mrówek: jak ślad feromonowy znajduje krótką drogę
30. Optymalizacja rojem cząstek: bezwładność, własne doświadczenie i doświadczenie roju
31. Neuroewolucja: ewolucja wag i kształtu sieci neuronowych oraz algorytm NEAT
32. Zbiory rozmyte i funkcje przynależności: jak zapisać „trochę ciepło”
33. Logika rozmyta a prawdopodobieństwo: dlaczego „trochę ciepło” nie znaczy „prawdopodobnie ciepło”
34. Logika rozmyta: t-normy, implikacje i reguły JEŻELI–TO
35. Sterowanie rozmyte: Mamdani i Sugeno od wentylatora po wahadło na wózku
36. Klasteryzacja rozmyta: algorytm fuzzy c-means i punkty między skupieniami
37. Systemy neuro-rozmyte (ANFIS): reguły rozmyte, które uczą się z danych
38. Łańcuchy Markowa: macierz przejścia, rozkład stacjonarny i PageRank
39. Ukryte modele Markowa: algorytm Viterbiego i nieuczciwe kasyno
40. Sieci bayesowskie: dlaczego trawa jest mokra i co z tego wynika dla zraszacza
41. Filtr Kalmana: jak z niedokładnych pomiarów oszacować, gdzie jest samochód i jak szybko jedzie
42. Rodzaje uczenia maszynowego: nadzorowane, nienadzorowane, półnadzorowane i inne
43. Prompty, kontekst i RAG: jak dać modelowi właściwe informacje
44. Wariacyjne autoenkodery (VAE): nowe obrazki z ciągłej przestrzeni latentnej
45. Generatywne sieci przeciwstawne (GAN): fałszerz kontra detektyw
46. Modele dyfuzyjne: jak z czystego szumu powstaje obraz
47. Procesy decyzyjne Markowa: stany, akcje, nagrody i równania Bellmana
48. Q-learning i DQN: uczenie się wartości akcji od tabeli po sieć neuronową
49. Policy gradient i PPO: uczenie się bezpośrednio polityki
50. Jak działa agent AI: model językowy w pętli z narzędziami
51. Programowanie z agentami AI: zadanie, testy i kontrola
52. Ocena i bezpieczeństwo systemów AI: jak mierzyć i jak pilnować

Pełny program serii Gotowe: 52 z 83 tematów

W 1913 roku rosyjski matematyk Andriej Markow siedział nad „Eugeniuszem Onieginem” Puszkina i robił coś, co literaturoznawca uznałby za barbarzyństwo: liczył, ile razy po samogłosce następuje kolejna samogłoska. Chciał pokazać, że prawo wielkich liczb obowiązuje także dla zdarzeń, które od siebie zależą — i przy okazji wymyślił model, który dziś ustala kolejność stron w wyszukiwarce, przewiduje pogodę, generuje tekst i stoi za całą rodziną algorytmów sztucznej inteligencji. Ta część otwiera moduł o modelach probabilistycznych.

Nawiązuje do części Prawdopodobieństwo warunkowe i twierdzenie Bayesa oraz Algebra liniowa dla uczenia maszynowego.

1. Proces bez pamięci

Definicja — łańcuch Markowa

Ciąg zmiennych losowych X₀, X₁, X₂, … o wartościach w skończonym zbiorze stanów S jest łańcuchem Markowa, gdy dla wszystkich t i wszystkich stanów zachodzi własność Markowa

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

Jeśli to prawdopodobieństwo nie zależy od t, łańcuch jest jednorodny.

Co daje własność Markowa, widać na prawdopodobieństwie całej trajektorii. Ogólnie rozkłada się ono regułą łańcuchową na iloczyn prawdopodobieństw warunkowych, z których każde zależy od całej przeszłości. Własność Markowa wykreśla z każdego warunku wszystko oprócz ostatniego stanu:

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

P(X₀ = x₀, …)

prawdopodobieństwo, że łańcuch przejdzie dokładnie przez ten ciąg stanów

π₀(x₀)

rozkład początkowy — skąd łańcuch wyrusza, macierz nie mówi; ta informacja musi przyjść z zewnątrz

∏_t=1^T

iloczyn po krokach — kroki następują po sobie i każdy musi „wyjść”, dlatego się je mnoży

P(x_t | x_t−1)

prawdopodobieństwo przejścia w jednym kroku, czyli element macierzy przejścia w wierszu x_t−1 i kolumnie x_t — dzięki własności Markowa zależy tylko od poprzedniego stanu, a nie od całej historii; bez niej stałoby tu P(x_t | x₀, …, x_t−1)

2. Macierz przejścia

Definicja — macierz przejścia

Jednorodny łańcuch o n stanach jest wyznaczony przez macierz przejścia P = (p_ij), gdzie p_ij = P(X_t+1 = j | X_t = i). Macierz jest stochastyczna: p_ij ≥ 0 i każdy wiersz sumuje się do 1.

Zabawkowy model pogody z trzema stanami: po słonecznym dniu z prawdopodobieństwem 0,6 znów jest słonecznie, 0,3 pochmurno i 0,1 pada deszcz; po pochmurnym 0,3 / 0,4 / 0,3; po deszczowym 0,2 / 0,4 / 0,4. Jako graf:

Ta sama informacja jako macierz — wiersz to dzisiejsza pogoda, kolumna jutrzejsza:

Przykład — prawdopodobieństwo jednej trajektorii

Dziś jest słonecznie (π₀ = (1; 0; 0)). Jakie jest prawdopodobieństwo, że kolejne trzy dni będą: słonecznie, pochmurno, deszcz? Według wzoru na trajektorię

P = 1 · p_{słonecznie→słonecznie} · p_{słonecznie→pochmurno} · p_{pochmurno→deszcz} = 1 · 0,6 · 0,3 · 0,3 = 0,054.

Czyli 5,4 %. Suma po wszystkich 3³ = 27 możliwych trójkach dni wynosi 1 — właśnie dlatego, że każdy wiersz macierzy sumuje się do 1.

3. Jak zmienia się rozkład

Twierdzenie — rozkład po n krokach

Jeśli π_t jest wierszowym wektorem rozkładu X_t, to π_t+1 = π_t P, a zatem π_t = π₀ P^t. Element (i, j) macierzy Pⁿ to prawdopodobieństwo przejścia z i do j w n krokach.

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

π_t+1(j)

prawdopodobieństwo, że jutro będzie stan j — jedna składowa nowego wektora wierszowego

∑_i

suma po wszystkich dzisiejszych stanach — do j można dojść skądkolwiek, a te drogi wzajemnie się wykluczają, więc ich prawdopodobieństwa się sumują (wzór na prawdopodobieństwo całkowite)

π_t(i)

jak prawdopodobne jest, że dziś jesteśmy w i — waga drogi przez i

p_ij

prawdopodobieństwo przejścia z i do j — z własności Markowa wystarczy znać tylko dzisiejszy stan

Przykład — rozkład na pojutrze

Jutro (po słonecznym dniu dzisiaj) jest π₁ = (0,6; 0,3; 0,1). Na pojutrze po składowych — kolumna macierzy pomnożona przez wektor π₁:

• słonecznie: 0,6 · 0,6 + 0,3 · 0,3 + 0,1 · 0,2 = 0,36 + 0,09 + 0,02 = 0,47,
• pochmurno: 0,6 · 0,3 + 0,3 · 0,4 + 0,1 · 0,4 = 0,18 + 0,12 + 0,04 = 0,34,
• deszcz: 0,6 · 0,1 + 0,3 · 0,3 + 0,1 · 0,4 = 0,06 + 0,09 + 0,04 = 0,19.

Suma znów wynosi 1. Za trzy dni tym samym sposobem wychodzi (0,422; 0,353; 0,225).

Ciekawa rzecz: mniej więcej po tygodniu jest obojętne, czy dziś świeci słońce, czy pada. Oba rozkłady spotykają się przy tych samych wartościach i dalej się nie zmieniają. Łańcuch „zapomniał”, gdzie zaczął.

Twierdzenie — jak szybko łańcuch zapomina

Jeśli macierz P o n stanach ma n różnych wartości własnych 1 = λ₁, λ₂, …, λ_n i |λ_k| < 1 dla k ≥ 2, to każdy rozkład początkowy rozkłada się na lewe wektory własne i

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

gdzie π jest rozkładem stacjonarnym. Odchylenie od π maleje więc jak |λ₂|^t, gdzie λ₂ to druga największa co do wartości bezwzględnej wartość własna.

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

π_t

rozkład po t dniach

π

rozkład stacjonarny — należy do wartości własnej 1, która przy potęgowaniu się nie zmienia; dlatego to jedyna część, która przetrwa

a₂u₂

początkowe odchylenie w kierunku drugiego wektora własnego — tylko tu widać, skąd łańcuch wyszedł (słońce czy deszcz); w składowej „słonecznie” jest dodatnie dla słonecznego startu i ujemne dla deszczowego

λ₂^t

z każdym dniem odchylenie mnoży się przez λ₂ — tempo zapominania; pozostałe składniki z mniejszymi |λ| znikają jeszcze szybciej, dlatego wolno je pominąć

Przykład — wartości własne macierzy pogody

Suma wartości własnych to ślad macierzy, 0,6 + 0,4 + 0,4 = 1,4, a ich iloczyn to wyznacznik, który wynosi 0,01. Jedna wartość własna to 1 (wiersze sumują się do 1), więc pozostałe dwie spełniają λ₂ + λ₃ = 0,4 i λ₂λ₃ = 0,01. Są to pierwiastki λ² − 0,4λ + 0,01 = 0:

λ_2,3 = 0,2 ± √0,03 = (2 ± √3)/10, czyli λ₂ ≈ 0,373 i λ₃ ≈ 0,027.

Odchylenie prawdopodobieństwa słonecznej pogody od wartości stacjonarnej 0,393 przy słonecznym starcie wynosi po 3, 4, 5 dniach 0,0286; 0,0107; 0,0040 — każdego dnia mniej więcej 0,373 razy tyle co poprzednio. Po tygodniu wynosi 0,0006, a przy deszczowym starcie −0,0005: oba początki różnią się dopiero na czwartym miejscu po przecinku. Do jednej setnej odchylenie zmaleje po ln 0,01 / ln 0,373 ≈ 4,7 dnia.

4. Rozkład stacjonarny

Definicja — rozkład stacjonarny

Rozkład π jest stacjonarny, gdy π P = π — czyli π jest lewym wektorem własnym macierzy P z wartością własną 1.

Definicja — łańcuch nieprzywiedlny i nieokresowy

Oznaczmy przez p_ij⁽ⁿ⁾ element (i, j) macierzy Pⁿ, czyli prawdopodobieństwo przejścia z i do j w n krokach.

• Łańcuch jest nieprzywiedlny, gdy dla każdych dwóch stanów i, j istnieje n ≥ 1 takie, że p_ij⁽ⁿ⁾ > 0.
• Okres stanu i to d(i) = NWD{n ≥ 1 : p_ii⁽ⁿ⁾ > 0} — największy wspólny dzielnik długości wszystkich dróg, które wracają do i. Przy d(i) = 1 stan jest nieokresowy; w łańcuchu nieprzywiedlnym wszystkie stany mają ten sam okres.

Pogoda spełnia oba warunki od razu: wszystkie elementy P są dodatnie (wystarczy n = 1) i p_ii > 0, więc powrót jest możliwy w 1 kroku, a okres wynosi 1. Natomiast łańcuch z dwoma stanami, który regularnie je przełącza (p₁₂ = p₂₁ = 1), jest nieprzywiedlny, ale ma okres 2: π₀P^t dla startu (1; 0) w nieskończoność przeskakuje między (1; 0) a (0; 1), choć rozkład stacjonarny (½; ½) istnieje.

Twierdzenie — twierdzenie ergodyczne dla łańcuchów skończonych

Jeśli skończony łańcuch jest nieprzywiedlny (z każdego stanu można dojść do każdego) i nieokresowy, ma jedyny rozkład stacjonarny π i dla każdego rozkładu początkowego π₀ P^t → π. Ponadto udział czasu, który łańcuch spędza w stanie j, z prawdopodobieństwem 1 dąży do π_j, a średni czas powrotu do j wynosi 1/π_j.

Dla naszego modelu rozkład stacjonarny wychodzi dokładnie (24/61; 22/61; 15/61) ≈ (0,393; 0,361; 0,246): na dłuższą metę słonecznie jest przez 39 % dni, pochmurno przez 36 %, a pada przez 25 %. Po deszczowym dniu na kolejny deszcz czekamy średnio 1/0,246 ≈ 4,07 dnia.

Przykład — rozkład stacjonarny pogody ręcznie

Szukamy π = (a; b; c) takiego, że πP = π. Po kolumnach macierzy:

• a = 0,6a + 0,3b + 0,2c, czyli 4a = 3b + 2c,
• b = 0,3a + 0,4b + 0,4c,
• c = 0,1a + 0,3b + 0,4c, czyli 6c = a + 3b.

Równania są zależne (po zsumowaniu wszystkich trzech dostajemy a + b + c = a + b + c), więc środkowe pomijamy. Z trzeciego a = 6c − 3b, po podstawieniu do pierwszego 24c − 12b = 3b + 2c, czyli b = 22c/15 i a = 6c − 66c/15 = 24c/15. Stosunek wynosi a : b : c = 24 : 22 : 15, a warunek a + b + c = 1 daje

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

Średni czas powrotu do deszczu to 1/π_deszcz = 61/15 ≈ 4,07 dnia.

A symulacja jednego losowego przebiegu pokazuje twierdzenie ergodyczne w działaniu:

Symulacja losuje każdy dzień osobno z wiersza dzisiejszego stanu: losową liczbę u z [0, 1) porównuje się z kolejnymi sumami częściowymi wiersza. Po słonecznym dniu u < 0,6 prowadzi do stanu „słonecznie”, 0,6 ≤ u < 0,9 do stanu „pochmurno”, a reszta do deszczu:

stav = słonecznie
for den in 1 … N:
    u = losowa liczba z [0, 1)
    j = 0
    while u ≥ P[stav][j]:          # odejmuj prawdopodobieństwa, aż u „wpadnie” do przegródki
        u = u − P[stav][j]
        j = j + 1
    stav = j
    počet[stav] += 1
podíly = počet / N                 # według twierdzenia ergodycznego → π

Sam rozkład stacjonarny można obliczyć bez losowania, wielokrotnym mnożeniem przez macierz:

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):          # metoda potęgowa: π ← π P
    pi = pi @ P
print(pi.round(3))            # [0.393 0.361 0.246]

5. Markow, Oniegin i Máj

Markow przeszedł przez pierwsze 20 000 liter „Eugeniusza Oniegina” i każdą oznaczył jako samogłoskę albo spółgłoskę. Samogłosek było 43,2 %. Gdyby litery następowały po sobie niezależnie, samogłoska po samogłosce pojawiałaby się także w 43,2 % przypadków. Markow naliczył jednak tylko 12,8 %, podczas gdy po spółgłosce 66,3 %. Litery od siebie zależą — a mimo to udział samogłosek w długim tekście niezawodnie zbiega. To był jego dowód, że prawo wielkich liczb nie potrzebuje niezależności.

Powtórzmy to na pierwszej strofie „Máju” („Maj”), poematu Karela Hynka Máchy („Byl pozdní večer – první máj…”). Ma 311 liter, samogłosek jest 37,6 %. Oszacowanie macierzy przejścia z liczebności par:

W strofie jest tylko 6 par samogłosek z rzędu — czeszczyzna przeplata je ze spółgłoskami jeszcze chętniej niż rosyjski. A rozkład stacjonarny tego łańcucha wychodzi 37,7 % samogłosek: łańcuch oszacowany z tekstu „ustala się” praktycznie na udziale, który w tekście rzeczywiście występuje (różnicę robią tylko pierwsza i ostatnia litera).

p̂_ij = n_ij / ∑_k n_ik

p̂_ij

oszacowanie prawdopodobieństwa przejścia — daszek mówi, że chodzi o liczbę obliczoną z danych, a nie o prawdziwą wartość

n_ij

ile razy w tekście po i bezpośrednio nastąpiło j — liczy się pary sąsiednich liter, bo łańcuch Markowa patrzy tylko o jeden krok wstecz

∑_k n_ik

ile razy po i nastąpiło cokolwiek — dzielenie sprawia, że wiersz sumuje się do 1, jak wymaga tego macierz stochastyczna

Przykład — liczebności par w pierwszej strofie

311 liter daje 310 par sąsiednich liter. Samogłoska–samogłoska 6, samogłoska–spółgłoska 111, spółgłoska–samogłoska 111, spółgłoska–spółgłoska 82. Stąd

p̂_sam→sam = 6/117 = 0,051, p̂_sam→spół = 111/117 = 0,949, p̂_spół→sam = 111/193 = 0,575, p̂_{spół→spół} = 82/193 = 0,425.

Łańcuch z dwoma stanami ma rozkład stacjonarny dany prostym wzorem:

π_sam = p_spół→sam / (p_sam→spół + p_spół→sam)

π_sam

długoterminowy udział samogłosek

p_spół→sam

przepływ do samogłosek — im częściej ze spółgłoski przechodzi się na samogłoskę, tym więcej samogłosek

p_sam→spół

przepływ z samogłosek — im szybciej opuszcza się samogłoskę, tym mniej ich jest

Przykład — Máj i Oniegin według wzoru

Máj: π_sam = 0,575 / (0,949 + 0,575) = 0,377. Dokładniej: przejść samogłoska→spółgłoska i spółgłoska→samogłoska jest tyle samo (111), więc π_sam = (111/193) / (111/117 + 111/193) = 117/310. Rzeczywisty udział samogłosek to 117/311 — różni się tylko mianownikiem, bo ostatnia litera strofy („r”) nie zaczyna żadnej pary.

Oniegin: z liczb Markowa (samogłoska po samogłosce 12,8 %, czyli samogłoska→spółgłoska 87,2 %; samogłoska po spółgłosce 66,3 %) wychodzi π_sam = 0,663 / (0,872 + 0,663) = 0,432 — dokładnie 43,2 % samogłosek, które Markow naliczył bezpośrednio.

6. PageRank: losowy surfer

W 1998 roku Sergey Brin i Larry Page, założyciele Google’a, zaproponowali, jak uporządkować strony internetowe według ważności. Wyobrazili sobie surfera, który losowo klika w odnośniki, i zapytali: na których stronach spędzi najwięcej czasu?

Definicja — PageRank

Strona i ma k_i odnośników wychodzących. Losowy surfer z prawdopodobieństwem d (zwykle 0,85) klika w jeden z odnośników, wybrany jednostajnie losowo, w przeciwnym razie skacze na dowolną z N stron:

p_ij = (1 − d)/N + d/k_i, gdy i odsyła do j, w przeciwnym razie (1 − d)/N.

PageRank to rozkład stacjonarny tego łańcucha. Skoki gwarantują, że łańcuch jest nieprzywiedlny i nieokresowy.

Najwyżej jest C (0,374), do której odsyła prawie każda strona. Ciekawsza jest A: ma jeden jedyny przychodzący odnośnik, a mimo to jest druga (0,342) — bo ten odnośnik prowadzi z C, a C nie odsyła nigdzie indziej. B, do której odsyła tylko A, dostaje połowę wagi A (0,171). Strony D, E i F, które odsyłają głównie do siebie nawzajem, zostają w okolicach 0,04. Prawdziwy PageRank liczył to samo dla miliardów stron, metodą potęgową.

Równanie π = πP rozpisane dla jednej strony daje znaną postać PageRanku:

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

PR(j)

PageRank strony j — udział czasu, który surfer na niej spędzi; suma po wszystkich stronach wynosi 1

(1 − d)/N

wkład losowych skoków — dostaje go każda strona po równo, nawet ta, do której nic nie odsyła; dzięki niemu łańcuch jest nieprzywiedlny i nieokresowy

d

prawdopodobieństwo, że surfer kliknie w odnośnik, zamiast skoczyć gdzie indziej — 0,85 w oryginalnym artykule Brina i Page’a

∑_i→j

suma tylko po stronach, które odsyłają do j — odnośnik to „głos” na stronę docelową

PR(i) / k_i

głos strony i waży tyle, ile ważna jest sama i, i dzieli się między wszystkie jej k_i odnośniki — strona z tysiącami odnośników daje każdemu tylko trochę

Przykład — sprawdzenie A, B i C

Dla N = 6 i d = 0,85 jest (1 − d)/N = 0,025. Do A prowadzi tylko odnośnik z C, która ma jeden jedyny odnośnik (k_C = 1); do B tylko z A, która ma dwa:

• 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.

Wartości z metody potęgowej spełniają równanie — po tym poznaje się, że iteracja dobiegła końca.

PR = [1/N] * N                              # zacznij równomiernie
repeat:
    nové = [(1 − d)/N] * N                  # losowe skoki
    for i in stránky:
        if i nie ma odnośników:             # ślepy zaułek: skocz gdziekolwiek
            nové[j] += d · PR[i]/N  dla wszystkich j
        else:
            for j in odkazy[i]:
                nové[j] += d · PR[i]/k_i
    PR = nové
until PR prawie się nie zmienia

7. Łańcuchy, tekst i modele językowe

Łańcuch, którego stanami są litery, można zmusić do generowania. Z par liter w pierwszej strofie „Máju” szacujemy, co następuje po której literze, a potem losujemy. Tak wygląda 90 znaków:

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

Bzdura — ale bzdura, która „brzmi po czesku”: przeplata samogłoski i spółgłoski, ma krótkie słowa i sylaby takie jak „lás” czy „kol”. Ten sam eksperyment przeprowadził Claude Shannon w 1948 roku z angielskim i pokazał, że z dłuższym kontekstem (trójki liter, pary słów) tekst wygląda coraz naturalniej.

Przykład — wiersz „l” modelu bigramowego

Tekst strofy zamieniamy na małe litery, a interpunkcję zastępujemy spacją. Po literze „l” następuje w nim kolejny znak 31 razy: 13 razy spacja, 7 razy „a”, 6 razy „á”, 2 razy „o” i po jednym razie „i”, „h”, „u”. Według wzoru na oszacowanie jest więc

P(spacja | 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, a pozostałe 1/31 ≈ 0,03.

Generowanie robi potem to samo co symulacja pogody: z wiersza aktualnego znaku losuje następny znak. Po „l” słowo najczęściej się kończy — „byl”, „lhal”, „kol”, „bol”.

Definicja — model n-gramowy

Model n-gramowy przewiduje kolejny symbol na podstawie n − 1 poprzednich: P(w_t | w_t−n+1, …, w_t−1). Jest to łańcuch Markowa, którego stanem jest ostatnich n − 1 symboli.

Przykład — ile stanów ma model n-gramowy

Przy słowniku V symboli model n-gramowy ma |V|ⁿ⁻¹ stanów, a w każdym wierszu |V| prawdopodobieństw. Strofa „Máju” używa 32 różnych znaków (litery i spacja):

• bigramy (n = 2): 32 stany, macierz 32 × 32 = 1 024 liczby — więcej, niż strofa ma znaków, więc większość z nich wychodzi zerowa;
• trigramy: 32² = 1 024 stany i ponad 32 tysiące liczb — większości par liter strofa w ogóle nie zawiera i ich wiersze zostają puste;
• model językowy ze słownikiem 50 000 tokenów i oknem 1 000 tokenów: 50 000^1 000 ≈ 10^4 699 stanów.

Dlatego dłuższy kontekst wymaga albo ogromnych danych, albo modelu, który nie bierze prawdopodobieństw z tabeli, tylko szacuje je funkcją — siecią neuronową.

8. Dokąd prowadzą łańcuchy Markowa

• Ukryte modele Markowa — co, jeśli stanu nie widzimy, a widzimy tylko jego przejawy? Temu poświęcona jest następna część.
• Procesy decyzyjne Markowa dodają akcje i nagrody: na nich opiera się uczenie przez wzmacnianie.
• Metody Monte Carlo oparte na łańcuchach Markowa (MCMC) budują łańcuch, którego rozkładem stacjonarnym jest ten, z którego chcemy próbkować — typowo rozkład a posteriori w statystyce bayesowskiej. Kryterium Metropolisa z części o symulowanym wyżarzaniu jest właśnie takim łańcuchem.

9. Podsumowanie

• Łańcuch Markowa nie ma pamięci: następny stan zależy tylko od obecnego. Opisuje go stochastyczna macierz przejścia P.
• Rozkład zmienia się przez mnożenie przez macierz, π_t = π₀ P^t.
• Nieprzywiedlny nieokresowy łańcuch ustala się na jedynym rozkładzie stacjonarnym π = π P, niezależnie od początku; dla pogody (0,393; 0,361; 0,246).
• Markow pokazał zależność liter na „Onieginie”; w „Máju” samogłoska następuje po samogłosce tylko w 5 % przypadków.
• PageRank to rozkład stacjonarny losowego surfera; modele n-gramowe i dzisiejsze modele językowe to łańcuchy Markowa z dużym stanem.

Chcesz to wypróbować? Poproś agenta AI, żeby zbudował słowny model bigramowy z całego „Máju” albo z twoich własnych e-maili i generował z niego zdania — a potem spróbuj trigramów.

Masz inne zdanie? Napisz na support@coden-app.com.