Grafoide

Un grafoide es un conjunto de enunciados de la forma " X es irrelevante para Y dado que conocemos Z ", donde X , Y y Z son conjuntos de variables. La noción de "irrelevancia" y "dado que conocemos" puede tener diferentes interpretaciones, incluyendo probabilísticas , relacionales y correlacionales, según la aplicación. Estas interpretaciones comparten propiedades comunes que pueden representarse mediante caminos en grafos (de ahí el nombre de "grafoide"). La teoría de los grafoides caracteriza estas propiedades en un conjunto finito de axiomas comunes a la irrelevancia informacional y sus representaciones gráficas.

Historia

Judea Pearl y Azaria Paz ^{[ 1 ]} acuñaron el término "grafoides" tras descubrir que un conjunto de axiomas que rigen la independencia condicional en la teoría de la probabilidad es compartido por los grafos no dirigidos . Las variables se representan como nodos en un grafo de tal manera que los conjuntos de variables X e Y son independientes condicionados a Z en la distribución siempre que el conjunto de nodos Z separe X de Y en el grafo. Los axiomas para la independencia condicional en probabilidad fueron derivados previamente por A. Philip Dawid ^{[ 2 ]} y Wolfgang Spohn . ^{[ 3 ]} La correspondencia entre dependencia y grafos se extendió posteriormente a los grafos acíclicos dirigidos (DAG) ^{[ 4 ]}^{[ 5 ]}^{[ 6 ]} y a otros modelos de dependencia. ^{[ 1 ]}^{[ 7 ]}

Definición

Un modelo de dependencia M es un subconjunto de tripletas ( X , Z , Y ) para las cuales el predicado I ( X , Z , Y ): X es independiente de Y dado Z , es verdadero. Un grafoide se define como un modelo de dependencia que es cerrado bajo los siguientes cinco axiomas:

Simetría: $I(X,Z,Y)\Leftrightarrow I(Y,Z,X)$
Descomposición: $I(X,Z,Y\cup W)\Rightarrow I(X,Z,Y)~\&~I(X,Z,W)$
Unión débil: $I(X,Z,Y\cup W)\Rightarrow I(X,Z\cup W,Y)~\&~I(X,Z\cup Y,W)$
Contracción: $I(X,Z,Y)~\&~I(X,Z\cup Y,W)\Rightarrow I(X,Z,Y\cup W)$
Intersección: $I(X,Z\cup W,Y)~\&~I(X,Z\cup Y,W)\Rightarrow I(X,Z,Y\cup W)$

Un semigrafoide es un modelo de dependencia cerrado bajo 1–4. Estos cinco axiomas se conocen como los axiomas del grafoide. ^{[ 8 ]} Intuitivamente, las propiedades de unión débil y contracción implican que la información irrelevante no debería alterar el estado de relevancia de otras proposiciones en el sistema; lo que era relevante sigue siendo relevante y lo que era irrelevante sigue siendo irrelevante. ^{[ 8 ]}

Tipos de grafoides

Grafoides probabilísticos

Independencia condicional, definida como

I(X,Z,Y)\Leftrightarrow P(X\mid Y,Z)=P(X\mid Z)

es un semigrafoide que se convierte en un grafoide completo cuando P es estrictamente positivo. ^{[ 1 ]}^{[ 7 ]}

Grafoides correlacionales

Un modelo de dependencia es un grafoide correlacional si en alguna función de probabilidad tenemos,

I_{c}(X,Y,Z)\Leftrightarrow \rho _{xy.z}=0{\text{ para todo }}x\in X{\text{ y }}y\in Y

dónde $\rho _{xy.z}$ es la correlación parcial entre x e y dado el conjunto Z.

En otras palabras, el error de estimación lineal de las variables en X utilizando mediciones en Z no se reduciría al agregar mediciones de las variables en Y , lo que hace que Y sea irrelevante para la estimación de X. Los modelos de dependencia correlacional y probabilística coinciden para distribuciones normales. ^{[ 1 ]}^{[ 7 ]}

Grafoides relacionales

Un modelo de dependencia es un grafoide relacional si satisface

P(X,Z)>0~\&~P(Y,Z)>0\implica P(X,Y,Z)>0.

En otras palabras, el rango de valores permitidos para X no está restringido por la elección de Y , una vez que Z está fijo. Las declaraciones de independencia que pertenecen a este modelo son similares a las dependencias multivaluadas incrustadas (EMVD) en bases de datos. ^{[ 1 ]}^{[ 7 ]}

Grafoides inducidos por grafos

Si existe un grafo no dirigido G tal que,

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

Entonces, el grafoide se denomina grafoinducido. En otras palabras, existe un grafo no dirigido G tal que cada declaración de independencia en M se refleja como una separación de vértices en G y viceversa. Una condición necesaria y suficiente para que un modelo de dependencia sea un grafoide inducido es que satisfaga los siguientes axiomas: simetría, descomposición, intersección, unión fuerte y transitividad.

Estados de unión fuertes que

I(X,Z,Y)\implies I(X,Z\cup W,Y)

La transitividad establece que

I(X,Z,Y)\implies \left(\forall ~\gamma \notin X\cup Y\cup Z,~~I(X,Z,\gamma ){\text{ o }}I(\gamma ,Z,Y)\right)

Los axiomas de simetría, descomposición, intersección, unión fuerte y transitividad constituyen una caracterización completa de los grafos no dirigidos. ^{[ 9 ]}

grafoides inducidos por DAG

Un grafoide se denomina inducido por DAG si existe un grafo acíclico dirigido D tal que $I(X,Z,Y)\Leftrightarrow \langle X,Z,Y\rangle _ {D}$ dónde $\langle X,Z,Y\rangle _ {D}$ d representa la d- separación en D. La d- separación ( d- connota "direccional") extiende la noción de separación de vértices de grafos no dirigidos a grafos acíclicos dirigidos. Permite leer las independencias condicionales a partir de la estructura de las redes bayesianas . Sin embargo, las independencias condicionales en un DAG no pueden caracterizarse completamente mediante un conjunto finito de axiomas. ^{[ 10 ]}

Inclusión y construcción

Los grafoides inducidos por grafos y los inducidos por DAG están contenidos en grafoides probabilísticos. ^{[ 11 ]} Esto significa que para cada grafo G existe una distribución de probabilidad P tal que toda independencia condicional en P está representada en G , y viceversa. Lo mismo ocurre con los DAG. Sin embargo, existen distribuciones probabilísticas que no son grafoides y, además, no existe una axiomatización finita para las dependencias condicionales probabilísticas. ^{[ 12 ]}

Thomas Verma demostró que todo semigrafoide tiene una forma recursiva de construir un DAG en el que toda d- separación es válida. ^{[ 13 ]} La construcción es similar a la utilizada en las redes bayesianas y se realiza de la siguiente manera:

Ordene las variables en algún orden arbitrario 1, 2,...,i,..., N y, comenzando con i = 1,
elegir para cada nodo i un conjunto de nodos PA _i tal que i sea independiente de todos sus predecesores, 1, 2,..., i − 1, condicionado a PA _i .
Dibuja flechas desde PA _i hasta i y continúa.

El DAG creado mediante esta construcción representará todas las independencias condicionales que se derivan de las utilizadas en la construcción. Además, cada d -separación mostrada en el DAG será una independencia condicional válida en el grafoide utilizado en la construcción.

Referencias

1 2 3 4 5 Pearl, Judea; Paz, Azaria (1985). "Graphoids: Una lógica basada en grafos para razonar sobre relaciones de relevancia" (PDF) .
↑ Dawid, A. Philip (1979). "Independencia condicional en la teoría estadística". Journal of the Royal Statistical Society, Serie B : 1–31 .
↑ Spohn, Wolfgang (1980). "Independencia estocástica, independencia causal y capacidad de protección" . Journal of Philosophical Logic . 9 : 73–99 . doi : 10.1007/bf00258078 .
↑ Pearl, Judea (1986). "Fusión, propagación y estructuración en redes de creencias". Inteligencia Artificial . 29 (3): 241– 288. doi : 10.1016/0004-3702(86)90072-x .
↑ Verma, Thomas; Pearl, Judea (1988). "Redes causales: semántica y expresividad". Actas del 4.º Taller sobre Incertidumbre en Inteligencia Artificial : 352–359 .
↑ Lauritzen, SL (1996). Modelos gráficos . Oxford: Clarendon Press.
1 2 3 4 Geiger, Dan (1990). "Graphoids: Un marco cualitativo para la inferencia probabilística" (Tesis doctoral, Informe técnico R-142, Departamento de Ciencias de la Computación, Universidad de California, Los Ángeles) .
1 2 Pearl, Judea (1988). Razonamiento probabilístico en sistemas inteligentes: redes de inferencia plausible . Morgan Kaufmann.
↑ A. Paz, J. Pearl y S. Ur, "Una nueva caracterización de grafos basada en relaciones de intercepción", Journal of Graph Theory, vol. 22, n.º 2, 125-136, 1996.
↑ Geiger, D. (1987). "La no axiomatizabilidad de las dependencias en grafos acíclicos dirigidos" (PDF) . Informe técnico de informática de la UCLA R-83 .
↑ Geiger, D.; Pearl, J. (1993). "Propiedades lógicas y algorítmicas de la independencia condicional y los modelos gráficos". The Annals of Statistics . 21 (4): 2001– 2021. CiteSeerX 10.1.1.295.2043 . doi : 10.1214/aos/1176349407 .
↑ Studeny, M. (1992). Kubik, S.; Visek, JA (eds.). «Las relaciones de independencia condicional no tienen una caracterización completa finita». Teoría de la información, funciones de decisión estadística y procesos aleatorios. Actas de la 11.ª Conferencia de Praga . B. Dordrecht: Kluwer: 377–396 .
↑ Verma, T.; Pearl, J. (1990). Shachter, R.; Levitt, TS; Kanal, LN (eds.). "Redes causales: semántica y expresividad". Incertidumbre en IA 4. Elsevier Science Publishers: 69–76 .

[pearl:paz85-1] 1 2 3 4 5 Pearl, Judea; Paz, Azaria (1985). "Graphoids: Una lógica basada en grafos para razonar sobre relaciones de relevancia" (PDF) .

[dawid:79-2] Dawid, A. Philip (1979). "Independencia condicional en la teoría estadística". Journal of the Royal Statistical Society, Serie B : 1–31 .

[spohn:80-3] Spohn, Wolfgang (1980). "Independencia estocástica, independencia causal y capacidad de protección" . Journal of Philosophical Logic . 9 : 73–99 . doi : 10.1007/bf00258078 .

[pearl:86-4] Pearl, Judea (1986). "Fusión, propagación y estructuración en redes de creencias". Inteligencia Artificial . 29 (3): 241– 288. doi : 10.1016/0004-3702(86)90072-x .

[verma:pea88-5] Verma, Thomas; Pearl, Judea (1988). "Redes causales: semántica y expresividad". Actas del 4.º Taller sobre Incertidumbre en Inteligencia Artificial : 352–359 .

[lauritzen:96-6] Lauritzen, SL (1996). Modelos gráficos . Oxford: Clarendon Press.

[geiger:90-7] 1 2 3 4 Geiger, Dan (1990). "Graphoids: Un marco cualitativo para la inferencia probabilística" (Tesis doctoral, Informe técnico R-142, Departamento de Ciencias de la Computación, Universidad de California, Los Ángeles) .

[pearl:88-8] 1 2 Pearl, Judea (1988). Razonamiento probabilístico en sistemas inteligentes: redes de inferencia plausible . Morgan Kaufmann.

[9] A. Paz, J. Pearl y S. Ur, "Una nueva caracterización de grafos basada en relaciones de intercepción", Journal of Graph Theory, vol. 22, n.º 2, 125-136, 1996.

[geiger:87-10] Geiger, D. (1987). "La no axiomatizabilidad de las dependencias en grafos acíclicos dirigidos" (PDF) . Informe técnico de informática de la UCLA R-83 .

[geiger:pea93-11] Geiger, D.; Pearl, J. (1993). "Propiedades lógicas y algorítmicas de la independencia condicional y los modelos gráficos". The Annals of Statistics . 21 (4): 2001– 2021. CiteSeerX 10.1.1.295.2043 . doi : 10.1214/aos/1176349407 .

[studeny:92-12] Studeny, M. (1992). Kubik, S.; Visek, JA (eds.). «Las relaciones de independencia condicional no tienen una caracterización completa finita». Teoría de la información, funciones de decisión estadística y procesos aleatorios. Actas de la 11.ª Conferencia de Praga . B. Dordrecht: Kluwer: 377–396 .

[verma:pea90-13] Verma, T.; Pearl, J. (1990). Shachter, R.; Levitt, TS; Kanal, LN (eds.). "Redes causales: semántica y expresividad". Incertidumbre en IA 4. Elsevier Science Publishers: 69–76 .

[ 9 ]