M.Julia Flores , José A. Gámez & Kristian G. Olesenleo.ugr.es/elvira/Meetings/Donosti2004/CIparaElvira.pdf1 1 Compilación Incremental de redes Bayesianas en la práctica Compilación

1

1

Compilación Incremental de redes Bayesianas en la práctica


Artículo metodógico (UAI’03)

M.Julia Flores , José A. Gámez & Kristian G. Olesen

Implementación en Elvira

(artículo en proceso de revisión en ISDA’04)

2


Experimentos realizadosExperimentos realizados

ResultadosResultados

Principales conclusionesPrincipales conclusiones

Implementación en Implementación en

2

3





Implementación en Implementación en

4

Compilación Incremental basada en la descomposición en subgrafos primos maximales

Nuestro método:

Recordatorio:

RB COMPILACIÓN JT

Cam

bios en la red

RB’ RECOMPILACIÓN JT’

rb

DSPM

jtcomp

3

5

Implementación en • Todas las clases están en:elvira.inference.clustering.IncrementalCompilation

• Básicamente dos clases:

IncrementalCompilation.javaDonde se lleva a cabo el método de la compilación incremental

ICModification.java

•ICModificationAddNode.java

•ICModificationRemoveNode.java

•ICModificationAddLink.java

•ICModificationRemoveLink.java

Esta clase trabaja con las modificaciones sobre la red, y las acciones a realizar en la CI difieren dependiendo del tipo de modificación. Por ello, también incluimos:

6

IncrementalCompilation.java

Constructor a partir de una red Bayesiana (Bnet):

G GM GMT JT (treeOfCliquesByGTriangulation) MPST

Principal información que guarda (campos):

• Grafo moral y red Bayesiana

• Árbol de grupos (Join Tree)

• Árbol de SPMs (MPS Tree)

• Lista de modificaciones

• Subgrafos marcados por las modificaciones (lista)

Principales métodos:•runICModification

•runListOfModifications (usa el anterior n veces, 1 por mod)

•makeConnection

4

7

runICModification

makeConnection

8

runICModification

1. Hacemos la modificación correspondiente

2. Dependiendo del tipo de modificación realizamos unas acciones u otra ICModification.java

5

9

ICModification.java

Dos métodos:

•modifyMoralGraph

•markAffectedMPSs

Según el tipo de modificación, estos métodos realizarán acciones distintas y se necesitarán otros métodos específicos.

ICModificationRemoveNode y ICModificationAddNodeson más simples gracias al planteamiento inicial.

Cada modificación guardará el cambio que implica. Por ejemplo, ICModificationAddLink contendrá un campo myLink con el enlace que añade.

10

makeConnection Calculamos los subárboles marcados desconectados mediante markedMPSs

Para cada uno de ellos calculamos el minigrafoasociado y lo compilamos construyendo el JT y MPST

Estos miniárboles son conectados al JT y MPST totales

Y ya podemos borrar los cliques (SPMs) marcados asociados.

6

11





Implementación en

12





Implementación en

7

13

Experimentos realizadosPara una primera evaluación práctica de la Compilación Incremental (con esta implementación) buscábamos un problema…

• … donde participaran las 4 modificaciones básicas: inserción/borrado de nodos/arcos.

• … donde las modificaciones realizadas sean realistas.

• … donde se pueda estudiar la cantidad (ratio) de nodos/arcos que han cambiado, así como su posición relativa en el grafo.

Seleccionar/generar aleatoriamente los nodos/arcos a añadir/borrar podría llevarnos a situaciones muy poco realistas.

14

Nuestra propuesta fue:

Partimos de un parámetro numCases que indicará (en cierta medida) el número de modificaciones a realizar

Para una red B dada

Y lo eliminamos (borrar un nodo implica borrar sus enlaces incidentes previamente).En modListD tendremos la lista de borrar estos enlaces/nodos en el orden que corresponda y modListA contiene la lista de operaciones inversas en el orden contrario.

Para cada caso escogemos aleatoriamente un nodo de la red

8

15

• 5 tipos de experimentos a partir de este esquema:

Exp. : Random: selección completamente aleatoria de los nodos

Exp. : Neighbour: exp. poco realista, las modificaciones estarán normalmente en una misma zona.

Exp. : Variando el parámetro numCases: para medir el impacto que tiene la cantidad de elementos (nodos y enlaces) de la red que han sido modificados.

Exp. : Distinguiendo entre la fase borrado (D) y la fase de inserción (A): para conocer si hay diferencias entre una y otra operación.

Exp. : Con la inicialización de las tablas (además de la construcción del árbol): para comprobar que una compilación más rápida implica que la inicialización de los potenciales también lo es.

16

• Redes empleadas:

Reales: 10 redes reales.

Creadas artificialmente: Estructura en rebanadas. RbNxS (N:vbles por rebanada, S:num de rebanadas)

Las rebanadas i e i+1 completamente separadas por el Subgrafo{X4.i,X6.i,X3.(i+1),X5.(i+1)} la red se divide en 2*S + (S-1) SPMs

9

17

• Los resultados se mostrarán sobre un subconjunto de las redes estudiadas, cuyas características se indican en la siguiente tabla:

18


Experimentos realizados



Implementación en

10

19





Implementación en

20

• Para cada uno de los experimentos anteriores compilación incremental vs compilación tradicional (desde el principio)

Resultados

• Parámetros que mostramos en las tablas:

- El ratio entre el tiempo requerido por la recompilación [tN] y la CI [tI], así como tN- El número de variables [V] y enlaces modificados en GM

- El ratio (recompilación/IC) de variables y enlaces involucrados en la triangulación.- Se muestran medias [µ] (sobre 40 ejecuciones 20 series) y en el último parámetro también desviación [σ]

= n si #V ≤ 100numCases- Parámetro n sino, = n% de #V

• A partir de una red B compilada, hemos realizado los cambios oportunos (B’) y hemos aplicado los dos métodos

11

21

Resultados del exp (Random)

n = 2

22

Exp (Random)

n = 4

12

23

Resultados del exp (Neighbour)

n = 2

24

Exp (Neighbour)

n = 4

13

25

Resultados del exp (variando numCases)Munin1

numCases

tI/tN(log)

26

Exp Pigs

14

27

Exp

Munin4

28

Exp

Rb10x5

15

29

Exp Rb10x10

30

Exp Rb20x50

16

31

Resultados del exp (comparando A y D)

32

Resultados del exp (con tablas)

17

33



Resultados


Implementación en

34



Resultados


Implementación en

18

35

Principales conclusiones• Cuando las modificaciones son aleatorias la ganancia que proporciona la CI depende de la complejidad de la red, la DSPM y la porción cambiada.• Si simulamos un comportamiento más real, esto se cumple, pero además la ganancia aumenta considerablemente.• Cuanto mayor sea la red mayor es la ganancia. Este era precisamente nuestro objetivo las redes grandes son las idóneas para la CI• Un comportamiento normal no se modificarían demasiados elementos de una en el exp podemos observar la enorme ganancia cuando numCases es pequeño.• Además, el exp muestra lo bien que IC funciona (sobre todo ante los casos más realistas).• Añadir enlaces afecta a más SPMs que eliminarlos (más lento).• El hecho de inicializar las tablas aún acentúa más la mejoraobtenida por la CI, sobre todo ante potenciales complejos.

36



Resultados

Principales conclusiones

Implementación en

Documents

M.Julia Flores , José A. Gámez & Kristian G. Olesenleo.ugr.es/elvira/Meetings/Donosti2004/CIparaElvira.pdf1 1 Compilación Incremental de redes Bayesianas en la práctica Compilación