Markovove reťazce: prechodová matica, stacionárne rozdelenie a PageRank

Nech (Ω, 𝓕, P) je pravdepodobnostný priestor, S konečná neprázdna množina (množina stavov) a X₀, X₁, X₂, … : Ω → S postupnosť náhodných premenných (X_t je stav v čase t ∈ ℕ₀). Postupnosť (X_t)_{t ≥ 0} je Markovov reťazec práve vtedy, keď pre každé t ∈ ℕ₀ a všetky stavy i₀, …, i_t−1, i, j ∈ S také, že P(X_t = i, X_t−1 = i_t−1, …, X₀ = i₀) > 0, platí Markovova vlastnosť

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

Markovov reťazec je homogénny práve vtedy, keď existujú čísla p_ij ∈ [0, 1] (i, j ∈ S) také, že

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

Slovami: rozdelenie budúceho stavu závisí len od súčasného stavu, nie od cesty, ktorou sa doň reťazec dostal; pri homogénnom reťazci navyše nezávisí ani od času t. Rozdelenie π₀(i) = P(X₀ = i) sa nazýva počiatočné rozdelenie.

Nech n ≥ 1. Matica A = (a_ij) ∈ ℝ^n×n je stochastická práve vtedy, keď

1. a_ij ≥ 0 pre všetky i, j ∈ {1, …, n};
2. ∑_j=1ⁿ a_ij = 1 pre každé i ∈ {1, …, n} (každý riadok má súčet 1).

Nech (X_t)_{t ≥ 0} je homogénny Markovov reťazec s množinou stavov S = {1, …, n} a číslami p_ij z definície vyššie. Jeho prechodová matica je

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

Prechodová matica je stochastická: pre pevné i je riadok (p_i1, …, p_in) rozdelenie pravdepodobnosti stavu X_t+1 za podmienky X_t = i. Naopak každá stochastická matica spolu s počiatočným rozdelením π₀ určuje homogénny Markovov reťazec. (Rovnaké písmeno P pre pravdepodobnosť aj pre maticu je ustálené; z kontextu je vždy jasné, ktoré je ktoré.)

Dnes je slnečno (π₀ = (1; 0; 0)). Aká je pravdepodobnosť, že ďalšie tri dni budú slnečno, oblačno, dážď? Podľa vzorca pre trajektóriu

P = π₀(slnečno) · p_{slnečno→slnečno} · p_{slnečno→oblačno} · p_{oblačno→dážď} = 1 · 0,6 · 0,3 · 0,3 = 0,054

(farby podľa vzorca pre trajektóriu vyššie).

Teda 5,4 %. Súčet cez všetkých 3³ = 27 možných trojíc dní je 1 — presne preto, že každý riadok matice má súčet 1.

Nech (X_t)_{t ≥ 0} je homogénny Markovov reťazec s množinou stavov S = {1, …, n} a prechodovou maticou P ∈ ℝ^n×n. Pre t ∈ ℕ₀ označme π_t = (π_t(1), …, π_t(n)) ∈ ℝ^1×n riadkový vektor rozdelenia X_t, t. j. π_t(i) = P(X_t = i). Potom pre každé t ∈ ℕ₀

1. π_t+1 = π_t P, t. j. π_t+1(j) = ∑_i=1ⁿ π_t(i) p_ij pre každé j ∈ S;
2. π_t = π₀ P^t;
3. pre 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.

Prvok (i, j) matice P^m je teda pravdepodobnosť prechodu z i do j za m krokov. Bod 1 je zákon úplnej pravdepodobnosti s rozkladom podľa hodnoty X_t, bod 2 z neho vyplýva indukciou.

Zajtra (po slnečnom dnešku) je π₁ = (0,6; 0,3; 0,1). Pre pozajtra po zložkách — stĺpec matice vynásobený vektorom π₁:

• slneč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ždom riadku je prvý činiteľ π₁(i) a druhý p_ij (farby podľa vzorca vyššie). Súčet je opäť 1. Za tri dni vyjde rovnakým postupom (0,422; 0,353; 0,225).

Nech P ∈ ℝ^n×n (n ≥ 2) je prechodová matica homogénneho Markovovho reťazca a predpokladajme, že

1. P má n navzájom rôznych (vo všeobecnosti komplexných) vlastných čísel λ₁, …, λ_n, očíslovaných tak, že λ₁ = 1 a |λ₂| ≥ |λ₃| ≥ … ≥ |λ_n|;
2. |λ_k| < 1 pre všetky k = 2, …, n.

Pre k = 2, …, n nech u_k ∈ ℂ^1×n je ľavý vlastný vektor prislúchajúci λ_k (u_kP = λ_ku_k) a nech π ∈ ℝ^1×n je ľavý vlastný vektor prislúchajúci λ₁ = 1 so súčtom zložiek 1 — stacionárne rozdelenie (definícia nižšie). Potom pre každé počiatočné rozdelenie π₀ existujú čísla a₂, …, a_n ∈ ℂ také, že pre všetky t ∈ ℕ₀

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

Dôvod. Vlastné vektory prislúchajúce rôznym vlastným číslam tvoria bázu, takže π₀ = a₁π + ∑_k≥2 a_ku_k, a násobenie P^t vynásobí k-tu zložku λ_k^t. Pre k ≥ 2 má u_k súčet zložiek 0 (z u_kP1 = u_k1, kde 1 je stĺpec jednotiek, a λ_k ≠ 1), preto porovnanie súčtov dá a₁ = 1.

Odchýlka π_t − π teda klesá k nule rádovo ako |λ₂|^t, kde λ₂ je druhé najväčšie vlastné číslo v absolútnej hodnote.

Súčet vlastných čísel je stopa matice, 0,6 + 0,4 + 0,4 = 1,4, a ich súčin je determinant, ktorý vyjde 0,01. Jedno vlastné číslo je 1 (riadky majú súčet 1), takže zvyšné dve spĺňajú λ₂ + λ₃ = 0,4 a λ₂λ₃ = 0,01. Sú to korene λ² − 0,4λ + 0,01 = 0:

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

Odchýlka pravdepodobnosti slnečna od stacionárnej hodnoty 0,393 je pri slnečnom štarte po 3, 4, 5 dňoch 0,0286; 0,0107; 0,0040 — každý deň asi 0,373-krát menšia (farby podľa vzorca vyššie). Po týždni je 0,0006 a pri daždivom štarte −0,0005: oba začiatky sa líšia až na štvrtom desatinnom mieste. Na stotinu sa odchýlka zmenší za t dní, kde 0,373^t = 0,01, teda

t = ln 0,01/ln 0,373 ≈ 4,7 dňa.

Nech P = (p_ij) ∈ ℝ^n×n je prechodová matica homogénneho Markovovho reťazca s množinou stavov S = {1, …, n}. Riadkový vektor π = (π₁, …, π_n) ∈ ℝ^1×n je stacionárne rozdelenie reťazca práve vtedy, keď

1. π_j ≥ 0 pre každé j ∈ S a ∑_j=1ⁿ π_j = 1 (π je rozdelenie na S);
2. π P = π, t. j. π_j = ∑_i=1ⁿ π_i p_ij pre každé j ∈ S.

Podmienka 2 hovorí, že π je ľavý vlastný vektor matice P s vlastným číslom 1. Slovami: ak má X₀ rozdelenie π, má podľa vety o rozdelení po t krokoch rozdelenie π aj každé X_t — rozdelenie sa krokom reťazca nezmení.

Nech (X_t)_{t ≥ 0} je homogénny Markovov reťazec s konečnou množinou stavov S a prechodovou maticou P. Pre i, j ∈ S a m ∈ ℕ označme p_ij^(m) = (P^m)_ij pravdepodobnosť prechodu z i do j za m krokov.

1. Reťazec je nerozložiteľný (ireducibilný) práve vtedy, keď ∀ i, j ∈ S ∃ m ∈ ℕ : p_ij^(m) > 0.
2. Nech i ∈ S je stav, pre ktorý je množina R(i) = {m ∈ ℕ : p_ii^(m) > 0} neprázdna. Perióda stavu i je d(i) = NSD R(i), najväčší spoločný deliteľ dĺžok všetkých ciest, ktoré sa do i vracajú.
3. Stav i je neperiodický práve vtedy, keď d(i) = 1. Reťazec je neperiodický práve vtedy, keď sú neperiodické všetky jeho stavy.

V nerozložiteľnom reťazci majú všetky stavy rovnakú periódu, takže stačí overiť jeden stav.

Počasie je oboje hneď: všetky prvky P sú kladné (m = 1 stačí) a p_ii > 0, takže návrat je možný za 1 krok a perióda je 1. Naopak reťazec s dvoma stavmi, ktorý ich pravidelne strieda (p₁₂ = p₂₁ = 1), je nerozložiteľný, ale má periódu 2: π₀P^t pre štart (1; 0) donekonečna preskakuje medzi (1; 0) a (0; 1), hoci stacionárne rozdelenie (½; ½) existuje.

Nech (X_t)_{t ≥ 0} je homogénny Markovov reťazec s konečnou množinou stavov S = {1, …, n} a prechodovou maticou P, ktorý je nerozložiteľný a neperiodický. Potom

1. reťazec má práve jedno stacionárne rozdelenie π = (π₁, …, π_n) a π_j > 0 pre každé j ∈ S;
2. pre každé počiatočné rozdelenie π₀ platí lim_t→∞ π₀P^t = π (po zložkách);
3. pre každé počiatočné rozdelenie a každý stav j ∈ S platí s pravdepodobnosťou 1 lim_T→∞ |{t ∈ {0, …, T − 1} : X_t = j}|/T = π_j, t. j. podiel času stráveného v stave j sa blíži k π_j;
4. pre každý stav j ∈ S je stredná doba návratu do j m_j = E[min{t ≥ 1 : X_t = j} | X₀ = j] = 1/π_j.

Hľadáme π = (a; b; c) s πP = π. Po stĺpcoch matice:

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

Rovnice sú závislé (sčítaním všetkých troch dostaneme a + b + c = a + b + c), a tak prostrednú vynecháme. Z tretej a = 6c − 3b, dosadením do prvej 24c − 12b = 3b + 2c, teda b = 22c/15 a a = 6c − 66c/15 = 24c/15. Pomer je a : b : c = 24 : 22 : 15 a podmienka a + b + c = 1 dá

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

Priemerná doba návratu do dažďa je podľa ergodickej vety m_dážď = 1/π_dážď = 61/15 ≈ 4,07 dňa.

311 písmen dáva 310 susedných dvojíc. Samohláska–samohláska 6, samohláska–spoluhláska 111, spoluhláska–samohláska 111, spoluhláska–spoluhláska 82. Odtiaľ

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

p̂_spo→sam = 111/193 = 0,575,   p̂_spo→spo = 82/193 = 0,425

(farby podľa vzorca vyššie; 117 = 6 + 111 dvojíc začína samohláskou, 193 = 111 + 82 spoluhláskou).

Máj (farby podľa vzorca vyššie):

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

Presnejšie: prechodov samohláska→spoluhláska aj spoluhláska→samohláska je rovnako (111), takže

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

Skutočný podiel samohlások je 117/311 — líši sa len menovateľom, pretože posledné písmeno strofy („r“) žiadnu dvojicu nezačína.

Onegin: z Markovových čísel (samohláska po samohláske 12,8 %, teda samohláska→spoluhláska 87,2 %; samohláska po spoluhláske 66,3 %) vychádza

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

— presne 43,2 % samohlások, ktoré Markov napočítal priamo.

Nech N ≥ 1 je počet stránok, stránky sú očíslované 1, …, N a L ⊆ {1, …, N} × {1, …, N} je množina odkazov: (i, j) ∈ L práve vtedy, keď stránka i odkazuje na stránku j. Pre každú stránku i nech k_i = |{j : (i, j) ∈ L}| je počet jej odchádzajúcich odkazov a nech d ∈ (0, 1) je tlmiaci faktor (zvyčajne d = 0,85). Reťazec náhodného surfera je homogénny Markovov reťazec so stavmi {1, …, N} a prechodovou maticou P = (p_ij), kde

1. p_ij = 1 − d/N + d/k_i,   ak (i, j) ∈ L;
2. p_ij = 1 − d/N,   ak k_i ≥ 1 a (i, j) ∉ L;
3. p_ij = 1/N pre všetky j,   ak k_i = 0 (stránka bez odkazov — surfer skočí kamkoľvek).

Každý riadok má súčet k_i · d/k_i + N · 1 − d/N = 1 (resp. N · 1/N = 1), matica je teda stochastická. PageRank je stacionárne rozdelenie PR = (PR(1), …, PR(N)) tohto reťazca, t. j. PR · P = PR a ∑_j PR(j) = 1.

Slovami: surfer s pravdepodobnosťou d klikne na jeden z odkazov aktuálnej stránky (všetky rovnako pravdepodobne), inak skočí na ľubovoľnú z N stránok. Keďže všetky p_ij > 0, je reťazec nerozložiteľný a neperiodický a podľa ergodickej vety má PageRank jediný.

Pre N = 6 a d = 0,85 je 1 − d/N = 1 − 0,85/6 = 0,025. Do A vedie len odkaz z C, ktorá má jediný odkaz (k_C = 1); do B len z A, ktorá má dva (farby podľa vzorca vyššie):

• 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 mocninovej metódy rovnicu spĺňajú — tak sa spozná, že iterácia dobehla.

Text strofy prevedieme na malé písmená a interpunkciu nahradíme medzerou. Po písmene „l“ v ňom 31-krát nasleduje ďalší znak: 13-krát medzera, 7-krát „a“, 6-krát „á“, 2-krát „o“ a po jednom „i“, „h“, „u“. Podľa vzorca pre odhad je teda

P(medzera | 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

(farby podľa vzorca pre odhad p̂_ij v časti o Máji).

Generovanie potom robí to isté čo simulácia počasia: z riadku aktuálneho znaku vylosuje ďalší znak. Po „l“ je slovo najčastejšie na konci — „byl“, „lhal“, „kol“, „bol“.

Nech V je konečná neprázdna množina symbolov (slovník) a n ≥ 2 celé číslo. N-gramový model rádu n je súbor rozdelení pravdepodobnosti q(· | v) na V, jedno pre každý kontext v = (v₁, …, v_n−1) ∈ Vⁿ⁻¹. Postupnosť symbolov W₁, W₂, … s hodnotami vo V sa podľa modelu generuje tak, že pre každé t ≥ n a w ∈ V

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

t. j. ďalší symbol závisí len od n − 1 predchádzajúcich. Postupnosť Y_t = (W_t−n+2, …, W_t) ∈ Vⁿ⁻¹ (t ≥ n − 1) je potom homogénny Markovov reťazec s množinou stavov Vⁿ⁻¹: jeho stavom je posledných n − 1 symbolov. Pre n = 2 (bigramy) je stavom jediný symbol a q(w | v) je priamo prechodová pravdepodobnosť p_vw.

So slovníkom V symbolov má n-gramový model |V|ⁿ⁻¹ stavov a v každom riadku |V| pravdepodobností. Strofa Mája používa 32 rôznych znakov (písmená a medzera):

• bigramy (n = 2): 32 stavov, matica 32 × 32 = 1 024 čísel — viac, než má strofa znakov, takže väčšina z nich vyjde nulová;
• trigramy: 32² = 1 024 stavov a vyše 32 tisíc čísel — väčšinu dvojíc písmen strofa vôbec neobsahuje a ich riadky zostanú prázdne;
• jazykový model so slovníkom 50 000 tokenov a oknom 1 000 tokenov: 50 000^1 000 ≈ 10^4 699 stavov.

Preto dlhší kontext potrebuje buď obrovské dáta, alebo model, ktorý pravdepodobnosti nepočíta z tabuľky, ale odhaduje ich funkciou — neurónovou sieťou.