Univerzita Karlova v PrazeMatematicko-fyzikální fakulta
DISERTAČNÍ PRÁCE
Petr Šimeček
Nezávislostní modely
Katedra pravděpodobnosti a matematické statistiky
Školitel: RNDr. Milan Studený, DrSc., ÚTIA AV ČRStudijní program: matematikaStudijní obor: pravděpodobnost a matematická statistika
2007
Děkuji svému školiteli, RNDr. Milanu Studenému, DrSc. za starostlivé ve-dení práce, konzultace a nezměrné množství času a energie, Ing. FrantiškuMatúšovi, CSc. a Mgr. Radimu Lněničkovi za podněty a připomínky, bezkterých by tato práce jen těžko vznikla, a kolegům z ÚTIA AV ČR a KPMSMFF UK za podporu a spolupráci.
Prohlašuji, že jsem svou disertační práci napsal samostatně a výhradně s po-užitím citovaných pramenů. Souhlasím se zapůjčováním práce.
V Praze dne 13. června 2007
Petr Šimeček
Obsah
Úvod 4
1 Základní pojmy 81.1 Podmíněná nezávislost . . . . . . . . . . . . . . . . . . . . . 81.2 Gaussovo, diskrétní a binární rozdělení . . . . . . . . . . . . 111.3 Nezávislostní modely . . . . . . . . . . . . . . . . . . . . . . 181.4 Charakterizace třídy nezávislostních modelů pomocí seznamu
zakázaných minorů . . . . . . . . . . . . . . . . . . . . . . . 21
2 Gaussovsky reprezentovatelné nezávislostní modely 242.1 Regulární Gaussovská reprezentovatelnost . . . . . . . . . . 262.2 Obecná Gaussovská reprezentovatelnost . . . . . . . . . . . . 282.3 Inferenční pravidla . . . . . . . . . . . . . . . . . . . . . . . 332.4 Neexistence konečné charakterizace . . . . . . . . . . . . . . 35
3 Diskrétně a binárně reprezentovatelné nezávislostní modely 413.1 Pozitivní binární reprezentovatelnost . . . . . . . . . . . . . 423.2 Obecná diskrétní reprezentovatelnost . . . . . . . . . . . . . 463.3 Pozitivní diskrétní reprezentovatelnost . . . . . . . . . . . . 493.4 Neexistence konečné charakterizace . . . . . . . . . . . . . . 53
4 Grafické nezávislostní modely 574.1 Teorie grafů . . . . . . . . . . . . . . . . . . . . . . . . . . . 604.2 Pravděpodobnostní rozdělení nad grafickými nezávislostními
modely . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 654.3 Hledání modelu . . . . . . . . . . . . . . . . . . . . . . . . . 71
Závěr 83
2
Název práce: Nezávislostní modelyAutor: Petr ŠimečekKatedra: Katedra pravděpodobnosti a matematické statistikyVedoucí práce: RNDr. Milan Studený, DrSc.Email vedoucího práce: [email protected]
Abstrakt:Důležitou součástí teorie rozhodování za neurčitosti je oblast gra-fických modelů, kde mnohorozměrné pravděpodobnostní rozdělení je přiřa-zeno k nezávislostní struktuře. Zajímavou otázkou pocházející od J. Pearla jeotázka reprezentovatelnosti takových struktur neboli pro jaké seznamy pod-míněných nezávislostí existuje rozdělení splňující tyto a pouze tyto nezávi-slosti. Tato práce shrnuje známé výsledky a dále je rozšiřuje v několika distri-bučních rámcích. Zaměříme se především na případ čtyř náhodných veličin,kdy zodpovíme otázku reprezentovatelnosti pro obecné Gaussovo rozdělení(zobecnění výsledku R. Lněničky) a nalezneme částečné řešení v případě dis-krétního a binárního rozdělení. Na závěr využijeme dosažené výsledky proodvození odhadu varianční matice v případě regulárního Gaussova rozdělení.Klíčová slova: podmíněná nezávislost, grafické a nezávislostní modely
Title: Independence modelsAuthor: Petr ŠimečekDepartment: Department of probability and mathematical statisticsSupervisor: RNDr. Milan Studený, DrSc.Supervisor‘ s email: [email protected]
Abstract: An essential part of probabilistic reasoning is the theory of gra-phical models endowing a multivariate probabilistic distribution with theindependence structure. An interesting question originally coming from J.Pearl is the problem of probabilistic representability, i.e. for which lists ofconditional independence constraints there exists a random vector satisfyingthese and only these independences. In this work the known results are collec-ted and the problem is further studied in several distributional frameworks.The focus is particularly on a special case of four random variables where thesolution is found for a general Gaussian distribution (extending the resultof R. Lněnička) and partially for discrete and binary distributions. At theend the achieved results are used to derive the variance matrix estimator ina case of regular Gaussian distribution.Key words: conditional independence, graphical and independence models
3
Úvod
„A k čemu je to vlastně dobré, to, co děláš?ÿ byl dotaz, který jsem opako-vaně slýchával od svých kolegů. Stručnou odpovědí na tuto otázku zároveňnastíníme, co bude tématem této práce.V aplikované statistice se často setkáváme s přístupem, že její „uživa-
teléÿ si vyberou svoji „oblíbenouÿ míru závislosti mezi dvěmi veličinami ak ní příslušný test (t–test, χ2–test v kontingenčních tabulkách m× n, . . . ),který následně bez rozmyslu používají. Taktéž často dochází k podceněníanalýzy, zda by nebylo vhodné při zkoumání uvedené závislosti zahrnoutdo studie další důležité faktory. Tento přístup „vezmi-dvě-veličiny-a-změř-závislostÿ však vede k absurdním výsledkům jako že nepřítomnost perskýchkoberců v bytě napomáhá častějším astmatickým záchvatům jeho obyvatel1,že nadměrná konzumace kávy snižuje u mužů středního věku krevní tlak2 čidokonce, že čápi skutečně nosí děti3.
Pomoci může kvalitní literatura zaměřená na metodiku výzkumu, viznapř. [Dis00], ale také popularizace a lepší pochopení konceptu tzv. „podmí-něné nezávislosti náhodných veličinÿ jakožto rozšíření „klasickéÿ nezávislostiznámé ze základních kurzů pravděpodobnosti o myšlenku, že dvě náhodnéveličiny se stanou nezávislými teprve, když dostaneme informaci o veličinětřetí. Na první pohled jednoduchá a intuitivně jasná idea má však řaduúskalí.Platí, že pokud jsou dvě náhodné veličiny ξa a ξb podmíněně nezávislé
dáno (ξc)c∈C (tzn. stanou se nezávislými, pokud již známe hodnotu souboruveličin (ξc)c∈C), potom jsou nutně ξa a ξb podmíněně nezávislé, i když pod-mínku změníme na (ξd)d∈D, kde D ⊇ C (ev. D ⊆ C)? Kdy nezávislostní
1Pochopitelně, neb kdo tento koberec v bytě má, těžko bude astmatik.2Bylo prezentováno jako součást [ŠZTJ04]. Kdo má vysoký krevní tlak, zpravidla nepije
kávu přesmíru nebo to alespoň nepřizná svému lékaři.3Čápi se vyskytují tam, kde je dobré životní prostředí, a tento faktor je taktéž korelován
s vysokou porodností.
4
tvrzení vyplývá z platnosti jiných nezávislostních tvrzení? Lze tato pravidlanějak jednoduše charakterizovat či axiomatizovat alespoň při omezeném po-čtu veličin? To bude typ otázek, na něž se budeme snažit v této práci naléztiodpověď.
Často pro jednoduchost předpokládáme, že se dá nezávislostní strukturamezi náhodnými veličinami zobrazit diagramem (grafem), v němž body (vr-choly grafu) odpovídají jednotlivým veličinám a čáry či šipky (orientovanéči neorientované hrany) přímým závislostem. Takovéto „diagramyÿ mají ne-oddiskutovatelnou výhodu a to, že jsou snadno pochopitelné i pro laika. Prodanou třídu modelů se vžil název „grafické modelyÿ.Grafické modely prošly od 70. let minulého století bouřlivým vývojem
a dnes mají uplatnění v řadě odlišných oblastí, jako jsou na jedné straněexpertní systémy (viz [CLDS99], program Hugin aj.) a systémy pro pod-poru rozhodování (seznam aplikací na konci [CGH96]) a na straně druhévýpočetní Bayesovská statistika (modul Doodle programu WinBUGS, balí-ček MCMCpack pro R aj.) a v návaznosti na ni rozpoznávání řeči, obrazu,analýza textu, aplikace v bioinformatice (pro přehled viz [Jor04]) a dobýváníznalostí z dat (viz [Cas02]).
Návod k použití
Po tomto spíše neformálním úvodu následují čtyři kapitoly. V první z nichzavedeme základní pojmy jako jsou podmíněná nezávislost, její kritéria v zá-vislosti na uvažovaném distribučním rámci, nezávislostní model (volně pře-loženo seznam nezávislostních vztahů), reprezentovatelnost nezávislostníchmodelů a (ne)existence její konečné charakterizace. Vyjma některých tech-nických záležitostí jako je zobecnění kritéria podmíněné nezávislosti na obec-né, ne nutně regulární Gaussovo rozdělení (Lemma 5) a netradiční parametri-zace binárního rozdělení a z ní odvozená kritéria pro podmíněnou nezávislosttato část neobsahuje originální výsledky.V druhé kapitole se soustředíme na Gaussovskou reprezentovatelnost ne-
závislostních modelů nad čtyřmi veličinami neboli rozšíříme výsledek R. Lně-ničky pro regulární Gaussovskou reprezentovatelnost [Lně05] na obecný pří-pad (publikováno v [Šim06b]). Na závěr za pomoci analogické myšlenkyjako v [Stu92] dokážeme, že ani Gaussovskou reprezentovatelnost nelze ko-nečně charakterizovat ve smyslu seznamu zakázaných minorů (publikovánov [Šim06a]).
5
Třetí kapitola je zaměřena na diskrétní reprezentovatelnost nezávislost-ních modelů nad čtyřmi veličinami. Jsou zde shrnuty známé výsledky F.Matúše a M. Studeného (viz [Mat97] a [SB94]) a opraven rozšířený omylo počtu takto reprezentovatelných modelů (publikováno v [Šim06d]). Dáleje diskutována otázka, které z výše zmíněných diskrétně reprezentovatel-ných modelů jsou i pozitivně reprezentovatelné. Pro čtyři veličiny je určenahorní a dolní mez, vyslovena hypotéza, že horní mez je skutečným počtemtěchto modelů, a určeno 12 modelů, o jejichž reprezentovatelnosti je třebarozhodnout, aby hypotéza byla dokázána či vyvrácena.Ve čtvrté kapitole se snažíme propojit tyto výsledky s teorií grafických
modelů. Jsou připomenuty základní pojmy z teorie grafů, odpovídajících ne-závislostních modelů a pravděpodobnostních rozdělení. Pro nově příchozíhodo oboru může být užitečné zkusit si jako cvičení dokončit části důkazů, ježjsou označeny jako snadné. Následně testujeme schopnost určit na základědat model a identifikovat jeho parametry (část publikována v [Šim06c]).Práci zakončuje simulační studie na případu Gaussova rozdělení nad čtyřmiveličinami: Je ukázáno, že při malém počtu pozorování je identifikace sku-tečného modelu nepravděpodobná. Studován je též odhad varianční matice,kdy chování odhadů založených pouze na grafických modelech je shledánoneuspokojivým, pokud skutečné rozdělení grafickému modelu neodpovídá.Odhady založené na nezávislostních modelech se ve všech případech pocho-pitelně chovají lépe.Veškeré seznamy nezávislostních modelů, jakožto i procedury pro mani-
pulaci s nimi a R–balíček pro výše zmíněné odhady lze nalézt na přiloženémCD.
Protože obtížnost jednotlivých částí textu je poměrně různorodá a lzepředpokládat, že vhled čtenářů do dané problematiky se bude dramatickylišit a jen málokterý z nich bude mít zájem postupovat od začátku do konce,sepsal jsem (zcela nezávazný) seznam doporučení, jak tuto práci číst. Sche-maticky je tento „návod k použitíÿ znázorněn na obr. 1.Začátečníkem je myšlen nově příchozí do této oblasti, který se snaží v
rychlosti posbírat potřebné kvantum informací o podmíněné nezávislosti agrafických modelech.Pokročilý uživatel tohoto textu je již s teorií grafických modelů dobře
obeznámen a zajímají jej toliko podrobnosti okolo nezávislostních modelů ajejich reprezentovatelnosti. A pro několik „expertůÿ, jež hledají pouze novéa originální výsledky, je určena poslední kategorie.
6
Obrázek 1: Jak číst tuto práci.
7
Kapitola 1
Základní pojmy
V této kapitole uvedeme základní definice, tvrzení a pojmy, s kterými sebudeme ve zbytku práce setkávat a na které budeme odkazovat. Čtenář ma-jící základní znalosti o pravděpodobnosti a podmíněné nezávislosti ji můžepřeskočit, případně se omezit na oddíly 1.3 a 1.4.
Předmětem našeho studia bude náhodný vektor neboli soubor náhod-ných veličin ξ = (ξa)a∈N indexovaný (konečnou) množinou N = {1,2,. . . , n}a nabývající hodnot z R
n. Sdružené rozdělení tohoto vektoru budeme značitpísmenem P . Pokud má toto rozdělení hustotu vůči pevně zvolené souči-nové σ−konečné míře µ, budeme ji značit f(x). Pro podmnožinu indexovémnožiny A ⊆ N definujeme podvektor ξA jako ξA = (ξa)a∈A za konvenceξ∅ = 0 (konstanta). Analogicky budeme chápat marginální rozdělení PA,jeho hustotu fA a podvektor hodnot xA.Náhodné veličiny a vektory budeme označovat písmeny řecké abecedy,
množiny (vyjmaN) velkými písmeny ze začátku abecedy, jejich prvky písme-ny malými. Vektory a matice budeme tisknout tučným písmem. Determi-nant čtvercové matice Σ budeme značit |Σ|, její hodnost dim(Σ), inverzi azobecněnou inverzi po řadě Σ−1 a Σ−.V případě, že nebude hrozit nebezpečí omylu, budeme pro zjednodušení
značení a větší čitelnost vynechávat znaménko sjednocení, tedy ξAB ≡ ξA∪B,a složené závorky kolem jednoprvkových množin, tedy ξAb ≡ ξA∪{b}.
1.1 Podmíněná nezávislost
Existuje mnoho způsobů jak zavést pojem podmíněné nezávislosti, od intui-tivních, úzce vymezených, viz [Nea03], až po matematicky rigorózní a značně
8
obecné, viz [Stu05].My se v této práci omezíme na případ rozdělení s hustotou f vůči σ−ko-
nečné součinové míře µ, kde navíc je buďto µ Lebesgueova a f spojitá neboµ diskrétní. Veškerá níže uvedená tvrzení o hustotě f je třeba chápat vesmyslu µ−skoro všude.
Definice 1. Řekneme, že pro náhodný vektor ξ = (ξa)a∈N a po dvou dis-junktní podmnožiny A,B,C ⊆ N je podvektor ξA podmíněně nezávislýna ξB dáno ξC (značíme ξA⊥⊥ξB|ξC) právě tehdy, když
fABC(xABC) · fC(xC) = fAC(xAC) · fBC(xBC). (1.1)
Pokud C = ∅, je podle příslušné konvence f∅ ≡ 1 a v tomto případě sejedná o (klasickou) nepodmíněnou nezávislost (značíme ξA⊥⊥ξB).Smysl formální definice ξA⊥⊥ξB|ξC je podobný jako u nepodmíněné ne-
závislosti: Jestliže již známe hodnotu ξC , potom je hodnota ξA irelevantní(nepodstatná, neužitečná pro predikci, neovlivňující podmíněné rozdělení,apod.) pro hodnotu ξB a naopak.
Lemma 1 uvádí několik dalších způsobů zavedení pojmu podmíněné ne-závislosti ekvivalentních s (1.1), viz [Lau96], str. 29. Podmíněnou hustotoufA|B(xA|xB) zde budeme značit funkci fAB(xAB)/fB(xB), definovanou po-kud fB(xB) > 0, jinak necháváme nedefinováno. Příslušným rovnostem jetřeba rozumět tak, že platí na množině, kde jsou podmíněné hustoty defino-vány.
Lemma 1. Nechť A,B a C jsou po dvou disjunktní podmnožiny N . Potomnásledující tvrzení jsou ekvivalentní:
i) ξA⊥⊥ξB|ξC
ii) fAB|C(xAB|xC) = fA|C(xA|xC) · fB|C(xB|xC)
iii) fA|BC(xA|xBC) = fA|C(xA|xC)
iv) fAC|B(xAC |xB) = fA|C(xA|xC) · fC|B(xC |xB)
v) fABC(xABC) = fA|C(xA|xC) · fBC(xBC)
vi) ∃g, h funkce : fABC(xABC) = g(xAC) · h(xBC)
9
Pokud má rozdělení navíc konečnoumultiinformaci (MI), tj. Kullback–Leiblerovu divergenci (≡relativní entropii) sdruženého rozdělení vůči součinujednorozměrných marginál (viz [Stu05], str. 35), lze charakterizovat nezávis-lostní vztahy za pomoci následujícího lemmatu.
Lemma 2. Nechť ξ je vektor s konečnou multiinformací a A,B,C jsou podvou disjunktní podmnožiny N . Potom platí
MI(ξABC) +MI(ξC)−MI(ξAC)−MI(ξBC) ≥ 0,
a navíc(MI(ξABC) +MI(ξC)−MI(ξAC)−MI(ξBC) = 0
)⇐⇒
(ξA⊥⊥ξB|ξC
).
Důkaz. Důkaz lze nalézt v [Stu05], str. 27–28.
Za pomoci podmiňování (viz např. [Lac04]) lze podmíněnou nezávislostmezi ξA a ξB dáno ξC definovat „v širším smysluÿ jako platnost tvrzení, žerozdělení ξAB|ξC je součinem příslušných podmíněných rozdělení, neboli
L(ξAB|ξC = xC) = L(ξA|ξC = xC)⊗ L(ξB|ξC = xC) PC−s.v. (1.2)
Snadno se nahlédne, že (1.2) implikuje (1.1). Definici podmíněné nezávislostiv širším smyslu využijeme jen v případě neregulárního Gaussova rozdělení.
Jak ukazuje následující lemma, podmíněnou nezávislost je možné charak-terizovat pomocí souboru elementárních nezávislostních vztahů, tj. souborupodmíněných nezávislostí (ξAi
⊥⊥ξBi|ξCi)i takových, že |Ai| = |Bi| = 1.
Lemma 3. Pro A,B,C po dvou disjunktní podmnožiny N platí
(ξA⊥⊥ξB|ξC)⇔ (∀a ∈ A, b ∈ B,D ⊆ ABC \ {a, b} : C ⊆ D ⇒ ξa⊥⊥ξb|ξD) .
Důkaz. Viz [Mat92], lemma 3.
Další vlastnosti podmíněné nezávislosti budou odvozeny v oddílu 1.3.
10
1.2 Gaussovo, diskrétní a binární rozdělení
V tomto oddílu zavedeme tři základní typy rozdělení, se kterými se budemev této práci setkávat: Gaussovo, diskrétní a binární.
1.2.1 Gaussovo rozdělení
Definice 2. Gaussovo rozdělení náhodného vektoru ξ = (ξ1, . . . , ξn) jepravděpodobnostní rozdělení dané svou charakteristickou funkcí
ϕξ(t) ≡ E exp(it′ξ) = exp(
it′µ−t′Σt
2
),
které je parametrizované střední hodnotou µ ∈ Rn a varianční (symetrickou,
pozitivně semidefinitní) maticí Σ.
Jestliže je matice Σ pozitivně definitní (≡regulární), značíme Σ > 0,budeme hovořit o regulárním Gaussově rozdělení. Regulární Gaussovorozdělení má spojitou verzi hustoty vůči Lebesgueově míře tvaru
f(x) =1
(2π)n2 |Σ|
1
2
exp(−12(x− µ)′Σ−1(x− µ)
)
a konečnou multiinformaci
MI(ξ) = −12
(log(|Σ|)−
n∑
a=1
log σa·a
).
Naopak neregulární Gaussovo rozdělení nemá hustotu vůči Lebesgueověmíře a obecně ani konečnou multiinformaci. Takovéto rozdělení je degenero-vané ve smyslu, že existuje nenulový vektor konstant a takový, že
a′(ξ − µ) = 0 (s.j.), (1.3)
viz [And78], str. 71. Tedy oborem hodnot ξ je vlastní afinní podprostor Rn.
Pro matici Σ = (σa·b)a,b∈N a A,B neprázdné podmnožiny N definujemematiciΣA·B jako matici, do níž byly zeΣ vybrány pouze řádky příslušné prv-kům A a sloupce příslušné prvkům B při zachování pořadí řádků a sloupců,neboli
ΣA·B = (σa·b)a∈A, b∈B.
11
Jak ukazuje následující lemma, třída Gaussových rozdělení je uzavřenána operace marginalizace a podmiňování.
Lemma 4. Nechť ξ je náhodný vektor s Gaussovým rozdělením, Σ příslušnávarianční matice, A,B disjunktní podmnožiny N :
i) Marginální rozdělení ξA je Gauss. rozdělení s varianční maticí ΣA·A.
ii) Podmíněné rozdělení ξA dáno ξB = xB je Gaussovo rozdělení s vari-anční maticí ΣA·A|B = ΣA·A −ΣA·BΣ
−B·BΣB·A, kde Σ
−B·B je libovolná
zobecněná inverze ΣB·B.
iii) Navíc, pokud je Σ regulární, potom jsou regulární i ΣA·A a ΣA·A|B.
Důkaz. Pro i) a ii) viz [Lau96], str. 256. Z předpokladu regularity Σ přímoplyne regularita ΣA·A a ΣB·B.Aplikujeme-li na matici Σ Choleského rozklad (předpokládá existenci
U−1)(
R ST U
)=(
I SU−1
0 I
)(R− SU−1T 0
0 U
)(I 0
U−1T I
)(1.4)
dosazením R = ΣA·A, U = ΣB·B a S = T ′ = ΣA·B, získáme na levé straně(1.4) regulární matici Σ a tudíž musí být regulární i všechny matice součinuna pravé straně (1.4). Tedy je regulární i ΣA·A|B = R− SU−1T .
Povšimněme si, že varianční matice podmíněného rozdělení ΣA·A|B zůs-tává stejná bez ohledu na to, jakou hodnotou xB z oboru hodnot ξB pod-míníme. To je důležitá speciální vlastnost Gaussova rozdělení, která neplatív případě dalších rozdělení.
Lemma 5. Nechť ξ je náhodný vektor s Gaussovým rozdělením, Σ příslušnávarianční matice, A,B a C po dvou disjunktní podmnožiny N :
i) (ξA⊥⊥ξC)⇔ (ΣA·C = 0).
ii) Pro ΣB·B > 0, (ξA⊥⊥ξC |ξB)⇔ (∀a ∈ A, c ∈ C : |ΣaB·cB| = 0).
iii) Pro D ⊂ B takovou, že ΣD·D > 0 a dim(ΣD·D) = dim(ΣB·B), platí(ξA⊥⊥ξC |ξB)⇔ (ξA⊥⊥ξC |ξD).
12
Důkaz. První část je dobře známý fakt, viz [Lau96], str. 257. Pokud a ∈A, c ∈ C a vyjádříme-li determinant ΣaB·cB za dosazení do Choleského roz-kladu (1.4) R = Σa·c, U = ΣB·B, S = Σa·B a S = ΣB·c, zjistíme, že pro|ΣB·B| 6= 0 platí
|ΣaB·cB| = 0 ⇔ σa·c−Σa·BΣ−1B·BΣB·c = 0 ⇔ (Σac·ac|B)a·c = 0 ⇔ ξa⊥⊥ξc|ξB,
přičemž poslední ekvivalence vyplývá z výše zmíněné neměnnosti variančnímatice Σac·ac|B vzhledem k podmínění libovolnou hodnotou ξB.Dále již stačí použít část i) tohoto lemmatu, abychom si uvědomili, že
(∀a ∈ A, c ∈ C : ξa⊥⊥ξc|ξB
)⇐⇒ ξA⊥⊥ξC |ξB.
Platnost části iii) snadno nahlédneme za pomoci lemmatu 4, pokud siuvědomíme, že jeden ze způsobů konstrukce zobecněné inverze Σ−
B·B je na-leznout výše popsanou ΣD·D plné hodnosti, invertovat ji a na zbylá místadoplnit nuly, viz [Rao73], oddíl 1b.5. Neboli při vhodném uspořádání prvkůN ,
Σ−B·B =
(Σ−1
D·D 00 0
).
Tudíž, Σa·BΣ−B·BΣB·c = Σa·DΣ
−1D·DΣD·c a požadované tvrzení dostáváme
jako důsledek charakterizace podmíněného rozdělení v lemmatu 4 ii).
1.2.2 Diskrétní rozdělení
Definice 3. Rozdělení náhodného vektoru ξ = (ξ1, . . . , ξn) nazveme dis-krétní, pokud existuje konečná množina taková, že vektor nabývá hodnotmimo tuto množinu s nulovou pravděpodobností (neboli rozdělení mající hus-totu vůči nějaké diskrétní míře).
Analogicky lze zavést diskrétní rozdělení definováním jeho hustoty nebolifunkce p ze součinu konečných množin X =
∏n
a=1Xa do intervalu [0, 1]takové, že ∑
x∈X
p(x) = 1.
Pokud pro všechna x ∈X je p(x) > 0, řekneme, že dané diskrétní rozděleníje kladné.Definici podmíněné nezávislosti ξA⊥⊥ξB|ξC můžeme v případě diskrétně
rozděleného vektoru přepsat jako platnost vztahu
P (ξABC = xABC)P (ξC = xC) = P (ξAC = xAC)P (ξBC = xBC) (1.5)
13
pro všechna příslušná xABC . Obdobně lze pro tento případ přeformulovat ivšechna ekvivalentní tvrzení z lemmatu 1.Multiinformace diskrétně rozděleného vektoru ξ = (ξ1, . . . , ξn) je z defi-
nice rovna ∑
xN∈X
P (ξN = xN) log(
P (ξN = xN)∏n
a=1 P (ξa = xa)
)
za konvence 0 · log 0 = 0 a je vždy konečná.
1.2.3 Binární rozdělení
Speciálním typem diskrétního rozdělení je rozdělení binární.
Definice 4. Rozdělení náhodného vektoru ξ = (ξ1, . . . , ξn) nazveme bi-nární, pokud pro všechna a = 1, . . . , n existuje pro ξa dvouprvková množinataková, že hodnot mimo tuto množinu nabývá ξa s nulovou pravděpodobností.
Bez újmy na obecnosti budeme dále předpokládat, že ony dvě hodnoty,jichž každá z binárních veličin nabývá, jsou−1 a 1. Tato úmluva nám umožnívhodným způsobem binární rozdělení parametrizovat.Podmínku (1.5) pro nezávislostní vztah ξa⊥⊥ξb|ξC lze v případě binárního
rozdělení upravit na tvar
P (ξa = 1, ξb = 1, ξC = xC)P (ξa = −1, ξb = −1, ξC = xC) =P (ξa = 1, ξb = −1, ξC = xC)P (ξa = −1, ξb = 1, ξC = xC),
(1.6)
pro všechna xC ∈ {−1, 1}C .
Třídu binárních rozdělení budeme parametrizovat pomocí momentů. Propodmnožinu indexové množiny A ⊆ N zaveďme značení
eA = E∏
a∈A
ξa =∑
xN∈{−1,1}N
P (ξN = xN)∏
a∈A
xa, (1.7)
přičemž pro A = ∅ položíme∏
a∈A xa = 1, tudíž nutně e∅ = 1.
Lemma 6. Nechť (eA)A⊆N je daný soubor čísel z intervalu [−1, 1] indexo-vaný podmnožinami množiny N takový, že e∅ = 1. Jestliže
∀xN ∈ {−1, 1}N : p(xN) :=(12
)|N | ∑
A⊆N
(∏
a∈A
xa
)eA ≥ 0, (1.8)
potom existuje právě jedno binární rozdělení s momenty (eA)A⊆N a platí
P (ξN = xN) = p(xN).
14
Důkaz. Předpokládejme, že nějaké binární rozdělení s danými momenty exis-tuje, a uvažme jedno pevné x∗
N . Potom přes všechna A ⊆ N sečtěme 2|N |
rovnic daných vztahem (1.7) a pronásobených navíc součinem∏
a∈A x∗a. Na
levé straně součtu rovnic dostáváme 2|N |p(x∗N), zatímco na pravé straně
∑
xN∈{−1,1}N
P (ξN = xN)
(∑
A⊆N
∏
a∈A
xax∗a
)= P (ξN = x∗
N)2|N |,
přičemž jsme využili, že pro x 6= x∗ je∑
A⊆N
∏a∈A xax
∗a = 0.
Zbývá ukázat, že rozdělení splňující (1.8) bude mít skutečně požadovanémomenty. Uvažme libovolnou podmnožinu indexové množiny B ⊆ N , potom
E∏
b∈B
ξb =(12
)|B| ∑
xB∈{−1,1}B
∑
A⊆B
eA
(∏
b∈B
xb
)(∏
a∈A
xa
)= eB,
kde jsme využili prohození sum a fakt, že pro A vlastní podmnožinu B platí
∑
xB∈{−1,1}B
(∏
b∈B
xb
)(∏
a∈A
xa
)= 0.
Kupříkladu pro dvě náhodné veličiny, neboli N = {1, 2}, dostáváme
P (ξ1 = 1, ξ2 = 1) = 1+e1+e2+e124
, P (ξ1 = −1, ξ2 = −1) = 1−e1−e2+e124
,P (ξ1 = 1, ξ2 = −1) = 1+e1−e2−e12
4, P (ξ1 = −1, ξ2 = 1) = 1−e1+e2−e12
4,
přičemž, jak lze snadno nahlédnout, je podmínka existence (1.8) ekvivalentnís podmínkou
1− |e1 − e2| ≥ e12 ≥ −1 + |e1 + e2|.
Bohužel pro |N | > 2 takovýto elegantní způsob ověření podmínky (1.8) neníznám.Dále si povšimněme, že pokud pro všechny neprázdné A ⊆ N jsou eA
blízko nuly, potom je podmínka (1.8) vždy splněna. Pokud jsou všechnymomenty eA rovny nule, jedná se o rovnoměrné rozdělení.Ukažme si, jak při parametrizaci pomocí momentů vypadá charakterizace
podmíněné nezávislosti.
15
Lemma 7. Nechť ξ = (ξ1, . . . , ξn) je binární náhodný vektor a (eA)A⊆N
příslušný soubor jeho momentů. Potom platí, že ξa⊥⊥ξb|ξC právě tehdy, kdyžpro všechna xC ∈ {−1, 1}C
(∑
D⊆C
eabD
∏
d∈D
xd
)·
(∑
D⊆C
eD
∏
d∈D
xd
)=
(∑
D⊆C
eaD
∏
d∈D
xd
)·
(∑
D⊆C
ebD
∏
d∈D
xd
).
Důkaz. Pro marginální rozdělení ξabC dosadíme za pravděpodobnosti z (1.6)za pomoci vztahu (1.8)(∑
D⊆C
(eD + eaD + ebD + eabD)∏
d∈D
xd
)·
(∑
D⊆C
(eD − eaD − ebD + eabD)∏
d∈D
xd
)=
(∑
D⊆C
(eD − eaD + ebD − eabD)∏
d∈D
xd
)·
(∑
D⊆C
(eD + eaD − ebD − eabD)∏
d∈D
xd
)
Zbývá již jen drobná technická úprava a to každou z řad rozdělit na čtyři řadyR∅, Ra, Rb, Rab rozsekáním součtu momentů v závorkách na jednotlivé členy,schematicky dostaneme (R∅+Ra+Rb+Rab) · (R∅−Ra−Rb+Rab) = (R∅−Ra+Rb−Rab) · (R∅+Ra−Rb−Rab) a odtud odečtením členů vyskytujícíchse na obou stranách získáme požadovanou rovnost R∅ ·Rab = Ra ·Rb.
Důkaz lemmatu 7 demonstruje výhodu parametrizace pomocí momentů,kterou je snadný přechod k marginálnímu rozdělení. Bez důkazu zmiňmei možnost (přirozené) konstrukce nestranných, nekorelovaných odhadů jed-notlivých parametrů (momentů).
Rozepišme si ještě vztah pro podmíněnou nezávislost ξa⊥⊥ξb|ξC z lem-matu 7 pro |C| = 0, 1, 2:
• ξa⊥⊥ξb ⇐⇒ eab = eaeb
• ξa⊥⊥ξb|ξc ⇐⇒eabc + eabec = eaebc + ebeac
eab + eabcec = eacebc + eaeb
• ξa⊥⊥ξb|ξcd ⇐⇒eabcd + eabced + eabdec + eabecd = eaebcd + ebeacd + eacebd + eadebc
eabc + eabdecd + eabec + edeabcd = eadebcd + ebdeacd + eaebc + ebeac
eabd + eabcecd + eabed + eceabcd = eacebcd + ebceacd + eaebd + ebead
eab + eceabc + edeabd + ecdeabcd = eaeb + eacebc + eadebd + eacdebcd
16
Pokud místo obyčejných momentů použijeme parametrizaci centrova-nými momenty
fA = E∏
a∈A
(ξa − ea),
dostaneme po dosazení
eab = fab + eaeb
eabc = fabc + eafbc + ebfac + ecfab + eaebec
a následné úpravě
• ξa⊥⊥ξb ⇐⇒ fab = 0
• ξa⊥⊥ξb|ξc ⇐⇒(1− e2c)fab = facfbc
fabc = −2ecfab
Obdobně lze dosadit
eabcd = fabcd +∑
i∈{a,b,c,d}
(eifabcd\i) +12
∑
i,j∈{a,b,c,d}, i6=j
(eiejfabcd\ij) + eaebeced
do výše uvedených rovnic pro ξa⊥⊥ξb|ξcd, avšak výsledná soustava rovnic jesložitější než ta pro necentrované momenty.Pokud navíc platí, že ea = eb = ec = ed = 0, jsou centrované a necentro-
vané momenty totožné a výše uvedené se zjednoduší vztahy na
• ξa⊥⊥ξb ⇐⇒ eab = 0
• ξa⊥⊥ξb|ξc ⇐⇒eabc = 0eab = eacebc
• ξa⊥⊥ξb|ξcd ⇐⇒eabcd + eabecd = eacebd + eadebc
eabc + eabdecd = eadebcd + ebdeacd
eabd + eabcecd = eacebcd + ebceacd
eab + ecdeabcd = eacebc + eadebd + eacdebcd
Na závěr si povšimněme zajímavého faktu, že v případě |N | = 4 při volbě∀a, b, c ∈ N : ea = 0, eabc = 0 a případně eabcd = eacebd + eadebc − eabecd
dostáváme rovnice pro eab charakterizující podmíněnou nezávislost totožnés rovnicemi pro koeficienty korelační matice σa·b u regulárního Gaussovarozdělení odvozených dle lemmatu 5.Zajímavá by mohla být též parametrizace za pomoci Möbiovy transfor-
mace necentrovaných momentů, to jest gD =∑
A⊆D(−1)|D\A|eA pro D ⊆ N .
17
1.3 Nezávislostní modely
V tomto oddílu bude zaveden formální „nezávislostní modelÿ. Je třeba při-znat, že tento termín není ustálený a v literatuře se ve stejném nebo po-dobném významu setkáme se „strukturou podmíněné nezávislostiÿ, [Stu97],„objektem podmíněné nezávislostiÿ, [Jir03], případně „seznamem podmíně-ných nezávislostíÿ, [CGH96]. Značení zde je inspirováno pracemi [RS02] a[Mat97].
Definice 5. Množinou tripletů TN nad konečnou množinou N budeme rozu-mět množinu všech dvojic 〈ab|C〉 takových, že ab je (neuspořádaná) dvojicedvou různých prvků z N a C je podmnožinou N \ ab.
Jednotlivé triplety odpovídají elementárním nezávislostním vztahům, takjak byly zavedeny na konci oddílu 1.1.
Definice 6. Nezávislostním modelem nad konečnou množinou N jemyšlena libovolná podmnožina množiny TN . Nezávislostní model I(ξ) odpo-vídající rozdělení náhodného vektoru ξ = (ξ1, ξ2, . . . , ξn) je nezávislostnímodel nad N = {1, . . . , n} definovaný následovně
I(ξ) = {〈ab|C〉; ξa⊥⊥ξb|ξC} .
Zdůrazněme, že nezávislostní model I(ξ) určuje podle lemmatu 3 jedno-značně i všechny ostatní podmíněné nezávislosti mezi podvektory ξ.
Definice 7. Pokud pro nezávislostní model I existuje náhodný vektor ξ
i) s Gaussovým rozdělením
ii) s diskrétním rozdělením
iii) s binárním rozdělením
takový, že I = I(ξ), budeme I nazývat
i) Gaussovsky reprezentovatelný (g–reprezentovatelný)
ii) diskrétně reprezentovatelný (d–reprezentovatelný)
iii) binárně reprezentovatelný (b–reprezentovatelný)
a ξ, respektive jeho rozdělení, budeme nazývat reprezentací tohoto modelu.
18
Pokud budeme navíc chtít zdůraznit, že nás zajímají pouze regulární,resp. kladné reprezentace, budeme hovořit o pozitivní reprezentovatelnostia nad příslušnou zkratku umístíme znaménko „+ÿ (g+–reprezentovatelnost,d+–reprezentovatelnost, b+–reprezentovatelnost).Pokud použijeme pojem „reprezentovatelnéÿ bez přívlastku, budeme mít
na mysli obecnou pravděpodobnostní reprezentovatelnost (pro účely tétopráce je možné tento pojem chápat omezeně jako reprezentovatelnost jednímz výše uvedených způsobů).
Lemma 8. Nechť a, b, c jsou různé prvky N a D je podmnožinou N \ abc.Pro reprezentovatelný model I platí
({〈ab|cD〉, 〈ac|D〉} ⊆ I
)⇔({〈ac|bD〉, 〈ab|D〉} ⊆ I
). (1.9)
Pokud je model navíc pozitivně reprezentovatelný, potom({〈ab|cD〉, 〈ac|bD〉} ⊆ I
)⇒({〈ab|D〉, 〈ac|D〉} ⊆ I
). (1.10)
Důkaz. Jedná se o tzv. „semigrafoidovouÿ, resp. „grafoidovouÿ vlastnost, viz[Lau96] nebo podrobněji [Stu05].
Popsání nezávislostního modelu výčtem tripletů je špatně uchopitelné anepříliš názorné. Pro |N | ≤ 4 můžeme použít grafické znázornění nezávis-lostního modelu „diagramyÿ navrženými R. Lněničkou.Každému prvku N přiřadíme jeden bod. Jestliže I obsahuje 〈ab|∅〉, spo-
jíme body odpovídající a a b čarou. Pokud je mezi prvky I triplet 〈ab|c〉,spojíme a a b čarou a doprostřed přilepíme „zobáčekÿ směřující k c. JestližeI obsahuje jak 〈ab|c〉, tak 〈ab|d〉, nakreslíme obě čáry přes sebe a připojíme„dvojzobáčekÿ ukazující k c i d. A konečně pokud 〈ab|cd〉 ∈ I, spojíme a ab svorkou.
21
34 {
Obrázek 1.1: Příklad grafického znázornění nezávislostního modelu.
19
Lépe to bude pochopitelné na příkladu: Nezávislostní model zobrazenýna obr. 1.1 na str. 19 je model
{〈12|∅〉, 〈23|1〉, 〈23|4〉, 〈34|12〉, 〈14|∅〉, 〈14|2〉
}.
Definice 8. Dva nezávislostní modely I (nad množinouM) a J (nad množi-nou N) nazveme izomorfní, jestliže existuje bijektivní zobrazení π množinyM na množinu N takové, že
〈ab|C〉 ∈ I ⇔ 〈π(a)π(b)|π(C)〉 ∈ J,
kde pod π(C) rozumíme {π(c); c ∈ C}. Třídu rozkladu nezávislostních mo-delů podle ekvivalence „býti izomorfníÿ budeme nazývat typ.
Izomorfismus je z diagramů snadno rozpoznatelný1. Pro ilustraci, všechnymodely znázorněné na obr. 1.2 jsou stejného typu, tj. navzájem izomorfní.
Obrázek 1.2: Tři izomorfní nezávislostní modely.
Nečiní problém nahlédnout, že modely daného typu jsou buďto všechnyreprezentovatelné nebo naopak není reprezentovatelný žádný z nich. To námumožňuje hovořit o reprezentovatelnosti typů.
Nezávislostní model I můžeme zúžit na podmnožinu proměnných, pří-padně vybrat pouze ty triplety, jejichž podmínková část zahrnuje zadanoupodmnožinu proměnných. Jedná se o analogie operací marginalizace a pod-mínění pro pravděpodobnostní rozdělení. Výsledné modely budeme nazývatminory2 I.
1Jedná se vlastně o permutaci náhodných veličin.2Raději zdůrazněme, že pojem minor zde používáme tak, jak byl zaveden v [Mat97],
nikoli tedy ve významu determinant podmatice.
20
Definice 9. Nechť I je nezávislostní model nad N a E,F jsou disjunktnípodmnožiny N . Potom definujeme minor I [FE jako nezávislostní model nadN \EF , do kterého jsou vybrány právě ty triplety neobsahující žádný z prvkůE a obsahující v podmínce F z jejichž podmínkové části je následně F vy-puštěno, formálně
I [FE = {〈ab|C〉; E ∩ (abC) = ∅, 〈ab|CF 〉 ∈ I} .
Pokud budeme chtít zdůraznit, že se jedná o minor nad množinou o kprvcích (neboli, že |N | − |EF | = k), budeme mluvit o k–minorech.Povšimněme si, že
I [∅∅ = I
a taktéž, pro E1F1 ∩ E2F2 = ∅,(I [F1E1
)[F2E2= I [F1F2E1E2
. (1.11)
Třídu nezávislostních modelů nazveme uzavřenou na minory, jestližes každým svým modelem obsahuje i všechny jeho minory. Jak bude ukázánov dalších dvou kapitolách, třídy Gaussovsky a diskrétně reprezentovatelnýchmodelů jsou uzavřené na minory, zatímco třída binárně reprezentovatelnýchmodelů na minory uzavřená není.
1.4 Charakterizace třídy nezávislostních mo-delů pomocí seznamu zakázaných minorů
Charakterizovat třídu reprezentovatelných modelů nemusí být vždy jedno-duché. Původní hypotéza J. Pearla v [Pea98], že jediné podmínky (pozitivní)reprezentovatelnosti jsou (1.9) a (1.10) uvedené v lemmatu 8, se ukázala býtimylná. Krom řady dalších vlastností reprezentovatelných modelů, publiko-vaných např. v [Spo94] a [Stu89], existuje důkaz v [Stu92] (pro podrobnějiokomentovanou verzi, viz [SV98]), že třída d–reprezentovatelných modelůnemá konečnou charakterizaci pomocí konečného počtu inferenčních pravi-del (jistého typu). V této práci se pokusíme k podobnému závěru dojít i protřídy g–reprezentovatelných a b–reprezentovatelných modelů, avšak místojazyka inferenčních pravidel budeme používat charakterizaci seznamem za-kázaných minorů navrženou v [Mat97].
21
Definice 10. O nezávislostním modelu J nad množinou M řekneme, že jezakázaným minorem pro třídu nezávislostních modelů C, jestliže žádnýz modelů v C nemá |M |–minor izomorfní s modelem J .Třída nezávislostních modelů C je charakterizovaná seznamem za-
kázaných minorů D, jestliže pro libovolný nezávislostní model I platí, žeI je v C právě tehdy, když žádný z minorů I není izomorfní s žádným z prvkůD.
Kupříkladu dle lemmatu 8 je model {〈12|3〉, 〈13|∅〉}, znázorněný vlevona obr. 1.3, (ale i řada dalších, např. {〈12|3〉, 〈13|2〉, 〈13|∅〉}) zakázanýmminorem pro třídy nezávislostních modelů, jež jsou d–, b– nebo g–reprezento-vatelné. Navíc, model {〈12|3〉, 〈13|2〉}, znázorněný vpravo na obr. 1.3, jezakázaným minorem pro třídu kladně reprezentovatelných nezávislostníchmodelů.
Obrázek 1.3: Dva příklady zakázaných minorů.
Definice 11. Třída nezávislostních modelů je konečně charakterizova-telná, pokud ji lze charakterizovat za pomoci konečného seznamu zakáza-ných minorů.
Poznamenejme, že tato definice je mírně odlišná od definice konečné cha-rakterizace uvedené v [Stu92], která je v termínech speciálních inferenčníchpravidel.V našem případě jde o charakterizaci v temínech zakázaných minorů, a
tak má pojem rozumný smysl pouze pro třídy nezávislostních modelů, kteréjsou na minory uzavřené.
Lemma 9. Existuje-li nekonečný seznam (navzájem neizomorfních) zaká-zaných minorů E pro třídu nezávislostních modelů C takový, že pro každýmodel J ∈ E nad množinou M leží všechny jeho (|M | − 1)–minory v C,potom třída C není konečně charakterizovatelná.
22
Důkaz. Předpokládejme sporem, že existuje konečný seznam zakázaných mi-norů D charakterizující třídu C. Každý model D ∈ D je uvažován nad ně-jakou indexovou množinou MD. Nechť m je maximální kardinalita MD přesvšechny D ∈ D. Jelikož E je nekonečná a složená z neizomorfních modelů,musí v ní existovat model E ∈ E nad množinou s kardinalitou n > m a tedyneizomorfní žádnému prvku D. Spor spočívá v tom, že tento model současněpatří i nepatří do C.Závěr E /∈ C plyne z toho, že E je zakázaný minor pro C. Naopak E ∈ C,
neboť předpokládáme, že (n − 1)–minory E patří do C a tedy ani ony, adle identity (1.11) ani jiné vlastní minory E nižší kardinality nemohou mítizomorfní kopii v D.
Pokud třída nezávislostních modelů není konečně charakterizovatelná,zůstává jedinou nadějí k popsání jejich prvků omezit se na modely nad mno-žinou N o pevně dané velikosti. Jak v následujících dvou kapitolách uvidíme,tato úloha je pro třídy modelů reprezentovatelných v daném distribučnímrámci triviální pro |N | ≤ 3, obtížná pro |N | = 4 a prakticky neřešitelná pro|N | ≥ 5.
23
Kapitola 2
Gaussovsky reprezentovatelnénezávislostní modely
V této kapitole nalezneme všechny Gaussovsky reprezentovatelné nezávis-lostní modely pro |N | ≤ 4. Tato práce navazuje na výsledky z [Mat05]a [Lně05], kde byly charakterizovány všechny g+–reprezentovatelné modelypro po řadě |N | = 3 a |N | = 4. Ve srovnání s [Lně05] zde budeme prezentovatalternativní, matematicky méně elegantní zato však více přímočaré řešenícharakterizace g+–reprezentovatelných modelů a toto poté rozšíříme na cha-rakterizaci g–reprezentovatelných modelů (pro |N | = 4). Na závěr dokážeme,že obecně třída g–reprezentovatelných nezávislostních modelů nemá koneč-nou charakterizaci a zmíníme několik zajímavých otevřených problémů.
Pro |N | ≤ 2 jsou všechny možné modely zjevně reprezentovatelné. Za-čněme tedy s rozborem pro |N | = 3. Modely, jež vyhovují podmínce (1.9) zlemmatu 8 jsou 9 typů, které jsou znázorněny na obr. 2.1 na str. 25.Prvních 5 typů modelů je skutečně g+–reprezentovatelných. Další 2 po-
zitivně reprezentovatelné býti nemohou, neboť nesplňují vlastnost (1.10)z lemmatu 8, ale jsou alespoň g–reprezentovatelné. Variační matice přísluš-ných reprezentací na obr. 2.1 odpovídají řazení vrcholů v diagramech protisměru hodinových ručiček s počátkem v levém dolním rohu.Není obtížné dokázat, že poslední tři typy nejsou g–reprezentovatelné.
Lemma 10. Nechť a, b a c jsou různé prvky N. Nezávislostní modely
i) I1 = {〈ab|∅〉, 〈ac|∅〉}
ii) I2 = {〈ab|∅〉, 〈ac|∅〉, 〈bc|∅〉}
24
Obrázek 2.1: Po řadě od shora g+–reprezentovatelné, zbylé g–repre-zentovatelné a g–nereprezentovatelné typy pro |N | = 3.
iii) I3 = {〈ab|∅〉, 〈ab|c〉}
nejsou g–reprezentovatelné.
Důkaz. Pokud by ξ = (ξa, ξb, ξc) byl náhodný vektor s Gaussovým rozděle-ním a varianční maticí Σ reprezentující jeden z těchto typů, je zjevné, žežádná z jeho tří složek by nemohla mít nulový rozptyl (neboli být neregu-lární, čili degenerovaná, konstatní). V opačném případě by totiž tato složkaξa byla automaticky nezávislá se zbylými dvěmi složkami ξb a ξc neboli dlelemmatu 3
ξa⊥⊥(ξb, ξc)⇔(ξa⊥⊥ξb & ξa⊥⊥ξc & ξa⊥⊥ξb|ξc & ξa⊥⊥ξc|ξb
),
což by byl spor.
i,ii) Dále pokud u vektoru bez degenerovaných složek platí ξa⊥⊥ξb a ξa⊥⊥ξc,což je podle první části lemmatu 5 ekvivalentní s σa·b = σa·c = 0, potomnutně platí dle druhé části lemmatu 5 i
σa·bσc·c − σa·cσb·c = σa·cσb·b − σa·bσb·c = 0
25
neboli ξa⊥⊥ξb|ξc a ξa⊥⊥ξc|ξb. To je ve však sporu s tím, že I1 a I2 jsoureprezentovatelné.
iii) Analogicky pokud platí ξa⊥⊥ξb a ξa⊥⊥ξb|ξc, což je podle lemmatu 5ekvivalentní s σa·b = 0 a σa·b− σa·cσb·c = 0, potom nutně σa·c = 0 neboσb·c = 0 a tudíž ξa⊥⊥ξc nebo ξb⊥⊥ξc. To je však ve sporu s tím, že I3 jereprezentovatelný.
Jak ukazuje následující lemma, třídy g+–reprezentovatelných a g–repre-zentovatelných nezávislostních modelů jsou uzavřené na minory.
Lemma 11. Jestliže nezávislostní model I je g–reprezentovatelný (resp. g+–reprezentovatelný), potom i všechny minory I jsou g–reprezentovatelné (resp.g+–reprezentovatelné).
Důkaz. Nechť ξ je g–reprezentace I s varianční maticí Σ. Potom I [FE je g–reprezentován Gaussovým rozdělením s varianční maticí ΣN\EF ·N\EF |F , vizlemma 4, první a druhá část. Pokud je navíc Σ regulární, potom se podlelemmatu 4 iii) jedná o pozitivní reprezentaci.
2.1 Regulární Gaussovská reprezentovatelnost
Podle lemmatu 11 musí být minory g+–reprezentovatelného modelu, taktéžg+–reprezentovatelné. Připomeňme, že pro |N | = 3 existuje 5 g+–reprezen-tovatelných typů nezávislostních modelů, viz horní část obr. 2.1. Nutnoupodmínkou pro g+–reprezentovatelnost nezávislostního modelu nad N ={1, 2, 3, 4} je tedy, že jeho osm 3–minorů je jednoho z pěti nám již známýchtypů. Zároveň si uvědomme elementární, ale důležitý fakt, že každý modelnad 4-prvkovou množinou je jednoznečně určen svými 3-minory. Pro ilustraciviz obr. 2.2.Jak lze za pomoci počítače snadno ověřit, existuje 58 typů modelů, je-
jichž 3–minory jsou g+–reprezentovatelné (viz M1–M53 na obr. 2.3 a M54–M58 na obr. 2.4). Nastiňme alespoň základní myšlenku, jak byla počítačováimplementace realizována: Protože projít všechny nezávislostní modely nad|N | = 4 a testovat jejich 3–minory by bývalo příliš časově náročné, postupo-vali jsme z opačného konce. Snažili jsme se najít osm g+–reprezentovatelnýchmodelů nad tříprvkovou množinou (tj. vybírali jsme z 11 modelů rozpada-jících se do 8 typů, viz obr. 2.2), tak aby tyto tvořily příslušné minory
26
{{
Obrázek 2.2: Model I spolu s 3–minory I [∅e a I [f∅ , kde e, f = 1, . . . , 4.
nezávislostního modelu nad N = {1, 2, 3, 4}. Stačilo by nám tedy prozkou-mat 118 = 214358881 možností výběru minorů. Ve skutečnosti jsme využiliněkterých symetrií a toto číslo řádově snížili.
Dalším krokem bylo nalézt reprezentace co nejvíce z těchto typů, resp.příslučné varianční matice těchto reprezentací. Prověřeny byly všechny sy-metrické, pozitivně definitní matice mající na všech diagonálních pozicíchstejné číslo a to číslo menší nebo rovno 24. Nalezeny byly g+–reprezentacepro 53 typů, viz M1–M53 na obr. 2.3, str. 39.Zbylých 5 typů (viz M54–M58 na obr. 2.4) nemůže být g+–reprezentova-
telných, neboť neodpovídají pravidlům odvozeným na základě „nezávislostníimplikaceÿ. Tento komplexní nástroj, použitelný pro libovolné rozdělení s ko-nečnou multiinformací, je založený na tzv. „strukturálních imsetechÿ, celo-číselných vektorech reprezentujících nezávislostní modely. Teorie nutná projeho pochopení přesahuje rámec této práce, viz [Stu05], str. 114. Avšak bezjakýchkoli formálních znalostí je možné využít „nezávislostní implikaceÿ díkyjava appletu
http : //staff.utia.cas.cz/studeny/VerifyView.html .
Navíc, v příštím oddílu bude přímo dokázáno, že dotyčných 5 typů není anig–reprezentovatelných. Shrňme tedy dosažené výsledky:
Věta 1. Nad množinou N = {1, 2, 3, 4} existuje 629 g+–reprezentovatelnýchnezávislostních modelů, které se rozpadají do 53 typů.
Pro inferenční pravidla charakterizující g+–reprezentovatelné modely vizlemma 16 na konci oddílu 2.3, str. 34.Grafické znázornění g+–reprezentovatelných typů spolu s varianční ma-
ticí vybrané reprezentace je na obr. 2.3, str. 39. Varianční matice reprezen-tací odpovídají řazení vrcholů v diagramech po směru hodinových ručiček
27
s počátkem v levém horním rohu. Počet izomorfních modelů příslušnýchkaždému z g–reprezentovatelných typů lze nalézt v tabulce 2.1 na straně 30.
2.2 Obecná Gaussovská reprezentovatelnost
V tomto oddílu budou nalezeny všechny g–reprezentovatelné modely nadmnožinou N = {1, 2, 3, 4}. Klíčová jsou následující dvě pomocná tvrzení.
Lemma 12. Jestliže je model I g–reprezentovatelný I = I(ξ), potom exis-tuje jeho g–reprezentace ξ∗ = (ξ∗1 , . . . , ξ
∗4) taková, že
Var ξ∗x = 1, x = 1, . . . , 4.
Důkaz. Pokud je nějaká složka degenerovaná (s nulovým rozptylem), potomje z definice nezávislá se zbytkem vektoru. Abychom se vyhnuli komplikacím,zaměníme proto nejprve všechny složky ξa s nulovým rozptylem (konstanty)za novou náhodnou náhodnou veličinu s nenulovým rozptylem nezávislou sezbytkem náhodného vektoru. Následně stačí definovat
ξ∗ =((Var ξ1)−
1
2 · ξ1, (Var ξ2)−1
2 · ξ2, (Var ξ3)−1
2 · ξ3, (Var ξ4)−1
2 · ξ4)
.
Snadno se ověří, že I(ξ) = I(ξ∗).
Díky lemmatu 12 se tedy lze při hledání maticových reprezentací omezit namatice mající na diagonále jedničky neboli na
Σ =
1 σ1·2 σ1·3 σ1·4σ2·1 1 σ2·3 σ2·4σ3·1 σ3·2 1 σ3·4σ4·1 σ4·2 σ4·3 1
, (2.1)
kde ze symetrie varianční matice σa·b = σb·a a díky její pozitivní semidefinit-nosti |σa·b| ≤ 1. Pozorný čtenář si zajisté povšimnul, že jsme vlastně přesliod varianční matice k matici korelační.Pokud jsou dvě náhodné veličiny ξa a ξb vzájemně funkčně závislé
(značíme ξa ≃ ξb), což je za výše zmíněného omezení ekvivalentní požadavkuξa = ±ξb, resp. σa·b = ±1, potom ξa⊥⊥ξc|ξb, ξb⊥⊥ξc|ξa, ξa⊥⊥ξc|ξbd a ξb⊥⊥ξc|ξad,kde a, b, c a d jsou různé prvky N .
28
Uvedený pojem lze zobecnit i na soubor více veličin: řekneme že (ξa)a∈A,A ⊆ N jsou vzájemně funkčně závislé (značíme ≃(ξA)), pokud |ΣA·A| = 0neboli dle (1.3) existuje vektor konstant cA takový, že
∑
a∈A
caξa = konst.
Pokud navíc pro žádnou neprázdnou podmnožinu B ⊆ A neplatí ≃(ξB),potom jsou (ca)a∈A nutně nenulové a tudíž
∀a ∈ A,∃ funkce fa : ξa = fa(ξA\a), (2.2)
navíc jelikož degenerovaná (konstantní) náhodná veličina je nezávislá s čím-koli, lze ze vztahu (2.2) snadno odvodit
∀a ∈ A,E ⊆ N \ A,F ⊆ N \ AE : ξa⊥⊥ξE|ξAF\a.
Lemma 13. Nechť I je g–reprezentovatelný nezávislostní model, a, b, c a djsou různé prvky N .
i) Jestliže {〈ab|c〉, 〈ac|b〉} ⊆ I, potom {〈ab|∅〉, 〈ac|∅〉} ⊆ I nebo ξb ≃ ξc.
ii) Jestliže {〈ab|cd〉, 〈ac|bd〉} ⊆ I, potom buďto {〈ab|d〉, 〈ac|d〉} ⊆ I nebo〈ad|bc〉 ∈ I nebo ξb ≃ ξc.
Důkaz. Snadno nahlédneme, že má-li náhodný vektor ξabcd některou ze slo-žek degenerovanou (konstantní), je pravá strana implikací i) a ii) splněnaautomaticky. Bez újmy na obecnosti se tedy opět omezíme na důkaz prorozdělení s varianční maticí typu (2.1).Požadované nezávislosti ξa⊥⊥ξb|ξc a ξa⊥⊥ξc|ξb neboli σa·b = σa·cσb·c a
σa·c = σa·bσb·c dávají po dosazení σa·b = σa·bσ2b·c, což implikuje σa·b = σa·c = 0
(ξ1⊥⊥ξ2 a ξ1⊥⊥ξ3) nebo |σb·c| = 1 (ξb ≃ ξc).Důkaz druhé části je myšlenkově analogický. Předpokládejme nejprve, že
≃(ξbcd) neboli existují konstanty r, s, t a u takové, že
r = sξb + tξc + uξd.
Pokud u = 0, potom ξb ≃ ξc. Naopak je-li u 6= 0, lze vyjádřit ξd jako funkcizbylých dvou složek ξd = fd(ξb, ξc), a proto ξd⊥⊥ξa|ξbc.Pokud naopak |Σbcd·bcd| 6= 0 a předpokládáme-li ξa⊥⊥ξb|ξcd a ξa⊥⊥ξc|ξbd,
dostáváme po podmínění ξd = xd z část i) že ξa⊥⊥ξb|ξd a ξa⊥⊥ξc|ξd (možnostvzájemné funkční závislosti ξb a ξc po podmínění ξd je ve sporu s nenulovostídeterminantu Σbcd·bcd).
29
M1: 6 M2: 12 M3: 6 M4: 6 M5: 24 M6: 6M7: 12 M8: 12 M9: 3 M10: 12 M11: 24 M12: 3M13: 6 M14: 24 M15: 24 M16: 12 M17: 24 M18: 24M19: 12 M20: 6 M21: 12 M22: 6 M23: 12 M24: 24M25: 24 M26: 12 M27: 24 M28: 24 M29: 12 M30: 6M31: 24 M32: 6 M33: 12 M34: 12 M35: 3 M36: 3M37: 12 M38: 12 M39: 12 M40: 12 M41: 12 M42: 4M43: 4 M44: 24 M45: 12 M46: 12 M47: 4 M48: 12M49: 12 M50: 3 M51: 6 M52: 1 M53: 1M59: 4 M60: 12 M61: 12 M62: 12 M63: 12 M64: 12M65: 12 M66: 24 M67: 1 M68: 12 M69: 6 M70: 6M71: 3 M72: 24 M73: 6 M74: 6 M75: 12 M76: 6M77: 12 M78: 6 M79: 12 M80: 3 M81: 4 M82: 12M83: 1 M84: 4 M85: 12
Tabulka 2.1: Počet izomorfních modelů nad N = {1, 2, 3, 4} pro každý z g–reprezentovatelných typů na obr. 2.3 a 2.4.
Existuje 178 typů nezávislostních modelů, jejichž 3–minory jsou jednohoze sedmi typů g–reprezentovatelných pro |N | = 3 (viz obr. 2.1). Lemma 13nám umožňuje ukázat, že 90 z nich nemůže mít g–reprezentaci. Zbýva tedyrozhodnout o g–reprezentovatelnosti 88 typů (M1–M88, obr. 2.3 a obr. 2.4).Počítačovým prohledáváním prostoru celočíselných symetrických pozi-
tivně semidefinitních matric bylo nalezeno 79 g–reprezentací a 1 další bylanalezena později bez použití počítače (M1–M53, obr. 2.3, a M59–M85, obr.2.4). Varianční matice reprezentací na obr. 2.3 a 2.4 odpovídají řazení vr-cholů v diagramech po směru hodinových ručiček s počátkem v levém hornímrohu. Počet izomorfních modelů pro každý typ lze nalézt v tabulce 2.1.Zbývajících 8 typů (M54–M58 a M86–M88, obr. 2.4) není g–reprezento-
vatelných, jak dokážeme v následujícím lemmatu.
Lemma 14. Nechť a, b, c a d jsou různé prvky N . Nezávislostní modely
i) I1 = {〈cd|a〉, 〈ad|b〉, 〈bd|c〉}
ii) I2 = {〈ab|c〉, 〈cd|b〉, 〈bd|a〉, 〈ac|d〉}
iii) I3 = {〈cd|∅〉, 〈ab|c〉, 〈bd|a〉, 〈ac|bd〉}
iv) I4 = {〈cd|∅〉, 〈ab|c〉, 〈ab|d〉, 〈cd|ab〉}
30
v) I5 = {〈ab|∅〉, 〈cd|∅〉, 〈ac|bd〉, 〈bd|ac〉}
vi) I6 = {〈ab|d〉, 〈bc|d〉, 〈ac|d〉, 〈ab|cd〉, 〈bc|ad〉, 〈cd|ab〉, 〈ac|bd〉}
vii) I7 = {〈ab|d〉, 〈bc|d〉, 〈ac|d〉, 〈ab|cd〉, 〈bc|ad〉, 〈cd|ab〉, 〈ad|bc〉, 〈ac|bd〉,〈bd|ac〉}
viii) I8 = {〈ab|d〉, 〈bc|d〉, 〈ac|d〉, 〈ab|c〉, 〈bd|c〉, 〈ad|c〉, 〈ab|cd〉, 〈bc|ad〉,〈cd|ab〉, 〈ad|bc〉, 〈ac|bd〉, 〈bd|ac〉}
nejsou g–reprezentovatelné.
Důkaz. Předpokládejme, že ξ je g–reprezentací některého z výše uvedenýchmodelů, Σ je příslušná varianční matrice typu (2.1). Přičemž pokud zkou-maný model I neobsahuje triplet 〈xy|∅〉, můžeme automaticky předpokládátσx·y 6= 0, a pokud pro dané x, y neobsahuje všechny triplety typu 〈xu|y〉,〈yu|x〉, 〈xu|yt〉 a 〈yu|xt〉, lze předpokládat ξx 6≃ ξy.V částech i)-viii) dospějeme ke sporu pro modely po řadě I1,. . . ,I8 a
to způsobem, že si vypíšeme vztahy odpovídající tripletům v modelu a znich vyvodíme nezávislostní vztah v modelu neobsažený, případně funkčnízávislost, kterou model nedovoluje.
i) Požadované nezávislosti dle lemmatu 5 implikují: σc·d = σa·cσa·d, σa·d =σa·bσb·d a σb·d = σb·cσc·d. Dosadíme-li do sebe tyto rovnice, dostaneme
σc·d = σa·cσa·bσb·cσc·d,
a tudíž σc·d = σa·d = σb·d = 0 (ξd⊥⊥ξabc) nebo ξa ≃ ξb ≃ ξc, což je spor.
ii) Analogicky lze z σa·b = σa·cσb·c, σa·c = σa·dσc·d, σc·d = σb·cσb·d a σb·d =σa·bσa·d odvodit
σa·b = (σb·cσa·d)2 σa·b
a odtud σa·b = 0 (ξa⊥⊥ξb) nebo ξb ≃ ξc a ξa ≃ ξd.
iii) Pokud vyloučíme ξb ≃ ξd a dosadíme-li σc·d = 0, σa·b = σa·cσb·c aσb·d = σa·bσa·d do
σa·c + σb·dσc·dσa·b + σb·dσb·cσa·d − σa·dσc·d − σa·bσb·c − σa·cσ2b·d = 0
dostaneme po úpravě
σa·c((1− σ2b·c) + σ2a·dσ2b·c(1− σ2a·c)) = 0.
Odtud plyne σa·c = 0 (ξa⊥⊥ξc) nebo σ2b·c = 1 (ξb ≃ ξc).
31
iv) Analogicky, dosazením σc·d = 0, σa·b = σa·cσb·c a σb·d = σa·b/σa·d =σa·cσb·c/σa·d do rovnice příslušné tripletu 〈cd|ab〉
σa·bσb·cσa·d + σa·bσb·dσa·c − σa·cσa·d − σb·cσb·d = 0
dostanemeσa·c
σa·d(σ2a·d(1− σ2b·c) + σ2b·c(1− σ2a·c)) = 0
a odtud plyne σa·c = 0 (ξa⊥⊥ξc) nebo σa·d = 0 (ξa⊥⊥ξd) nebo |σb·c| = 1(ξb ≃ ξc).
v) Pokud nenastanou funkcionální závislosti ξa ≃ ξc nebo ξb ≃ ξd, do-staneme dosazením σa·b = σc·d = 0 do rovnicí příslučným tripletům〈ac|bd〉 a 〈bd|ac〉
σa·c − σa·cσ2b·d + σa·dσb·cσb·d = 0,
σb·d − σb·dσ2a·c + σa·dσb·cσa·c = 0.
Odečtením první rovnice vynásobené σb·d od druhé rovnice vynáso-bené σa·c dostaneme σa·cσb·d(σa·c − σb·d)(σa·c + σb·d) = 0. Odtud budťoσa·c = 0 nebo σb·d = 0 nebo σa·c = ±σb·d. Pro σa·c = ±σb·d lzedále z pozitivní semidefinitnosti matic Σabc·abc a Σacd·acd ukázat, že1 − σ2a·c ≥ max(σ
2a·d, σ
2b·c) ≥ |σa·dσb·c|, přičemž v druhém případě na-
stává rovnost jen pro |σa·d| = |σb·c|. Toto dosadíme zpět do rovnicpříslušných 〈ac|bd〉 a 〈bd|ac〉 a dostáváme σa·d = ∓σb·c, což vede zapředpokladu ξc 6≃ ξd na ξa⊥⊥ξb|ξcd.
vi)+vii) Dosadíme-li dle předpokladů σa·b = σb·dσa·d, σb·c = σb·dσc·d a σa·c =σa·dσc·d do rovnice příslušné tripletu 〈cd|ab〉 (můžeme předpokládatξa 6≃ ξb), dostaneme
σc·d(1− σ2b·d)(1− σ2a·d) = 0,
odtud ξc⊥⊥ξd nebo ξa ≃ ξd nebo ξb ≃ ξd, což je spor.
viii) Jestliže ξc ≃ ξd, potom lze z nezávislosti ξc⊥⊥ξd|ξab odvodit ≃(ξabc).Uvážíme-li dále ξa⊥⊥ξb|ξc, dostáváme ξa ≃ ξc nebo ξb ≃ ξc, což je spor.V opačném případě (ξc 6≃ ξd) dostaneme spor způsobem popsanýmv části „vi)+vii)ÿ.
32
Shrňme tedy dosažené poznatky do závěrečné věty:
Věta 2. Nad množinou N = {1, 2, 3, 4} existuje 877 g–reprezentovatelnýchnezávislostních modelů 80 typů. Pozitivně reprezentovatelných je 629 z nich(53 typů) a jsou to právě ty splňující podmínku (1.10).
2.3 Inferenční pravidla
Někteří autoři dávají přednost charakterizaci reprezentovatelných modelůza pomoci inferenčních pravidel. Přestože je zjevné, že tato práce se neubírátímto směrem, uveďme pro srovnání seznam inferenčních pravidel vyply-nuvších z dosažené charakterizace Gaussovsky reprezentovatelných modelůnad čtyřprvkovou množinou.
Lemma 15. Nechť N je konečná množina a I je g–reprezentovatelný ne-závislostní model nad N . Potom pro a, b, c, d různé prvky N a množinyE ⊆ N \ abc a F ⊆ N \ abcd platí:
i) {〈ab|E〉, 〈ac|bE〉} ⊆ I ⇐⇒ {〈ac|E〉, 〈ab|cE〉} ⊆ I
ii) {〈ab|E〉, 〈ac|E〉} ⊆ I =⇒ 〈ab|cE〉 ∈ I
iii) {〈ab|E〉, 〈ab|cE〉} ⊆ I =⇒(〈ac|E〉 ∈ I
)∨(〈bc|E〉 ∈ I
)
iv) {〈ab|cF 〉, 〈ac|bF 〉} ⊆ I =⇒(〈ab|F 〉 ∈ I
)∨({〈bd|cF 〉, 〈cd|bF 〉} ⊆ I
)
v) {〈ab|cdF 〉, 〈ac|bdF 〉} ⊆ I =⇒(〈ab|dF 〉 ∈ I
)∨(〈ad|bcF 〉 ∈ I
)∨(
{〈bd|cF 〉, 〈cd|bF 〉} ⊆ I)
vi) {〈ab|F 〉, 〈cd|F 〉, 〈ac|bdF 〉, 〈bd|acF 〉} ⊆ I =⇒(〈ac|F 〉 ∈ I
)∨(
{〈ab|cdF 〉, 〈ad|bcF 〉} ⊆ I)
vii) {〈ab|F 〉, 〈cd|aF 〉, 〈cd|bF 〉, 〈ab|cdF 〉} ⊆ I =⇒ 〈cd|F 〉 ∈ I
viii) {〈ab|F 〉, 〈bd|cF 〉, 〈cd|aF 〉, 〈ac|bdF 〉} ⊆ I =⇒ 〈bd|F 〉 ∈ I
ix) {〈ab|cF 〉, 〈ac|dF 〉, 〈ad|bF 〉} ⊆ I =⇒ 〈ab|dF 〉 ∈ I
x) {〈ab|cF 〉, 〈bc|dF 〉, 〈cd|aF 〉, 〈ad|bF 〉} ⊆ I =⇒ 〈ab|dF 〉 ∈ I
xi) {〈ab|dF 〉, 〈ac|dF 〉, 〈bc|dF 〉, 〈cd|abF 〉} ⊆ I =⇒(〈cd|bF 〉 ∈ I
)∨(
〈cd|aF 〉 ∈ I)
33
Důkaz. První část je semigrafoidová vlastnostnost z lemmatu 8, druhá atřetí jsou důsledky důkazu lemmatu 10, další dvě důsledkem lemmatu 13.Dalších šest dostaneme rozborem g–reprezentovatelných nadmodelů mo-
delů z lemmatu 14 (M54–58 a M86–88) za pomoci obr. 2.3 a obr. 2.4. Kekaždému g–nereprezentovatelnému modelu I nalezneme všechny g–reprezen-tovatelné nadmodely Ji ⊃ I a jako nové inferenční pravidlo přidáme „Pokudje I podmnožinou g–reprezentovatelného modelu, potom daný model obsa-huje i (libovolně zvolený) triplet z průniku ∩iJiÿ.Dodejme, že takto dostaneme jedno pravidlo pro každý z modelů M54–
58, zatímco modely M86–88 jsou zaráz vyloučeny jediným pravidlem xi).
Pro |N | ≤ 4 dávají inferenční pravidla z lemmatu 15 charakterizaci úpl-nou, tzn. nezávislostní model je g–reprezentovatelný právě tehdy, když spl-ňuje pravidla i)-xi).Regulárně Gaussovsky reprezentovatelné modely nad čtyřprvkovou mno-
žinou již byly charakterizovány pomocí inferenčních pravidel v [Lně05]. Proúplnost uvedeme i tento výsledek (bez dalšího zdůvodnění).
Lemma 16. Nechť N je konečná množina a I je g+–reprezentovatelný ne-závislostní model nad N . Potom pro a, b, c, d různé prvky N a množinyE ⊆ N \ abc a F ⊆ N \ abcd platí:
i) {〈ab|E〉, 〈ac|bE〉} ⊆ I ⇐⇒ {〈ac|E〉, 〈ab|cE〉} ⊆ I
ii) {〈ab|cE〉, 〈ac|bE〉} ⊆ I ⇐⇒ {〈ab|E〉, 〈ac|E〉} ⊆ I
iii) {〈ab|E〉, 〈ab|cE〉} ⊆ I =⇒(〈ac|E〉 ∈ I
)∨(〈bc|E〉 ∈ I
)
iv) {〈ab|F 〉, 〈cd|F 〉, 〈ac|bdF 〉, 〈bd|acF 〉} ⊆ I =⇒ 〈ac|F 〉 ∈ I
v) {〈ab|F 〉, 〈cd|aF 〉, 〈cd|bF 〉, 〈ab|cdF 〉} ⊆ I =⇒ 〈cd|F 〉 ∈ I
vi) {〈ab|F 〉, 〈bd|cF 〉, 〈cd|aF 〉, 〈ac|bdF 〉} ⊆ I =⇒ 〈ac|F 〉 ∈ I
vii) {〈ab|cF 〉, 〈ac|dF 〉, 〈ad|bF 〉} ⊆ I =⇒ 〈ab|F 〉 ∈ I
viii) {〈ab|cF 〉, 〈bc|dF 〉, 〈cd|aF 〉, 〈ad|bF 〉} ⊆ I =⇒ 〈ab|F 〉 ∈ I
Snad by bylo vhodné poznamenat, že vlastnosti v)− viii) v lemmatu 16jsou díky vlastnostem i)−iii) z lemmatu 16 vlastně ekvivalentní vlastnostemvii)−x) z lemmatu 15 a že pro |N | ≤ 4 dává lemma 16 úplnou charakterizacig+–reprezentovatelných modelů.
34
2.4 Neexistence konečné charakterizace
V tomto oddílu dokážeme, že Gaussovsky reprezentovatelné nezávislostnímodely nelze charakterizovat konečným seznamem zakázaných minorů. Po-stupovat budeme podle návodu z lemmatu 9 v oddílu 1.4.
Lemma 17. Pro libovolné n ≥ 4 je nezávislostní model
Jn = {〈12|3〉, 〈13|4〉, . . . , 〈1(n− 1)|n〉, 〈1n|2〉} (2.3)
zakázaným minorem pro třídu Gaussovsky reprezentovatelných modelů.
Důkaz. Předpokládejme, že by existoval g–reprezentovatelný nezávislostnímodel I nad množinou {1, . . . , n} ∪ EF takový, že I [FE = Jn. Potom by dlelemmatu 11 byl g–reprezentovatelný i model Jn. Označme tedy Σ variančnímatici typu ∀a : σa·a = 1 (viz lemma 12) příslušné g–reprezentace ξ.Požadované nezávislosti
ξ1⊥⊥ξ2|ξ3, ξ1⊥⊥ξ3|ξ4, . . . , ξ1⊥⊥ξn−1|ξn, ξ1⊥⊥ξn|ξ2
odpovídají dle lemmatu 5 vztahům
σ1·2 = σ1·3σ2·3, σ1·3 = σ1·4σ3·4, . . . , σ1·(n−1) = σ1·nσ(n−1)·n, σ1·n = σ1·2σ2·n
a opakovaným dosazením dostáváme
σ1·2 = σ1·2 ·(σ2·3σ3·4 . . . σ(n−1)·nσ2·n
).
Tudíž, buďto σ1·2 = 0 (tj. ξ1⊥⊥ξ2) nebo |σ2·3| = 1 (tj. ξ1⊥⊥ξ3|ξ2), což je spors tím, že ξ je g–reprezentace modelu Jn.
Lemma 18. Pro libovolné n ≥ 3 jsou nezávislostní modely
In = {〈12|3〉, 〈13|4〉, . . . , 〈1(n− 1)|n〉},
I∗n = {〈12|∅〉}, I∗∗
n = ∅
regulárně Gaussovsky reprezentovatelné nad množinou N = {1, . . . , n}.
Důkaz. Nechť ξ = (ξa)a∈{1,...,n} je Gaussovsky rozdělený náhodný vektor svarianční maticí Σ = (σa·b)a,b∈{1,...,n} takovou, že
∀a : σa·a = 1,
∀a > 1 : σ1·a = σa·1 = ǫn−a+1,
∀a, b > 1, a 6= b : σa·b = σb·a = ǫ,
35
kde ǫ > 0 je libovolně zvolené dostatečně malé číslo. Zjevně, Σ > 0, neboť∀A ⊆ {1, . . . , n} : |ΣA·A| = 1 + ǫ(· · · ) > 0, kde „. . . ÿ zastupuje polynomv proměnné ǫ.Nyní použijeme obdobných argumentů v kombinaci s lemmatem 5 pro
důkaz, že I(ξ) = In:
i) Pro a, b ∈ {1, 2, . . . , n} je σa·b 6= 0, tudíž zjevně neplatí ξa⊥⊥ξb.
ii) Pro a, b ∈ {2, 3, . . . , n} a množinu C, ∅ 6= C ⊆ {1, . . . , n} \ ab, deter-minant
|ΣaC·bC | =
∣∣∣∣∣∣∣∣∣∣∣
ǫ ǫ ǫ ǫ · · ·ǫ 1 ǫ ǫ · · ·ǫ ǫ 1 ǫ · · ·ǫ ǫ ǫ 1 · · ·............. . .
∣∣∣∣∣∣∣∣∣∣∣
= ǫ+ ǫ2(. . . ) 6= 0
a tudíž tvrzení ξa⊥⊥ξb|ξC nemůže býti platným (pro ǫ dostatečně malé).
iii) Pro a ∈ {2, 3, . . . n} a neprázdnou množinu C = {c1, c2, . . . , ck} ⊆{2, 3, . . . , a− 1}, determinant
|ΣaC·1C | =
∣∣∣∣∣∣∣∣∣∣∣
ǫn−a+1 ǫ ǫ ǫ · · ·ǫn−c1+1 1 ǫ ǫ · · ·ǫn−c2+1 ǫ 1 ǫ · · ·ǫn−c3+1 ǫ ǫ 1 · · ·...
.......... . .
∣∣∣∣∣∣∣∣∣∣∣
= ǫn−a+1 + ǫn−a+2(. . . ) 6= 0.
Proto ani tvrzení ξa⊥⊥ξ1|ξC nemůže býti platným.
iv) Analogicky, pro a ∈ {2, 3, . . . n} a C = {c1, . . . , ck} ⊆ {2, 3, . . . , n} \ atakovou, že m := maxc∈C c > a+ 1, příslušný determinant má tvar
|ΣaC·1C | =
∣∣∣∣∣∣∣∣∣∣∣
ǫn−a+1 ǫ ǫ ǫ · · ·ǫn−c1+1 1 ǫ ǫ · · ·ǫn−c2+1 ǫ 1 ǫ · · ·ǫn−c3+1 ǫ ǫ 1 · · ·...
.......... . .
∣∣∣∣∣∣∣∣∣∣∣
= ±ǫn−m+2+ǫn−m+3(. . . ) 6= 0,
Proto ani v tomto případě tvrzení ξa⊥⊥ξ1|ξC nemůže býti platným.
36
v) Zbývá vyšetřit případ a ∈ {2, 3, . . . n− 1} a C = {(a + 1), c2, . . . , ck},∅ 6= C ⊆ (a + 1) ∪ {2, 3, . . . , a − 1}. Pro C dvou či víceprvkovou mádeterminant |ΣaC·1C | tvar∣∣∣∣∣∣∣∣∣∣∣
ǫn−a+1 ǫ ǫ ǫ · · ·ǫn−a 1 ǫ ǫ · · ·
ǫn−c2+1 ǫ 1 ǫ · · ·ǫn−c3+1 ǫ ǫ 1 · · ·...
.......... . .
∣∣∣∣∣∣∣∣∣∣∣
= ǫn−a+1− ǫn−a+1± ǫn−a+2+ ǫn−a+3(. . . ).
Tudíž |Σ1C·aC | 6= 0 a tvrzení ξ1⊥⊥ξa|ξC neplatí.
Avšak pokud je naopak C = {a+ 1} jednoprvková, potom
|Σa(a+1)·1(a+1)| =
∣∣∣∣(
ǫn−a+1 ǫǫn−a 1
)∣∣∣∣ = 1ǫn−a+1 − ǫǫn−a = 0.
Skutečně tedy platí ξ1⊥⊥ξa|ξa+1.
Zcela analogickými argumenty lze ukázat, že modely I∗n a I∗∗
n jsou g+–reprezentovány Gaussovskými náhodnými vektory s variančními maticemi
Σ∗ =
1 0 ǫ ǫ · · ·0 1 ǫ ǫ · · ·ǫ ǫ 1 ǫ · · ·ǫ ǫ ǫ 1 · · ·............. . .
, Σ∗∗ =
1 ǫ ǫ ǫ · · ·ǫ 1 ǫ ǫ · · ·ǫ ǫ 1 ǫ · · ·ǫ ǫ ǫ 1 · · ·............. . .
.
Dopracování důkazu je ponecháno pozornému čtenáři.
S využitím lemmatu 9 dostáváme jako důsledek lemmat 17 a 18 násle-dující závěrečné tvrzení:
Věta 3. Třídy (obecně) Gaussovsky a regulárně Gaussovsky reprezentova-telných nezávislostních modelů nejsou konečně charakterizovatelné.
37
2.5 Závěr kapitoly
V této kapitole jsme dokázali, že neexistuje konečná charakterizace Gaussov-sky reprezentovatelných nezávislostních modelů pomocí zakázaných minorůa nalezli všechny Gaussovsky reprezentovatelné modely nad N = {1, 2, 3, 4}.Vyvstává přirozená otázka, zda by nebylo možné pokračovat dále a charak-terizovat Gaussovsky reprezentovatelné modely pro |N | = 5. Lze ukázat,že existuje 366177 typů nezávislostních modelů s g+–reprezentovatelnými4–minory. Bohužel, u většiny těchto typů nejsme zatím schopni najít g+–reprezentaci, ani dokázat, že neexistuje.Zmiňme ještě několik dalších otevřených problémů. Všechny matice roz-
ptylu na obr. 2.3 a obr. 2.4 vyjma matice příslušné modelu M85 jsou ce-ločíselné. Otevřeným problémem zůstává, zda lze lze celočíselnou (resp.racionální) reprezentaci nalézt pro každý g+–reprezentovatelný (resp. g–reprezentovatelný) model. Tento problém úzce souvisí s hypotézou vyslove-nou F. Matúšem na konci [Mat99], že pro každý d–reprezentovatelný modelexistuje jeho racionální reprezentace.Poslední bod se již týká obsahu příštích dvou kapitol. Je snadné zkon-
struovat model, jenž je d–reprezentovatelný nebo b–reprezentovatelný, alenení g–reprezentovatelný. M. Studený však formuloval otázku, zda existujeg–reprezentovatelný model, jenž by nebyl d–reprezentovatelný. Odpověď natuto otázku dává model M71 na obr. 2.4, jenž protiřečí pravidlům odvoze-ným z „nezávislostní implikaceÿ a může být tedy reprezentován jen rozděle-ním, které nemá konečnou multiinformaci. Nadále však zůstává otevřenýmproblémem, zda existuje g+–reprezentovatelný model, který by nebyl b+–reprezentovatelný, resp. d+–reprezentovatelný. Tento problém bude podrob-něji studován na konci následující kapitoly.
38
Obrázek 2.3: g+–reprezentovatelné typy s varianční maticí reprezentace.
39
Obrázek 2.4: Po řadě od shora g+–nereprezentovatelné typy s g+–reprezen-tovatelnými minory, zbylé g–reprezentovatelné typy, g–nereprezentovatelnétypy s g–reprezentovatelnými minory splňující vlastnosti z lemmatu 13.
40
Kapitola 3
Diskrétně a binárněreprezentovatelné nezávislostnímodely
V této kapitole nalezneme všechny diskrétně (resp. binárně) reprezentova-telné nezávislostní modely pro |N | ≤ 3. Dále uvedeme známý výsledek prodiskrétní reprezentovatelnost v případě |N | = 4 doplněný částečnými vý-sledky pro pozitivní diskrétní a binární reprezentovatelnost.
Obrázek 3.1: Po řadě od shora a zleva: b+/d+–reprezentovatelné, b/d–reprezentovatelné a zbylý d+–reprezentovatelný typ pro |N | = 3.
41
Pro |N | ≤ 2 jsou všechny možné nezávislostní modely zjevně (pozitivněbinárně) reprezentovatelné. S rozborem tedy začneme pro |N | = 3. Modely,jež vyhovují podmínce (1.9) z lemmatu 8 jsou 10 typů, které jsou znázorněnyna obr. 3.1 na str. 41.Podmínce pro kladně reprezentovatelné modely (1.10) vyhovuje 8 typů,
z nichž všechny jsou d+–reprezentovatelné, ovšem jeden z nich není b+–reprezentovatelný (viz níže, lemma 19). Zbylé 2 typy jsou (obecně) binárněa tedy i diskrétně reprezentovatelné.
Lemma 19. Nezávislostní model {〈ab|c〉, 〈ab|∅〉} není b–reprezentovatelný.
Důkaz. Jedná se o známý fakt, viz např. [Spo94]. V námi zvolené parametri-zaci se provede důkaz následovně: rovnice příslušné nezávislostním vztahůmξa⊥⊥ξb a ξa⊥⊥ξb|ξc jsou
eab = eaeb
eabc = eaebc + ebeac − eabec
eab + eabcec = eacebc + eaeb
Pokud dosadíme první dvě rovnice do třetí, dostaneme po úpravě
(eac − eaec) · (ebc − ebec) = 0,
a proto nutně ξa⊥⊥ξc nebo ξb⊥⊥ξc.
3.1 Pozitivní binární reprezentovatelnost
Poněkud netradičně začneme u rozboru reprezentovatelnosti nad čtyřmi ná-hodnými veličinami s pozitivní binární reprezentovatelností, neboť tyto vý-sledky (byť značně neúplné) nám budou později užitečné při charakterizacipozitivně diskrétně reprezentovatelných modelů.Připomeňme, že třídy b–reprezentovatelných a b+–reprezentovatelných
modelů nejsou uzavřené na minory: kupříkladu model I = {〈ab|cd〉, 〈ab|d〉}je b+–reprezentovatelný1, zatímco model I [d podle lemmatu 19 b–reprezen-tovatelný není.
1Reprezentaci snadno získáme jako směsové rozdělení, kdy za podmínky ξd = −1 zvo-líme za rozdělení ξabc nějakou reprezentaci modelu {〈ab|c〉, 〈ab|∅〉, 〈ac|b〉, 〈ac|∅〉} a za pod-mínky ξd = 1 zvolíme za rozdělení ξabc reprezentaci modelu {〈ab|c〉, 〈ab|∅〉, 〈bc|a〉, 〈bc|∅〉}.
42
Použili jsme podobný postup jako v případě Gaussovské reprezentova-telnosti. Jako horní odhad počtu b+–reprezentovatelných modelů můžemevzít všechny nezávislostní modely I nad N = {1, 2, 3, 4} takové, že jejich 3–minory neprotiřečí podmínce (1.10) z lemmatu 8 (tzn. jsou jednoho z osmitypů z obr. 3.1), a zároveň je splněna podmínka z lemmatu 19 (tzn. nena-stane I [d = {〈ab|c〉, 〈ab|∅〉}). Počet typů modelů splňujících výše uvedené je240.Následně jsme náhodně generovali soubor racionálních čísel z intervalu
[−1, 1] indexovaný podmnožinamiN a testovali, zda-li pokud vezmeme tentosoubor jako soubor momentů (eA)A⊆N dostaneme parametrizaci nějakéhobinárního rozdělení a případně jakého typu je model tomuto rozdělení pří-slušný. Pro generování jsme využili několika algoritmů, kdy pro zmenšeníprohledávaného prostoru jsme například volili e1 = e2 = e3 = e4 = 0 nebo(na základě poznámky na konci pododdílu 1.2.3) se snažili odvodit binárníreprezentaci na základě reprezentace Gaussovské. Takto jsme dostali klad-nou binární reprezentaci 139 typů.Ač je pochopitelně možné zvláště horní mez počtu b+–reprezentovatel-
ných typů dále vylepšovat (např. za pomoci dále v textu zmíněných vlast-ností diskrétně a pozitivně diskrétně reprezentovatelných modelů lze roz-hodnout o reprezentovatelnosti dalších zhruba 40 typů), je zjevné, že zbývávelké množství typů, u nichž nejsme schopni rozhodnout, zda jsou či nejsoub+–reprezentovatelné .Uveďme však několik nových vlastností, specifických pro b+–reprezento-
vatelné modely, jež jsme na základě našeho zkoumání získali.
Lemma 20. Nechť I je b+–reprezentovatelný nezávislostní model nad N aa, b, c, d jsou různé prvky N . Potom platí:
i) {〈ab|cd〉, 〈ab|c〉, 〈ad|∅〉, 〈cd|∅〉} ⊆ I =⇒{〈ad|c〉, 〈cd|a〉} ⊆ I ∨ 〈bd|∅〉 ∈ I
ii) {〈ab|cd〉, 〈ab|c〉, 〈ad|∅〉, 〈bd|∅〉} ⊆ I =⇒{〈ad|b〉, 〈bd|a〉} ⊆ I ∨ 〈cd|∅〉 ∈ I
iii) {〈ab|cd〉, 〈ab|∅〉, 〈bc|∅〉, 〈cd|∅〉, 〈ad|∅〉} ⊆ I =⇒{〈ad|c〉, 〈cd|a〉} ⊆ I ∨ {〈bd|c〉, 〈cd|b〉} ⊆ I
iv) {〈ab|cd〉, 〈ad|b〉, 〈cd|b〉} ⊆ I =⇒{〈bc|∅〉, 〈cd|∅〉, 〈bc|d〉} ⊆ I ∨ 〈ab|c〉 ∈ I
43
v) {〈ab|cd〉, 〈ab|∅〉, 〈bc|∅〉, 〈bd|∅〉, 〈ab|c〉, 〈bc|a〉} ⊆ I =⇒ 〈ad|∅〉 ∈ I ∨〈ac|∅〉 ∈ I ∨ 〈cd|∅〉 ∈ I ∨ 〈ad|c〉 ∈ I ∨ {〈ab|d〉, 〈bd|a〉} ⊆ I
vi) {〈ab|cd〉, 〈ab|d〉, 〈bc|a〉} ⊆ I =⇒〈ac|∅〉 ∈ I ∨ 〈ad|∅〉 ∈ I ∨ 〈cd|∅〉 ∈ I ∨ 〈cd|a〉 ∈ I ∨ 〈ac|d〉 ∈ I
Důkaz. Celý důkaz provedeme v parametrizaci s centrovanými momenty. Přivýpočtech je vhodné použít software umožňující práci s algebraickými vzorci(Maple, Mathematica, . . . ), neboť jinak jsou příliš pracné.
i) Pokud předpokládáme, že ξa⊥⊥ξd a ξc⊥⊥ξd, potom fad = fcd = 0. Pokudnavíc ξa⊥⊥ξb|ξc, potom fab =
facfbc
1−e2ca fabc = −2ecfab. Dosadíme-li toto
do první rovnice příslušné vztahu ξa⊥⊥ξb|ξcd, viz str. 17, dostaneme
fabcd = −2ecfabd + facfbd (3.1)
a dosadíme-li (3.1) do druhé rovnice příslušné vztahu ξa⊥⊥ξb|ξcd, zís-káme po úpravě
0 = fbdfacd.
Za uvedených předpokladů tedy buďto ξb⊥⊥ξd (fbd = 0) nebo ξa⊥⊥ξd|ξc
a zároveň ξc⊥⊥ξd|ξa (facd = 0).
ii) Pokud dosadíme předpoklady fad = fbd = 0, fab =facfbc
1−e2ca fabc =
−2ecfab do první rovnice příslušné vztahu ξa⊥⊥ξb|ξcd, viz str. 17, do-staneme
fabcd =−facfbcfcd − 2ecfabd + 2e3cfabd
1− e2ka dosadíme-li toto do druhé rovnice příslušné vztahu ξa⊥⊥ξb|ξcd, zís-káme
0 = fcdfabd.
Za uvedených předpokladů tedy buďto ξc⊥⊥ξd nebo ξa⊥⊥ξd|ξb a zároveňξb⊥⊥ξd|ξa.
iii) Pokud dosadíme předpoklady fab = fbc = fcd = fad = 0 do prvnírovnice příslušné vztahu ξa⊥⊥ξb|ξcd, dostaneme
fabcd = −2ecfabd − 2edfabc + facfbd. (3.2)
Dosadíme-li (3.2) do druhé rovnice příslušné vztahu ξa⊥⊥ξb|ξcd, zís-káme
fbd =fabc(1− e2d)
facd
. (3.3)
44
Dosadíme-li dále (3.2) a (3.3) do třetí rovnice příslušné ξa⊥⊥ξb|ξcd,získáme
fac =fabd(1− e2c)
fbcd
. (3.4)
Nakonec, pokud (3.2), (3.3) a (3.4) dosadíme do čtvrté rovnice pří-slušné vztahu ξa⊥⊥ξb|ξcd, dostaneme
0 = facdfbcd.
Nutně tedy buďto ξd⊥⊥ξac (facd = 0) nebo ξc⊥⊥ξbd (fbcd = 0).
iv) Postupujeme opět analogicky jako v předchozích případech. Z rovnicpříslušných nezávislostním vztahům ξa⊥⊥ξd|ξb a ξc⊥⊥ξd|ξb vyjádřímefad, fabd, fcd a fbcd a z rovnic příslušných ξa⊥⊥ξb|ξcd vyjádříme fabcd,fabc a facd. Dosazením do poslední rovnice příslušné ξa⊥⊥ξb|ξcd zjistíme,že buďto fbc = 0 (ξb⊥⊥ξc|∅) nebo
0 =(fbd + 1 + eb + ebed + ed) · (fbd − 1− eb + ebed + ed) ·(fbd − 1 + eb + ebed − ed) · (fbd + 1− eb + ebed − ed) ·(facfbc + e2cfab − fab).
(3.5)
Ovšem za předpokladu kladného rozdělení ξbd může být jediný člen napravé straně (3.5) nulový a to facfbc+ e2cfab− fab. Dosadíme-li toto dotřetí rovnice příslušné ξa⊥⊥ξb|ξcd, dostaneme fabc+2ecfacfbc−fabce
2c = 0
(ξa⊥⊥ξb|ξc).
v) Analogicky, za předpokladu fab = fbc = fabc = fbd = 0 použijemeprvní rovnici příslušnou ξa⊥⊥ξb|ξcd, abychom vyjádřili fabcd, druhou,abychom vyjádřili fbcd, a z třetí dostáváme, že buďto fad = 0 (ξa⊥⊥ξd|∅)nebo fabd = 0 (ξa⊥⊥ξb|ξd, ξb⊥⊥ξd|ξa) nebo fad =
facfcd
1−e2c. Pokud za fad
do předchozích rovnic dosadíme facfcd
1−e2c, zjistíme, že buďto fcd = 0
(ξc⊥⊥ξd|∅) nebo fac = 0 (ξa⊥⊥ξc|∅) nebo facd − facde2c + 2ecfacfcd = 0
(ξa⊥⊥ξd|ξc).
vi) Obdobně, lze za předpokladů ukázat, že buďto je fac nebo fad nebofcd rovno nule nebo
0 =(fcde
2a − fcd + fadfac) · (fad + 1 + ed + eaed + ea)·
(fad + 1− ed + eaed − ea) · (fad − 1− ed + eaed + ea) ·(fad − 1 + ed + eaed − ea) · (fadfcd − fac + face
2d),
45
odkud za předpokladu kladně rozděleného ξad plyne, že buďto fcde2a−
fcd+fadfac = 0 nebo fadfcd−fac+face2d = 0. A dosazením za fcd (resp.
fac) ověříme, že skutečně ξc⊥⊥ξd|ξa (resp. ξa⊥⊥ξd|ξc).
3.2 Obecná diskrétní reprezentovatelnost
Problém d–reprezentovatelnosti pro |N | = 4 byl vyřešen F. Matúšem (s přis-pěním M. Studeného) v sérii článků [MS95], [Mat95] a [Mat99]. Závěry byly včitelnější a k čtenáři vlídnější formě následně prezentovány v článcích [SB94]a [Mat97]2.
Klíčovým nástrojem pro popis třídy diskrétně reprezentovatelných mo-delů je následující lemma.
Lemma 21. Nechť I = I(ξ) a I ′ = I(ξ′) jsou d–reprezentovatelné nezávis-lostní modely nad množinou N . Potom I ∩ I ′ je taktéž d–reprezentovatelný.Navíc, pokud jsou ξ a ξ′ pozitivní reprezentace, potom je i I ∩ I ′ pozitivnědiskrétně reprezentovatelný.
Důkaz. Nechť X =∏
Xa a X ′ =∏
X ′a jsou po řadě stavové prostory ξ a
ξ′. Definujme požadovanou reprezentaci ξ̂ modelu I(ξ̂) = I ∩ I ′ na prostoru
X̂ =∏
a∈N
(Xa ×X ′a)
s následujícím rozdělením
P (ξ̂ = (xa, x′a)a∈N) = P (ξ = (xa)a∈N) · P (ξ
′ = (x′a)a∈N).
Tudíž zjevně ξ̂a⊥⊥ξ̂b|ξ̂C právě tehdy, když ξa⊥⊥ξb|ξC a zároveň ξ′a⊥⊥ξ′b|ξ′C .
Jako důsledek lemmatu 21 odvodíme, že minory diskrétně reprezentova-telných modelů jsou taktéž diskrétně reprezentovatelné.
Lemma 22. Třídy d–reprezentovatelných a d+–reprezentovatelných modelůjsou uzavřené na minory.
2Abychom předešli nedorozumění, dovolil bych si upozornit na drobný přetisk v ji-nak bezchybném článku [Mat97] na str. 21, obr. 14. Nad horní čarou v prvních dvoudiagramech má být ∅ namísto ∗.
46
Obrázek 3.2: Generátory třídy d–reprezentovatelných modelů.
Důkaz. Nechť I je obecně (resp. pozitivně) diskrétně reprezentovatelný mo-del a ξ příslušná reprezentace. Potom snadno nahlédneme, že pro E ⊆ Nplatí I [∅E = I(ξN\E).Dále, z definice podmíněné nezávislosti pro diskrétní rozdělení je pro
F ⊆ N minor I [F∅ průnikem nezávislostních modelů příslušných rozdělenínáhodného vektoru ξN\F podmíněnému ξF = xF přes všechny hodnoty
xF , již ξF nabývá s nenulovou pravděpodobností. Platí tedy, že minor I [F∅je průnikem konečně mnoha diskrétně reprezentovatelných modelů a tudížmusí být diskrétně reprezentovatelný.Pro libovolný minor I [FE dostáváme tvrzení kombinací výše uvedených
dvou kroků za pomoci identity (1.11).
Z lemmatu 21 plyne, že průnik konečného počtu d–reprezentovatelnýchmodelů je opět d–reprezentovatelný. Tudíž přirozenou cestou, jak popsatd–reprezentovatelné modely, je nalezení množiny (d–reprezentovatelných)modelů–generátorů takových, že každý netriviální3 d–reprezentovatelný mo-del můžeme zapsat jako průnik těchto generátorů. Ve výše zmíněné literatuřeje ukázáno, že modely–generátory pro |N | = 4 jsou 13 typů a to právě těchzobrazených na obr. 3.2.
Poněkud pikantní je otázka celkového počtu d–reprezentovatelných mo-delů (a typů) pro |N | = 4. V řadě pramenů můžeme nalézt, že počet d–reprezentovatelných nezávislostních modelů nad N = {1, 2, 3, 4} je 18300,
3tj. neprázdný, neúplný
47
viz např. [Stu02], [LR02], [RSSW03], [Šim06b]. . . To však není pravda a sku-tečný počet těchto modelů je 18478 a tyto se rozpadají na 1098 typů.Uvedená čísla byla překontrolována několika počítačovými programy včetněprogramu SG POKUS P. Bočka. Seznam d–reprezentovatelných modelů atypů lze nalézt na přiloženém CD.
Pro úplnost si ještě uveďme seznam inferenčních pravidel vyplynuvšíchz dosažené charakterizace diskrétně reprezentovatelných modelů nad čtyř-prvkovou množinou, jenž byl převzat z [SB94].
Lemma 23. Nechť N je konečná množina a I je d–reprezentovatelný ne-závislostní model nad N . Potom pro a, b, c, d různé prvky N a množinyE ⊆ N \ abcd a F ⊆ N \ abcd platí:
i) {〈ab|E〉, 〈ac|bE〉} ⊆ I ⇐⇒ {〈ac|E〉, 〈ab|cE〉} ⊆ I
ii) {〈ab|cdF 〉, 〈cd|aF 〉, 〈cd|bF 〉, 〈ab|F 〉} ⊆ I ⇐⇒⇐⇒ {〈cd|abF 〉, 〈ab|cF 〉, 〈ab|dF 〉, 〈cd|F 〉} ⊆ I
iii) {〈ab|cdF 〉, 〈ad|bF 〉, 〈cd|aF 〉, 〈bc|F 〉} ⊆ I ⇐⇒⇐⇒ {〈ad|bcF 〉, 〈ab|dF 〉, 〈bc|aF 〉, 〈cd|F 〉} ⊆ I
iv) {〈ac|dF 〉, 〈bd|cF 〉, 〈bc|aF 〉, 〈ad|bF 〉} ⊆ I ⇐⇒⇐⇒ {〈ad|cF 〉, 〈bc|dF 〉, 〈bd|aF 〉, 〈ac|bF 〉} ⊆ I
v) {〈ab|cF 〉, 〈ac|dF 〉, 〈ad|bF 〉} ⊆ I ⇐⇒ {〈ac|bF 〉, 〈ad|cF 〉, 〈ab|dF 〉} ⊆ I
vi) {〈ab|cdF 〉, 〈cd|abF 〉, 〈ac|F 〉, 〈bd|F 〉} ⊆ I ⇐⇒⇐⇒ {〈ac|bdF 〉, 〈bd|acF 〉, 〈ab|F 〉, 〈cd|F 〉} ⊆ I
vii) {〈ab|cF 〉, 〈ab|dF 〉, 〈bc|aF 〉, 〈cd|F 〉} ⊆ I =⇒ 〈ab|F 〉 ∈ I
viii) {〈ab|cF 〉, 〈ac|dF 〉, 〈bc|aF 〉, 〈bd|F 〉} ⊆ I =⇒ 〈ab|F 〉 ∈ I
ix) {〈ab|cF 〉, 〈ac|dF 〉, 〈cd|aF 〉, 〈bd|F 〉} ⊆ I =⇒ 〈ab|F 〉 ∈ I
x) {〈ab|cF 〉, 〈ac|dF 〉, 〈ad|cF 〉, 〈bd|F 〉} ⊆ I =⇒ 〈ab|F 〉 ∈ I
xi) {〈ab|dF 〉, 〈ac|bF 〉, 〈bd|cF 〉, 〈ad|bF 〉} ⊆ I =⇒ 〈ab|cF 〉 ∈ I
xii) {〈ab|dF 〉, 〈ac|bF 〉, 〈bd|cF 〉, 〈bd|aF 〉} ⊆ I =⇒ 〈ab|cF 〉 ∈ I
xiii) {〈ab|dF 〉, 〈ac|bF 〉, 〈bd|cF 〉, 〈bc|dF 〉} ⊆ I =⇒ 〈ab|cF 〉 ∈ I
48
xiv) {〈ab|dF 〉, 〈ac|bF 〉, 〈bd|cF 〉, 〈cd|bF 〉} ⊆ I =⇒ 〈ab|cF 〉 ∈ I
xv) {〈ab|dF 〉, 〈ac|bF 〉, 〈bd|acF 〉, 〈ad|bF 〉} ⊆ I =⇒ 〈ab|cdF 〉 ∈ I
xvi) {〈ab|dF 〉, 〈ac|bF 〉, 〈bd|acF 〉, 〈bd|aF 〉} ⊆ I =⇒ 〈ab|cdF 〉 ∈ I
xvii) {〈ab|cF 〉, 〈ab|dF 〉, 〈ac|dF 〉, 〈cd|abF 〉} ⊆ I =⇒ 〈ab|cdF 〉 ∈ I
xviii) {〈ac|dF 〉, 〈ab|dF 〉, 〈bc|aF 〉, 〈ad|bcF 〉} ⊆ I =⇒ 〈ab|cdF 〉 ∈ I
xix) {〈ab|dF 〉, 〈ac|bF 〉, 〈ac|dF 〉, 〈bd|cF 〉} ⊆ I =⇒ 〈ab|cF 〉 ∈ I
xx) {〈ab|cF 〉, 〈ab|dF 〉, 〈ab|F 〉, 〈cd|abF 〉} ⊆ I =⇒ 〈ab|cdF 〉 ∈ I
xxi) {〈ab|cF 〉, 〈ab|dF 〉, 〈cd|aF 〉, 〈cd|F 〉} ⊆ I =⇒ 〈ab|F 〉 ∈ I
xxii) {〈ab|cF 〉, 〈ac|dF 〉, 〈bd|cF 〉, 〈bd|F 〉} ⊆ I =⇒ 〈ab|F 〉 ∈ I
xxiii) {〈ab|cF 〉, 〈ac|dF 〉, 〈bd|aF 〉, 〈bd|F 〉} ⊆ I =⇒ 〈ab|F 〉 ∈ I
xxiv) {〈ab|cF 〉, 〈ad|bF 〉, 〈bc|adF 〉, 〈ad|F 〉} ⊆ I =⇒ 〈ab|cdF 〉 ∈ I
xxv) {〈ab|cF 〉, 〈ad|bF 〉, 〈bc|adF 〉, 〈cd|bF 〉} ⊆ I =⇒ 〈ab|cdF 〉 ∈ I
3.3 Pozitivní diskrétní reprezentovatelnost
Je s podivem, že ač se v praxi s konceptem kladného diskrétního rozdělenímsetkáváme poměrně často, nebyla dosud reprezentovatelnost nezávislostníchmodelů za pomoci pozitivního diskrétního rozdělení podrobena důkladněj-šímu zkoumání a výsledky jsou zatím spíše skromné.
Je zjevné, že množina d+–reprezentovatelných modelů je podmnožinoud–reprezentovatelných modelů. Jsou známy dvě podmínky, jež musí navícd+–reprezentovatelný model splňovat: podmínku (1.10) z druhé části lem-matu 8 a podmínku ze [Spo94], která je v mírně pozměněné podobě uvedenav následujícím lemmatu.
Lemma 24. Nechť a, b, c, d jsou různé prvky množiny N . Jestliže I je d+–reprezentovatelný nezávislostní model nad N takový, že
{〈ab|cd〉, 〈cd|ab〉, 〈cd|a〉} ⊆ I, (3.6)
potom〈cd|b〉 ∈ I ⇐⇒ 〈cd|∅〉 ∈ I.
49
Důkaz. Nechť ξ je d+–reprezentace modelu I. Za předpokladu (3.6) lzevýraz P (ξabcd = xabcd) rozepsat jako
P (ξabc=xabc)P (ξabd=xabd)P (ξab=xab)
nebo také jakoP (ξac=xac)P (ξad=xad)P (ξbcd=xbcd)
P (ξa=xa)P (ξcd=xcd). Platí tedy identita
P (ξabc = xabc)P (ξabd = xabd)P (ξab = xab)
=P (ξac = xac)P (ξad = xad)P (ξbcd = xbcd)
P (ξa = xa)P (ξcd = xcd).
Zvolíme-li xa libovolné, pevné, můžeme předchozí rovnost přepsat jako
P (ξbcd = xbcd) = P (ξcd = xcd)g(xbc)h(xbd), (3.7)
kde g a h jsou nějaké funkce s oborem hodnot (0,∞). Pokud dále předpo-kládáme ξc⊥⊥ξd neboli P (ξcd = xcd) = P (ξc = xc)P (ξd = xd), dostáváme ze(3.7) dle lemmatu 1, části vi), že i ξc⊥⊥ξd|ξb. A naopak, pokud předpoklá-dáme ξc⊥⊥ξd|ξb a zafixujeme v (3.7) hodnotu xb, dostáváme ξc⊥⊥ξd.
Nad N = {1, 2, 3, 4} existuje 5547 d–reprezentovatelných modelů (356typů), které navíc splňují podmínku (1.10) z lemmatu 8 a podmínku z lem-matu 24 a určují nám tedy odhad shora pro počet pozitivně reprezentova-telných modelů nad N . Na základě lemmatu 21 můžeme tuto nadmnožinumnožiny d+–reprezentovatelných modelů opět popsat množinou modelů–generátorů, která ji za pomoci operace průniku generuje. Seznam modelů–generátorů (resp. jejich 23 typů) lze nalézt na přiloženém CD.
K nalezení odhadu zdola jsme využili 139 b+–reprezentovatelných typůnalezených v oddíle 3.1. Jelikož z lemmatu 21 víme, že množina d+–repre-zentovatelných modelů je uzavřená na operaci průniku, dostáváme aplikacíuzávěru na průnik množinu 4555 modelů (299 typů), jež jsou nutně d+–reprezentovatelné. Zbývalo tedy rozhodnout o d+–reprezentovatelnosti 57typů P1–P57, které jsou znázorněny na obr. 3.3.
Další vlastnosti charakteristické pro d+–reprezentovatelnost se však au-torovi nalézt nepodařilo. Pokud by existovaly, musel by jejich důkaz býtzaložen na jiných „principechÿ než je tomu u grafoidové či Spohnovy vlast-nosti.Se značným usilím se byla ověřena d+–reprezentovatelnost P54 a P49 (a
tudíž díky lemmatu 21 i P52, P50 a P12), pro reprezentace viz tab. 3.1. Pra-covní (zatím nepotvrzená, ani nevyvrácená) hypotéza zní, že všechny typyna obr. 3.3 jsou reprezentovatelné. K jejímu důkazu by bylo třeba naléztreprezentace pro P57, P46, P45 a P37, P41 a P32, P39 a P30, P24, P19, P3,
50
xabcd P54 P49
0 0 0 0 1
4· 1·1·622
3·3·83325
1
3· 1·1·333·7·112
0 0 0 1 1
4· 1·1·827033·3·83325
1
3· 1·1·793·7·112
0 0 1 0 1
4· 1·2·622
3·3·83325
1
3· 1·6·333·7·112
0 0 1 1 1
4· 1·2·827033·3·83325
1
3· 1·6·793·7·112
0 1 0 0 1
4· 2·1·622
3·3·83325
1
3· 2·1·333·7·112
0 1 0 1 1
4· 2·1·827033·3·83325
1
3· 2·1·793·7·112
0 1 1 0 1
4· 2·2·622
3·3·83325
1
3· 2·6·333·7·112
0 1 1 1 1
4· 2·2·827033·3·83325
1
3· 2·6·793·7·112
1 0 0 0 1
4· 1·1·299
4·4·27775
1
3· 1·1·12·5·8
1 0 0 1 1
4· 1·1·274764·4·27775
1
3· 1·1·72·5·8
1 0 1 0 1
4· 1·3·299
4·4·27775
1
3· 1·4·12·5·8
1 0 1 1 1
4· 1·3·274764·4·27775
1
3· 1·4·72·5·8
1 1 0 0 1
4· 3·1·299
4·4·27775
1
3· 1·1·12·5·8
1 1 0 1 1
4· 3·1·274764·4·27775
1
3· 1·1·72·5·8
1 1 1 0 1
4· 3·3·299
4·4·27775
1
3· 1·4·12·5·8
1 1 1 1 1
4· 3·3·274764·4·27775
1
3· 1·4·72·5·8
xabcd P54 P49
2 0 0 0 1
3· 1·1·1
2·3·100
1
3· 1·1·16·3·7
2 0 0 1 1
3· 1·1·992·3·100
1
3· 1·1·66·3·7
2 0 1 0 1
3· 1·2·1
2·3·100
1
3· 1·2·16·3·7
2 0 1 1 1
3· 1·2·992·3·100
1
3· 1·2·66·3·7
2 1 0 0 1
3· 1·1·1
2·3·100
1
3· 5·1·16·3·7
2 1 0 1 1
3· 1·1·992·3·100
1
3· 5·1·66·3·7
2 1 1 0 1
3· 1·2·1
2·3·100
1
3· 5·2·16·3·7
2 1 1 1 1
3· 1·2·992·3·100
1
3· 5·2·66·3·7
3 0 0 0 1
6· 1·91·1
3·120·101–
3 0 0 1 1
6· 1·91·1003·120·101
–
3 0 1 0 1
6· 1·29·1
3·120·101–
3 0 1 1 1
6· 1·29·1003·120·101
–
3 1 0 0 1
6· 2·91·1
3·120·101–
3 1 0 1 1
6· 2·91·1003·120·101
–
3 1 1 0 1
6· 2·29·1
3·120·101–
3 1 1 1 1
6· 2·29·1003·120·101
–
Tabulka 3.1: Pravděpodobnostní distribuce reprezentací modelů P54 a P49
P2, celkem tedy 12 reprezentací, neboť za předpokladu, že tyto jsou repre-zentovatelné dostaneme zbylé průsekem s již známými d+–reprezentovatel-nými modely. Naopak pokud výše uvedená hypotéza neplatí, musí existovatvlastnost, která vyloučí reprezentovatelnost alespoň jednoho ze zmíněných12 typů.
Shňme tedy dosažené poznatky do závěrečné věty:
Věta 4. Nad množinou N = {1, 2, 3, 4} existuje 18478 diskrétně reprezento-vatelných nezávislostních modelů 1098 typů. Kladně reprezentovatelných je4607–5547 z nich (304–356 typů).
51
Obrázek 3.3: Typy, jejíž reprezentace musí být nalezena pro ověření výšeuvedené hypotézy na str. 50.
52
3.4 Neexistence konečné charakterizace
V tomto oddílu dokážeme, že diskrétně, ani binárně reprezentovatelné ne-závislostní modely nelze charakterizovat konečným seznamem zakázanýchminorů. Postupovat budeme obdobně jako v případě Gaussovsky reprezen-tovatelných modelů: ukážeme, že pro libovolné n ≥ 4 není model
Jn = {〈12|3〉, 〈13|4〉, . . . , 〈1(n− 1)|n〉, 〈1n|2〉}
d–reprezentovatelný, zatímco jeho (n−1)–minory jsou b+–reprezentovatelné,a následně využijeme lemmatu 9 z oddílu 1.4.Uvědomme si, že třídy b–reprezentovatelných a b+–reprezentovatelných
modelů konečnou charakterizaci seznamem zakázaných minorů mít nemohouuž proto, že nejsou uzavřené na minory. Z níže uvedených argumentů všakvyplývá, že konečná charakterizace neexistuje pro libovolnou třídu diskrét-ních rozdělení, která je uzavřená na minory a zahrnuje b+–reprezentovatelnémodely. Příkladem je třída d+–reprezentovatelných modelů.
Lemma 25. Pro libovolné n ≥ 4 je nezávislostní model
Jn = {〈12|3〉, 〈13|4〉, . . . , 〈1(n− 1)|n〉, 〈1n|2〉} (3.8)
zakázaným minorem pro třídu diskrétně reprezentovatelných modelů.
Důkaz. Předpokládejme, že by existoval d–reprezentovatelný nezávislostnímodel I nad množinou {1, . . . , n} ∪ EF takový, že I [FE = Jn. Potom bydle lemmatu 22 byl d–reprezentovatelný i model Jn. Označme příslušnou d–reprezentaci ξ a dále pokračujme Studeného důkazem převzatým z [Stu92],str. 6.Z druhé části lemmatu 2 pro nezávislostní vztahy ξ1⊥⊥ξ2|ξ3, ξ1⊥⊥ξ3|ξ4,
. . . ,ξ1⊥⊥ξn−1|ξn, ξ1⊥⊥ξn|ξ2 vyplývá, že
0 =[MI(ξ123) +MI(ξ3)−MI(ξ23)−MI(ξ13)
]+
+[MI(ξ134) +MI(ξ4)−MI(ξ34)−MI(ξ14)
]+
+ · · ·+
+[MI(ξ12n) +MI(ξ2)−MI(ξ2n)−MI(ξ12)
]
=[MI(ξ123) +MI(ξ2)−MI(ξ23)−MI(ξ12)
]+
+[MI(ξ134) +MI(ξ3)−MI(ξ34)−MI(ξ13)
]+
+ · · ·+
+[MI(ξ12n) +MI(ξn)−MI(ξ2n)−MI(ξ1n)
],
53
přičemž členy v závorkách musí být dle lemmatu 2 nezáporné a tedy nulové.To však znamená, že nutně ξ1⊥⊥ξ3|ξ2, ξ1⊥⊥ξ4|ξ3, . . . , ξ1⊥⊥ξ2|ξn, což je spors předpokladem I(ξ) = Jn.
Lemma 26. Pro libovolné n ≥ 3 jsou nezávislostní modely
In = {〈12|3〉, 〈13|4〉, . . . , 〈1(n− 1)|n〉},
I∗n = {〈12|∅〉}, I∗∗
n = ∅
kladně binárně reprezentovatelné nad množinou N = {1, . . . , n}.
Důkaz. Důkaz je analogický k důkazu lemmatu 18. Uvažme binární rozděleníξ takové, že
∀a : ea = 0,
∀a > 1 : e1a = ǫn−a+1,
∀a, b > 1, a 6= b : eab = ǫ,
∀A ⊆ N, |A| > 2 : eA = 0.
Pro ǫ > 0 dostatečně blízko 0 se zjevně jedná o kladné binární rozdělení aníže ukážeme, že I(ξ) = In. Podmínku pro platnost ξa⊥⊥ξb|ξC z lemmatu 7lze v našem případě přeformulovat jako platnost tvrzení4, že je výraz
eab ·
1 +∑
D⊆C,|D|=2
eD
∏
d∈D
xd
−(∑
c∈C
eacxc
)·
(∑
c∈C
ebcxc
)(3.9)
roven nule pro každé xC ∈ {−1, 1}C .
i) Pro a, b ∈ {1, 2, . . . , n} je eab 6= 0, tudíž zjevně neplatí ξa⊥⊥ξb.
ii) Pro a, b ∈ {2, 3, . . . , n} a množinu C, ∅ 6= C ⊆ {1, . . . , n} \ ab, dostá-váme dosazením do vztahu (3.9) pro ξa⊥⊥ξb|ξC
ǫ(1 + ǫ(. . . ))− ǫ2(. . . ), (3.10)
kde „. . . ÿ je zástupný symbol pro polynom v ǫ. Výraz (3.10) je řádověǫ, neboť krom jediného jsou všechny členy řádu ǫ2 či vyššího a tudížpro ǫ dostatečně malé je zjevně nenulový. Tudíž ani tvrzení ξa⊥⊥ξb|ξC
nemůže býti platným.
4Povšimněme si, že se na rozdíl od Gaussovského případu jedná o větší počet rovnic.
54
iii) Pro a ∈ {2, 3, . . . n} a neprázdnou množinu C = {c1, c2, . . . , ck} ⊆{2, 3, . . . , a− 1}, nabývá výraz (3.9) pro ξa⊥⊥ξ1|ξC hodnoty
ǫn−a+1(1 + ǫ(. . . ))− ǫn−a+3(. . . ) 6= 0.
Proto ani tvrzení ξa⊥⊥ξ1|ξC nemůže býti (pro ǫ dostatečně malé) plat-ným.
iv) Analogicky, pro a ∈ {2, 3, . . . n} a C = {c1, . . . , ck} ⊆ {2, 3, . . . , n} \ atakovou, že m := maxc∈C c > a+ 1, nabývá výraz (3.9) pro ξa⊥⊥ξ1|ξC
a xC = {1}C nenulové hodnoty
ǫn−a+1(. . . )− |C|ǫn−m+2 − ǫn−m+3(. . . ) 6= 0.
Proto ani v tomto případě tvrzení ξa⊥⊥ξ1|ξC nemůže býti platným.
v) Zbývá vyšetřit případ a ∈ {2, 3, . . . n− 1} a C = {(a + 1), c2, . . . , ck},∅ 6= C ⊆ (a + 1) ∪ {2, 3, . . . , a − 1}. Pro C dvou či víceprvkovou axC = {1}C je výraz (3.9) roven
ǫn−a+1(1+ǫ(. . . ))−|C|ǫn−a+1−ǫn−a+2(. . . ) = (1−|C|)ǫn−a+1+ǫn−a+2(. . . ),
což (pro ǫ dostatečně malé) je nenulové a tudíž ani tvrzení ξ1⊥⊥ξa|ξC
neplatí.
Avšak pokud je naopak C = {a+1} jednoprvková, potom pro libovolnéx(a+1) ∈ {−1, 1} platí
1ǫn−a+1 − x2(a+1)ǫǫn−a = 0.
Skutečně tedy (dle lemmatu 7) platí ξ1⊥⊥ξa|ξa+1.
Obdobně lze ukázat, že pokud definujeme binární rozdělení ξ∗ jako
∀a : e∗a = 0,
e∗12 = 0,
∀a, b, a 6= b, a+ b > 3 : e∗ab = ǫ,
∀A ⊆ N, |A| > 2 : e∗A = 0,
dostaneme kladnou binární reprezentaci I∗n a pro ξ∗∗
∀a : e∗a = 0,
∀a, b, a 6= b : e∗ab = ǫ,
∀A ⊆ N, |A| > 2 : e∗A = 0,
kladnou binární reprezentaci I∗∗n .
55
S využitím lemmatu 9 dostáváme jako důsledek lemmat 25 a 26 násle-dující závěrečné tvrzení:
Věta 5. Třídy (obecně) diskrétně, kladně diskrétně, (obecně) binárně, anikladně binárně reprezentovatelných nezávislostních modelů nejsou konečněcharakterizovatelné.
3.5 Závěr kapitoly
V této kapitole jsme diskutovali možná rozšíření známého výsledku o dis-krétní reprezentovatelnosti nad čtyřmi veličinami na pozitivní, případně bi-nární pozitivní reprezentovatelnost. Uvedli jsme si několik charakteristik bi-nárně pozitivně reprezentovatelných modelů a vyslovili hypotézu o pozitivnědiskrétně reprezentovatelných modelech nad N = {1, 2, 3, 4}. Pro její ově-ření nebo vyvrácení je třeba rozhodnout o d+–reprezentovatelnosti modelůP2, P3, P19, P24, P30, P32, P39, P37, P41, P45, P46 a P57 z obr. 3.3.Připomeňme otevřený problém zmíněný již v závěru 2. kapitoly a to
vztah tříd g+–reprezentovatelných a b+–reprezentovatelných modelů. Z 53g+–reprezentovatelných typů byla nalezena b+–reprezentace pro 51 z nich,nerozhodnuté zůstávají M25 a M37 z obr. 2.3. Binární reprezentaci modelulze z Gaussovské odvodit přímo, jestliže jsou prvky varianční matice mimodiagonálu blízko nule, na základě poznámky na konci pododdílu 1.2.3. Ta-kovou g+–reprezentaci však nemáme pro všechny typy k dispozici.
56
Kapitola 4
Grafické nezávislostní modely
V této kapitole se budeme věnovat odhadům v nezávislostních modelech.Každý nezávislostní model lze totiž chápat při daném distribučním rámcijako „statistický modelÿ, tj. určitou rodinu pravděpodobnostních rozdělení.Určení tohoto statistického modelu je proces skládající se ze tří částí: iden-tifikace samotného nezávislostního modelu, parametrizaci modelu vzhledemk omezením na podmíněnou nezávislost a odhadu těchto parametrů.V první oddíle se budeme věnovat teorii tzv. „grafických modelůÿ s dů-
razem zvláště na třídu tzv. rozložitelných modelů (tj. těch modelů, jejichžnezávislostní strukturu lze reprezentovat jak neorientovaným, tak orientova-ným acyklickým grafem), která má v praxi nejvíce aplikací. V druhé částise bude zabývat statistickými modely pro nezávislostní, zvláště pak grafickémodely.A konečně poslední oddíl bude věnován hledání nezávislostního modelu
na základě dat. Za pomoci simulace se pokusíme zodpovědět otázku, jakvelké chyby se dopouštíme, pokud se omezujeme ze všech g+–reprezentova-telných nezávislostních modelů pouze na modely grafické.
Na začátek si neodpustím připojit několik autorových poznámek k danéproblematice. Pro nově příchozího do této oblasti může být tato diskuzeobtížně stravitelná a nezbývá než mu doporučit přejít přímo na oddíl 4.1 (apřípadně se k ní později vrátit).Grafické nezávislostní modely1 jsou specifickou podtřídou nezávilostních
modelů, kde seznam tripletů příslušných modelu lze získat za pomoci něja-
1V literatuře se obvykle hovoří o „grafických modelechÿ a pod tímto pojmem je myš-lena jak nezávislostní struktura, tak i přímo pravděpodobnostní rozdělení této struktuřeodpovídající. Tedy celý statistický a nikoli pouze nezávislostní model.
57
Obrázek 4.1: Dvě praktické ukázky aplikace grafických modelů.
kého (separačního) kritéria z neorientovaného či orientovaného acyklickéhografu.
Příklad 1. Dva intuitivně pochopitelné příklady lze nalézt na obr. 4.1. Mezipočasím včera a zítra zjevně existuje jistá korelace, která však vymizí, jestližejiž známe dnešní počasí. Analogicky, přestože je úspěch studenta pozitivněkorelován s body z přijímacích zkoušek z biologie, neznamená to ještě nutně,že je kvalita tohoto testu dostačující. Pokud nezávislostní schéma vypadájako na obr. 4.1, je za předpokladu znalosti počtu bodů z chemie a fyziky jižznalost výsledku přijímaček z biologie pro predikci úspěchu studenta neuži-tečná. Dané dvě veličiny jsou totiž podmíněně nezávislé, neboli – vezmeme-liúspěch jako závislou veličinu – je regresní2 koeficient příslušný bodům z bio-logie nulový. Studenti by tedy měli být přijímáni pouze na základě váženéhoprůměru bodů z chemie a fyziky, biologická část by se neměla započítávat(nebo by se měl způsob testování změnit). Jedná se mimochodem o reálnoustudii na 1. LF UK, viz [ŠŠ06].
Použití grafů má jak interpretační výhodu, totiž že neorientované hranyodpovídají intuitivně pochopitelnému vztahu „míti souvislostÿ, orientované„býti příčinouÿ, tak je výhodný i z teoretického hlediska. Obecně totiž nenímožné u zvoleného nezávislostního modelu identifikovat parametry pravdě-podobnostního rozdělení (v daném distribučním rámci), jež maximalizuje
2Protože úspěch studenta byl měřen jako schopnost dokončit studium (binární veli-čina), jednalo by se v našem případě spíše o logistickou regresi.
58
pro daná data věrohodnostní funkci. Taktéž operace marginalizace či pod-mínění jsou v grafických modelech obvykle snáze proveditelné, viz [CLDS99],[Nea03], [CGH96], [Bou95], [Cas02], [Drt04] a [Koč01].
Obrázek 4.2: Tři DAGy reprezentující tentýž nezávislostní model.
Zmiňme také alespoň tři nejčastější problémy spojené s analýzou datza pomoci grafických modelů. Za prvé, v případě orientovaného grafu častonedokážeme rozlišit směr „kauzalityÿ. Tento problém je principiální a nelzejej vyřešit, pokud data pocházejí z jediného časového okamžiku: grafům naobr. 4.2 odpovídá totiž tentýž nazávislostní model. Z praktického hlediskanás ale „směr kauzalityÿ nesmírně zajímá, neboť odpovídá na otázku, co sestane, když nějakou proměnnou zásahem zvenčí pevně nastavíme na danouhodnotu, viz [Lau01].Dalším problémem je obrovské množství grafických nezávislostních mo-
delů a marná snaha o identifikaci jednoho „správnéhoÿ modelu při rostoucímmnožství (≈ desítky) náhodných veličin a reálném množství dat (≈ tisíce po-zorování). Přestože se teoreticky pravděpodobnost výběru správného modeluasymptoticky blíží jedné, v reálných případech se obvykle věrohodnost ně-kolika nejlepších nezávislostních modelů liší pouze nepatrně, přestože jejichpříčinná interpretace může být zcela jiná. Proto je velice užitečné ubezpečitse proto o důvěryhodnosti dosažených výsledků za pomoci simulační studie,viz např. [Šim04].V neposlední řadě je třeba mít na paměti, že grafických je pouze nepa-
trný díl ze všech nezávislostních modelů. Přesněji řečeno, logaritmus počtugrafických nezávislostních modelů roste polynomiálně v závislosti na počtunáhodných veličin, zatímco logaritmus počtu všech nezávislostních modelůroste exponenciálně (detaily v [Stu05]).
Existují i jiné způsoby reprezentace nezávislostního modelu, v prvé řadětzv. řetězcové grafy (viz [Lau96]), používající v grafu zároveň orientovanéi neorientované hrany, a různá jejich rozšíření o další typy hran, viz např.[RS02] a [CW96]. Jinou možnou volbou jsou tzv. „imsetyÿ, nezávislostní
59
model reprezentující celočíselné vektory, viz [Stu05], s řadou zajímavýchteoretických problémů (viz např. [ŠS04]).
4.1 Teorie grafů
4.1.1 Neorientované grafy
Neorientovaným grafem (zkráceně3 UG) G = (N,E) budeme rozumětkonečnou množinu vrcholů N a množinu neorientovaných hran E,
E ⊆
(N
2
)= {ab; a, b ∈ N, a 6= b}.
Řekneme, že graf (N ′, E ′) je podgrafem (N,E), pokud N ′ ⊆ N a E ′ ⊆(N ′
2
)∩E. Jestliže E ′ =
(N ′
2
)∩E, budeme mluvit o indukovaném podgrafu
(značíme GN ′). Graf je úplný, pokud E =(
N
2
). Podmnožinu množiny vr-
cholů A ⊆ N nazveme úplnou, jestliže indukuje úplný podgraf. MnožinuA ⊆ N nazveme klikou, pokud je úplná a maximální vzhledem k relaci „⊆ÿ(neexistuje úplná vlastní nadmnožina A).Cesta mezi vrcholy a a b je posloupnost k ≥ 1 vrcholů a = c1, . . . , ck = b
taková, že cici+1 ∈ E, i = 1, 2, . . . , k − 1. Vrcholy a a b nazveme spojené(značíme a ∼ b) pokud existuje cesta je spojující. Množiny vrcholů A a Bjsou spojené, pokud existují vrcholy a ∈ A a b ∈ B, které jsou spojené.Povšimněme si, že relace spojitosti mezi vrcholy grafu je zjevně ekvivalencí,její třídy budeme nazývat komponentami grafu.Množinou sousedů množiny A ⊆ N rozumíme
ne(A) = {b; a ∈ A, b ∈ N \ A, ab ∈ E}.
Nechť A, B, C jsou po dvou disjunktní podmnožiny N . Řekneme, že Codděluje A a B (značíme A⊥B|C), jestliže každá cesta mezi A a B obsahujevrchol z C neboli v grafu GN\C nejsou A a B spojené. Pro a, b ∈ N nazvememnožinu C ⊆ N minimálním ab–separátorem, pokud a⊥b|C v grafu G aje minimální taková vzhledem k relaci „⊆ÿ (neexistuje vlastní podmnožinaC oddělující a a b).Nezávislostní model odvozený globálním separačním kritériem z ne-
orientovanému grafu G je nezávislostní model nad N definovaný následovně
IgUG(G) = {〈ab|C〉; a⊥b|C v grafu G} .
3z anglického „undirected graphÿ
60
Dále definujeme nezávislostní modely odvozené z lokálního a párovéhokritéria
I lUG(G) = {〈ab|C〉; ne(a) ⊆ C, ab /∈ E} ,
IpUG(G) = {〈ab|N \ ab〉; ab /∈ E} .
Povšimněme si, že pro libovolný graf G zjevně platí
IpUG(G) ⊆ I
lUG(G) ⊆ I
gUG(G). (4.1)
Rozbor, kdy jsou inkluze v 4.1 ostré, lze nalézt v [Mat92].
Obrázek 4.3: Neorientovaný graf G.
Příklad 2. Ilustrujme zavedené pojmy na grafu G z obr. 4.3. Povšimněmesi, že hrana mezi dvěmi vrcholy je znázorněna čárou tyto vrcholy spojující.G123 je úplný a {1, 2, 3} je klika G. Ovšem {1, 2} klikou G není, přestože G12je úplný. Libovolné dva vrcholy grafu jsou spojené cestou. Množina sousedůvrcholu 4 je ne(4) = {2, 3}. Platí 1⊥4|23 a {2, 3} je minimální 14–separátor.Taktéž platí 1⊥4|235, ovšem {2, 3, 5} není minimálním ab–separátorem prožádnou volbu a, b.
4.1.2 Orientované acyklické grafy
V následujících dvou oddílech je mnoho důkazů vynecháno či nahrazenoodkazem s poznámkou „snadné cvičeníÿ, aby čtenář nebyl ošizen o radostdokázat si daná tvrzení sám.Orientovaným acyklickým grafem (zkráceně4 DAG) G = (N,E)
budeme rozumět konečnou množinu vrcholů N a množinu orientovanýchhran E,
E ⊆ {(a, b); a, b ∈ N, a 6= b}
4z anglického „directed acyclic graphÿ
61
splňující podmínku, že v grafu neexistuje orientovaný cyklus, t.j. posloup-nost k ≥ 2 vrcholů c1, . . . , ck taková, že (ci, ci+1) ∈ E, i = 1, 2, . . . , k − 1 anavíc (ck, c1) ∈ E. Podgraf a indukovaný podgraf definujeme analogicky jakov případě neorientovaného grafu. Kostrou orientovaného grafu G = (N,E)rozumíme neorientovaný graf
G∼ = (N, {ab; (a, b) ∈ E ∨ (b, a) ∈ E}).
Obrázek 4.4: Graf G, jeho kostra G∼ a zmoralizovaný graf Gm.
Orientovanou cestou mezi vrcholy a a b (značíme a b) nazvemeposloupnost k ≥ 2 vrcholů a = c1, . . . , ck = b takovou, že (ci, ci+1) ∈ E,i = 1, 2, . . . , k − 1. Množinou rodičů, dětí, předků a následníků5 množinyA ⊆ N rozumíme po řadě množiny
pa(A) = {b; a ∈ A, b ∈ N \ A, (b, a) ∈ E},
ch(A) = {b; a ∈ A, b ∈ N \ A, (a, b) ∈ E},
an(A) = {b; a ∈ A, b ∈ N \ A, b a},
de(A) = {b; a ∈ A, b ∈ N \ A, a b}.
Nechť A, B, C jsou po dvou disjunktní podmnožiny N . Řekneme, že Codděluje A a B (značíme A⊥B|C) v acyklickém orientovaném grafu G,jestliže mezi A a B není hrana (∀a ∈ A, b ∈ B : (a, b) /∈ E, (b, a) /∈ E) a prokaždou (neorientovanou) cestu v G∼ o k > 2 vrcholech A ∋ a = d1, . . . , dk =b ∈ B existuje vrchol di, jež není na kraji (1 < i < k), pro nějž nastávájedna z následujících dvou možností
• (di−1, di) ∈ E ∧ (di+1, di) ∈ E a zároveň(di ∪ de(di)
)∩ C = ∅
•[(di−1, di) /∈ E ∨ (di+1, di) /∈ E
]a zároveň di ∈ C.
5Většina autorů užívá mírně odlišnou definici, kdy vrchol je sám sobě předkem anásledníkem.
62
Existuje ekvivalentní způsob, jak definovat oddělitelnost v orientovanémgrafu G = (N,E), a to za pomoci moralizačního grafu6, tj. neorientova-ného grafu
Gm =(N, {ab; a, b ∈ N, a 6= b, (ab je hrana v G∼) ∨ (ch(a)∩ ch(b) 6= ∅)}
).
Příklad lze nalézt na obr. 4.4.
Lemma 27. Nechť G = (N,E) je DAG a A, B, C jsou po dvou disjunktnípodmnožiny N . Potom A⊥B|C vzhledem ke G právě tehdy, když A⊥B|Cvzhledem ke (GABC∪an(ABC))m.
Důkaz. [Lau96], str. 48–49 (nepříliš těžké cvičení)
Nezávislostní model příslušný orientovanému acyklickému grafu G de-finujeme analogicky jako pro UG, tzn. jako nezávislostní model nad N
IDAG(G) = {〈ab|C〉; a⊥b|C v grafu G} .
Jak ukazuje obr. 4.2, různým orientovaným acyklickým grafům můžebýt příslušný tentýž nezávislostní model. Následující lemma (převzaté z[CGH96], věta 6.16) charakterizuje takové DAGy.
Lemma 28. Nechť G1 = (N,E1) a G2 = (N,E2) jsou DAGy. Potom platí
IDAG(G1) = IDAG(G2)
právě tehdy, když kostry grafů jsou totožné G1∼ = G2
∼ a v obou grafech sena týchž místech vyskytují tzv. v–konfigurace, tj. indukované podgrafy typui→ j ← k.
Obrázek 4.5: Orientovaný acyklický graf G.
6„Moralizaceÿ znamená, že se „hranou sezdajíÿ vrcholy, jež mají společné dítě.
63
Příklad 3. Ilustrujme zavedené pojmy na grafu G z obr. 4.5. Hranu (a, b)je znázorňujeme jako šipku z vrcholu a do vrcholu b. Graf je acyklický, k po-rušení tohoto předpokladu by došlo například přidáním hrany (4, 5). Platípa(5) = ∅, ch(3) = {1, 2}, an({1, 2}) = {3, 4, 5}, de(4) = {1, 2}.Nezávislostní model příslušný grafu G je IDAG(G) =
{〈14|23〉, 〈14|235〉,
〈15|3〉, 〈15|34〉, 〈15|23〉, 〈15|234〉, 〈25|3〉, 〈25|34〉, 〈25|13〉, 〈25|134〉, 〈45|3〉,〈45|13〉, 〈45|23〉, 〈45|123〉
}.
Povšimněme si, že tentýž nezávislostní model lze odvodit i z neoriento-vaného grafu na obr. 4.3.
4.1.3 Rozložitelné grafy
Rozložitelný graf je speciální typ UG s množstvím překvapivých vlastností.Uvedeme rekurzivní definici podle počtu vrcholů grafu:Neorientovaný graf G = (N,E) nazveme rozložitelný, jestliže je buďto
úplný nebo existuje rozklad množiny vrcholů N = ABC na tři po dvoudisjunktní množiny A 6= ∅, B 6= ∅, C a platí, že A⊥B|C v grafu G, GC jeúplný a GAC , GBC jsou rozložitelné.
Lemma 29. Nechť G = (N,E) je neorientovaný graf. Potom jsou následu-jící tvrzení ekvivalentní.
i) Graf G je rozložitelný.
ii) Graf G je chordální, tzn. neobsahuje jako indukovaný podgraf kruž-nici
Cn =({c1, . . . , cn}, {c1c2, c2c3, . . . , cn−1cn, cnc1}
)
o n ≥ 4 vrcholech.
iii) Všechny minimální ab–separátory jsou úplné.
iv) Existuje uspořádaní klik grafu C1, . . . , Ck takové, že tvoří perfektníposloupnost, tj. platí
∀i, 1 < i ≤ k ∃j < i : Ci ∩i−1⋃
k=1
Ck ⊆ Cj. (4.2)
v) Existuje uspořádání vrcholů grafu N = {c1, . . . , cn} takové, že(ci ∪ ne(ci)
)∩ {c1, . . . , ci}, i = 1, . . . , n (4.3)
tvoří posloupnost úplných množin.
64
Důkaz. [Lau96], (i)⇔ (ii)⇔ (iii), str. 9, (i)⇔ (iv)⇔ (v), str. 19.
Příklad rozložitelného grafu lze nalézt na obr. 4.3. Algoritmy, jak naléztuspořádání klik (4.2) a vrcholů (4.3), lze nalézt např. v dodatku k [Šim03].
Nezávislostní modely odvoditelné z rozložitelných grafů jsou právě ty, ježlze odvodit jak z UG, tak z DAG.
Lemma 30. Nechť I je nezávislostní model nad N . Potom jsou následujícídvě tvrzení ekvivalentní
i) Existuje rozložitelný graf G takový, že I = IgUG(G).
ii) Existují UG G′ a DAG G′′ takové, že I = IgUG(G
′) = IDAG(G′′).
Důkaz. Pro přehled provázanosti těchto i jiných tříd modelů, viz [Cas02],str. 36, nebo [CGH96], str. 261.
K druhému tvrzení z předchozího lemmatu ještě poznamenejme, že pří-slušný UG G′ a DAG G′′ jsou navzájem provázané následujícím způsobem:G′ = (G′′)∼ = (G′′)m a naopak G′′ získáme z G′, pokud zorientujeme jehohrany ve směru uspořádání (4.3) z lemmatu 29.
4.2 Pravděpodobnostní rozdělení nad grafic-kými nezávislostními modely
Definice 12. Nechť I je nezávislostní model. Potom rodinu takových ná-hodných rozdělení vektoru ξ, že platí I ⊆ I(ξ), budeme značit P(I).
Obvykle nás budou zajímat rozdělení v daném distribučním rámci, kterýbude naznačen příslušným dolním indexem. Např. Pg({〈12|∅〉}) je třídavšech Gaussovských rozdělení náhodného vektoru ξ takových, že ξ1⊥⊥ξ2 ne-boli prvek varianční matice σ1·2 je nulový.
Pro pozitivní reprezentace rodiny rozdělení odvozené z UG párovým,lokálním a globálním kritériem splývají. Z tohoto důvodu budeme později vtextu indexy „glÿ, „locÿ a „parÿ u pozitivních rodin rozdělení vynechávat.
Lemma 31. Označíme-li P+(I) průnik P(I) s třídou všech pozitivních roz-dělení, potom pro libovolný neorientovaný graf G platí
P+(IparUG(G)) = P+(I
locUG(G)) = P+(I
glUG(G)).
65
Důkaz. Cvičení na použití vlastnosti (1.10) z lemmatu 8, viz [Lau96], str.34.
Pro acyklický orientovaný graf G lze za pomoci moralizačního kritérianahlédnout, že pro všechna rozdělení z P(IDAG(G)) platí, že jejich hustotulze za pomoci lemmatu 1 faktorizovat následujícím způsobem
f(x) =∏
a∈N
fa|pa(a)(xa|xpa(a)) =∏
a∈N
fa∪pa(a)(xa∪pa(a))fpa(a)(xpa(a))
za konvence 00= 0.
4.2.1 Faktorizace pravděpodobnostních rozdělení nadrozložitelnými grafy
Nyní se podrobněji podíváme, jak tyto rodiny rozdělení vypadají, pokud jegraf G rozložitelný.
Lemma 32. Nechť G je rozložitelný graf a C1, C2, . . . Cm perfektně uspořá-daná posloupnost jeho klik. Označíme-li7 dále
Si = Ci \i−1⋃
j=1
Cj, i = 2, . . . ,m, (4.4)
potom pro hustotu rozdělení z P(IDAG(G)) platí
f(x) =
∏m
i=1 fCi(xCi)∏m
i=2 fSi(xSi)
(4.5)
za konvence 00= 0. Konkrétně pro diskrétní rozdělení můžeme (4.5) přepsat
na
P (ξ = x) =
∏m
i=1 P (ξCi= xCi
)∏m
i=2 P (ξSi= xSi
)(4.6)
a pro regulární Gaussovské rozdělení s varianční maticí Σ platí
Σ−1 =m∑
i=1
[(ΣCi·Ci)−1]N −
m∑
i=2
[(ΣSi·Si)−1]N , (4.7)
7Jak dokázal F. Matúš, systém {Si, i = 2, . . . ,m} je zároveň systémem všech mini-málních ab–separátorů grafu G, více viz definice ab–separátoru a jeho indexu v [Šim05].Tento fakt však nebude v této práci dále využit.
66
kde operací [·]N myslíme zvětšení marginální matice na původní rozměr,přičemž prvky marginální matice jsou umístěny na odpovídající místa a nata zbylá jsou doplněny nuly.
Důkaz. Snadné cvičení (opakované použití lemmatu 1 postupně odzadu naseznam klik), viz [Lau96], str. 90 a str. 145.
Jako ilustraci použití perfektního uspořádání klik a lemmatu 32 uvaž-me následující problém z [Šim05]: Mějme rozložitelný graf G = (N,E) aoznačme Pp
b (IUG(G)) všechna pravděpodobnostní rozdělení z Pb(IUG(G)),jež navíc splňují
maxa∈N
P (ξa = 1) ≤ p,
kde p ∈ [0, 1].Našim cílem bude pro dané p minimalizovat výraz
P (⋂
a∈N
ξa = −1) (4.8)
přes všechna rozdělení z Ppb (I
glUG(G)).
Lemma 33. Nechť G je rozložitelný graf a p ∈ [0, 1]. Potom
minP∈Pp
b(Igl
UG(G))
P (⋂
a∈N
ξa = −1) =
{Qma=1 (1−|Ca|p)Qma=2 (1−|Sa|p)
, p ≤ 1maxa=1,...,m |Ca|
0 p > 1maxa=1,...,m |Ca|
Důkaz. Uspořádejme kliky G do perfektní posloupnosti C1, . . . , Cm a defi-nujme S2,. . . ,Sm podle vztahu (4.4). Jestliže p ≤ 1
maxa=1,...,m |Ca|, potom mů-
žeme definovat pravděpodobnostní rozdělení P ∗ pro každou kliku Ca jako
P ∗(⋂
c∈Caξc = −1) = 1− |Ca|p
∀b ∈ Ca : P ∗(ξb = 1,⋂
c∈Ca\bξc = −1) = p
P ∗(. . . ) = 0 jinak
a rozdělení P ∗ je dále jednoznačně určeno lemmatem 32.Zjevně P ∗ ∈ Pp
b (IglUG(G)), stačí tedy dokázat
∀P ∈ Ppb (I
glUG(G)) : P (
⋂
a∈N
ξa = −1) ≥
∏m
a=1 (1− |Ca|p)∏m
a=2 (1− |Sa|p).
67
To lze provést indukcí na počtu klik m. Pro jednu kliku je výsledek zřejmý.Jinak označme T = Sm = Cm ∩ (∪a=1,...,m−1Ca) a z (4.2) dostáváme, žeexistuje a ∈ {1, . . . ,m − 1} takové, že T ⊂ Ca. Graf G′ = G(N\Cm)∪T máoproti grafu G o jednu kliku méně, můžeme tedy použít indukční předpokladpro pravděpodobnost P (
⋂a∈N ξa = −1) zapsanou jako součin
P (T
a∈T ξa=−1,T
a∈Cm\T ξa=−1)
P (T
a∈T ξa=−1)· P (
⋂a∈(N\Cm)∪T ξa = −1) ≥
≥ 1−p̂−(|Cm|−|T |)p1−p̂
·Qm−1
a=1 (1−|Ca|p)Qm−1a=2 (1−|Sa|p)
, (4.9)
kde definujeme p̂ ≡ 1− P (⋂
a∈T ξa = −1) ≤ |T | · p.Zlomek v na levé straně (4.9) nabývá minima pro p̂ = |T |.p a tudíž
P (⋂
a∈N
ξa = −1) ≥1− |Cm|p
1− |T |p·
∏m−1a=1 (1− |Ca|p)∏m−1a=2 (1− |Sa|p)
=
∏m
a=1 (1− |Ca|p)∏m
a=2 (1− |Sa|p),
čímž je indukčních krok dokončen.Zbývá rozebrat případy p > 1
maxa∈N |Ca|. Stačí si však uvědomit, že mi-
nimum (4.8) je zjevně nerostoucí funkce p a již pro p = 1maxa∈N |Ca|
nabývánuly.
4
1
8
7
6
5
3
2
4
1
8
7
6
5
3
2
Obrázek 4.6: Graf G, jeho kliky Ca (vlevo) a separátory Sa (vpravo)
Příklad 4. Nechť G je rozložitelný graf znázorněný na obr. 4.6. Jeho klikyjsou {1, 3},{2, 3, 4},{3, 4, 5, 6},{5, 6, 7},{6, 7, 8}. Tudíž dle lemmatu 33,
minP∈Pp
b(Igl
UG(G))
P (⋂
a∈N
ξa = −1) =
{(1−2p)(1−3p)3(1−4p)(1−p)(1−2p)3
= (1−3p)3(1−4p)(1−p)(1−2p)2
pokud p ≤ 14,
0 pokud p ≥ 14.
68
4.2.2 Maximálně věrohodné odhady
V tomto oddíle vysvětlíme, v čem je vyjímečná třída rozložitelných modelů.Umožňuje totiž elegantně vyřešit otázku identifikace parametrů modelu nazákladě dat.
Metoda maximální věrohodnosti (MV) je nejpoužívanějším způso-bem, jak odhadnout parametry v dané rodině rozdělení. Za odhad zvo-líme takovou hodnotu parametru, která maximalizuje log–věrohodnostnífunkci. Za předpokladu, že rozdělení náhodné veličiny patří do exponenci-ální rodiny8, takovýto odhad skoro jistě existuje a je jednoznačný. Čtenáře,který si potřebuje znalosti MV odhadů a jejich vlastností spolu s teorií ex-ponenciálních rodin doplnit, si dovolujeme odkázat na [And78] a dodatky[Lau96].
Nechť X jsou data o k řádcích neboli matice, kde každé z k nezávislýchpozorování náhodného vektoru ξ, je zapsáno do jednoho řádku.Jestliže ξ má diskrétní rozdělení, potom MV odhad jeho parametrů bez
nezávislostních omezení je při označení hustoty vůči čítací míře p(x) =P (ξ = x) roven
p̂(x) =1k
k∑
a=1
I[Xa = x],
kde I[A] = 1 pokud jev A nastal a nula naopak, a Xa je a–té měření (řádeka matice X).Pokud má ξ naopak regulární Gaussovské rozdělení, potom MV odhady
jeho parametrů bez nezávislostních omezení vypadají následovně:
• µ̂a = 1k
∑k
b=1Xba,
• σ̂a·b = 1k
∑k
c=1(Xca − µ̂a)(Xcb − µ̂b).
Níže zmíníme, jak situace vypadá v případě regulárního Gaussovskéhorozdělení nad UG a diskrétního (resp. binárního) či Gaussovského rozdělenínad rozložitelným grafem.Není obtížné nahlédnout, že v obou případech se jedná o exponenciální
rodiny (viz [Lau96]). Ovšem v případě UG je nám známo pouze iteračnířešení, zatímco v druhém případě je znám exaktní vzorec.
8a několika dalších technických předpokladů jako že se skutečná hodnota nenachází nahranici prostoru parametrů. . .
69
Lemma 34. Předpokládejme, že ξ je regulárně Gaussovsky rozdělený vektorse střední hodnotou µ a s varianční maticí Σ. Za předpokladu, že rozděleníξ je prvkem rodiny rozdělení Pg+(IUG(G)), nalezneme maximálně věrohodnéodhady µ̂ a Σ̂ následovně:Nechť X jsou data o k řádcích. Potom
• µ̂a = 1k
∑k
b=1Xba,
u inverze varianční matice platí
• 〈ab|N \ ab〉 ∈ IUG(G) ⇒ (Σ̂−1)a·b = 0
a zároveň ovšem
• σ̂a·a = 1k
∑k
b=1(Xba − µ̂a)2
• 〈ab|N \ ab〉 /∈ IUG(G) ⇒ σ̂a·b = 1k
∑k
c=1(Xca − µ̂a)(Xcb − µ̂b)
Důkaz. Viz [Lau96], str. 133.
Povšimněme si dvou faktů. U neorientovaného grafu G = (N,E) platí
〈ab|N \ ab〉 ∈ IUG(G) ⇐⇒ ab /∈ E (4.10)
a poslední dvě rovnice, jež musí prvky varianční matice MV odhadu splňovat,jsou za požadavku na nulovost některých členů Σ−1 řešitelné pouze iteračně.Faktorizace rozdělení nad rozložitelnými grafy spolu s perfektním uspo-
řádáním klik lze použít pro odvození následujícího lemmatu:Předpokládejme, že G je rozložitelný graf a rozdělení ξ je prvkem třídy
P(IUG(G)). Potom jestliže dokážeme nalézt MV odhady pro rozdělení klik(viz začátek tohoto oddílu), můžeme nalézt MV odhad pro parametry ξ nazákladě lemmatu 32 (formální důkaz je v [Lau96], str. 84).
Lemma 35. Nechť G je rozložitelný graf a rozdělení ξ je prvkem třídyPd(IUG(G)). Potom při perfektním uspořádáním klik C1, . . . , Cm, definiciS2,. . . ,Sm podle vztahu (4.4) a označení hustoty vůči čítací míře p(x) =P (ξ = x) platí, že
p̂(x) =
∏m
a=11k
∑k
b=1 I[Xb·Ca= xCa
]∏m
a=21k
∑k
b=1 I[Xb·Sa= xSa
].
Analogicky, pokud rozdělení ξ je prvkem Pg+(IUG(G)) a Σ̂Ca·Cajsou MV
odhady variančních matic rozdělení klik ξCa, potom nám vztah (4.7) udává
MV odhad pro varianční matici ξ.
Důkaz. Viz [Lau96], str. 91 a 145.
70
4.3 Hledání modelu
V zásadě existují dva způsoby jak na základě dat vybrat nezávislostní mo-del. V této kapitole si oba stručně představíme a uvedeme použití při výběrugrafického modelu. Na závěr se je pokusíme aplikovat na Gaussovsky repre-zentovatelné nezávislostní modely nad čtyřmi veličinami.
První způsob je založený na opakovaném testování podmíněné nezávis-losti:
1. Pro všechna 〈ab|C〉 ∈ TN testuj, zda-li ξa⊥⊥ξb|ξC .
2. Z daného prostoru nezávislostních modelů vyber takový, který odpovídánalezeným nezávislostem z bodu 1.
Ve skutečnosti často v bodě 1 není třeba testovat všechny elementárnípodmíněné nezávislosti, ale můžeme využít vlastností prostoru modelů, zkterého vybíráme. Například díky vlastnosti (4.10) nezávislostních modelůpříslušných UG lze předchozí algoritmus zjednodušit na
1. Pro všechna a, b různé prvky N testuj, zda-li ξa⊥⊥ξb|ξN\ab.
2. Vyber graf G takový, že bude mít mezi a a b hranu právě tehdy, když testnezávislosti mezi ξa⊥⊥ξb|ξN\ab není signifikatní.
Analogická, byť složitější optimalizece kroku 1 pro DAG se nazývá PCalgoritmus, viz např. [Nea03], str. 542.Neodstranitelným problémem však zůstává, že po (např. Bonferroniho)
korekci na mnohonásobné testování získáme při zachované hladině α velmikonzervativní testy jednotlivých elementárních nezávislostí. Pokud naopakkorekci na mnohonásobné testování neprovedeme, není výběr modelu asymp-toticky konzistentní9 a je třeba být velmi opatrný s interpretací výsledků.
Druhou možností je nalézt model maximalizací Akaikeho (AIC), Baye-sovského (BIC) či jiného informačního kritéria
AIC(θ̂,X) = 2LL(θ̂,X)− 2D = 2k∑
i=1
log fθ̂(Xi)− 2D,
BIC(θ̂,X) = 2LL(θ̂,X)−D log k = 2k∑
i=1
log fθ̂(Xi)−D log k,
9Tzn. neplatí, že pokud jde počet pozorování k nekonečnu, blíží se pravděpodobnostvýběru správného modelu k jedné.
71
kde X jsou data o k řádcích, LL log–věrohodnostní funkce, θ̂ MV odhadparametrů rozdělení a D dimenze prostoru parametrů. Podle [Nea03] (po-drobnosti v [Mee97]) je výběr modelu za pomoci AIC/BIC asymptotickykonzistentní.Jak již bylo zmíněno, problémem je obrovský počet možných grafů (a
tudíž i modelů). Je tedy třeba zvolit nějakou vyhledávací strategii. Ať jižpostupné odebírání (resp. přidávání) hran z úplného (resp. prázdného) grafunebo střídavé přidávání, odebírání (a u DAG obracení směru hran) podletoho, co maximalizuje nejvíce nárůst hodnoty kritéria. Tyto algoritmy sicemohou být asymtoticky konzistentní, nicméně při větším množství veličina reálném množství dat (viz úvod) je šance na určení správného modelupoměrně malá.
4.3.1 Gaussovky reprezentovatelné modely
Do této chvíle jsme předpokládali, že data skutečně pocházejí z rozdělení,jehož příslušný nezávislostní model je grafický. Jak však bylo zmíněno vúvodu tento předpoklad je sice nezbytný (už jenom kvůli superexponen-ciálně rostoucímu počtu všech nezávislostních modelů), v praxi často aninezmiňovaný, nicméně na první pohled obtížně ospravedlnitelný.V tomto oddíle si nejprve ukážeme, že třída UG grafických modelů je
přirozenou volbou ve smyslu, že jsou to právě ty g+–reprezentovatelné ne-závislostní modely, které odpovídají exponenciálním rodinám. Následně sepokusíme naleznout algoritmus pro výběr modelu a identifikaci parametrův případě Gaussovsky reprezentovatelných nezávislostních (ne nutně gra-fických) modelů. A konečně, v simulační studii srovnáme odhady založenépouze na grafických modelech a na všech g+–reprezentovatelných nezávis-lostních modelech. Bez újmy na obecnosti se omezíme na regulárně reprezen-tovatelné modely, neboť u ostatních případů lze z varianční matice snadnourčit funkční závislosti mezi veličinami a převést úlohu na výběr a hledáníparametrů u příslušného regulárního podvektoru.
Pro každý neorientovaný graf G je IUG(G) g+–reprezentovatelný (důkazv [Lně05]) a navíc, jak již bylo zmíněno v předchozím oddíle, je rodinarozdělení Pg+(IUG(G)) exponenciální. Toto tvrzení lze však i obrátit, jakukazuje následující lemma:
Lemma 36. Nechť I je g+–reprezentovatelný nezávislostní model a Pg+(I)je exponenciální rodina. Potom existuje UG G takový, že I = IUG(G).
72
Důkaz. Důkaz lze nalézt v [Šim06c]. Myšlenka však pochází od F. Matúše.
Omezme se nyní až na g+–reprezentovatelné modely nad N = {1, 2, 3, 4}.Tento předpoklad budeme do konce kapitoly pro zjednodušení vynechávat,protože s žádnými jinými než g+–reprezentovatelnými modely nad čtyřmiveličinami pracovat nebudeme. Nejsnažší způsob, jak vybrat obecný nezá-vislostní model pro daná dataX o k řádcích, je pochopitelně otestovat všech24 elementárních nezávislostí.Pokud ale chceme omezit chybu omylem přidané nezávislosti na hladinu
α = 0,05 musíme (při Bonferroniho korekci) jednotlivé testy provádět nahladině α
24
.= 0,0021. Sílu testu je možné optimalizovat, jestliže využijemetoho, jak jsou jednotlivé nezávislostní modely do sebe „vnořenyÿ, a zvolímesekvenční strategii výběru modelu.
Druhou možností je výběr modelů a určení jeho parametrů na základěAIC/BIC. Odhad střední hodnoty je pro všechny modely stejný a to
µ̂a =1k
k∑
b=1
Xba, a = 1, . . . , 4.
Varianční matici Σ parametrizujme jako
Σ =
σ11 0 0 00 σ22 0 00 0 σ33 00 0 0 σ44
Σ0
σ11 0 0 00 σ22 0 00 0 σ33 00 0 0 σ44
,
kde
Σ0 =
1 ρ12 ρ13 ρ14ρ21 1 ρ23 ρ24ρ31 ρ32 1 ρ34ρ41 ρ42 ρ43 1
.
Odhady parametrů σ11, . . . , σ44 získáme jako klasické MV odhady rozptylujednotlivých veličin, tedy
σ̂2aa =1k
k∑
b=1
(Xba − µ̂a)2, a = 1, . . . , 4.
Zbývá nalézt MV odhad parametrů z Σ0 vhledem k nezávislostním omeze-ním příslušného modelu.
73
V některých případech bude snadnější parametrizovat nikoli variančnímatici, ale její inverzi Σ−1 při analogické triku s převodem na matici s jed-ničkami na diagonále jako výše, tedy označme Σ−1
0 = (∂ij)i,j=1,...,4.Připomeňme, že
ξa⊥⊥ξb|ξC ⇐⇒ |ΣaC·bC | = 0 ⇐⇒ |(Σ−1)a(N\abC)·b(N\abC)| = 0.
Níže jsou navrženy parametrizace pro modely typů M1–M53 z obr. 2.3,str. 39:
M1) ρ12 = 0
M2) ρ12 = ρ14ρ24
M3) ρ12 =ρ14ρ24+ρ13ρ23−ρ13ρ24ρ34−ρ14ρ23ρ34
1−ρ234
M4) ρ12 = 0, ρ13 = −ρ14(ρ23ρ34−ρ24)
ρ24ρ34−ρ23
M5) ρ12 = 0, ρ34 =ρ23(1−ρ2
14)+ρ13ρ24ρ14ρ24
M6) ρ12 = 0, ρ34 = ρ13ρ14 + ρ23ρ24
M7) ρ12 = 0, ρ34 = ρ14ρ13
M8) ρ12 = ρ14ρ24, ρ34 = ρ14ρ13
M9) ∂12 = 0, ∂34 = 0
M10) ρ12 = ρ14ρ24, ρ13 =ρ34+ρ23ρ24ρ
214−ρ23ρ24−ρ2
14ρ224
ρ34
ρ14(1−ρ224)
M11) ρ12 = 0, ρ23 = ρ24ρ34
M12) ρ12 = 0, ρ34 = 0
M13) ρ12 = ρ14ρ24, ρ13 =ρ14ρ24
ρ23
M14) ρ12 = ρ14ρ24, ρ13 =ρ14(1−ρ2
23−ρ224+ρ23ρ24ρ34)
ρ34−ρ23ρ24
M15) ρ14 = ρ13ρ34, ρ12 = ρ24ρ13ρ34
M16) ∂14 = 0, ∂23 = 0, ∂12 = −∂13∂24∂341−∂2
34
74
M17) ρ12 = 0, ρ14 = ρ13ρ34, ρ23 =ρ34(1−ρ2
13)
ρ24
M18) ρ12 = 0, ρ34 = ρ13ρ14, ρ24 = −ρ14(1−ρ2
13−ρ223)
ρ13ρ23
M19) ρ12 = 0, ρ34 = 0, ρ13 = −ρ23(1−ρ2
14)
ρ14ρ24
M20) ∂12 = 0, ∂34 = 0, ∂13 = −∂14∂24∂23
M21) ρ12 = 0, ρ34 = ρ13ρ14, ρ23 = −ρ24ρ14(1−ρ2
13)
ρ13(1−ρ214)
M22) ρ12 = 0, ρ34 = ρ23ρ24, ρ13 =ρ23ρ24
ρ14
M23) ρ12 = 0, ρ23 = ρ24ρ34, ρ14 = ρ13ρ34
M24) ρ12 = 0, ρ34 = ρ23ρ24, ρ14 = ρ13ρ23ρ24
M25) ρ12 = 0, ρ14 = ρ13ρ34, ρ23 = −1−ρ2
24−ρ234
ρ24ρ34
M26) ρ12 = ρ14ρ24, ρ13 =ρ14ρ24
ρ23, ρ34 = ρ23ρ24
M27) ρ12 = 0, ρ14 = ρ13ρ34, ρ24 =ρ23(1−ρ2
13ρ234)
ρ34(1−ρ213)
M28) ρ12 = ρ14ρ24, ρ23 = ρ14ρ24ρ13, ρ34 = ρ14ρ224ρ13
M29) ∂14 = 0, ∂12 = ∂13∂23, ∂34 = ∂23∂24
M30) ρ12 = 0, ρ34 = 0, ρ13 = −ρ14ρ24
ρ23
M31) ∂23 = 0, ∂14 = ∂13∂34, ∂12 = ∂13∂34∂24
M32) ∂34 = 0, ∂12 = ∂14∂24, ∂13 = ∂14∂24∂23
M33) ρ12 = 0, ρ23 = 0
M34) ∂12 = 0, ∂23 = 0
M35) ρ12 = 0, ρ34 = 0, ρ13 = ±ρ24, ρ14 = ∓ρ23
M36) ρ34 = ρ23ρ24, ρ12 = ±ρ23ρ24, ρ13 = ±ρ24, ρ14 = ±ρ23
M37) ρ12 = 0, ρ23 = ρ24ρ34, ρ13 = ±√1− ρ224, ρ14 = ±ρ34
√1− ρ224
M38) ρ12 = 0, ρ14 = 0, ρ23 =ρ24(1−ρ2
13)
ρ34
75
M39) ρ12 = 0, ρ23 = 0, ρ13 = ρ14ρ34
M40) ∂14 = 0, ∂24 = 0, ∂13 =∂12(1−∂2
34)
∂23
M41) ∂14 = 0, ∂24 = 0, ∂12 = ∂13∂23
M42) ρ12 = 0, ρ13 = 0, ρ23 = 0
M43) ∂12 = 0, ∂13 = 0, ∂23 = 0
M44) ρ12 = 0, ρ23 = 0, ρ14 = ρ13ρ34
M45) ρ12 = 0, ρ23 = 0, ρ34 = 0
M46) ∂12 = 0, ∂23 = 0, ∂34 = 0
M47) ρ12 = 0, ρ13 = 0, ρ14 = 0
M48) ρ12 = 0, ρ23 = 0, ρ13 = 0, ρ14 = 0
M49) ∂12 = 0, ∂13 = 0, ∂23 = 0, ∂14 = 0
M50) ρ12 = 0, ρ14 = 0, ρ23 = 0, ρ34 = 0
M51) ρ12 = 0, ρ13 = 0, ρ14 = 0, ρ23 = 0, ρ34 = 0
M52) ρ12 = 0, ρ13 = 0, ρ14 = 0, ρ24 = 0, ρ23 = 0, ρ34 = 0
M53) saturovaný model (žádná omezení)
Pro maximalizaci log–věrohodností funkce a následné určení hodnotyAIC/BIC je vhodné využít optimalizační algoritmus nějakého numerickéhosoftwaru (např. funkci optim v [RD05]). Dimenze prostoru parametrů D je14 bez počtu nezávislostních omezení (to jest rovnic, nikoli vztahů) pro danýmodel. Například pro model M11 je D = 14− 2 = 12, neboť máme omezenína σ12 a σ23.Otázkou však zůstává, zda optimalizací skutečně nalezneme maximum
log–věrohodnostní funkce. Tak tomu jistě bude u UG modelů, neboť tyto(díky lemmatu 36) vedou na exponenciální rodiny, kdy je log–věrohodnostnífunkce konkávní. Vyhovující algoritmus existuje i pro zakřivené exponen-ciální rodiny (viz [Lau96], str. 272). Nevíme však, zda jsou rodiny příslušnémodelům M1–M53 skutečně zakřiveně exponenciální.
76
Na okraj zmiňme, že za pomoci článku [Drt06] lze zkonstruovat postaču-jící podmínku pro ověření, že daná rodina je zakřiveně exponenciální. Teoriese opírá o algebraickou geometrii a výpočet je proveden v programu Sin-gular, [GPS05]. Avšak pro modely typů M4, M13, M20, M21, M22, M25,M26, M30, M35, M36 a M37 nebyla tato podmínka splněna a přesvědčenío funkčnosti maximalizačních algoritmů pro tyto modely je založeno pouzena empirii.
Odhady varianční matice a algoritmus výběru modelu na základě BICkritéria jsou implementovány v přiloženém balíčku pro statistické prostředíR. Výběr správného modelu trvá v prostředí Windows na notebooku Inspi-ron 1501 (AMD Sempron 3500+, 1800 GHz, 1 GB RAM) kolem 9 minut.Uvědomme si, že velikost dat není pro složitost výpočtu směrodatná, neboťpostačující statistikou je běžný odhad parametrů pro saturovaný model (tj.bez nezávislostních omezení).Validita algoritmu byla ověřena následující simulací:
1. Pro každý z 53 typů zvolíme jeden model, označme jej I, a náhodněnagenerujeme varianční matici s tímto modelem korespondující, označmeji V .
2. Nagenerujeme data z normálního rozdělení s varianční maticí V o k řád-cích.
3. Na základě AIC/BIC kritéria vybereme jeden z 629 nezávislostních modelů,označme jej J .
4. Zjistíme, zda-li I a J jsou shodné. Pakliže ano, nazveme identifikaci mo-delu úspěšnou, ve všech ostatních případech neúspěšnou.
Zdůrazněme, že je lhostejné, jak při simulaci zvolíme parametr středníhodnoty, a že bez újmy na obecnosti můžeme brát varianční matici s jednič-kami na diagonále. Kód pro R vypadá následovně:
I<-ind.identification(type=testovany.typ)$model
V<-ind.rgauss(model=I)
data<-generate.data(V,k)
J<-model.selection(data)$model
if (I==J) print(’Uspech’) else print (’Neuspech’)
77
4 6 8 10
0.0
0.2
0.4
0.6
0.8
1.0
AIC
log(k)
prob
abili
tyof
suc
cess
4 6 8 10
0.0
0.2
0.4
0.6
0.8
1.0
BIC
log(k)
prob
abili
tyof
suc
cess
Obrázek 4.7: Úspěšnost identifikace modelu na základě AIC a BIC.
Celou simulaci jsme opakovali pro každý z 53 typů a každou z 15 různýchvelikostí dat k celkem čtyřikrát. Graf průměrné pravděpodobnosti úspěšnéidentifikace podle AIC/BIC v závislosti na log(k) můžete vidět na obr. 4.7.Vidíme, že identifikace na základě BIC je podstatně úspěšnější než u AIC.
Dále se tedy budeme zabývat pouze tímto kritériem. Pokud daty proložímepřímku, lze odvodit pomocné pravidlo
P (úspěšné identifikace) ≈ 0,23 · log10(k)− 0,24.
Chceme-li tedy mít pravděpodobnost úspěchu nad 80%, jsou k tomu třebadata o alespoň 40 tisíci řádek.
To, že nezvolíme správný model, nemusí nutně znamenat, že bychom do-stali špatný odhad varianční matice. Pokud je např. korelace mezi dvěmi ve-ličinami 0,000001 a my mezi nimi předpokládáme nezávislost, nedopouštímese zjevně velké chyby. Vzdálenost mezi skutečným a odhadnutým rozdělenímbudeme měřit tzv. Kullback–Leiblerovy divergencí
DIV (µ, V, µ̂, V̂ ) =12
(log
(|̂V |
|V |
)+ tr
(V̂ −1V
)+ (µ̂− µ)′V̂ −1(µ̂− µ)− n
),
kde µ, V, µ̂, V̂ jsou po řadě parametry střední hodnoty a matice rozptyluprvního a druhého rozdělení, n je počet složek vektoru (tj. v našem případěn = 4), tr je stropa matice.
78
Odhad budeme považovat za tím „lepšíÿ, čím nižší má průměrnou Kull-back–Leiblerovu divergenci přes 53 možných typů modelů. Nyní tedy ko-nečně můžeme srovnat odhad bez nezávislostních omezení, odhad založenýna základě grafického modelu maximalizujícího BIC, odhad založený na zá-kladě nezávislostního modelu maximalizujícího BIC a odhad, kdy je námskutečný nezávislostní model znám:
1. Pro každý z 53 typů zvolíme jeden model, označme jej I, a náhodněnagenerujeme varianční matici s tímto modelem korespondující, označmeji V .
2. Nagenerujeme data z normálního rozdělení s varianční maticí V o k řád-cích.
3. Spočítáme odhad varianční matice v saturovaném modelu a označíme jejV̂0. Na základě BIC kritéria vybereme nejlepší grafický model a příslušnýodhad označíme V̂1. Analogicky vybereme nezávislostní model a příslušnýodhad označíme V̂2. Odhad varianční matice pro nezávislostní model Ioznačíme V̂3.
4. Spočteme Kullback–Leiblerovu divergenci mezi V na jedné a V̂0 až V̂3 nadruhé straně.
Kód pro R by vypadal následovně:
I<-ind.identification(type=testovany.typ)$model
V<-solve(ind.rgauss(model=I))
data<-generate.data(Sigma=V,n=k)
V0<-ind.mle(data,type=53)$Sigma
SEL<-model.selection(data)
V1<-SEL$gSigma
V2<-SEL$Sigma
V3<-ind.mle(data,type=I)$Sigma
DIV0<-kl.div(V,V0,inv=FALSE)
DIV1<-kl.div(V,V1,inv=FALSE)
DIV2<-kl.div(V,V2,inv=FALSE)
DIV3<-kl.div(V,V3,inv=FALSE)
79
Celou simulaci jsme opakovali pro každý z 53 typů a každou z 11 různýchvelikostí dat k celkem čtyřikrát. Výsledky je skutečně obtížné graficky zná-zornit. Vezměme odhad pro saturovaný model jako referenční a spočtěme, okolik jsou jiné odhady lepší či horší. Průměrné10 rozdíly divergencí v závis-losti na log(k) můžete vidět na levé straně obr. 4.8, detail na témže obrázkuvpravo.
5 6 7 8 9
−0.
008
−0.
004
0.00
0
Trimmed Mean
log(k)
diffe
renc
e
5 6 7 8 9
−0.
0015
−0.
0005
0.00
05
Detail
log(k)
diffe
renc
e
Obrázek 4.8: Saturovaný model černě, grafické červeně, nezávislostní zeleně,skutečný nezávislostní modře.
Pokusme se výsledky simulace interpretovat:
1. Odvozený odhad varianční matice odpovídající nezávislostnímu mo-delu maximalizujícímu BIC lze doporučit při rozsahu dat do 10 tisícřádek. Nad touto mezí jsou si již všechny odhady podobné.
2. Odhad založený pouze na grafických modelech dává pro data o méněnež tisíci řádkách velmi neuspokojivé výsledky. Ve všech případech jehorší než odhad založený na všech nezávislostních modelech.
3. Odhad odpovídající skutečnému nezávislostnímu modelu dává (vcelkupochopitelně) nejlepší výsledky.
10Abychom odstranili extrémní případy, použijme ořezaný průměr s parametrem ořezu20%.
80
4. Pro to aby se mělo cenu pokoušet o výběr z 629 nezávislostních modelůa hledání toho skutečného jsou potřeba data o desetitisících, ale spíšestatisících pozorování.
S trochou kreativity lze uvedený postup výběru nezávislostního modeluna základě BIC aplikovat i v jiných případech. Jak jsme již zmínili, po-stačující statistikou pro příslušné odhady je běžný odhad varianční maticevzhledem k saturovanému modelu. Můžeme tedy odhadnout nejprve vari-anční matici nějakým jiným způsobem (např. použít některý z robustníchodhadů) a výběr nezávislostního modelu aplikovat až ex-post. Výše uvedenýpostup lze tedy chápat jako jistou korekci ošetřující možné podmíněné ne-závislosti.
Podobně jestliže je náhodných veličin více než čtyři a zapíšeme-li si in-dexovou množinu N jako sjednocení čtveřic
N =⋃
i
{ai1, a
i2, a
i3, a
i4},
takové, že každá dvojice různých prvků N se vyskytuje v alespoň jedné tétočtveřici, potom na tyto čtveřice můžeme aplikovat standardní odhad na zá-kladě nezávislostního modelu maximalizujícího BIC. Každý prvek variančnímatice je odhadnut díky předpokladu alespoň jednou, v případě více odhadůpro jeden prvek použijeme průměr. Nemáme však zaručeno, že dostanemepozitivně definitní matici.V některých případech může být výhodnější odhadovat nikoli varianční
matici, ale její inverzi. Záleží na tom, zda se domníváme, že se nám budouv datech vyskytovat spíše nezávislosti typu ξi⊥⊥ξj,ξi⊥⊥ξj|ξk, ξi⊥⊥ξj|ξkl neboξi⊥⊥ξj|ξN\ij,ξi⊥⊥ξj|ξN\ijk, ξi⊥⊥ξj|ξN\ijkl. Výše uvedené postupy je třeba uží-
vat s opatrností a o rozumném chování odhadů se důkladně ujistit za pomocísimulační studie či vyčleněné kontrolní skupiny.
Příklad 5. Uvedeme si ryze praktický příklad. V chovu hospodářskýh zvířatje snaha o soustavné zlepšování efektivity. Hodnota zvířete pro daný selekčnícíl se určuje pomocí tzv. selekčního indexu I. Ten je roven lineární kombi-naci daných vlastností pro konkrétní zvíře x = (x1, . . . , xn) s koeficientyb = (b1, . . . , bn) závislými na ekonomické hodnotě a genetických paramet-rech těchto vlastností. Pro b platí vztah P · b = G · v, kde P je kovariančnímatice pozorovaných vlastností (fenotypová varianční matice), G shrnuje
81
genetické vlastnosti těchto znaků (genetická varianční matice) a v je vektorekonomických hodnot.Určováním genetické varianční matice a ekonomických hodnot se zde ne-
budeme zabývat. Naším cílem bude odhadnout fenotypovou varianční matici.Tento odhad musí být velmi přesný, protože se od něj odvíjí kvalita celéhošlechtitelského procesu. Základem musí být znalost hodnot sledovaných vlast-ností u co největšího reprezentativního vzorku jedinců a následně co nejlepšíodhad varianční matice.V našem příkladě se budeme zajímat o případ šlechění býků českého stra-
katého skotu. Základem jsou informace o býcích z let 1960 – 2006 z datovébanky připravované Českomoravskou společností chovatelů a Plemdat s.r.o.Vlastnosti zahrnuté do selekčního indexu jsou průměrné množství nadoje-ného mléka za laktaci u dcer (v kg), množství tuku v tomto mléce (v kg),procento tuku v mléce, množství (v kg) a procento bílkovin v mléce a dále tě-lesné vlastnosti býka, tedy jeho výška v kohoutku, výška v kříži a délka trupu(v cm). Všechny tyto hodnoty jsou vyjádřeny jako odchylka od průměrnéhodnoty v populaci. V databázi je všech těchto osm vlastností zaznamenánou 2063 býků.
Data si rozdělíme na experimentální skupinu o 1800 býcích a kontrolnískupinu o 263 býcích. Indexovou množinu N = {1, 2, 3, 4, 5, 6, 7, 8} lze zapsatjako sjednocení 10 čtveřic: {1, 2, 3, 4}, {5, 6, 7, 8}, {1, 2, 7, 8}, {3, 4, 5, 6},{1, 3, 6, 8}, {2, 4, 5, 7}, {1, 4, 6, 7}, {2, 3, 5, 8}, {1, 2, 5, 6}, {3, 4, 7, 8}. V ex-perimentální i kontrolní skupině odhadneme parametr varianční matice ato jak v saturovaném modelu, tak za pomoci nezávislostních modelů, jak jepopsáno výše. Odhady pro 1800 pozorování jsou si zjevně velice blízké, sou-střeďme se tedy na odhady pro kontrolní skupinu. A zde s potěšením zjišťu-jeme, že odhad na základě nezávislostních modelů má nejen nižší divergencik obdobnému odhadu v experimentální skupině, ale dokonce i k odhadu prosaturovaný model (byť o méně než 0,0001). Zdá se tedy, že odhad za pomocinezávislostních modelů by mohl být pro tento případ vhodný.
Pro praktickou konstrukci podobných odhadů by však bylo potřeba vý-razně snížit časovou náročnost hledání modelu. Toho by snad bylo možnédosáhnout za pomoci přepsání programu do jazyka C, částečně algebraickénamísto čistě numerické optimalizace (výpočet gradientu) a odstraněnímopakovaných výpočtů a přenosů dat. U typů modelů, které odpovídají ex-ponenciálním či alespoň zakřiveně exponenciálním rodinám, je zajisté ještěvelká rezerva.
82
Závěr
Cílem této práce byl za prvé stručný úvod do problematiky podmíněné nezá-vislosti a grafických modelů a za druhé podrobný rozbor známých výsledkůreprezentovatelnosti nezávislostních modelů nad čtyřmi (a méně) náhodnýmiveličinami a jejich další rozšíření. Nakolik byl tento úkol splněn nechávámena posouzení čtenáři.Krom odpovědí nabízí tato práce i velké množství zajímavých otázek.
Jednak se jedná o problémy racionální reprezentovatelnosti a vztahu meziregulárně gaussovsky a kladně binárně (potažmo diskrétně) reprezentovatel-nými nezávislostními modely zmíněnými na konci kapitoly 2. Dále o otevře-nou otázku kladné diskrétní reprezentovatelnosti 12 modelů, jejíž zodpově-zení je nutné k potvrzení či vyvrácení hypotézy z kapitoly 3. Následně o lepšíporozumění, softwarovou implementaci a popularizaci Gaussovských rodinrozdělení z kapitoly 4. V neposlední řadě se zdá být lákavé koncept podmí-něné nezávislosti (a tudíž i reprezentovatelnosti) rozšířit na obecné náhodnéveličiny, resp. σ–algebry (viz [MR84] a [PS85]) nebo dokonce na obecné (nenutně konečné) míry. Platí i v tomto případě, že reprezentovatelné modelynelze konečně charakterizovat?Věřím, že předchozí část pojednávající o konstrukci odhadů založených
na nezávislostních modelech by mohla být zajímavá i pro výzkumníky v ob-lasti aplikované statistiky. Pokud předpokládáme, že podmíněná nezávislostnení jen teoretický pojem, ale i jev vyskytující se v reálném světě, potompro tuto teorii existuje dle mého názoru široké uplatnění.
Pro snadnější využití dosažených výsledků jsou nalezené soubory nezávis-lostních modelů vzhledem k různým distribučním rámcům spolu s popisempříslušného formátu a procedurami pro snadnou manipulaci přiložené naCD. Zde také naleznete balíček pro prostředí R, v kterém jsou implemento-vány odhady parametrů regulárního Gaussova rozdělení popsané ve čtvrtékapitole. Dotazy a připomínky k této práci posílejte na adresu
83
Literatura
[And78] J. Anděl. Matematická statistika. SNTL/ALFA, 1978.
[Bou95] R. R. Bouckaert. Bayesian Belief Networks: from Constructionto Inference. PhD. práce, University of Utrecht, 1995.
[Cas02] R. Castelo. The Discrete Acyclic Digraph Markov Model in DataMining. PhD. práce, University of Utrecht, 2002.
[CGH96] E. Castillo, J. M. Gutierrez a A. S. Hadi. Expert Systems andProbabilistic Network Models. Springer, 1996.
[CLDS99] R. G. Cowell, S. L. Lauritzen, A. P. Dawid a D. J. Spiegelhalter.Probabilistic Networks and Expert Systems. Springer, 1999.
[CW96] D.R. Cox a N. Wermuth. Multivariate Dependencies: Models,Analysis and Interpretation. Chapman & Hall, 1996.
[Dis00] M. Disman. Jak se vyrábí sociologická znalost. Karolinum, 2000.
[Drt04] M. Drton. Maximum Likelihood Estimation in Gaussian AMPChain Graph Models and Gaussian Ancestral Graph Models.PhD. práce, University of Washington, 2004.
[Drt06] M. Drton. Algebraic techniques for Gaussian models. V M. Huš-ková a M. Janžura, editoři, Proceedings of Prague Stochastics2006, str. 81–90, 2006.
[GPS05] G.-M. Greuel, G. Pfister a H. Schönemann. Singular 3.0.A Computer Algebra System for Polynomial Computations. Cen-tre for Computer Algebra, University of Kaiserslautern (2005).http://www.singular.uni-kl.de.
84
[Jir03] R. Jiroušek. On approximating multidimensional probability dis-tributions by compositional models. V J.-M. Bernard, T. Seiden-feld a M. Zaffalon, editoři, Proceedings of the Third InternationalSymposium on Imprecise Probabilities and Their Applications,str. 305–320, Waterloo, 2003. Carleton Scientific.
[Jor04] M. I. Jordan. Graphical models. Statistical Science, 15:140–155,2004.
[Koč01] T. Kočka. Graphical models – learning and applications. PhD.práce, VŠE Praha, 2001.
[Lac04] P. Lachout. Teorie pravděpodobnosti. Karolinum, 2004.
[Lau96] S. L. Lauritzen. Graphical Models. Oxford University Press,1996.
[Lau01] S. L. Lauritzen. Causal inference from graphical models. V O.E.Barndorff-Nielsen, D.R. Cox a C. Klüppelberg, editoři, ComplexStochastic Systems, str. 63–107. Chapman & Hall/CRC, 2001.
[Lně05] R. Lněnička. On Gaussian conditional independence structures.Interní publikace DAR–ÚTIA 2005/14, ÚTIA AV ČR, Praha,2005.
[LR02] S. L. Lauritzen a T. S. Richardson Chain graph models and theircausal interpretations. Journal of the Royal Statistical Society:Series B (Statistical Methodology), 64:321–361, 2002.
[Mat92] F. Matúš. On equivalence of Markov properties over undirectedgraphs. Journal of Applied Probability, 29:745–749, 1992.
[Mat95] F. Matúš. Conditional independences among four random va-riables II. Combinatorics, Probability & Computing, 4:407–417,1995.
[Mat97] F. Matúš. Conditional independence structures examined viaminors. The Annals of Mathematics and Artificial Intelligence,21:99–128, 1997.
[Mat99] F. Matúš. Conditional independences among four random vari-ables III. Combinatorics, Probability & Computing, 8:269–276,1999.
85
[Mat05] F. Matúš. Conditional independences in Gaussian vectors andrings of polynomials. V G. Kern-Isberner, W. Rödder a F. Kul-mann, editoři, Conditionals, Information a Inference, Internati-onal Workshop. WCII 2002, str. 152–161. Springer, 2005.
[Mee97] C. Meek. Graphical models: selecting causal and statistical mo-dels. PhD. práce, Carnegie Mellon University, 1997.
[MR84] M. Mouchart a J. M. Rolin. A note on conditional independencewith statistical application. Statistica, 44:557–584, 1984.
[MS95] F. Matúš a M. Studený. Conditional independences among fourrandom variables I. Combinatorics, Probability & Computing,4:269–278, 1995.
[Nea03] R.E. Neapolitan. Learning Bayesian Networks. Chapman &Hall/CRC, 2003.
[Pea98] J. Pearl. Probabilistic Reasoning in Intelligent Systems. MorganKaufmann, 1998.
[PS85] C. van Putten a J. H. van Schuppen. Invariance properties ofconditional independence relation. The Annals of Probability,13:934–945, 1985.
[RD05] R Development Core Team. R: A Language and Environment forStatistical Computing. R Foundation for Statistical Computing,Vienna, Austria, 2005. ISBN 3-900051-07-0.
[Rao73] R. C. Rao. Linear Statistical Inference and Its Applications.John Wiley & Sons, 1973.
[RS02] T. Richardson a P. Spirtes. Ancestral graph Markov models.Annals of Statistics, 30:962–1030, 2002.
[RSSW03] J. M. Robins, R. Scheines, P. Spirtes a L. Wasserman. Uniformconsistency in causal inference. Biometrika, 90:491–515, 2003.
[SB94] M. Studený a P. Boček. Ci-models arising among 4 randomvariables. V Proceedings of the 3rd workshop WUPES, str. 268–282, 1994.
86
[Spo94] W. Spohn. On the properties of conditional independence. VP. Humphreys, editor, Patrick Suppes: Scientific Philosopher, vo-lume 1, str. 173–194. Kluwer, 1994.
[Stu89] M. Studený. Multiinformation and the problem of characteri-zation of conditional independence relations. Problems of Controland Information Theory, 18:3–16, 1989.
[Stu92] M. Studený. Conditional independence relations have no finitecomplete characterization. V S. Kubík a J.A. Víšek, editoři,Information Theory, Statistical Decision Functions and Ran-dom Processes. Transactions of the 11th Prague Conference, vo-lume B, str. 377–396. Kluwer, 1992.
[Stu97] M. Studený. Semigraphoids and structures of probabilistic con-ditional independence. Annals of Mathematics and Artificial In-telligence, 21:71–98, 1997.
[Stu02] M. Studený. On stochastic conditional independence: the pro-blems of characterization and description. Annals of Mathema-tics and Artificial Intelligence, 35:241–323, 2002.
[Stu05] M. Studený. Probabilistic Conditional Independence Structures.Springer, 2005.
[SV98] M. Studený a J. Vejnarová. The multiinformation function as atool for measuring stochastic dependence. V M. I. Jordan, editor,Learning in Graphical Models, str. 261–298. Kluwer, 1998.
[Šim03] P. Šimeček. On the minimal probability of intersection of de-pendent events. diplomová práce, Karlova Univerzita v Praze,2003.
[Šim04] P. Šimeček. A short note on structure learning. V Jana Šafrán-ková, editor, Proceedings of the 14th Annual Conference of Doc-toral Students - WDS 2004, str. 84–87, Prague, 2004. Matfy-zpress.
[Šim05] P. Šimeček. On the minimal probability of intersection of condi-tionally independent events. Submitted to Kybernetika, 2005.
87
[Šim06a] P. Šimeček. Classes of Gaussian, discrete and binary represen-table independence models have no finite characterization. VM. Hušková a M. Janžura, editoři, Proceedings of Prague Sto-chastics 2006, CD volume, str. 622–631. MATFYZPRESS, 2006.
[Šim06b] P. Šimeček. Gaussian representation of independence modelsover four random variables. V A. Rizzi, editor, Proceedings ofCOMPSTAT 2006, CD volume, str. 1405–1412. Springer, 2006.
[Šim06c] P. Šimeček. Independence models. V J. Vejnarová, editor, Pro-ceedings of Workshop on Uncertainty Processing 2006, str. 151–161. University of Economics, 2006.
[Šim06d] P. Šimeček. A short note on discrete representability of indepen-dence models. V M. Studený a J. Vomlel, editoři, Proceedings ofWorkshop on Probabilistic Graphical Models 2006, str. 287–292.Action M Agency, 2006.
[ŠS04] P. Šimeček a M. Studený. Využití Hilbertovy báze k ověřováníshodnosti strukturálních a kombinatorických imset̊u. V JaromírAntoch a Gejza Dohnal, editoři, Sborník prací 13. letní školyJČMF ROBUST, str. 395–402. Jednota českých matematik̊u afyzik̊u, 2004.
[ŠŠ06] Č. Štuka a P. Šimeček. Studium souvislostí mezi úspěšnostístudia medicíny, známkami na střední škole a výsledky přijíma-cích zkoušek. V Sborník konference MEDSOFT 2006. Action MAgency, 2006.
[ŠZTJ04] P. Šimeček, J. Zvárová, M. Tomečková a R. Jiroušek. Applicationof compositional models to cardiology. V M. Fleschl, editor,Abstracts of the 11th World Congress on Medical Informatics,CD volume, str. 1863. IMIA, 2004.
88
