Využití Hilbertovy báze k ověření shodnosti strukturálních a kombinatorických imsetů

Petr Šimeček (MFF UK)Milan Studený (ÚTIA AV ČR)

Motivace – podmíněná nezávislost

Nepodmíněná nezávislost: Diskrétní n.v. Spojité n.v.

Podmíněná nezávislost: Diskrétní n.v.

Spojité n.v.

YX yxyxyx ,)p()p(),p( .v.sP)f()f(),f( yxyx

ZYX |

zyx

zyzxzzyx

,,

),p(),p()p(),,p(

.v.sP

),f(),f()f(),,f(

zyzxzzyx

Motivace – podmíněná nezávislost

N náhodných veličin X1, X2, …, XN a nějaké jejich rozdělení P

Seznam všech podmíněných i nepodmíněných nezávislostí mezi nimi

)},(|),(),(,},...,1{,,);|,{( CiXBiXAiXdisjunktníNCBACBA iii

Popis PN pomocí seznamu

Seznam musí splňovat určitá pravidla, např.

Tudíž je zbytečné skladovat v paměti celý seznam!

Neexistuje konečný počet pravidel schopný rozhodnout, zda něco je či není seznam.

Seznam je nepřehledný.

]|[&]|[]|),[( 4324314321 XXXXXXXXXX

Popis PN pomocí grafů

X6

X5 X4

X3

X2

X1

X1

X3

X2

X4

Popis PN pomocí grafů

Výhody: Názornost, čitelné i pro laika Každý graf je pravděpodobnostně

reprezentovatelný (dokonce diskrétní n.v.)

Nevýhody: Ne každé rozdělení je

reprezentovatelné pomocí grafů (početní argument)

Popis PN pomocí imsetů

Seznam PN popíšeme pomocí zobrazení z P({1,2,…,N}) do Z

Př. pro N=3 (3 náhodné veličiny)

{} {1} {2} {3} {1,2} {1,3} {2,3} {1,2,3}

0 1 0 0 -1 -1 0 1

Popis PN pomocí imsetů

Nevýhody: Méně intuitivní, těžší vyčíst nezávislosti Ne každý imset je reprezentovatelný Vyšší paměťová náročnost (oproti grafu)

Výhody: Libovolný seznam PN reprezentovatelný

imsetem Méně paměťově náročné než seznam PN Grafovou reprezentaci lze na imsety snadno

převést

Semielementární imsety

A,B,C disjunktní podmnožiny {1,…,N}:Semielementárním imsetemrozumíme zobrazení, jež přiřadí 1 množinám a -1 množinám aa nulu ostatním prvkům z potenční množiny

CBA |

CBA C

CA CB

Semielementární imsety

Příklad: N=3, s.e. imsetOdpovídající nezávislosti

3}2,1{

3})2,1{,( XiX i

{} {1} {2} {3} {1,2} {1,3} {2,3} {1,2,3}

1 0 0 -1 -1 0 0 1

Elementární imsety EN

Elementárním imsetemrozumíme zobrazení, jež přiřadí 1 množinám a -1 množinám aa nulu ostatním prvkům z potenční množiny, přičemž {i},{j} a C jsoudisjunktní podmnožiny množiny {1,

…,N}.

Cji },{ C

Ci }{ Cj }{

Příklad - E3

{} {1} {2} {3} {1,2} {1,3} {2,3} {1,2,3}

1 -1 -1 0 1 0 0 0

1 -1 0 -1 0 1 0 0

1 0 -1 -1 0 0 1 0

0 1 0 0 -1 -1 0 1

0 0 1 0 -1 0 -1 1

0 0 0 1 0 -1 -1 1

Kombinatorické imsety CN

Kombinatorickým imsetem nazvemekaždou nezápornou celočíselnou kombinaci elementárních imsetů.

{} {1} {2} {3} {1,2} {1,3} {2,3} {1,2,3}

1 -1 -1 0 1 0 0 0

1 -1 0 -1 0 1 0 0

2 -2 -1 -1 1 1 0 0

Strukturální imsety SN

Strukturálním imsetem nazvemekaždou nezápornou reálnou kombinaci elementárních imsetů, jež je imsetem.

Zjevně každý kombinatorický imset je i strukturálním imsetem neboli NN SC

Platí CN = SN ???

Existuje strukturální imset, který by nebyl kombinatorický?

Otázku zodpovíme pro N<5, pro jiná N zatím není známa. Tato otázka jeklíčovým problémem reprezentacepomocí imsetů.

Příklad na to, že by nemuselo

E’ = {[1,2],[2,1]}

nezáporná reálná kombinace (S)1/3*[1,2] + 1/3*[2,1] = [1,1]

ovšem [1,1] zjevně nelze získat jakonezápornou celočíselnou kombinaci (C)

Stupeň imsetu

Stupeň imsetu je součtem koeficientův kombinaci elementárních imsetů:

Př.: u = 1*e1 + 2*e2 + 0,5*e3

deg(u) = 3,5

Platí:

},...,1{

)()1|(|||)deg(NA

AmAAu

Postup ověření:

Konvexní kužel generovaný EN lze popsat

jako průnik jistých poloprostorů, které proN<6 spočteme Fourier-Motzkinovoueleminací.

Imsety SN jsou celočíselnými body v tomto

kuželu. Stačí je tedy (po jednotlivýchstupních) projít a ujistit se, že všechny jsousoučtem imsetu stupně o 1 nižšího aelementárního imsetu.

Trik – celočíselná Hilbertova báze

Důkaz v [Schrivjer] nám zaručuje, že pokud nějaký imset v SN - CN existuje,

potom alespoň jeden takovýto leží v mnohostěnu:

},],1,0[;{ jiproeeEee jiNiii

ii

Výsledky

N=3 Bez problémů v několika sekundách

ověříme, že C3 = S3

N=4 Je potřeba využít dalších vlastností

strukturálních imsetů, opět C4 = S4

N=5 Víme pouze to, že pokud existuje prvek

Hilbertovy báze mimo E5, pak je jeho stupeň alespoň 5

Literatura: Studený M. (2001): On the mathematical

description of probabilistic conditional independence structures, doktorská práce, ÚTIA AV ČR.

Studený M. (2004): On Probabilistic Independence Structures, Springer.

Studený, Bouckhaert, Kočka (2000): Extreme Supermodular Set Functions, výzkumná zpráva, UTIA AV ČR.

Schrijver A. (1998): Theory of Linear and Integral Programming, John Wiley.