Un grafoide es un conjunto de declaraciones 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 sabemos" puede obtener diferentes interpretaciones, incluyendo probabilística , relacional y correlacional, dependiendo de la aplicación. Estas interpretaciones comparten propiedades comunes que se pueden capturar mediante rutas en gráficos (de ahí el nombre "grafoide"). La teoría de los 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 grafos no dirigidos . Las variables se representan como nodos en un gráfico 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 gráfico. 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 gráficos se extendió posteriormente a gráficos acíclicos dirigidos (DAG) [4] [5] [6] ya otros modelos de dependencia. [1] [7]
Definición
Un modelo de dependencia M es un subconjunto de tripletes ( X , Z , Y ) para el cual 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 se cierra bajo los siguientes cinco axiomas:
- Simetría:
- Descomposición:
- Unión débil:
- Contracción:
- Intersección:
Un semi-grafoide es un modelo de dependencia cerrado en 1-4. Estos cinco axiomas juntos se conocen como axiomas grafoides. [8] Intuitivamente, las propiedades de unión débil y contracción significan que la información irrelevante no debe 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 [1] [7]
Independencia condicional, definida como
es un semi-grafoide que se convierte en grafoide completo cuando P es estrictamente positivo.
Grafoides correlacionales [1] [7]
Un modelo de dependencia es un grafoide correlacional si en alguna función de probabilidad tenemos,
dónde es la correlación parcial entre x y y dado conjunto Z .
En otras palabras, el error de estimación lineal de las variables en X utilizando mediciones en Z no sería reducida mediante la adición de mediciones de las variables en Y , con lo que Y irrelevante para la estimación de X . Los modelos de dependencia correlacional y probabilística coinciden para distribuciones normales.
Grafoides relacionales [1] [7]
Un modelo de dependencia es un grafoide relacional si satisface
En 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 de valores múltiples integradas (EMVD) en las bases de datos.
Grafoides inducidos por gráficos
Si existe un grafo no dirigido G tal que,
entonces el grafoide se llama inducido por grafos. En otras palabras, existe un gráfico 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 por grafos es que satisfaga los siguientes axiomas: simetría, descomposición, intersección, unión fuerte y transitividad.
Unión fuerte afirma que
La transitividad establece que
Los axiomas simetría, descomposición, intersección, unión fuerte y transitividad constituyen una caracterización completa de grafos no dirigidos. [9]
Grafoides inducidos por DAG
Un grafoide se denomina inducido por DAG si existe un gráfico acíclico dirigido D tal que dónde representa d : se separa en D . d -separation ( 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 independientes condicionales de la estructura de redes bayesianas . Sin embargo, las independientes condicionales en un DAG no se pueden caracterizar completamente por un conjunto finito de axiomas. [10]
Inclusión y construcción
Los grafoides inducidos por gráficos y los inducidos por DAG están contenidos en grafoides probabilísticos. [11] Esto significa que para cada gráfico G existe una distribución de probabilidad P tal que cada 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 cada separación d es válida. [13] La construcción es similar a la utilizada en las redes Bayes y es la siguiente:
- Organizar las variables en algún orden arbitrario 1, 2, ..., i, ..., N y, comenzando con i = 1,
- elija para cada nodo i un conjunto de nodos PA i tal que i sea independiente de todos sus predecesores, 1, 2, ..., i - 1, condicionado por PA i .
- Dibuja flechas de PA i a i y continúa.
El DAG creado por esta construcción representará todas las dependencias 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
- ^ a b c d e Perla, Judea; Paz, Azaria (1985). "Grafoides: una lógica basada en gráficos para razonar acerca de las relaciones de relevancia" (PDF) .
- ^ Dawid, A. Philip (1979). "Independencia condicional en teoría estadística". Revista de la Royal Statistical Society, Serie B : 1–31.
- ^ Spohn, Wolfgang (1980). "Independencia estocástica, independencia causal y capacidad de protección" . Revista de lógica filosófica . 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.
- ^ a b c d Geiger, Dan (1990). "Grafoides: 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) .
- ^ a b 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 gráficos basada en relaciones de intercepción" Journal of Graph Theory, vol. 22, N ° 2, 125-136, 1996.
- ^ Geiger, D. (1987). "La no axiomatizabilidad de dependencias en grafos acíclicos dirigidos" (PDF) . Informe tecnológico de ciencias de la computación de UCLA R-83 .
- ^ Geiger, D .; Pearl, J. (1993). "Propiedades lógicas y algorítmicas de la independencia condicional y 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. Transacciones de la XI Conferencia de Praga . Dordrecht: Kluwer. B : 377–396.
- ^ Verma, T .; Pearl, J. (1990). Shachter, R .; Levitt, TS; Kanal, LN (eds.). "Redes causales: semántica y expresividad". Incertidumbre en IA 4 . Editores de ciencia de Elsevier: 69–76.