Markovovy řetězce: přechodová matice, stacionární rozdělení a PageRank

Nechť (Ω, 𝓕, P) je pravděpodobnostní prostor, S konečná neprázdná množina (množina stavů) a X₀, X₁, X₂, … : Ω → S posloupnost náhodných veličin (X_t je stav v čase t ∈ ℕ₀). Posloupnost (X_t)_{t ≥ 0} je Markovův řetězec, právě když pro každé t ∈ ℕ₀ a všechny stavy i₀, …, i_t−1, i, j ∈ S takové, že P(X_t = i, X_t−1 = i_t−1, …, X₀ = i₀) > 0, platí Markovova vlastnost

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

Markovův řetězec je homogenní, právě když existují čísla p_ij ∈ [0, 1] (i, j ∈ S) taková, že

P(X_t+1 = j | X_t = i) = p_ij   pro všechna t ∈ ℕ₀ a i, j ∈ S s P(X_t = i) > 0.

Slovy: rozdělení příštího stavu závisí jen na současném stavu, ne na cestě, kterou se do něj řetězec dostal; u homogenního řetězce navíc nezávisí ani na čase t. Rozdělení π₀(i) = P(X₀ = i) se nazývá počáteční rozdělení.

Nechť n ≥ 1. Matice A = (a_ij) ∈ ℝ^n×n je stochastická, právě když

1. a_ij ≥ 0 pro všechna i, j ∈ {1, …, n};
2. ∑_j=1ⁿ a_ij = 1 pro každé i ∈ {1, …, n} (každý řádek má součet 1).

Nechť (X_t)_{t ≥ 0} je homogenní Markovův řetězec s množinou stavů S = {1, …, n} a čísly p_ij z definice výše. Jeho přechodová matice je

P = (p_ij)_i,j=1ⁿ ∈ ℝ^n×n,   p_ij = P(X_t+1 = j | X_t = i).

Přechodová matice je stochastická: pro pevné i je řádek (p_i1, …, p_in) rozdělení pravděpodobnosti stavu X_t+1 za podmínky X_t = i. Naopak každá stochastická matice spolu s počátečním rozdělením π₀ určuje homogenní Markovův řetězec. (Stejné písmeno P pro pravděpodobnost i pro matici je ustálené; z kontextu je vždy jasné, které je které.)

Dnes je slunečno (π₀ = (1; 0; 0)). Jaká je pravděpodobnost, že další tři dny budou slunečno, oblačno, déšť? Podle vzorce pro trajektorii

P = π₀(slunečno) · p_{slunečno→slunečno} · p_{slunečno→oblačno} · p_{oblačno→déšť} = 1 · 0,6 · 0,3 · 0,3 = 0,054

(barvy podle vzorce pro trajektorii výše).

Tedy 5,4 %. Součet přes všech 3³ = 27 možných trojic dní je 1 — přesně proto, že každý řádek matice má součet 1.

Nechť (X_t)_{t ≥ 0} je homogenní Markovův řetězec s množinou stavů S = {1, …, n} a přechodovou maticí P ∈ ℝ^n×n. Pro t ∈ ℕ₀ označme π_t = (π_t(1), …, π_t(n)) ∈ ℝ^1×n řádkový vektor rozdělení X_t, tj. π_t(i) = P(X_t = i). Pak pro každé t ∈ ℕ₀

1. π_t+1 = π_t P, tj. π_t+1(j) = ∑_i=1ⁿ π_t(i) p_ij pro každé j ∈ S;
2. π_t = π₀ P^t;
3. pro každé m ∈ ℕ a i, j ∈ S s P(X_t = i) > 0 platí P(X_t+m = j | X_t = i) = (P^m)_ij.

Prvek (i, j) matice P^m je tedy pravděpodobnost přechodu z i do j za m kroků. Bod 1 je zákon celkové pravděpodobnosti s rozkladem podle hodnoty X_t, bod 2 z něj plyne indukcí.

Zítra (po slunečném dnešku) je π₁ = (0,6; 0,3; 0,1). Pro pozítří po složkách — sloupec matice vynásobený vektorem π₁:

• slunečno: 0,6 · 0,6 + 0,3 · 0,3 + 0,1 · 0,2 = 0,36 + 0,09 + 0,02 = 0,47,
• oblačno: 0,6 · 0,3 + 0,3 · 0,4 + 0,1 · 0,4 = 0,18 + 0,12 + 0,04 = 0,34,
• déšť: 0,6 · 0,1 + 0,3 · 0,3 + 0,1 · 0,4 = 0,06 + 0,09 + 0,04 = 0,19.

V každém řádku je první činitel π₁(i) a druhý p_ij (barvy podle vzorce výše). Součet je opět 1. Za tři dny vyjde stejným postupem (0,422; 0,353; 0,225).

Nechť P ∈ ℝ^n×n (n ≥ 2) je přechodová matice homogenního Markovova řetězce a předpokládejme, že

1. P má n navzájem různých (obecně komplexních) vlastních čísel λ₁, …, λ_n, očíslovaných tak, že λ₁ = 1 a |λ₂| ≥ |λ₃| ≥ … ≥ |λ_n|;
2. |λ_k| < 1 pro všechna k = 2, …, n.

Pro k = 2, …, n nechť u_k ∈ ℂ^1×n je levý vlastní vektor příslušný λ_k (u_kP = λ_ku_k) a nechť π ∈ ℝ^1×n je levý vlastní vektor příslušný λ₁ = 1 se součtem složek 1 — stacionární rozdělení (definice níže). Pak pro každé počáteční rozdělení π₀ existují čísla a₂, …, a_n ∈ ℂ taková, že pro všechna t ∈ ℕ₀

π_t = π₀P^t = π + a₂λ₂^tu₂ + … + a_nλ_n^tu_n.

Důvod. Vlastní vektory příslušné různým vlastním číslům tvoří bázi, takže π₀ = a₁π + ∑_k≥2 a_ku_k, a násobení P^t vynásobí k-tou složku λ_k^t. Pro k ≥ 2 má u_k součet složek 0 (z u_kP1 = u_k1, kde 1 je sloupec jedniček, a λ_k ≠ 1), proto porovnání součtů dá a₁ = 1.

Odchylka π_t − π tedy klesá k nule řádově jako |λ₂|^t, kde λ₂ je druhé největší vlastní číslo v absolutní hodnotě.

Součet vlastních čísel je stopa matice, 0,6 + 0,4 + 0,4 = 1,4, a jejich součin je determinant, který vyjde 0,01. Jedno vlastní číslo je 1 (řádky mají součet 1), takže zbylé dvě splňují λ₂ + λ₃ = 0,4 a λ₂λ₃ = 0,01. Jsou to kořeny λ² − 0,4λ + 0,01 = 0:

λ_2,3 = 0,2 ± √0,03 = 2 ± √3/10,   tedy λ₂ ≈ 0,373 a λ₃ ≈ 0,027.

Odchylka pravděpodobnosti slunečna od stacionární hodnoty 0,393 je při slunečném startu po 3, 4, 5 dnech 0,0286; 0,0107; 0,0040 — každý den asi 0,373-krát menší (barvy podle vzorce výše). Po týdnu je 0,0006 a při deštivém startu −0,0005: oba začátky se liší až na čtvrtém desetinném místě. Na setinu se odchylka zmenší za t dní, kde 0,373^t = 0,01, tedy

t = ln 0,01/ln 0,373 ≈ 4,7 dne.

Nechť P = (p_ij) ∈ ℝ^n×n je přechodová matice homogenního Markovova řetězce s množinou stavů S = {1, …, n}. Řádkový vektor π = (π₁, …, π_n) ∈ ℝ^1×n je stacionární rozdělení řetězce, právě když

1. π_j ≥ 0 pro každé j ∈ S a ∑_j=1ⁿ π_j = 1 (π je rozdělení na S);
2. π P = π, tj. π_j = ∑_i=1ⁿ π_i p_ij pro každé j ∈ S.

Podmínka 2 říká, že π je levý vlastní vektor matice P s vlastním číslem 1. Slovy: má-li X₀ rozdělení π, má podle věty o rozdělení po t krocích rozdělení π i každé X_t — rozdělení se krokem řetězce nezmění.

Nechť (X_t)_{t ≥ 0} je homogenní Markovův řetězec s konečnou množinou stavů S a přechodovou maticí P. Pro i, j ∈ S a m ∈ ℕ označme p_ij^(m) = (P^m)_ij pravděpodobnost přechodu z i do j za m kroků.

1. Řetězec je nerozložitelný (ireducibilní), právě když ∀ i, j ∈ S ∃ m ∈ ℕ : p_ij^(m) > 0.
2. Nechť i ∈ S je stav, pro který je množina R(i) = {m ∈ ℕ : p_ii^(m) > 0} neprázdná. Perioda stavu i je d(i) = NSD R(i), největší společný dělitel délek všech cest, které se do i vracejí.
3. Stav i je neperiodický, právě když d(i) = 1. Řetězec je neperiodický, právě když jsou neperiodické všechny jeho stavy.

V nerozložitelném řetězci mají všechny stavy stejnou periodu, takže stačí ověřit jeden stav.

Počasí je obojí hned: všechny prvky P jsou kladné (m = 1 stačí) a p_ii > 0, takže návrat je možný za 1 krok a perioda je 1. Naproti tomu řetězec se dvěma stavy, který je pravidelně střídá (p₁₂ = p₂₁ = 1), je nerozložitelný, ale má periodu 2: π₀P^t pro start (1; 0) donekonečna přeskakuje mezi (1; 0) a (0; 1), přestože stacionární rozdělení (½; ½) existuje.

Nechť (X_t)_{t ≥ 0} je homogenní Markovův řetězec s konečnou množinou stavů S = {1, …, n} a přechodovou maticí P, který je nerozložitelný a neperiodický. Pak

1. řetězec má právě jedno stacionární rozdělení π = (π₁, …, π_n) a π_j > 0 pro každé j ∈ S;
2. pro každé počáteční rozdělení π₀ platí lim_t→∞ π₀P^t = π (po složkách);
3. pro každé počáteční rozdělení a každý stav j ∈ S platí s pravděpodobností 1 lim_T→∞ |{t ∈ {0, …, T − 1} : X_t = j}|/T = π_j, tj. podíl času stráveného ve stavu j se blíží π_j;
4. pro každý stav j ∈ S je střední doba návratu do j m_j = E[min{t ≥ 1 : X_t = j} | X₀ = j] = 1/π_j.

Hledáme π = (a; b; c) s πP = π. Po sloupcích matice:

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

Rovnice jsou závislé (sečtením všech tří dostaneme a + b + c = a + b + c), a tak prostřední vynecháme. Z třetí a = 6c − 3b, dosazením do první 24c − 12b = 3b + 2c, tedy b = 22c/15 a a = 6c − 66c/15 = 24c/15. Poměr je a : b : c = 24 : 22 : 15 a podmínka a + b + c = 1 dá

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

Průměrná doba návratu do deště je podle ergodické věty m_déšť = 1/π_déšť = 61/15 ≈ 4,07 dne.

311 písmen dává 310 sousedních dvojic. Samohláska–samohláska 6, samohláska–souhláska 111, souhláska–samohláska 111, souhláska–souhláska 82. Odtud

p̂_sam→sam = 6/117 = 0,051,   p̂_sam→sou = 111/117 = 0,949,

p̂_sou→sam = 111/193 = 0,575,   p̂_sou→sou = 82/193 = 0,425

(barvy podle vzorce výše; 117 = 6 + 111 dvojic začíná samohláskou, 193 = 111 + 82 souhláskou).

Máj (barvy podle vzorce výše):

π_sam = 0,575/0,949 + 0,575 = 0,377.

Přesněji: přechodů samohláska→souhláska i souhláska→samohláska je stejně (111), takže

π_sam = 111/193/111/117 + 111/193 = 1/193/117 + 1 =117/310.

Skutečný podíl samohlásek je 117/311 — liší se jen jmenovatelem, protože poslední písmeno sloky („r“) žádnou dvojici nezačíná.

Oněgin: z Markovových čísel (samohláska po samohlásce 12,8 %, tedy samohláska→souhláska 87,2 %; samohláska po souhlásce 66,3 %) vychází

π_sam = 0,663/0,872 + 0,663 = 0,432

— přesně 43,2 % samohlásek, které Markov napočítal přímo.

Nechť N ≥ 1 je počet stránek, stránky jsou očíslované 1, …, N a L ⊆ {1, …, N} × {1, …, N} je množina odkazů: (i, j) ∈ L, právě když stránka i odkazuje na stránku j. Pro každou stránku i nechť k_i = |{j : (i, j) ∈ L}| je počet jejích odchozích odkazů a nechť d ∈ (0, 1) je tlumicí faktor (obvykle d = 0,85). Řetězec náhodného surfaře je homogenní Markovův řetězec se stavy {1, …, N} a přechodovou maticí P = (p_ij), kde

1. p_ij = 1 − d/N + d/k_i,   je-li (i, j) ∈ L;
2. p_ij = 1 − d/N,   je-li k_i ≥ 1 a (i, j) ∉ L;
3. p_ij = 1/N pro všechna j,   je-li k_i = 0 (stránka bez odkazů — surfař skočí kamkoli).

Každý řádek má součet k_i · d/k_i + N · 1 − d/N = 1 (resp. N · 1/N = 1), matice je tedy stochastická. PageRank je stacionární rozdělení PR = (PR(1), …, PR(N)) tohoto řetězce, tj. PR · P = PR a ∑_j PR(j) = 1.

Slovy: surfař s pravděpodobností d klikne na jeden z odkazů aktuální stránky (všechny stejně pravděpodobně), jinak skočí na libovolnou z N stránek. Protože všechna p_ij > 0, je řetězec nerozložitelný a neperiodický a podle ergodické věty má PageRank jediný.

Pro N = 6 a d = 0,85 je 1 − d/N = 1 − 0,85/6 = 0,025. Do A vede jen odkaz z C, které má jediný odkaz (k_C = 1); do B jen z A, které má dva (barvy podle vzorce výše):

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

Hodnoty mocninné metody rovnici splňují — tak se pozná, že iterace doběhla.

Text sloky převedeme na malá písmena a interpunkci nahradíme mezerou. Písmeno „l“ je v něm 31krát následováno dalším znakem: 13krát mezerou, 7krát „a“, 6krát „á“, 2krát „o“ a po jednom „i“, „h“, „u“. Podle vzorce pro odhad je tedy

P(mezera | 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 ostatní   1/31 ≈ 0,03

(barvy podle vzorce pro odhad p̂_ij v části o Máji).

Generování pak dělá totéž co simulace počasí: z řádku aktuálního znaku vylosuje další znak. Po „l“ je slovo nejčastěji u konce — „byl“, „lhal“, „kol“, „bol“.

Nechť V je konečná neprázdná množina symbolů (slovník) a n ≥ 2 celé číslo. N-gramový model řádu n je soubor rozdělení pravděpodobnosti q(· | v) na V, jedno pro každý kontext v = (v₁, …, v_n−1) ∈ Vⁿ⁻¹. Posloupnost symbolů W₁, W₂, … s hodnotami ve V se podle modelu generuje tak, že pro každé t ≥ n a w ∈ V

P(W_t = w | W₁, …, W_t−1) = q(w | W_t−n+1, …, W_t−1),

tj. další symbol závisí jen na n − 1 předchozích. Posloupnost Y_t = (W_t−n+2, …, W_t) ∈ Vⁿ⁻¹ (t ≥ n − 1) je pak homogenní Markovův řetězec s množinou stavů Vⁿ⁻¹: jeho stavem je posledních n − 1 symbolů. Pro n = 2 (bigramy) je stavem jediný symbol a q(w | v) je přímo přechodová pravděpodobnost p_vw.

Se slovníkem V symbolů má n-gramový model |V|ⁿ⁻¹ stavů a v každém řádku |V| pravděpodobností. Sloka Máje používá 32 různých znaků (písmena a mezera):

• bigramy (n = 2): 32 stavů, matice 32 × 32 = 1 024 čísel — víc, než má sloka znaků, takže většina z nich vyjde nulová;
• trigramy: 32² = 1 024 stavů a přes 32 tisíc čísel — většinu dvojic písmen sloka vůbec neobsahuje a jejich řádky zůstanou prázdné;
• jazykový model se slovníkem 50 000 tokenů a oknem 1 000 tokenů: 50 000^1 000 ≈ 10^4 699 stavů.

Proto delší kontext potřebuje buď obrovská data, nebo model, který pravděpodobnosti nepočítá z tabulky, ale odhaduje je funkcí — neuronovou sítí.