Graphoid - Graphoid

tento článek je sirotek, jako žádné další články odkaz na to. Prosím zavést odkazy na tuto stránku z související články; zkuste Najít odkaz nástroj pro návrhy. (Září 2014)

A graphoid je sada výpisů z formuláře, “X je irelevantní Y vzhledem k tomu, že víme Z„kde X, Y a Z jsou sady proměnných. Pojem „irelevance“ a „vzhledem k tomu, že víme“ může získat různé interpretace, včetně pravděpodobnostní, relační a korelační, v závislosti na aplikaci. Tyto interpretace sdílejí společné vlastnosti, které lze zachytit cestami v grafech (odtud název „graphoid“). Teorie grafoidů charakterizuje tyto vlastnosti v konečné sadě axiomy které jsou společné pro informační irelevanci a její grafické znázornění.

Dějiny

Judea Pearl a Azaria Paz^[1] vytvořil termín „graphoids“ poté, co zjistil, že vládne množina axiomů podmíněná nezávislost v teorie pravděpodobnosti sdílí neorientované grafy. Proměnné jsou reprezentovány jako uzly v grafu takovým způsobem, že proměnné sady X a Y jsou nezávislé podmíněny Z v distribuci, kdykoli je uzel nastaven Z odděluje X z Y v grafu. Axiomy pro podmíněnou nezávislost v pravděpodobnosti byly odvozeny dříve A. Philip Dawid^[2] a Wolfgang Spohn.^[3]Korespondence mezi závislostí a grafy byla později rozšířena na směrované acyklické grafy (DAG)^[4][5][6] a na další modely závislosti.^[1][7]

Definice

Model závislosti M je podmnožinou trojic (X,Z,Y) pro které predikát Já(X,Z,Y): X je nezávislý na Y daný Z, je pravda. Graphoid je definován jako model závislosti, který je uzavřen v následujících pěti axiomech:

1. Symetrie: ${ displaystyle I (X, Z, Y) Leftrowarrow I (Y, Z, X)}$
2. Rozklad: ${ Displaystyle I (X, Z, Y pohár W) Rightarrow I (X, Z, Y) ~ & ~ I (X, Z, W)}$
3. Slabá unie: ${ displaystyle I (X, Z, Y pohár W) Rightarrow I (X, Z pohár W, Y)}$
4. Kontrakce: ${ displaystyle I (X, Z, Y) ~ & ~ I (X, Z pohár Y, W) Rightarrow I (X, Z, Y pohár W)}$
5. Průsečík: ${ displaystyle I (X, Z pohár W, Y) ~ & ~ I (X, Z pohár Y, W) Rightarrow I (X, Z, pohár W)}$

Semi-grafhoid je model závislosti uzavřený pod 1–4. Těchto pět axiomů dohromady je známo jako grafoidní axiomy.^[8] Slabé vlastnosti spojení a kontrakce intuitivně znamenají, že irelevantní informace by neměly změnit stav relevance jiných propozic v systému; to, co bylo relevantní, zůstává relevantní a co irelevantní zůstává irelevantní.^[8]

Druhy grafoidů

Pravděpodobné grafoidy^[1][7]

Podmíněná nezávislost, definovaná jako

${ displaystyle I (X, Z, Y) Leftrightarrow P (X mid Y, Z) = P (X mid Z)}$

je semi-grafhoid, který se stane úplným grafhoidem, když P je přísně pozitivní.

Korelační grafoidy^[1][7]

Závislostní model je korelační grafoid, pokud v nějaké pravděpodobnostní funkci máme,

${ displaystyle I_ {c} (X, Y, Z) Leftrightarrow rho _ {xy.z} = 0 { text {pro každý}} x v X { text {a}} y v Y}$

kde ${ displaystyle rho _ {xy.z}}$ je částečná korelace mezi X a y daný soubor Z.

Jinými slovy, chyba lineárního odhadu proměnných v X pomocí měření na Z by se nesnížil přidáním měření proměnných v Y, čímž se Y irelevantní pro odhad X. Korelační a pravděpodobnostní modely závislosti se shodují pro normální rozdělení.

Relační grafoidi^[1][7]

Model závislosti je relační grafoid, pokud splňuje

${ Displaystyle P (X, Z)> 0 ~ & ~ P (Y, Z)> 0 znamená P (X, Y, Z)> 0.}$

Slovem rozsah povolených hodnot pro X není omezen výběrem Yjednou Z je opraveno. Prohlášení o nezávislosti patřící k tomuto modelu jsou podobná jako vložené vícehodnotové závislosti (EMVD s) v databázích.

Grafem indukované grafoidy

Pokud existuje neorientovaný graf G takový, že

${ displaystyle I (X, Z, Y) Leftrightarrow langle X, Z, Y rangle _ {G},}$

pak se grafoid nazývá grafem indukovaný. Jinými slovy, existuje neorientovaný graf G tak, že každé prohlášení o nezávislosti v M se odráží jako oddělení vrcholů v G a naopak. Nutnou a dostatečnou podmínkou pro to, aby závislostním modelem byl grafoidem indukovaný grafoid, je splnění následujících axiomů: symetrie, rozklad, průnik, silná unie a tranzitivita.

Tvrdí to silná unie

${ displaystyle I (X, Z, Y) znamená I (X, Z šálek W, Y)}$

Transitivita to uvádí

${ displaystyle I (X, Z, Y) implikuje left ( forall ~ gamma notin X cup Y cup Z, ~~ I (X, Z, gamma) { text {nebo}} I ( gamma, Z, Y) vpravo)}$

Symetrie axiomů, rozklad, průnik, silná unie a tranzitivita tvoří úplnou charakteristiku nepřesměrovaných grafů.^[9]

DAG indukované grafoidy

Graphoid se nazývá DAG-indukovaný, pokud existuje směrovaný acyklický graf D takhle ${ displaystyle I (X, Z, Y) Leftrightarrow langle X, Z, Y rangle _ {D}}$ kde ${ displaystyle langle X, Z, Y rangle _ {D}}$ znamená d-oddělení v D. d-oddělení (d-connotes "directional") rozšiřuje pojem oddělení vrcholů z neorientovaných grafů na směrované acyklické grafy. Umožňuje čtení podmíněných nezávislostí ze struktury Bayesovské sítě. Podmíněné nezávislosti v DAG však nelze zcela charakterizovat konečnou sadou axiomů.^[10]

Zahrnutí a konstrukce

Grafem indukované a DAG indukované grafoidy jsou oba obsaženy v pravděpodobnostních grafoidech.^[11] To znamená, že pro každý graf G existuje rozdělení pravděpodobnosti P tak, aby každá podmíněná nezávislost v P je zastoupena v Ga naopak. Totéž platí pro DAG. Existují však pravděpodobnostní distribuce, které nejsou grafoidní, a navíc neexistuje pravděpodobná konečná axiomatizace pro pravděpodobnostní podmíněné závislosti.^[12]

Thomas Verma ukázal, že každý semi-grafhoid má rekurzivní způsob konstrukce DAG, ve kterém každý d-oddělení je platné.^[13]Konstrukce je podobná konstrukci použité v Bayesovy sítě a jde takto:

1. Uspořádejte proměnné v libovolném pořadí 1, 2, ..., i, ...,N a počínaje i = 1,
2. vyberte pro každý uzel i sada uzlů PA_i takhle i je nezávislý na všech svých předchůdcích, 1, 2, ...,i - 1, podmíněno PA_i.
3. Kreslete šipky z PA_i na i a pokračovat.

DAG vytvořený touto konstrukcí bude představovat všechny podmíněné nezávislosti, které vyplývají z těch použitých při konstrukci. Navíc každý d-oddělení zobrazené v DAG bude platnou podmíněnou nezávislostí na grafu použitém při stavbě.

Reference