modelos definidos gráficamente (2010/2011)
TRANSCRIPT
Modelos
Definidos
Gráficamente
(2010/2011)
Luis Valencia Cabrera
(http://www.cs.us.es/~lvalencia)
Ciencias de la Computacion e IA
(http://www.cs.us.es/)
Universidad de Sevilla
Hemos visto que… El funcionamiento de un sistema experto probabilístico depende
de la correcta definición del modelo, caracterizado por la función de probabilidad conjunta de las variables.
La estructura general de una función de probabilidad conjunta involucra un excesivo nº de parámetros. Se presentaron modelos simplificados, con hipótesis de
independencia globales sobre las variables. Problema: son restrictivos y sólo aplicables a problemas del tipo
“enfermedades-síntomas”.
A continuación se desarrolla la forma de obtener modelos probabilísticos más generales por medio de grafos. Utilizar grafos (no dirigidos o dirigidos) para construir un modelo de
dependencia que represente la estructura cualitativa del modelo probabilístico.
De esta forma, los modelos resultantes son generales, pues se crean a partir de un modelo de dependencia “arbitrario”, y no de uno impuesto inicialmente.
Notación - terminología Modelo probabilístico: estructura cualitativa y cuantitativa dada por una
función de probabilidad. Se utilizará como sinónimo de función de probabilidad.
Modelo de dependencia y modelo de independencia: estructura cualitativa de las relaciones entre variables. Permite comprobar conjuntos de variables incondicionalmente o condicionalmente dependientes o independientes.
Cada modelo probabilístico tiene asociado un modelo de dependencia M, que puede ser obtenido generando todas las relaciones de independencia condicional posibles para un conjunto de variables dado, y comprobando cuáles se satisfacen para la función de probabilidad. Ej: si X, Y y Z son tres subconjuntos disjuntos y p(x|y, z) = p(x|z), para cada
combinación de valores de x, y y z se verifica la relación de independencia I(X, Y |Z) X e Y son condicionalmente independientes dado Z.
Si p(x|y, z) = p(x|z) para algunos valores x, y, z, entonces X e Y son condicionalmente dependientes dado Z.
Así, se tiene que: Una función de probabilidad contiene una descripción completa (cuantitativa y
cualitativa) de las relaciones entre las variables, El modelo de dependencia M asociado sólo contiene una descripción
cualitativa. Modelo de dependencia probabilístico se refiere únicamente a modelo de dependencia asociado a una función de probabilidad.
Modelos de dependencia Como hemos visto, un modelo de dependencia
puede ser definido de forma alternativa mediante: Un grafo (dirigido o no dirigido), Una lista de relaciones de independencia, o Un conjunto de funciones de probabilidad
condicionada.
Estas tres alternativas determinan tres metodologías diferentes para construir un modelo de dependencia: Modelos definidos gráficamente. Modelos definidos por listas de independencias. Modelos definidos condicionalmente.
Alcance de los modelos Las tres metodologías son más generales que los modelos
presentados en el tema introductorio de los sistemas basados en probabilidad: Modelo de Síntomas Dependientes (MSD).
Modelo de Síntomas Independientes (MSI).
Modelo de Síntomas Relevantes Independientes (MSRI).
Modelo de Síntomas Relevantes Dependientes (MSRD).
Pueden ser aplicadas a problemas más generales que sólo a problemas de diagnóstico médico (tipo “síntoma-enfermedad”).
Requieren conceptos previos: Criterios de separación gráfica,
Propiedades de independencia condicional,
Grafoides y semigrafoides,etc.
tratados en el tema anterior.
Contenido del tema Este tema se centra en los modelos definidos gráficamente.
De forma más precisa, a los modelos definidos a partir de un único grafo. (El problema de los modelos descritos por un conjunto de grafos se analizará en el tema siguiente.)
En el tema de grafos se ha visto que un conjunto de variables X1, . . . , Xn y sus relaciones pueden ser representados mediante un grafo, asociando cada variable a un nodo y cada relación entre variables a una arista entre los nodos correspondientes. Nodo y variable se utilizan de forma sinónima. El orden de las variables (es decir, la dirección de las aristas) es
importante en algunos grafos (grafos dirigidos) y no en otros (grafo no dirigido).
Ventajas de los grafos: Muestran explícitamente las relaciones entre variables y las
conservan de forma cualitiativa (para cualquier valor numérico de los parámetros).
Son más intuitivos y fáciles de entender.
Distinción entre grafo dirigidos
y no dirigidos En el tema anterior se analizaron dos criterios gráficos de
separación para obtener las relaciones de independencia definidas por los grafos dirigidos y los no dirigidos.
Según esta distinción, los modelos definidos gráficamente pueden ser clasificados en dos grupos, dependiendo del tipo de grafo que se utilice: Modelos de dependencia definidos por grafos no dirigidos,
analizados en la sección 3 de este tema.
Modelos de dependencia definidos por grafos dirigidos, analizados en la sección 4.
Existe un tercer tipo de modelos gráficos que pueden ser representados por grafos mixtos (grafos con aristas dirigidas y no dirigidas), pero no se atienden aquí. Este tema se dedica a modelos definidos por grafos dirigidos y no dirigidos. Se puede leer sobre modelos de grafos mixtos en Lauritzen y Wermuth (1989) y Frydenberg (1990).
Aclaración Se ha utilizado el término dependencia en las definiciones
anteriores para enfatizar que un grafo sólo puede definir la estructura cualititativa del modelo.
Una vez que se conoce esta estructura cualitativa, puede construirse una factorización de la función de probabilidad e identificarse el conjunto de parámetros que definen el modelo. Los valores numéricos de los parámetros pueden ser dados por un experto, o estimados a partir de un conjunto de datos disponibles (como vimos en el tema anterior, en la sección de construcción de un sistema probabilístico).
El conjunto de funciones de probabilidad condicionada junto con los valores de los parámetros asignados se conoce como la estructura completa del modelo.
A lo largo del tema… En este tema se analiza también la capacidad de los
grafos dirigidos y no dirigidos para captar ciertos tipos de estructuras de dependencia propias de los modelos probabilísticos, o de los modelos de dependencia en general.
En la sección siguiente se introducen algunas definiciones y problemas a analizar.
Las dos secciones posteriores analizan los modelos de dependencia definidos por grafos no dirigidos y dirigidos, respectivamente.
A continuación se define y caracteriza las clases de modelos gráficos equivalentes.
La última sección del tema analiza la capacidad de los grafos dirigidos y no dirigidos para representar modelos de dependencia.
Algunas Definiciones y
Problemas El objetivo de este tema es representar un modelo de
dependencia probabilíıstico mediante un grafo. Por tanto, es importante conocer si los grafos permiten representar cualquier tipo de modelo de dependencia.
Definición Mapa perfecto. Un grafo G se dice que es un mapa perfecto de un
modelo de dependencia M si cada relación de independencia obtenida de G también puede ser obtenida de M y viceversa, es decir, I(X, Y |Z)M ⇔ I(X, Y |Z)G ⇔ Z separa X de Y.
Dependiendo del carácter dirigido o no dirigido del grafo G, los mapas perfectos se denominan mapas perfectos dirigidos o no dirigidos, respectivamente.
Mapa perfecto Dado que es necesario tratar con dos tipos de
grafos distintos, es necesario reformular el problema anterior de la forma siguiente:
Problema: ¿Puede representarse mediante un mapa perfecto dirigido o no dirigido cualquier modelo de dependencia? Desafortunadamente, no todo modelo de
dependencia tiene asociado un mapa perfecto. Los dos ejemplos siguientes muestran dos modelos de dependencia que no poseen un mapa perfecto.
En las secciones posteriores sobre grafos no dirigidos y dirigidos pueden encontrarse más ejemplos.
Ejemplo Modelo sin mapa
perfecto no dirigido Sea el conjunto de tres variables {X, Y,Z} relacionadas por el
siguiente modelo de dependencia M = {I(X, Y | Φ), I(Y,X|Φ)}, que sólo contiene una relación de independencia y su simétrica.
Se quiere representar este modelo por medio de un grafo no dirigido. En general, para un conjunto de n nodos podrían construirse los 2
𝑛(𝑛−1)/2grafos no dirigidos distintos (ver Whittaker
(1990)). La figura muestra los ocho grafos para el caso de tres variables.
Ejemplo Modelo sin mapa
perfecto no dirigido Estos grafos están ordenados en filas con grafos con el mismo nº aristas. La
figura (a) corresponde al grafo totalmente inconexo (sin ninguna arista), los grafos en (b)−(d) contienen 1 arista, los grafos en (e)−(g) contienen 2, y el último grafo es el grafo completo. La 2ª columna de la tabla muestra relaciones de independencia implicadas por cada uno de los grafos, y no contenidas en M. Se puede comprobar utilizando el criterio de U-separación. La última columna muestra cuando las relaciones de independencia de M están contenidas en el grafo G. Cada grafo G se puede encontrar una relación de independencia no contenida en M y/o viceversa. Por tanto, ninguno de los grafos de la figura es un mapa perfecto de M. Como este conjunto de grafos es exhaustivo, el modelo de dependencia M no posee mapa perfecto no dirigido.
Ejemplo Modelo sin mapa
perfecto no dirigido El modelo de dependencia M del ejemplo tiene un mapa perfecto
dirigido, a pesar de que no posee ningún mapa perfecto no dirigido. Un ejercicio consistiría en demostrar que el grafo dirigido mostrado en la figura es un mapa perfecto dirigido de M. En este caso, los grafos dirigidos son más potentes que los no dirigidos. Sin embargo, no todo modelo de dependencia posee un mapa perfecto dirigido.
Ejemplo Modelo sin mapa
perfecto dirigido El ejemplo siguiente muestra uno de estos modelos.
Ejemplo Modelo sin mapa perfecto dirigido. Sea el
conjunto de variables {X, Y,Z} y el modelo de dependencia M = {I(X, Y |Z), I(Y,Z|X), I(Y,X|Z), I(Z, Y |X)}.
No existe ningún grafo dirigido acíclico D que sea mapa perfecto del modelo de dependencia M.
En los casos en los que no existe un mapa perfecto, es necesario asegurarse de que el modelo gráfico que se utilice no posea ninguna independencia no contenida en el modelo, y que el nº de independencias del modelo que no sean reproducidas por el grafo sea mínimo.
Esto motiva las siguientes definiciones.
Mapa de independencia Definición Mapa de independencia. Un grafo G se dice que es un mapa de independencia (I-mapa)
de un modelo de dependencia M si I(X, Y |Z)G ⇒ I(X, Y |Z)M,
es decir, si todas las relaciones de dependencia derivadas de G son verificadas por M.
Un I-mapa G de un modelo de dependencia M incluye algunas de las independencias de M, pero no necesariamente todas. Entonces, se tiene I(X, Y |Z)G ⇒ I(X, Y |Z)M, lo cual implica D(X, Y |Z)M ⇒ D(X, Y |Z)G.
Por tanto, todas las dependencias de M están representadas en G. Por ejemplo, solamente el grafo completo de la figura previa es un I-mapa del modelo de dependencia dado. Cada uno de los grafos restantes implica algunas independencias que no son propias de M (ver tabla anterior). En general, un grafo completo es siempre un I-mapa trivial de cualquier modelo de dependencia.
Mapa de dependencia Definición Mapa de dependencia. Un grafo G se dice que es un mapa de
dependencia (D-mapa) de un modelo de dependencia M si D(X, Y |Z)G ⇒ D(X, Y |Z)M,
es decir, todas las relaciones de dependencia derivadas de G son verificadas por M.
Si G es un D-mapa de M, se tiene D(X, Y |Z)G ⇒ D(X, Y |Z)M, lo cual implica
I(X, Y |Z)M ⇒ I(X, Y |Z)G,
es decir, todas la independencias de M están representadas en G.
Modelo de dependencia Observe que un D-mapa de un modelo de dependencia
M sólo incluye algunas de las dependencias de M. Por ejemplo, el grafo totalmente inconexo de la figura
previa (h) es un D-mapa trivial, aunque inútil, del modelo de dependencia dado. Los grafos de las figuras (c) y (d) son también D-mapas del modelo de dependencia.
Por tanto, cada modelo de dependencia tiene asociados un I-mapa y un D-mapa triviales. Por ejemplo, cualquier grafo totalmente inconexo es un D-mapa trivial y cualquier grafo completo es un I-mapa trivial de cualquier modelo de dependencia. De esta forma, para que un grafo sea un mapa perfecto de un modelo, ha de ser simultáneamente un I-mapa y un D-mapa de ese modelo.
Definición I-mapa minimal Se dice que un grafo G es un I-mapa minimal de un modelo de dependencia M si
es un I-mapa de M, pero pierde esta propiedad cuando se elimina una cualquiera de sus aristas.
Los modelos de dependencia y las representaciones gráficas tienen numerosas aplicaciones, pero el interés principal para nosotros es la construcción de modelos probabilísticos Nos interesa conocer la relación entre las representaciones gráficas y las funciones de
probabilidad (relación entre nociones formales de dependencia probabilística y estructura topológica de un grafo).
Razón importante para representar la estructura de dependencia de un modelo mediante un grafo: comprobar la conexión de un conjunto de variables en un grafo (utilizando criterios de separación gráfica) es más fácil que comprobar la independencia condicional de un conjunto de variables utilizando fórmulas de Probabilidad.
Un D-mapa garantiza que todos los nodos conectados en el grafo serán dependientes; sin embargo, el grafo puede representar desconectados algunos conjuntos de variables dependientes. Por el contrario, un I-mapa garantiza que los nodos separados en el grafo siempre corresponden a variables independientes, pero no garantiza que todos los nodos conectados sean dependientes.
Los grafos totalmente inconexos son D-mapas triviales, mientras que los grafos completos son I-mapas triviales.
Modelos gráficos El problema de definir un modelo gráfico asociado a un modelo
de dependencia dado no es trivial.
Cuando se trata con un modelo donde la noción de vecindad/conexión es explícita (relaciones familiares, circuitos, redes de comunicación, etc.) hay pocos problemas para definir un grafo que represente las características principales del modelo.
Sin embargo, cuando se trata con relaciones conceptuales como asociación o relevancia, es a menudo difícil distinguir entre vecinos directos e indirectos. En estos casos, construir una representación gráfica es más difícil. Un ejemplo claro es la noción de independencia condicional en
probabilidad. Dada una función de probabilidad de tres variables X, Y y Z, es fácil comprobar si X e Y son independientes dada Z; sin embargo, la función de probabilidad no proporciona información sobre cuál de las variables es la causa y cuál el efecto.
Modelos gráficos Se introdujeron conceptos elementales sobre la
teoría de grafos y se ha visto que: los nodos de un grafo representan variables y
las aristas representan dependencias locales entre variables conceptualmente relacionadas.
Las aristas de un grafo permiten representar relaciones cualitativas y la topología del grafo muestra estas relaciones de forma explícita y las conserva tras la asignación numérica de los parámetros.
Este tema analiza la forma de representar algunos modelos probabilísticos mediante grafos dirigidos y no dirigidos.
Problemas asociados Como no todo modelo probabilístico puede ser representado por
un mapa perfecto, se presentan los siguientes problemas:
Problema: ¿Cuáles son los modelos de dependencia y, en particular, los modelos de dependencia probabilísticos que pueden ser representados por un mapa perfecto?
Problema: ¿Cuáles son los modelos de dependencia probabilísticos que poseen un único I-mapa minimal?
Problema: Si un modelo probabil´ıstico posee un único I-mapa minimal, ¿cómo se puede obtener este I-mapa?
Problema: Dado un grafo G, ¿existe algún modelo probabilístico P tal que G sea un I-mapa minimal de P?. En caso afirmativo, ¿c´omo se puede construir?
En la sección siguiente se analizarán estos problemas para los grafos no dirigidos y en la posterior para el caso de grafos dirigidos.
El problema del tema anterior: «¿cuál es la clase de modelos probabilísticos que puede ser representada por grafos?» se ha dividido ahora en dos partes: los dos primeros problemas arriba.
Modelos de Dependencia
Gráficos no Dirigidos En esta sección se analiza la forma de definir
modelos de dependencia utilizando grafos no dirigidos.
Objetivo: encontrar un grafo que reproduzca tantas independencias asociadas a un modelo probabilístico como sea posible. Se comienza con el problema de representar
estos modelos por medio de mapas perfectos e I-mapas y,
a continuación, se introduce un clase importante de modelos probabilísticos definidos por grafos no dirigidos.
Estos modelos se conocen por redes de Markov.
De Modelos a
Grafos no Dirigidos Esta sección analiza el problema de representar modelos
probabilísticos utilizando grafos no dirigidos. Objetivo: encontrar el grafo correspondiente a un modelo
de dependencia probabilístico. Como se ha visto en el primer ejemplo del tema, no todos
lo modelos probabilísticos de dependencia pueden ser representados por mapas perfectos no dirigidos.
Pearl y Paz (1987) probaron el siguiente teorema que caracteriza los modelos de dependencia que pueden ser representados mediante mapas perfectos no dirigidos.
El teorema se refiere no sólo a modelos de dependencia probabilísticos, sino a modelos de dependencia en general.
Teorema - Modelos con mapa
perfecto no dirigido Una condición necesaria y suficiente para que un modelo
de dependencia M tenga un mapa perfecto no dirigido es que satisfaga las siguientes propiedades: Simetría:
I(X, Y |Z)M ⇔ I(Y,X|Z)M.
Descomposición: I(X, Y ∪ W|Z)M ⇒ I(X, Y |Z)M y I(X,W|Z)M.
Intersección: I(X,W|Z ∪ Y )M y I(X, Y |Z ∪W)M ⇒ I(X, Y ∪ W|Z)M.
Unión fuerte: I(X, Y |Z)M ⇒ I(X, Y |Z ∪W)M.
Transitividad fuerte: I(X, Y |Z)M ⇒ I(X,A|Z)M o I(Y,A|Z)M,
donde A es un conjunto formado por un único nodo no contenido en {X, Y,Z}.
Modelos con mapa perfecto
no dirigido Así, la respuesta al primer problema planteado para el caso de grafos no
dirigidos es que solamente los modelos de dependencia que satisfagan estas propiedades tienen un mapa perfecto no dirigido, en el sentido de que las dependencias e independencias correspondientes al modelo y al mapa perfecto son las mismas.
El caso de grafos dirigidos es analizado en la sección siguiente.
En general, los grafoides y los semigrafoides no tienen mapas perfectos no dirigidos, pues los semigrafoides solamente han de cumplir las propiedades de simetría y descomposición y los grafoides sólo han de verificar las propiedades de simetría, descomposición, e intersección.
El modelo de dependencia del primer ejemplo es un grafoide, pero no tiene asociado un mapa perfecto, pues viola las propiedades de unión y transitividad fuerte.
Los modelos probabilísticos de dependencia también pueden violar las dos últimas propiedades y, por tanto, no todo modelo probabilístico puede representarse mediante un mapa perfecto no dirigido. Los siguientes ejemplos ilustran este hecho.
Ejemplo
Violación de la unión fuerte y
la transitividad fuerte La propiedad de unión fuerte afirma que si X e Y son
independientes dado Z, entonces también son independientes dado un conjunto mayor Z ∪ W: I(X, Y |Z) ⇒ I(X, Y |Z ∪ W).
Por ejemplo, considerando Z = Φ, esta propiedad implica: I(X, Y | Φ) ⇒ I(X, Y |W), que afirma que si X e Y son incondicionalmente independientes,
entonces también deben ser condicionalmente independientes dado otro subconjunto de variables cualquiera W.
Esta afirmación no es siempre cierta para modelos probabilísticos. Por ejemplo para la familia de funciones de probabilidad dada por
la factorización p(x, y, z) = p(x)p(y)p(z|x, y), se tiene I(X, Y | Φ), pero I(X, Y |Z) no es cierto, en general.
Por tanto, p(x, y, z) viola la propiedad de unión fuerte y, por esta razón, no puede ser representada por un mapa perfecto no dirigido, tal y como se ha visto en el ejemplo.
Ejemplo
Violación de la unión fuerte y
la transitividad fuerte Esta familia de funciones de probabilidad también viola la propiedad
de transitividad fuerte. Según esta propiedad, y considerando Z = Φ, se tiene I(X, Y | Φ) ⇒ I(X,A| Φ) o I(Y,A| Φ),
donde A es un conjunto formado por un único nodo distinto de {X, Y }.
En este caso A = Z. Sin embargo, aunque se cumple I(X, Y | Φ), la familia de probabilidades anterior no satisface ni I(X,Z| Φ) ni I(X,Z| Φ).
Ejercicio: hallar una combinación de valores numéricos para los parámetros asociados a las funciones de probabilidad condicionada de la familia que permitan obtener una función de probabilidad p(x, y, z) que viole ambas propiedades.
Notar que estos parámetros no pueden ser elegidos arbitrariamente pues alguna elección específica de los parámetros puede hacer que las variables X y Z, o Y y Z sean independientes y, por tanto, las propiedades anteriores no serían violadas.
Ejemplo… El ejemplo siguiente ilustra la violación de las
propiedades de:
unión fuerte y
transitividad fuerte
utilizando una función de probabilidad de tipo continuo.
Este ejemplo requiere una propiedad que vemos ahora sobre la función de distribución normal multivariada (ver Anderson (1984), Johnson y Wichern (1988), o Rencher (1995)).
Teorema – Distribución
normal multivaluada
Ejemplo
Violación de la unión fuerte y
la transitividad fuerte Sean las variables (X1,X2,X3) distribuidas de forma normal con
La propiedad de unión fuerte implica que si los conjuntos de variables X e Y son incondicionalmente independientes, entonces, también han de ser condicionalmente independientes dado otro subconjunto W. Es decir, I(X, Y | Φ) ⇒ I(X, Y |W).
En este ejemplo, las únicas variables incondicionalmente independientes son X1 y X2, ya que ΣX1X2 = ΣX2X1 = 0. Por tanto, se tiene I(X1,X2| Φ). Sin embargo, X1 y X2 no son condicionalmente independientes dada X3, es decir, no se verifica I(X1,X2|X3). (Para comprobar esta última afirmación, se utiliza la fórmula anterior para calcular:
Ejemplo
Violación de la unión fuerte y
la transitividad fuerte De los cálculos anteriores se obtiene que las funciones de distribución normales
de las variables (X1|X3) y (X1|X2,X3) son distintas la distribución normal cuya matriz de covarianzas se ha mostrado viola la propiedad de unión fuerte no puede ser representada por un mapa perfecto no dirigido.
De forma similar, para demostrar la violación de la propiedad de transitividad fuerte, se considera Z = Φ, obteniéndose
donde A es un conjunto de una única variable que no está contenida en {X, Y }. Esta propiedad no se verifica en el modelo probabilístico normal dado. Para comprobarlo, se toma X = X1, Y = X2, y A = X3. Se conoce que X1 y X2 son incondicionalmente independientes, pero cada una de ellas depende de X3. Las ecuaciones resueltas en la diapositiva anterior muestran que X1 y X3 no son independientes, pues ΣX1|X3 = ΣX1X1 . Por otra parte, utilizando ΣX|Y, se tiene
que muestra que X2 no es independiente de X3. Por tanto, el modelo probabilístico normal multivariado dado no satisface la propiedad de transitividad fuerte.
Conclusión del ejemplo En los casos en los que es imposible construir un mapa
perfecto, se trata de construir un I-mapa del modelo dado. A partir de la definición de I-mapa de independencia, se
sigue que todo modelo probabilístico posee un I-mapa pero, para que éste represente el mayor nº posible de independencias de M, ha de ser un minimal.
Sin embargo, obsérvese que un modelo de dependencia probabilístico puede no tener un único I-mapa minimal.
El siguiente teorema, debido a Pearl y Paz (1987) (ver también Verma y Pearl (1990)), muestra las condiciones que ha de satisfacer un modelo de dependencia para tener asociado un único I-mapa no dirigido minimal. Este teorema muestra también la forma de construirlo.
Teorema
I-mapa no dirigido minimal Todo modelo de dependencia M de un conjunto de
variables X = {X1, . . . , Xn} que satisfaga las propiedades de simetría, descomposición, e intersección tiene un único I-mapa no dirigido minimal que se obtiene eliminando del grafo completo toda arista (Xi,Xj) que satisfaga I(Xi,Xj |X\{Xi,Xj})M, donde X\{Xi,Xj} denota el conjunto de variables en X excluyendo aquellas en Xi y Xj .
Observe que los modelos probabilísticos no extremos satisfacen las tres propiedades exigidas en el teorema. Por tanto, cada función de probabilidad no extrema
tiene asociado un único I-mapa no dirigido minimal.
Teorema
I-mapa no dirigido minimal El teorema muestra la solución del segundo problema planteado
para grafos no dirigidos: «¿cuáles son los modelos de dependencia probabilísticos que poseen un único I-mapa minimal?»
El caso de grafos dirigidos se analizará en la sección siguiente.
Observe que los grafoides satisfacen las propiedades de simetría, descomposición, e intersección. Por tanto, una característica importante de los grafoides es que
poseen I-mapas no dirigidos minimales únicos, y permiten, por tanto, su construcción a través de independencias locales. Conectando cada variable Xi en X con cualquier otro subconjunto de variables que haga que Xi sea condicionalmente independiente del resto de las variables, se obtendrá un grafo que será un I-mapa del grafoide.
Esta construcción local no está garantizada para el caso de semigrafoides.
Ejemplo
I-mapa minimal no dirigido (I) Sea el conjunto de cuatro variables {X1,X2,X3,X4} relacionadas por el modelo
de dependencia: M = {I(X1,X2|X3), I(X1,X4|X2), I(X1,X4|{X2,X3}), I(X2,X1|X3), I(X4,X1|X2),
I(X4,X1|{X2,X3})},
Este modelo de dependencia cumple las tres propiedades requeridas en el teorema. Por tanto, puede obtenerse el I-mapa no dirigido minimal asociado
comprobando qué independencias de la forma I(Xi,Xj |X \ {Xi,Xj})M se cumplen en M.
Todas las posibles relaciones de independencia de esta forma para un conjunto de cuatro variables son I(X1,X2|{X3,X4}), I(X1,X3|{X2,X4}), I(X1,X4|{X2,X3}), I(X2,X3|{X1,X4}), I(X2,X4|{X1,X3}), I(X3,X4|{X1,X2}).
La única relación de independencia de esta lista que se cumple en M es I(X1,X4|{X2,X3}). Por tanto, para obtener el I-mapa no dirigido minimal de M únicamente ha de eliminarse la arista (X1 − X4) del grafo completo de la Figura 6.3(a). El grafo resultante se muestra en la Figura 6.3(b). (Ver diapositiva siguiente)
Ejemplo
I-mapa minimal no dirigido (I)
Ejemplo
I-mapa minimal no dirigido (I) Sea el nuevo modelo de dependencia M’ creado añadiendo la relación de
independencia I(X1,X2|{X3,X4}) al modelo M: M’ = M ∪ {I(X1,X2|{X3,X4})}.
Si se aplica a M’ el procedimiento anterior para construir un grafo no dirigido (ver teorema) se obtendrá el grafo dado en la Figura 6.3(c).
Sin embargo, este grafo no es un I-mapa de M’. Por ejemplo, la independencia I(X1,X4|X3)G se cumple en el grafo, pero no
está contenida en M’. La razón es que M’ no cumple las condiciones del teorema.
Por ejemplo, si se aplica la propiedad de intersección a I(X1,X2|{X3,X4}) e I(X1,X4|{X2,X3}) se obtiene I(X1, {X2,X4}|X3); si después se aplica descomposición a I(X1, {X2,X4}|X3) se tienen I(X1,X2|X3) y I(X1,X4|X3), no contenidas en M’.
De forma similar, si se aplica intersección a I(X1,X4|X2) y I(X1,X2|{X3,X4}) se obtiene I(X1, {X2,X4}| Φ) y aplicando descomposición se tienen I(X1,X2| Φ) y I(X1,X4|Φ). Por tanto, el modelo de dependencia M ∪ C, tiene el grafo dado en la Figura 6.3(c) como único I-mapa minimal, donde C es el conjunto que contiene las siguientes relaciones de independencia y sus relaciones simétricas: I(X1,X2|{X3,X4}), I(X1, {X2,X4}|X3), I(X1,X4|X3), I(X1, {X2,X4}| Φ) I(X1,X2| Φ), I(X1,X4| Φ).
Ejemplo
I-mapa minimal no dirigido (I) A partir del teorema se deduce que toda función de probabilidad no
extrema tiene asociado un único I-mapa no dirigido minimal obtenido eliminando del grafo completo toda arista Lij entre nodos Xi y Xj tales que I(Xi,Xj |X \ {Xi,Xj})P .
Observesque I(Xi,Xj |X \ {Xi,Xj})P es equivalente a
que implica
Esto sugiere el siguiente algoritmo para resolver el tercer problema planteado en el caso de grafos no dirigidos: «Si un modelo probabilístico posee un único I-mapa minimal, ¿cómo se puede obtener este I-mapa?”.
En la sección siguiente se analiza el caso de grafos dirigidos.
Algoritmo I-Mapa minimal
no dirigido Datos: Un conjunto de variables X = {X1, . . . , Xn} y una función de
probabilidad no extrema p(x).
Resultados: El I-mapa minimal no dirigido correspondiente a p(x).
1. Considérese un grafo completo de n nodos, en el cual existe una arista
entre cada par de nodos.
2. Para cada par de nodos (Xi,Xj) calcular
Entonces, si
eliminar la arista Lij entre los nodos Xi y Xj .
Ejemplo I-mapa minimal no
dirigido (II). Sea el conjunto de variables binarias X = {X1, . . . ,
X7} y una función de probabilidad definida mediante la factorización p(x) = p(x1)p(x2|x1)p(x3|x1)p(x4|x2,
x3)p(x5|x3)p(x6|x4)p(x7|x4).
que depende de 15 parámetros θ1, . . . , θ15.
Se desea construir el I-mapa minimal no dirigido asociado a p(x). La figura muestra un programa de ordenador que implementa el algoritmo para este caso. Este programa está escrito en Mathematica (verWolfram (1991)) pero puede ser implementado de forma similar en cualquier otro programa de cálculo simbólico.
Programa
Ejemplo I-mapa minimal no
dirigido (II). Comienza definiendo la función de probabilidad. Con este
fin se introducen las funciones PA[i], PB[i, j], etc., que se definen simbólicamente utilizando los parámetros p1, . . . , p15.
A continuación, se define la función de probabilidad conjunta como el producto de estas funciones.
Las funciones P1[i] y P2[i, j] son funciones auxiliares definidas para obtener funciones de probabilidad marginales de una variable Xi, o de dos variables Xi y Xj , respectivamente.
La última parte del programa comprueba si se satisface la condición anterior para todas las posibles combinaciones de nodos Xi y Xj .
Tras la ejecución del programa, se deduce que las aristas siguientes pueden ser eliminadas del grafo: L14, L15, L16, L17, L23, L25, L26,
L27, L36, L37, L45, L56, L57, L67.
Por tanto, comenzando con el grafo completo, en el que cada par de nodos está unido por una arista, se obtiene el grafo de la figura, que es el I-mapa minimal no dirigido correspondiente al modelo probabilístico dado.
Ejemplo I-mapa minimal
no dirigido (III) Suponga que una función de probabilidad de cinco
variables viene dada por la factorización p(x) = ψ1(x1, x2, x3)ψ2(x1, x3, x4)ψ3(x1, x4, x5),
donde ψ1, ψ2, y ψ3 son funciones positivas (factores potenciales) indeterminadas.
La figura muestra el I-mapa obtenido tras la ejecución del programa. Puede comprobarse que el I-mapa minimal no dirigido asociado a la función de probabilidad p(x) se obtiene eliminando las aristas L24, L25 y L35 del grafo completo.