Grafoide

Enunciados matemáticos de grafoides

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 obtener diferentes interpretaciones, incluidas las probabilísticas , relacionales y correlacionales, según la aplicación. Estas interpretaciones comparten propiedades comunes que pueden capturarse mediante trayectorias en grafos (de ahí el nombre "grafoide"). La teoría de grafoides caracteriza estas propiedades en un conjunto finito de axiomas que son comunes a la irrelevancia informativa y sus representaciones gráficas.

Historia

Judea Pearl y Azaria Paz ^[1] acuñaron el término "grafoides" después de descubrir que un conjunto de axiomas que gobiernan 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 a X de Y en el grafo. Los axiomas para la independencia condicional en probabilidad fueron derivados anteriormente por A. Philip Dawid ^[2] y Wolfgang Spohn ^[3] . La correspondencia entre dependencia y grafos se extendió más tarde 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 tripletes ( X , Z , Y ) para los 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 está cerrado bajo los siguientes cinco axiomas:

1. Simetría: ${\displaystyle I(X,Z,Y)\Leftrightarrow I(Y,Z,X)}$
2. Descomposición: ${\displaystyle I(X,Z,Y\cup W)\Rightarrow I(X,Z,Y)~\&~I(X,Z,W)}$
3. Unión débil: ${\displaystyle I(X,Z,Y\cup W)\Rightarrow I(X,Z\cup W,Y)~\&~I(X,Z\cup Y,W)}$
4. Contracción: ${\displaystyle I(X,Z,Y)~\&~I(X,Z\cup Y,W)\Rightarrow I(X,Z,Y\cup W)}$
5. Intersección: ${\displaystyle 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 los axiomas 1–4. Estos cinco axiomas en conjunto se conocen como axiomas de grafoide. ^[8] Intuitivamente, las propiedades de unión y contracción débiles significan 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

${\displaystyle 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,

${\displaystyle I_{c}(X,Y,Z)\Leftrightarrow \rho _{xy.z}=0{\text{ for every }}x\in X{\text{ and }}y\in Y}$

donde es la correlación parcial entre x e y dado el conjunto Z. ${\displaystyle \rho _{xy.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

${\displaystyle P(X,Z)>0~\&~P(Y,Z)>0\implies 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 es fijo. Las declaraciones de independencia que pertenecen a este modelo son similares a las dependencias multivaloradas integradas (EMVD) en las bases de datos. ^{[1] [7]}

Grafoides inducidos por grafos

Si existe un grafo no dirigido G tal que,

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

Entonces, el grafoide se llama grafoinducido. En otras palabras, existe un grafo no dirigido G tal que cada enunciado 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.

Un sindicato fuerte afirma que

${\displaystyle I(X,Z,Y)\implies I(X,Z\cup W,Y)}$

La transitividad establece que

${\displaystyle I(X,Z,Y)\implies \left(\forall ~\gamma \notin X\cup Y\cup Z,~~I(X,Z,\gamma ){\text{ or }}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 donde representa d -separación en D . 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 la lectura de independencias condicionales a partir de la estructura de redes bayesianas . Sin embargo, las independencias condicionales en un DAG no pueden caracterizarse completamente mediante un conjunto finito de axiomas. ^[10] ${\displaystyle I(X,Z,Y)\Leftrightarrow \langle X,Z,Y\rangle _{D}}$ ${\displaystyle \langle X,Z,Y\rangle _{D}}$

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 cada independencia condicional en P está representada en G , y viceversa. Lo mismo es cierto para los DAG. Sin embargo, hay distribuciones probabilísticas que no son grafoides y, además, no hay una axiomatización finita para las dependencias condicionales probabilísticas. ^[12]

Thomas Verma demostró que cada semigrafoide tiene una forma recursiva de construir un DAG en el que cada separación d es válida. ^[13] La construcción es similar a la utilizada en las redes de Bayes y es la siguiente:

1. Ordene las variables en un orden arbitrario 1, 2,...,i,..., N y, comenzando con i  = 1,
2. elija para cada nodo i un conjunto de nodos PA _i tales que i sea independiente de todos sus predecesores, 1, 2,..., i  − 1, condicionados a PA _i .
3. Dibuje flechas desde PA _i a i y continúe.

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

Referencias

1. Pearl, Judea; Paz, Azaria (1985). "Graphoids: una lógica basada en grafos para razonar sobre relaciones de relevancia" (PDF) .
2. Dawid, A. Philip (1979). "Independencia condicional en la teoría estadística". Revista de la Royal Statistical Society, Serie B : 1–31.
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.
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.
5. Verma, Thomas; Pearl, Judea (1988). "Redes causales: semántica y expresividad". Actas del 4º Taller sobre incertidumbre en inteligencia artificial : 352–359.
6. Lauritzen, SL (1996). Modelos gráficos . Oxford: Clarendon Press.
7. Geiger, Dan (1990). "Graphoids: A Qualitative Framework for Probabilistic Inference" (Tesis doctoral, Informe técnico R-142, Departamento de Ciencias de la Computación, Universidad de California, Los Ángeles) .
8. 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 gráficos basada en relaciones de interceptación", Journal of Graph Theory, vol. 22, núm. 2, 125-136, 1996.
10. Geiger, D. (1987). "La no axiomatización de dependencias en grafos acíclicos dirigidos" (PDF) . Informe técnico de informática de la UCLA R-83 .
11. Geiger, D.; Pearl, J. (1993). "Propiedades lógicas y algorítmicas de la independencia condicional y modelos gráficos". Anales de Estadística . 21 (4): 2001–2021. CiteSeerX 10.1.1.295.2043 . doi :10.1214/aos/1176349407. 
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.
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.