Bayesovské siete: prečo je tráva mokrá a čo z toho vyplýva pre postrekovač

Nech (Ω, 𝓕, P) je pravdepodobnostný priestor (pozri diel Čo je pravdepodobnosť), n ≥ 1 a X₁, …, X_n sú diskrétne náhodné premenné na ňom (pozri diel Náhodná premenná); premenná X_i nadobúda hodnoty z konečnej alebo spočítateľnej množiny 𝒳_i, i = 1, …, n. Združené rozdelenie premenných X₁, …, X_n je funkcia 𝒳₁ × ⋯ × 𝒳_n → [0, 1], ktorá každej kombinácii hodnôt (x₁, …, x_n) priradí číslo

P(x₁, …, x_n) = P({ω ∈ Ω : X₁(ω) = x₁ ∧ … ∧ X_n(ω) = x_n}),

písané aj P(x₁, …, x_n) = P(X₁ = x₁, …, X_n = x_n). Z axióm pravdepodobnosti vyplýva:

1. P(x₁, …, x_n) ≥ 0 pre všetky (x₁, …, x_n) ∈ 𝒳₁ × ⋯ × 𝒳_n;
2. ∑_{(x1, …, xn) ∈ 𝒳1 × ⋯ × 𝒳n} P(x₁, …, x_n) = 1.

Počet parametrov. Ak sú všetky premenné dvojhodnotové (|𝒳_i| = 2 pre i = 1, …, n, hodnoty áno/nie), má definičný obor 2ⁿ prvkov. Ľubovoľných 2ⁿ − 1 hodnôt možno zvoliť nezávisle (nezáporných, so súčtom najviac 1) a posledná je podmienkou 2 určená ako 1 mínus ich súčet. Združené rozdelenie n dvojhodnotových premenných má teda

2ⁿ − 1

nezávislých parametrov — toľko čísel treba, aby bolo určené jednoznačne.

Výpočet. 2⁴ − 1 = 15; 2³⁷ − 1 = 137 438 953 471.

Nech (Ω, 𝓕, P) je pravdepodobnostný priestor, n ≥ 2, X₁, …, X_n sú diskrétne náhodné premenné s hodnotami v 𝒳₁, …, 𝒳_n a (x₁, …, x_n) ∈ 𝒳₁ × ⋯ × 𝒳_n je kombinácia hodnôt, pre ktorú P(x₁, …, x_n−1) > 0. Zápisom P(x_i | x₁, …, x_i−1) rozumieme podmienenú pravdepodobnosť (pozri diel Podmienená pravdepodobnosť) javu {X_i = x_i} za podmienky {X₁ = x₁, …, X_i−1 = x_i−1}. Potom

P(x₁, …, x_n) = P(x₁) · P(x₂ | x₁) · P(x₃ | x₁, x₂) ⋯ P(x_n | x₁, …, x_n−1) = ∏_i=1ⁿ P(x_i | x₁, …, x_i−1),

kde činiteľ pre i = 1 je P(x₁) (prázdna podmienka).

Dôkaz: pre k ≤ n − 1 je jav {X₁ = x₁, …, X_k = x_k} nadmnožinou javu {X₁ = x₁, …, X_n−1 = x_n−1}, takže má kladnú pravdepodobnosť a všetky podmienené pravdepodobnosti vo vzorci sú definované. Z definície podmienenej pravdepodobnosti

P(x_n | x₁, …, x_n−1) = P(x₁, …, x_n)/P(x₁, …, x_n−1),

teda P(x₁, …, x_n) = P(x_n | x₁, …, x_n−1) · P(x₁, …, x_n−1). To isté použijeme na druhý činiteľ a tak ďalej, až zostane P(x₁). ∎

Reťazové pravidlo nič nešetrí: posledný činiteľ stále závisí od všetkých predchádzajúcich premenných, takže je to len iný zápis tej istej obrovskej tabuľky. Úspora príde, až keď niektoré podmienky vypustíme.

Nech n ≥ 1 a X₁, …, X_n sú premenné, X_i s hodnotami v konečnej neprázdnej množine 𝒳_i, i = 1, …, n. Bayesovská sieť nad týmito premennými je dvojica (G, Θ), kde

1. G = (V, H) je orientovaný acyklický graf (DAG, pozri diel Grafy a stromy) s množinou vrcholov V = {X₁, …, X_n} a množinou hrán H ⊆ V × V; rodičia vrcholu X_i sú rodičia(X_i) = {X_j ∈ V : (X_j, X_i) ∈ H};
2. Θ priraďuje každému vrcholu X_i tabuľku podmienených pravdepodobností: pre každú kombináciu hodnôt u jeho rodičov rozdelenie P( · | u) na 𝒳_i, t. j. čísla P(x_i | u) ≥ 0 pre x_i ∈ 𝒳_i také, že ∑_{xi ∈ 𝒳i} P(x_i | u) = 1. Vrchol bez rodičov má jediné rozdelenie P(x_i).

Sieť určuje združené rozdelenie premenných X₁, …, X_n predpisom

P(x₁, …, x_n) = ∏_i=1ⁿ P(x_i | rodičia(X_i))   pre všetky (x₁, …, x_n) ∈ 𝒳₁ × ⋯ × 𝒳_n,

kde v i-tom činiteli za rodičia(X_i) dosadzujeme hodnoty, ktoré majú rodičia v kombinácii (x₁, …, x_n). Súčin je nezáporný a cez všetky kombinácie dáva súčet 1 (ak sčítame najprv cez hodnoty vrcholu, ktorý je v topologickom poradí posledný, jeho činiteľ dá 1 a zostane sieť bez neho), takže je to naozaj združené rozdelenie.

Nech (Ω, 𝓕, P) je pravdepodobnostný priestor a A, C, E sú diskrétne náhodné premenné na ňom s hodnotami v 𝒜, 𝒞, ℰ (každá z nich môže byť aj skupina premenných, t. j. vektor; E smie byť prázdna skupina). Skrátene píšeme P(a | c, e) = P(A = a | C = c, E = e) a pod. Premenné A a C sú podmienene nezávislé pri E, píšeme A ⊥ C | E, práve vtedy, keď

∀a ∈ 𝒜 ∀c ∈ 𝒞 ∀e ∈ ℰ :   P(c, e) > 0 ⇒ P(a | c, e) = P(a | e).

Slovami: keď poznáme hodnotu E, znalosť hodnoty C nezmení pravdepodobnosť žiadnej hodnoty A. Rovnosť v definícii:

Nech G = (V, H) je orientovaný acyklický graf s vrcholmi V = {X₁, …, X_n}, ktoré sú diskrétne náhodné premenné na pravdepodobnostnom priestore (Ω, 𝓕, P), a vrcholy sú očíslované topologicky: (X_j, X_i) ∈ H ⇒ j < i. Potomkovia vrcholu X_i sú vrcholy rôzne od X_i, do ktorých z X_i vedie orientovaná cesta; nepotomkovia(X_i) = V ∖ ({X_i} ∪ potomkovia(X_i)). Predpokladajme miestnu Markovovu podmienku:

∀i ∈ {1, …, n} :   X_i ⊥ (nepotomkovia(X_i) ∖ rodičia(X_i)) | rodičia(X_i),

t. j. každá premenná je pri známych rodičoch podmienene nezávislá od všetkých ostatných premenných, ktoré nie sú jej potomkami. Potom pre každú kombináciu hodnôt (x₁, …, x_n) s P(x₁, …, x_n−1) > 0 platí

P(x₁, …, x_n) = ∏_i=1ⁿ P(x_i | rodičia(X_i)).

Dôkaz: v reťazovom pravidle v topologickom poradí stojí P(x_i | x₁, …, x_i−1). Medzi X₁, …, X_i−1 sú všetci rodičia X_i (rodič má menšie číslo) a žiadny jej potomok (potomok je v poradí až za ňou), teda {X₁, …, X_i−1} ⊆ nepotomkovia(X_i). Podľa Markovovej podmienky môžeme všetky premenné okrem rodičov z podmienky vypustiť a zostane P(x_i | rodičia(X_i)). ∎

Platí to aj naopak: každé rozdelenie dané súčinom tabuliek miestnu Markovovu podmienku spĺňa. Preto možno bayesovskú sieť definovať ktorýmkoľvek z oboch spôsobov.

Nech (G, Θ) je bayesovská sieť nad premennými X₁, …, X_n a tieto premenné sú rozdelené do troch disjunktných skupín: dotaz Q (jedna premenná s hodnotami v 𝒬), dôkazy E = (E₁, …, E_m) s pozorovanými hodnotami e = (e₁, …, e_m) a skryté premenné Y (všetky ostatné) s množinou kombinácií hodnôt 𝒴. Predpokladajme P(e) > 0. Potom pre každé q ∈ 𝒬 je

P(q | e) = ∑_{y ∈ 𝒴} P(q, e, y)/∑_{q′ ∈ 𝒬} ∑_{y ∈ 𝒴} P(q′, e, y),

kde každé P(q, e, y) je hodnota združeného rozdelenia siete — súčin čísel z tabuliek podľa faktorizácie. Odvodzovanie vymenovaním je algoritmus, ktorý podľa tohto vzorca počíta:

Vstup: sieť (G, Θ), dotazová premenná Q, dôkazy E = e s P(e) > 0. Výstup: čísla P(q | e) pre všetky q ∈ 𝒬. Kroky:

1. Pre každé q ∈ 𝒬 polož S(q) := 0.
2. Pre každé q ∈ 𝒬 a každé y ∈ 𝒴 vypočítaj súčin P(q, e, y) z tabuliek a pripočítaj ho k S(q).
3. Po prejdení všetkých (konečne mnohých) dvojíc (q, y) polož Z := ∑_{q′ ∈ 𝒬} S(q′) = P(e) a vráť P(q | e) = S(q)/Z pre každé q ∈ 𝒬.

Dôkaz je T = áno, dotaz D, skryté sú Z a P. Svetov s mokrou trávou je 2³ = 8; každý je súčin P(z) · P(p | z) · P(d | z) · P(t | p, d):

Riadky, kde pršalo, sú svety P(q, e, y) pre q = dážď áno; ich súčet cez skryté Z, P dá P(D, T) = 0,4581, súčet všetkých ôsmich P(T) = 0,6471. Posledné dva riadky sú nulové: bez dažďa aj bez postrekovača tráva mokrá nie je. Teda (farby podľa vzorca vyššie)

P(D | T) = 0,4581/0,6471 = 0,708.

Z tabuľky v predchádzajúcom príklade: svety, kde pršalo, bežal postrekovač a tráva je mokrá, majú dohromady P(P, D, T) = 0,0396 + 0,0495 = 0,0891. Preto

P(P | T, D) = P(P, D, T)/P(D, T) = 0,0891/0,4581 = 0,194,

P(D | T, P) = P(P, D, T)/P(P, T) = 0,0891/0,2781 = 0,320

(menovateľ je pravdepodobnosť dôkazov P(e), farby podľa vzorca odvodzovania vymenovaním vyššie).

Formálne je vysvetlenie preč nerovnosť P(P | T, D) < P(P | T): potvrdenie jednej príčiny zníži pravdepodobnosť druhej (0,194 < 0,430).

Nech G = (V, H) je orientovaný acyklický graf, A, C ∈ V sú rôzne vrcholy a E ⊆ V ∖ {A, C} je množina vrcholov (pozorované premenné).

1. Neorientovaná cesta medzi A a C je postupnosť navzájom rôznych vrcholov (V₀, V₁, …, V_k), k ≥ 1, s V₀ = A, V_k = C, taká, že (V_j−1, V_j) ∈ H ∨ (V_j, V_j−1) ∈ H   pre j = 1, …, k (susedné vrcholy spája hrana, smer šípky nehrá rolu).
2. Vnútorný vrchol V_j cesty (0 < j < k) je stredom reťaze práve vtedy, keď V_j−1 → V_j → V_j+1 alebo V_j−1 ← V_j ← V_j+1; vidlice práve vtedy, keď V_j−1 ← V_j → V_j+1; zrážky práve vtedy, keď V_j−1 → V_j ← V_j+1 (U → W znamená (U, W) ∈ H). Každý vnútorný vrchol je práve jedným z týchto troch.
3. Cesta je zablokovaná množinou E práve vtedy, keď má vnútorný vrchol V_j, pre ktorý platí aspoň jedno z: (a)  V_j je stredom reťaze alebo vidlice ∧ V_j ∈ E, (b)  V_j je stredom zrážky ∧ ({V_j} ∪ potomkovia(V_j)) ∩ E = ∅, kde potomkovia(V_j) sú vrcholy, do ktorých z V_j vedie orientovaná cesta.
4. Vrcholy A a C sú d-separované množinou E práve vtedy, keď je množinou E zablokovaná každá neorientovaná cesta medzi A a C.

Veta (Verma a Pearl). Nech (G, Θ) je bayesovská sieť, P združené rozdelenie, ktoré určuje, a A, C, E ako vyššie. Ak sú A a C d-separované množinou E, potom A ⊥ C | E vzhľadom na P — a to pre každú voľbu tabuliek Θ.

• Vidlica postrekovač ← zamračené → dážď. Bez znalosti oblohy: P(P | D) = 0,18 ≠ P(P) = 0,3, závislé. Pri známej oblohe: P(P | Z, D) = 0,1 = P(P | Z), teda P ⊥ D | Z.
• Zrážka postrekovač → mokrá tráva ← dážď. Pri známej oblohe sú P a D nezávislé (P(P | Z, D) = P(P | Z, ¬D) = 0,1), ale hneď ako pozorujeme trávu, už nie: P(P | Z, D, T) = 0,109, kým P(P | Z, ¬D, T) = 1.
• D-separácia zamračenej oblohy a mokrej trávy množinou {P, D}: obe cesty Z → P → T a Z → D → T sú reťaze so známym stredom, takže sú zablokované. A naozaj: P(Z | P, D) = 0,444 a P(Z | P, D, T) = 0,444; P(Z | P, ¬D) = 0,048 a P(Z | P, ¬D, T) = 0,048.

Oba algoritmy majú rovnaký vstup: bayesovskú sieť (G, Θ) nad premennými X₁, …, X_n očíslovanými topologicky (rodič má menšie číslo než dieťa), dotaz Q = q, dôkazy E = e a počet vzoriek N ∈ ℕ, N ≥ 1; a rovnaký výstup: odhad P̂(q | e) čísla P(q | e). Vylosovať x_i znamená zvoliť náhodne hodnotu z 𝒳_i podľa rozdelenia P( · | u) z tabuľky vrcholu X_i, kde u sú hodnoty jeho rodičov už určené v tejto vzorke.

Vzorkovanie so zamietaním:

1. Polož N_prij := 0, N_q := 0.
2. Opakuj N-krát: pre i = 1, …, n vylosuj x_i. Ak vzorka súhlasí s dôkazmi (každá dôkazová premenná má v nej pozorovanú hodnotu), zvýš N_prij o 1 a ak v nej navyše platí Q = q, zvýš o 1 aj N_q; inak vzorku zahoď.
3. Po N opakovaniach skonči a vráť P̂(q | e) = N_q/N_prij (pre N_prij = 0 odhad nie je definovaný).

Vážená vierohodnosť:

1. Polož W := 0, W_q := 0.
2. Opakuj N-krát (k-ta vzorka): polož w_k := 1 a pre i = 1, …, n: ak je X_i dôkazová premenná s pozorovanou hodnotou e_i, polož x_i := e_i (nelosuj) a w_k := w_k · P(e_i | u), kde u sú hodnoty rodičov vo vzorke; inak x_i vylosuj. Potom W := W + w_k a ak vo vzorke platí Q = q, aj W_q := W_q + w_k.
3. Po N opakovaniach skonči a vráť P̂(q | e) = W_q/W (pre W = 0 odhad nie je definovaný).

Jediný dôkaz je T = áno, jeho rodičia sú postrekovač a dážď. Váha vzorky je preto jednoducho P(T = áno | p, d) z tabuľky mokrej trávy:

• postrekovač aj dážď: w = 0,99,
• len jedno z nich: w = 0,9,
• ani jedno: w = 0 — taká vzorka neprispeje nikam, rovnako ako by ju zamietanie zahodilo.

(Farba podľa vzorca vyššie.)

Od oblohy váha nezávisí: zamračené nie je rodičom trávy.

Presne je p = 0,708 a P(e) = P(T) = 0,6471, takže z 10 000 vzoriek čakáme asi 6 471 prijatých (v skutočnosti ich bolo 6 524).

• N_prij = 70: σ = √0,708 · 0,292/70 = 0,054; skutočná chyba |0,686 − 0,708| = 0,022.
• N_prij = 6 524: σ = 0,0056; skutočná chyba 0,0050.

Obe skutočné chyby sú menšie než jedna smerodajná odchýlka — v súlade s tým, že asi dve tretiny odhadov padnú do ±σ (normálne rozdelenie podľa centrálnej limitnej vety).