Redes Bayesias

Facultad de Ciencias de la Computación
Ci

Aprendizaje en las redes bayesianas
Parte II

Abraham Sánchez López
Laboratorio MOVIS

Noción de equivalencia de Markov
Definición: Dos redes bayesianas 1 y 2 se denominan equivalentes en
el sentido de Markov ( 1 ≡ 2) si representan las mismas relaciones de
independencia condicional.
Con el fin de ilustrar simplemente esta noción, mostramosque las
estructuras 1 , 2 y 3 descritas a continuación son equivalentes.

Demostración
Demostramos para 1 y 2:
según 1 : P ( X , X , X )
A

según

Verano 2012

2:

B

C B1

= P( X A | X B ) * P( X B | X C ) * P( X C )

P ( X A , X B , X C )B2 = P ( X A ) * P( X B | X A ) * P( X C | X B )
(c) ASL

2

Continuación de la demostración
Pero de la definición de unaprobabilidad condicional,

P( X A , X B ) = P( X A | X B ) * P( X B ) * P( X A ) * P( X B | X A )
P( X B , X C ) = P( X C | X B ) * P( X B ) * P( X C ) * P( X B | X C )
y por lo tanto

= P( X A | X B ) * P( X B ) * P( X C | X B )
= P( X A | X B ) * P( X B | X C ) * P( X C )
= P( X A , X B , X C )B1
Las redes bayesianas 1 y 2 son por lo tanto equivalentes (de la misma
manera con 3).
Por elcontrario, estas tres estructuras no son equivalentes a la Vestructura 4. Es decir, tenemos:
P ( X A , X B , X C )B4 = P( X A ) * P ( X C ) * P( X B | X A , X C ) y el término
P( X B | X A , X C ) no puede simplificarse.
Verano 2012

(c) ASL

3

Algunos detalles, I
Verma y Pearl demostraron que todos los DAG equivalentes poseen el
mismo esqueleto (grafo no dirigido) y las mismas V-estructuras.
Una clase de equivalencia, es decir, un conjunto de redes bayesianas
que son todas equivalentes, puede por lo tanto representarse por el grafo
sin circuito parcialmente dirigido (PDAG) que tiene la misma estructura
que todas las redes equivalentes, pero para las cuales los arcos
reversibles (no pertenecen a las V-estructuras, o donde la inversión no
genera V-estructuras) son reemplazadospor vértices (no orientados).
El DAG parcialmente dirigido así obtenido se denomina completo
(CPDAG) o grafo esencial.
La figura del acetato 5 ilustra el grafo ASIA y su CPDAG que se
representa en el espacio de las clases de equivalencia de Markov.
Este CPDAG posee por lo tanto el mismo esqueleto que el DAG inicial,
así como sus dos V-estructuras.
Además, el arco O → X es necesariamenteorientado en este sentido
para no crear la V-estructura adicional.

Verano 2012

(c) ASL

4

Algunos detalles, II

Chickering propone un método para pasar de un DAG que representa
una red bayesiana a su CPDAG que representa su clase de equivalencia
de Markov.
Para esto, es necesario empezar por ordenar todos los arcos de la red de
salida (algoritmo Ordenar-Arco), a continuaciónrecorrer el conjunto de
los arcos así ordenados para simplificar los arcos reversibles (algoritmo
DAG to CPDAG).
A continuación, se detalla dicho método en pseudocódigo.
Verano 2012

(c) ASL

5

Algoritmo DAG to CPDAG
• Ordenar los arcos del DAG
• ∀arco, etiqueta(arco) ← ∅
• A ← lista de los arcos no etiquetados
• repetir
(Xi, Xj) ← minA(arco) (el arco más pequeño no etiquetado)
∀Xk/etiqueta(Xk, Xi) = Noreversible
Fin ← Falso
si Xk ∉ pa(Xj) entonces
etiqueta(*, Xj) ← Noreversible
A ← A \ (*, Xj)
Fin ← Verdadero
sino
etiqueta(Xk, Xj) ← Noreversible
A ← A \ (Xk, Xj)
si Fin = Falso entonces
si ∃arco (Xk° , Xj) / Xk° ∉ pa(Xi) ∪ {Xi} entonces
∀(Xk,Xj) ∈ A,
etiqueta(Xk,Xj) ← Noreversible
A ← A\(Xk, Xj)
sino
∀(Xk,Xj) ∈ A,
etiqueta(Xk,Xj) ← reversible
A ← A\(Xk, Xj)Mientras que A ≠ ∅

Verano 2012

(c) ASL

6

Algoritmo Ordenar-Arco
• Clasificar los Xi en el orden topológico
•k←0
• A ← lista de los arcos (no ordenados)
• repetir
Xj° ← minj(Xj /(Xi,Xj) ∈ A)
más pequeño nodo destino de un arco no ordenado
Xj° ← maxj(Xi /(Xi,Xj°) ∈ A)
más grande nodo origen de un arco no ordenado hacia Xj°
Ordenar(Xi° , Xj°) ← k
k ← k +1
A ← A \ (Xi° , Xj°)...