5.2 Flujo de probabilidad y d-Separación

De la discusión anterior, definimos caminos activos en una gráfica los que, dada cierta evidencia \(Z\), pueden potencialmente transmitir información probabilística.

Sea \(U\) un camino no dirigido en una gráfica \({\mathcal G}\). Decimos que el camino es activo dada evidencia \(W\) si:

  • Todos los colisionadores en el camino \(U\) están o tienen un descendiente en \(W\).

  • Ningún otro vértice de el camino está en \(W\).


Un caso adicional interesante es cuando los descendiente de un colisionador activan un camino.

  1. ¿Cuáles de los siguientes son caminos activos si observamos Calificación?
  1. \(Coh \rightarrow Dif \rightarrow Calif \leftarrow Int \rightarrow GRE\)
  2. \(Int \rightarrow Cal \rightarrow Rec \leftarrow Tra \rightarrow Fel\)
  3. \(Int \rightarrow GRE \rightarrow Tra \rightarrow Fel\)
  4. \(Coh \rightarrow Dif \rightarrow Cal \leftarrow Int \rightarrow GRE \rightarrow Tra \leftarrow Rec\)


Volviendo al ejemplo anterior

Algebráicamente: La distribución conjunta se factoriza como: \[p(z,a,y,x,b,w)=p(z)p(a|z)p(y|z)p(x|a)p(b|a,y)p(w|b)\] Por lo que la marginal \(p(x,y,w,z)\) se obtiene de la siguiente manera: \[p(x,y,w,z) = \sum_a \sum_b p(z,a,y,x,b,w)\]

\[= \sum_a \sum_b p(z)p(a|z)p(y|z)p(x|a)p(b|a,y)p(w|b)\] \[= p(z)p(y|z) \sum_a p(a|z)p(x|a) \sum_b p(b|a,y)p(w|b)\]

Notamos que \(X\) y \(Y\) interactúan a través de \(A\) y \(B\), por lo que no es posible encontrar dos funciones \(g\), \(h\), tales que \(p(x,y,w,z) \propto g(x,w,z) h(y,w,z)\) y concluímos que \(X \not \perp Y | W\).


Sean \(X\) y \(Y\) vértices distintos y \(W\) un conjunto de vértices que no contiene a \(X\) o \(Y\). Decimos que \(X\) y \(Y\) están d-separados dada \(W\) si no existen caminos activos dada \(W\) entre \(X\) y \(Y\).


Es decir, la \(d\)-separación desaparece cuando hay información condicionada en colisionadores o descendientes de colisionadores.

Este concepto de \(d\)-separación es precisamente el que funciona para encontrar todas las independencias condicionales:

Supongamos que \(p\) se factoriza sobre \(\mathcal G\). Sean \(A\), \(B\) y \(C\) conjuntos disjuntos de vértices de \({\mathcal G}\). Si \(A\) y \(B\) están \(d\)-separados por \(C\) entonces \(A\bot B | C\) bajo \(p\) .


5.2.0.1 Discusión

El resultado anterior no caracteriza la independencia condicional de una distribución \(p\) por una razón simple, que podemos entender como sigue: si agregamos aristas a una gráfica \({\mathcal G}\) sobre la que se factoriza \(p\), entonces \(p\) se factoriza también sobre la nueva gráfica \({\mathcal G}'\). Esto reduce el número de independencias de \(p\) que representa \({\mathcal G}\).

Un ejemplo trivial son dos variables aleatorias independientes \(X\) y \(Y\) bajo \(p\). \(p\) claramente se factoriza en \(X\to Y\), pero de esta gráfica no se puede leer la independencia de \(X\) y \(Y\).

¿Qué es lo malo de esto? En primer lugar, si usamos \({\mathcal G}'\) en lugar de \({\mathcal G}\), no reducimos la complejidad del modelo al usar las independencias condicionales gráficas que desaparecen al agregar aristas. En segundo lugar, la independencia condicional no mostrada en la gráfica es más difícil de descubrir: tendríamos que ver directamente la conjunta particular de nuestro problema, en lugar de leerla directamente de la gráfica.

Finalmente, estos argumentos también sugieren que quisiéramos encontrar mapeos que no sólo sean mínimos (no se pueden eliminar aristas), sino también perfectos en el sentido de que representan exactamente las independencias condicionales. Veremos estos temas más adelante.

Algo que sí podemos establecer es cómo se comporta la familia de distribuciones que se factorizan sobre una gráfica \(\mathcal G\):


Sea \(\mathcal G\) una DAG. Si \(X\) y \(Y\) no están \(d\)-separadas en \(\mathcal G\), entonces existe alguna distribución \(q\) (que se factoriza sobre \({\mathcal G}\)) tal que \(X\) y \(Y\) no son independientes bajo \(q\).


Para que existan independencias que no están asociadas a \(d\)-separación los parámetros deben tomar valores paticulares. Este conjunto de valores es relativamente chico en el espacio de parámetros (son superficies), por lo tanto podemos hacer más fuerte este resultado:


Sea \(\mathcal G\) una DAG. Excepto en un conjunto de “medida cero” en el espacio de distribuciones \(M({\mathcal G})\) que se factorizan sobre \(\mathcal G\), tenemos que \(d\)-separación es equivalente a independencia condicional. Es decir, \(d\)-separación caracteriza precisamente las independencias condicionales de cada \(p\in M(\mathcal G)\), excepto para un conjunto relativamente chico de \(p \in M({\mathcal G})\) .

5.2.1 Equivalencia Markoviana

En esta parte trataremos el problema de la unicidad de la representación gráfica dada un conjunto de independencias condicionales. La respuesta corta es que las representaciones no son únicas, pues algunas flechas pueden reorientarse sin que haya cambios en términos de la conjunta representada.

Decimos que dos gráficas \({\mathcal G}_1\) y \({\mathcal G}_2\) son Markov equivalentes cuando el conjunto de independencias implicadas de ambas es el mismo. Otra manera de decir esto, es que ambas gráficas tienen exactamente la misma estructura de \(d-\)separación.

La equivalencia Markoviana limita nuestra capacidad de inferir la dirección de las flechas únicamente de las probabilidades, esto implica que dos gráficas Markov equivalentes no se pueden distinguir usando solamente una base de datos. Por ejemplo, en la siguiente gráfica, cambiar la dirección del arco que une \(X_1\) y \(X_2\) genera una gráfica Markov equivalente, esto es, la dirección del arco que une a \(X_1\) y \(X_2\) no se puede inferir de información probabilística.

library(igraph)
gr <- graph( c(1,2,1,3,2,4,3,4,4,5)  )
plot(gr, vertex.label=c('X1','X2','X3','X4','X5'), 
  layout = matrix(c(-0.3,0,0,-0.3,0, 0.3,0.3,0,0.6,0), byrow = TRUE, ncol = 2),
  vertex.size = 20, vertex.color = 'salmon', vertex.label.cex = 1.2,
  vertex.label.color = 'gray40', vertex.frame.color = NA, asp = 0.5, 
  edge.arrow.size = 1)

Decimos que un colisionador no está protegido cuando las variables que apuntan a la colisión no tienen vértice entre ellas. Definimos adicionalmente el esqueleto de una GAD como la versión no dirigida de \(\mathcal G\). El siguiente resultado establece que la distribución sólo puede determinar la dirección de las flechas en presencia de un colisionador no protegido:

Dos gráficas \({\mathcal G}_1\) y \({\mathcal G}_2\) son Markov equivalentes si y sólo si

  • Sus esqueletos son iguales y

  • \({\mathcal G}_1\) y \({\mathcal G}_2\) tienen los mismos colisionadores no protegidos.


Las equivalencias que señala este teorema son importantes. Por ejemplo, las gráficas \(X\rightarrow Y \rightarrow Z\) y \(X\leftarrow Y \leftarrow Z\) son equivalentes, lo que implica que representan a las mismas distribuciones condicionales. Solamente usando datos (o el modelo), no podemos distinguir estas dos estructuras, sin embargo, puede ser que tengamos información adicional para preferir una sobre otra (por ejemplo, si es una serie de tiempo).

Una estructura que sí podemos identificar de manera dirigida es el colisionador. El resto de las direcciones pueden establecerse por facilidad de interpretación o razones causales.

Regresando a la gráfica anterior, notamos que al revertir el sentido del arco que une a \(X_1\) con \(X_2\) no se crea ni se destruye ningun colisionador y por tanto la gráfica resultante del cambio de sentido es efectivamente Markov equivalente. Consideremos ahora los arcos dirigidos que unen a \(X_2\) con \(X_4\) y a \(X_4\) con \(X_5\), notamos que no hay manera de revertir la dirección de estos arcos sin crear un nuevo colisionador, esto implica que algunas funciones de probabilidad \(p\) restringen la dirección de éstas flechas en la gráfica.

En el siguiente ejemplo, mostramos la clase de equivalencia de una red de ejemplo. Ahí vemos cuáles son las aristas que se pueden orientar de distinta manera, y cuáles pertenecen a colisionadores en los cuales las direcciones están identificadas:

library(bnlearn)
grafica.1 <- gs(insurance[c('Age', 'RiskAversion', 'Accident', 'DrivQuality',
  'Antilock', 'VehicleYear')], alpha = 0.01)
graphviz.plot(grafica.1)

¿Cuáles de las gráficas anteriores son Markov equivalentes?

  1. 1 y 2
  2. 1 y 3
  3. 2 y 4
  4. 2 y 4
  5. Ninguna

5.2.2 Resumen

  • Dada una gráfica \(G\) podemos encontrar las as independencias condicionales que establece, \(I(G)\).
  • Dada una distribución \(p\) podemos encontrar las independencias que implica, \(I(p)\) (en teoría).
  • Las independencias condicionales definidas por la red bayesiana son un subconjunto de las independencias en \(p\), esto es \(I(G) \subset I(p)\).
  • Equivalencia Markoviana se expresa como: \(I(G) = I(G')\).