Post on 04-Apr-2020
transcript
1
1
Compilación Incremental de redes Bayesianas en la práctica
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
Compilación Incremental de redes Bayesianas en la práctica
Experimentos realizadosExperimentos realizados
ResultadosResultados
Principales conclusionesPrincipales conclusiones
Implementación en Implementación en
2
3
Compilación Incremental de redes Bayesianas en la práctica
Experimentos realizadosExperimentos realizados
ResultadosResultados
Principales conclusionesPrincipales conclusiones
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
Compilación Incremental de redes Bayesianas en la práctica
Experimentos realizadosExperimentos realizados
ResultadosResultados
Principales conclusionesPrincipales conclusiones
Implementación en
12
Compilación Incremental de redes Bayesianas en la práctica
Experimentos realizadosExperimentos realizados
ResultadosResultados
Principales conclusionesPrincipales conclusiones
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
Compilación Incremental de redes Bayesianas en la práctica
Experimentos realizados
ResultadosResultados
Principales conclusionesPrincipales conclusiones
Implementación en
10
19
Compilación Incremental de redes Bayesianas en la práctica
Experimentos realizados
ResultadosResultados
Principales conclusionesPrincipales conclusiones
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
17
33
Compilación Incremental de redes Bayesianas en la práctica
Experimentos realizados
Resultados
Principales conclusionesPrincipales conclusiones
Implementación en
34
Compilación Incremental de redes Bayesianas en la práctica
Experimentos realizados
Resultados
Principales conclusionesPrincipales conclusiones
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
Compilación Incremental de redes Bayesianas en la práctica
Experimentos realizados
Resultados
Principales conclusiones
Implementación en