Post on 14-Jul-2022
c© Miguel Angel Carrillo Rincon, 2004
ii
Aprendizaje de la Estructura de Redes Bayesianas
usando Recocido Simulado y Criterio Bayesiano
Por
Ing. Miguel Angel Carrillo Rincon
Tesis
Presentada a la Division de Graduados en Electronica, Computacion, Informacion
y Comunicaciones como requisito parcial para obtener el grado academico de
Maestro en Ciencias en Sistemas Inteligentes
Instituto Tecnologico y de Estudios Superiores de Monterrey
Campus Monterrey
Monterrey, N.L. Mayo de 2004
iv
Reconocimientos
Deseo externar mi mas sincero agradecimiento a todas las personas que de alguna
u otra manera contribuyeron a la realizacion de este trabajo de investigacion. Al Dr.
Francisco Cantu por darme la oportunidad de trabajar con el en este fascinante campo
de investigacion, ası como por haberme dado trabajo para costear en parte mi estancia
en Monterrey. A mi comite de tesis, Dr. Ruben Morales-Menendez y Dr. Luis Eduardo
Garza por el tiempo dedicado a mi trabajo y las sugerencias realizadas para mejorarlo.
Al Dr. Hugo Terashima por sus ensenanzas y por siempre darse el tiempo necesario
para atender a los alumnos.
Quiero agradecer la ayuda, pero sobretodo, la amistad que muchas personas me
brindaron durante mis estudios. A mis amigos, Richie, Lefoz, Nelo, Martın, Cesar,
Chacho, Oscar, Michell, Scott, Daniel, Chema, Luisandro, Omar, Griss, Patty, Doris,
German, Novelo, Charly, Hector, Yoli, Mandujano, Fer, Brian, Carlitos, VicBD, Angel,
Walter, Sammer, Alexander, Hewson, Edgardo, Armando, Puru, Marin, Eduardo, Mar-
co y en especial a Alejandro Meade por las largas y provechosas discusiones que sostu-
vimos sobre mi trabajo de investigacion y por sus aportaciones a este.
Por ultimo deseo reconocer el gran amor y apoyo que siempre he recibido de mis
hermanas Angelica y Chela, de mi hermano Chava, de mis sobrinos Gibran, Joshua e
Itzcali, de mis cunados Hugo, Carlos y Luz, de mi tıa Sofıa y de mi Abuela Marıa. A
todos los amo y mi agradecimiento hoy y siempre.
Miguel Angel Carrillo Rincon
Instituto Tecnologico y de Estudios Superiores de Monterrey
Mayo 2004
vii
viii
Aprendizaje de la Estructura de Redes Bayesianas
usando Recocido Simulado y Criterio Bayesiano
Miguel Angel Carrillo Rincon, M.C.
Instituto Tecnologico y de Estudios Superiores de Monterrey, 2004
Asesor de la tesis: Dr. Francisco J. Cantu Ortız
En la actualidad existen muchos problemas de dominios tan diversos como medici-
na, pronostico del tiempo, mercado del petroleo, telecomunicaciones, etc., los cuales
requieren de modelos que nos permitan razonar bajo incertidumbre y tomar decisiones
aun cuando nuestro conocimiento sobre los eventos que se presentan es limitado. Para
modelar los problemas antes mencionados y razonar bajo incertidumbre, la comunidad
de Inteligencia Artificial basandose en la teorıa de probabilidad y en teorıa Bayesiana ha
desarrollado modelos probabilısticos denominados redes Bayesianas. Una red Bayesiana
es un grafo acıclico dirigido (DAG) en donde los nodos representan variables aleatorias
y los arcos entre variables representan relaciones de causalidad. Sin embargo, el princi-
pal obstaculo para el uso de estas redes es su construccion en dominios complejos. Un
enfoque muy promisorio para resolver este problema es tratar de construir automatica-
mente, o aprender tales representaciones de conjuntos de datos. Para esto, existen dos
vertientes, enfoque de busqueda y evaluacion que busca explorar el espacio de soluciones
posibles para encontrar aquella red que mejor evaluacion presente de acuerdo a cierta
medida de desempeno y analisis de dependencias que busca analizar las caracterısticas
inherentes de una red Bayesiana realizando pruebas de independencia e independencia
condicional. En esta investigacion se presenta un algoritmo al que hemos llamado SABS
y el cual esta basado en el enfoque de busqueda y evaluacion, utilizando el algoritmo
de optimizacion recocido simulado como metodo de busqueda y el criterio Bayesiano
como medida de evaluacion. Este algoritmo aprende la estructura de una red Bayesiana
a partir de un conjunto completo de datos, pero si dicho conjunto carece de algunos
valores, SABS es capaz de realizar la tarea de aprendizaje ya que se realiza un pre-
procesamiento mediante la implementacion de la primera etapa del algoritmo EM para
inferir los valores faltantes.
x
Indice General
Reconocimientos VII
Resumen IX
Indice de Tablas XV
Indice de Figuras XVII
Capıtulo 1. Introduccion 1
1.1. Definicion del Problema . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2. Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3. Hipotesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4. Alcances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5. Aporte de la Investigacion . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.6. Organizacion de la Tesis . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Capıtulo 2. Marco Teorico 9
2.1. Conceptos Basicos de Teorıa de Probabilidad . . . . . . . . . . . . . . . 9
2.1.1. Funciones de Probabilidad . . . . . . . . . . . . . . . . . . . . . 9
2.1.2. Probabilidad Condicional e Independencia . . . . . . . . . . . . 10
2.1.3. Teorema de Bayes . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.4. Variables Aleatorias y Probabilidad Conjunta . . . . . . . . . . 12
2.2. Introduccion a Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.1. Grafos Dirigidos . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.2. Adyacencia en Grafos . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.3. Trayectorias en Grafos . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.4. Ciclos en Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.5. Orden Topologico . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.6. Representacion Computacional de Grafos . . . . . . . . . . . . . 16
2.3. Redes Bayesianas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.1. La Condicion de Markov . . . . . . . . . . . . . . . . . . . . . . 18
2.3.2. La Regla de la Cadena para BNs . . . . . . . . . . . . . . . . . 19
xi
2.3.3. Densidad y Ordenacion de Nodos en BNs . . . . . . . . . . . . . 20
2.3.4. Diferentes Estructuras de BNs . . . . . . . . . . . . . . . . . . . 21
2.3.5. Independencia Condicional en BNs . . . . . . . . . . . . . . . . 21
2.4. Recocido Simulado para Optimizacion . . . . . . . . . . . . . . . . . . 24
2.4.1. El Algoritmo de Metropolis . . . . . . . . . . . . . . . . . . . . 24
2.4.2. El Algoritmo de Recocido Simulado . . . . . . . . . . . . . . . . 25
2.4.3. Implementacion del Algoritmo de Recocido Simulado . . . . . . 26
2.5. Criterio Bayesiano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.5.1. Suposiciones del Criterio Bayesiano . . . . . . . . . . . . . . . . 28
2.6. Aprendizaje de Redes Bayesianas . . . . . . . . . . . . . . . . . . . . . 31
2.6.1. Enfoque de Busqueda y Evaluacion . . . . . . . . . . . . . . . . 31
2.6.2. Enfoque de Analisis de Dependencias . . . . . . . . . . . . . . . 35
2.7. Resumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
Capıtulo 3. Algoritmos de Aprendizaje de Redes Bayesianas 39
3.1. El Algoritmo SABS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.1.1. Evaluacion de BNs usando el Criterio Bayesiano . . . . . . . . . 39
3.1.2. Descripcion del Algoritmo . . . . . . . . . . . . . . . . . . . . . 41
3.1.3. Analisis de Complejidad . . . . . . . . . . . . . . . . . . . . . . 49
3.2. El Algoritmo de Tres Fases . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.2.1. Aprendizaje de BNs usando Informacion Mutua . . . . . . . . . 50
3.2.2. Descripcion del Algoritmo . . . . . . . . . . . . . . . . . . . . . 51
3.2.3. Analisis de Complejidad . . . . . . . . . . . . . . . . . . . . . . 55
3.3. El Algoritmo de Inferencia . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.3.1. Analisis de Complejidad . . . . . . . . . . . . . . . . . . . . . . 58
3.4. Enfoques similares a SABS . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.5. Resumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
Capıtulo 4. Metodologıa y Diseno de Experimentos 63
4.1. Metodologıa General . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.2. Problemas de Prueba . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.2.1. La Red Bayesiana ASIA . . . . . . . . . . . . . . . . . . . . . . 66
4.2.2. La red Bayesiana ALARM . . . . . . . . . . . . . . . . . . . . . 67
4.3. Generacion de Conjuntos de Datos de Prueba . . . . . . . . . . . . . . 70
4.3.1. Algoritmo de Generacion de Conjuntos Incompletos . . . . . . . 70
4.3.2. Analisis de complejidad . . . . . . . . . . . . . . . . . . . . . . . 71
4.4. Experimentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.4.1. Experimentos con Conjuntos de Datos Completos . . . . . . . . 73
4.4.2. Experimentos con Conjuntos de Datos Incompletos . . . . . . . 74
4.5. Evaluacion de Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . 75
xii
4.6. Resumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
Capıtulo 5. Resultados Obtenidos, Analisis y Discusion 77
5.1. Resultados de Experimentacion . . . . . . . . . . . . . . . . . . . . . . 77
5.1.1. Conjuntos de Datos Completos . . . . . . . . . . . . . . . . . . 77
5.1.2. Conjuntos de Datos Incompletos . . . . . . . . . . . . . . . . . . 80
5.2. Analisis y Discusion de Resultados . . . . . . . . . . . . . . . . . . . . 80
5.3. Resumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
Capıtulo 6. Conclusiones y Trabajo Futuro 85
Bibliografıa 87
Capıtulo A. Detalle de resultados obtenidos 93
A.1. Resultados de Experimentacion . . . . . . . . . . . . . . . . . . . . . . 93
A.1.1. Conjuntos de Datos Completos . . . . . . . . . . . . . . . . . . 93
A.1.2. Conjuntos de Datos Incompletos . . . . . . . . . . . . . . . . . . 104
Capıtulo B. Ejemplo de seleccion de la red Bayesiana mas probable 113
Vita 115
xiii
xiv
Indice de Tablas
2.1. Mapeo de caracterısticas de termodinamica a optimizacion combinatoria. 26
3.1. Procedimiento principal del algoritmo SABS. . . . . . . . . . . . . . . . 41
3.2. Procedimiento para el calculo de informacion mutua. . . . . . . . . . . 42
3.3. Implementacion del algoritmo de recocido simulado. . . . . . . . . . . . 44
3.4. Parametros del algoritmo de recocido simulado . . . . . . . . . . . . . . 45
3.5. Procedimiento de generacion de redes Bayesianas candidatas. . . . . . . 47
3.6. Funcion de aceptacion o rechazo de nuevas estructuras de red Bayesiana. 47
3.7. Procedimiento para eliminacion de arcos redundantes. . . . . . . . . . . 48
3.8. Implementacion de la Fase I del algoritmo de tres fases. . . . . . . . . . 52
3.9. Implementacion de la Fase II del algoritmo de tres fases. . . . . . . . . 53
3.10. Implementacion de la Fase III del algoritmo de tres fases. . . . . . . . . 54
3.11. Procedimiento de busqueda de conjuntos de corte entre pares de nodos. 55
3.12. Algoritmo de inferencia para conjuntos incompleto de datos. . . . . . . 57
4.1. Atributos que conforman la estructura de la red Bayesiana ASIA. . . . 67
4.2. Atributos que conforman la estructura de la red Bayesiana ALARM. . . 69
4.3. Algoritmo para la generacion de conjuntos de datos incompletos. . . . . 70
4.4. Ejemplo de un conjunto de datos completo para la red Bayesiana ASIA. 71
4.5. Ejemplo de un conjunto de datos incompleto para la red Bayesiana ASIA. 71
5.1. Sıntesis comparativa de experimentos del algoritmo SABS y el algoritmo
de tres fases para la red ASIA. . . . . . . . . . . . . . . . . . . . . . . . 78
5.2. Sıntesis comparativa de experimentos del algoritmo SABS y el algoritmo
de tres fases para la red ALARM. . . . . . . . . . . . . . . . . . . . . . 78
5.3. Sıntesis comparativa de experimentos del algoritmo SABS y el algoritmo
de tres fases para la red ASIA. . . . . . . . . . . . . . . . . . . . . . . . 80
A.1. Resultados de SABS para la red ASIA con 1k casos completos. . . . . . 94
A.2. Resultados de SABS para la red ASIA con 3k casos completos. . . . . . 94
A.3. Resultados de SABS para la red ASIA con 5k casos completos. . . . . . 95
A.4. Resultados de SABS para la red ASIA con 10k casos completos. . . . . 95
xv
A.5. Resultados del algoritmo de tres fases para la red ASIA con 5k casos
completos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
A.6. Resultados del algoritmo de tres fases para la red ASIA con 10k casos
completos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
A.7. Resultados de SABS para la red ALARM con 1k casos completos. . . . 98
A.8. Resultados de SABS para la red ALARM con 3k casos completos. . . . 99
A.9. Resultados de SABS para la red ALARM con 5k casos completos. . . . 100
A.10.Resultados de SABS para la red ALARM con 10k casos completos. . . 101
A.11.Resultados del algoritmo de tres fases para la red ALARM con 5k casos
completos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
A.12.Resultados del algoritmo de tres fases para la red ALARM con 10k casos
completos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
A.13.Resultados de SABS para la red ASIA con 5k casos y 10 % de casos
incompletos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
A.14.Resultados de SABS para la red ASIA con 5k casos y 20 % de casos
incompletos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
A.15.Resultados de SABS para la red ASIA con 5k casos y 30 % de casos
incompletos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
A.16.Resultados de SABS para la red ASIA con 5k casos y 40 % de casos
incompletos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
A.17.Resultados de SABS para la red ASIA con 5k casos y 50 % de casos
incompletos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
A.18.Resultados del algoritmo de tres fases para la red ASIA con 5k casos y
10 % de casos incompletos. . . . . . . . . . . . . . . . . . . . . . . . . . 109
A.19.Resultados del algoritmo de tres fases para la red ASIA con 5k casos y
20 % de casos incompletos. . . . . . . . . . . . . . . . . . . . . . . . . . 110
A.20.Resultados del algoritmo de tres fases para la red ASIA con 5k casos y
30 % de casos incompletos. . . . . . . . . . . . . . . . . . . . . . . . . . 110
A.21.Resultados del algoritmo de tres fases para la red ASIA con 5k casos y
40 % de casos incompletos. . . . . . . . . . . . . . . . . . . . . . . . . . 111
A.22.Resultados del algoritmo de tres fases para la red ASIA con 5k casos y
50 % de casos incompletos. . . . . . . . . . . . . . . . . . . . . . . . . . 111
B.1. Conjunto de datos de ejemplo. . . . . . . . . . . . . . . . . . . . . . . . 113
xvi
Indice de Figuras
2.1. Grafo dirigido o digrafos. . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2. Representacion de un grafo como lista de adyacencias. . . . . . . . . . . 17
2.3. Red Bayesiana de 4 nodos, 5 arcos y 2 valores por cada variable. . . . . 18
2.4. Redes Bayesianas de acuerdo a su estructura . . . . . . . . . . . . . . . 21
2.5. Representacion de la sabana de Markov . . . . . . . . . . . . . . . . . . 22
2.6. Tipos de nodos de acuerdo a su configuracion . . . . . . . . . . . . . . 23
3.1. Seleccion de un nodo padre usando la distribucion de informacion mutua
acumulada. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.1. Estructura de la red Bayesiana ASIA. . . . . . . . . . . . . . . . . . . . 66
4.2. Estructura de la red Bayesiana ALARM. . . . . . . . . . . . . . . . . . 68
A.1. Mejor red ASIA aprendida por SABS para 1k casos completos. . . . . . 94
A.2. Mejor red ALARM aprendida por SABS para 1k casos completos. . . . 98
A.3. Mejor red ALARM aprendida por SABS para 3k casos completos. . . . 99
A.4. Mejor red ALARM aprendida por SABS para 5k casos completos. . . . 100
A.5. Mejor red ALARM aprendida por SABS para 10k casos completos. . . 101
A.6. Mejor red ALARM aprendida por el algoritmo de tres fases para 5k casos
completos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
A.7. Mejor red ALARM aprendida por el algoritmo de tres fases para 10k
casos completos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
A.8. Promedio de datos reales e inferidos para los valores 1 y 2 en el experi-
mento 11. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
A.9. Promedio de datos reales e inferidos para los valores 1 y 2 en el experi-
mento 12. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
A.10.Promedio de datos reales e inferidos para los valores 1 y 2 en el experi-
mento 13. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
A.11.Promedio de datos reales e inferidos para los valores 1 y 2 en el experi-
mento 14. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
A.12.Promedio de datos reales e inferidos para los valores 1 y 2 en el experi-
mento 15. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
xvii
B.1. Dos estructuras de red Bayesiana alternativas para caracterizar las de-
pendencias probabilısticas entre las variables aleatorias de la tabla B.1. 114
xviii
Capıtulo 1
Introduccion
En la actualidad existen muchos problemas de dominios tan diversos como medi-
cina, pronostico del tiempo, mercados financieros, telecomunicaciones, etc., los cuales
requieren de modelos que nos permitan razonar bajo incertidumbre y tomar decisiones
aun cuando nuestro conocimiento sobre los eventos que se presentan es limitado.
En el pasado, la logica proposicional ha servido como medio para razonar y tomar
decisiones, pero su alcance es limitado ya que esta se basa en inferir hechos de proposi-
ciones que se sabe son verdaderas, y generalmente este no es el caso. De hecho, fre-
cuentemente no se tiene la certeza de una proposicion, pero aun ası necesitamos realizar
inferencia de nuestro incompleto e incierto conocimiento. Esta es la situacion mas comun
para el razonamiento que realiza el ser humano. El razonamiento bajo incertidumbre
todavıa no esta bien entendido de manera que pueda ser formalizado enteramente para
una computadora. Existen varios enfoques para razonar bajo incertidumbre y la teorıa
de probabilidad es uno de ellos. Cuando el razonamiento alcanza una conclusion so-
bre una decision, usamos utilidades y se asume que la decision tomada es aquella que
maximiza la utilidad esperada. Sin embargo, no se puede siempre esperar este compor-
tamiento de los seres humanos, y por tanto el enfoque basado en teorıa de probabilidad
es llamado normativo. Existen otros enfoques para razonar bajo incertidumbre entre
los cuales se puede mencionar a la teorıa de posibilidad, la cual en ciertos contextos
suele ser llamada logica difusa, sin embargo por no formar parte del presente trabajo
de investigacion, no se abundara mas sobre esta.
Para modelar los problemas antes mencionados y razonar bajo incertidumbre, la
comunidad de Inteligencia Artificial basandose en la teorıa de probabilidad y en teorıa
Bayesiana ha desarrollado modelos probabilısticos denominados redes Bayesianas. Exis-
ten diferentes tipos de redes Bayesianas de acuerdo a su configuracion y entre estas se
pueden mencionar a los arboles, poli-arboles y las redes multiconectadas. Son estas
ultimas las de principal interes en esta investigacion ya que las redes Bayesianas de-
sarrolladas por Pearl [29] se han convertido en un estandar para la representacion y
razonamiento bajo incertidumbre.
Durante los anos 1980s, la redes Bayesianas atrajeron una gran cantidad de aten-
cion como medio para la construccion de sistemas normativos, no solo en institutos de
1
investigacion sino tambien en la industria y algunos otros campos, y actualmente el
uso de sistemas o aplicaciones que representan o razonan bajo incertidumbre mediante
el uso de redes Bayesianas ha proliferado (e.g. Hugin de Hugin Expert, BayesiaLab de
Bayesia y otros mas). Sin embargo, aun existen problemas que obstaculizan su uso y
que deben ser atacados de manera formal.
Uno de estos problemas y principal obstaculo para el uso de redes Bayesianas es
su construccion en dominios complejos. La tarea de construir una red Bayesiana que
pueda servir como modelo probabilıstico util para algun problema de dominio puede
llevar mucho tiempo, ademas de ser muy proclive a errores. Claramente, cualquier
mecanismo que pueda ayudar a automatizar esta tarea serıa muy benefico. Un enfoque
muy promisorio para resolver este problema es tratar de construir automaticamente
o aprender tales representaciones de conjuntos de datos. Esto sin embargo, tambien
presenta fuertes problemas debido a la naturaleza de la configuracion de las redes
Bayesianas. En el caso de redes Bayesianas multiconectadas, estas nos permiten modelar
de manera mas precisa la distribucion fundamental (de acuerdo al conjunto de datos),
pero computacionalmente son mucho mas difıciles de tratar. Es bien conocido que en
el peor de los casos calcular las probabilidades a-posteriori de una red multiconectada
es NP-Hard [7].
Existen dos vertientes mediante las cuales se ha buscado profundizar en este en-
foque de construccion automatica de la estructura de redes Bayesianas. El primero de
ellos se denomina busqueda y evaluacion y basicamente busca explorar el espacio de
soluciones posibles para encontrar aquella red que mejor evaluacion presente de acuerdo
a cierta medida de desempeno. La segunda vertiente busca analizar las caracterısticas
inherentes de una red Bayesiana, realizando pruebas de independencia e independen-
cia condicional para tratar de determinar las relaciones causales que den forma a la
estructura. A esta vertiente se le ha llamado analisis de dependencias. Ambas presen-
tan ventajas de acuerdo a los diferentes metodos que se utilizan, sin embargo, las dos
presentan el problema de explosion combinatoria. Hasta el momento ninguna ha de-
mostrado ser mejor que la otra, por el contrario, investigadores en ambas vertientes
han hecho significativas contribuciones a la solucion del problema, pero las tecnicas
desarrolladas son nuevas y aun evolucionan.
Otro problema que obstaculiza el uso de las redes Bayesianas es la existencia de
conjuntos de datos con registros incompletos. Estos registros incompletos son comunes
ya que con frecuencia algunas variables no son observadas en su totalidad. En este
caso, la construccion de la estructura de la red Bayesiana se vuelve un problema mas
complejo.
Esta investigacion esta enfocada al aprendizaje automatico de la estructura de
redes Bayesianas para conjuntos de datos que pueden estar completos o incompletos.
En el caso de conjuntos de datos completos se propone un algoritmo basado en el en-
foque de busqueda y evaluacion, utilizando el algoritmo de recocido simulado [21] como
2
metodo de busqueda y optimizacion, y el criterio Bayesiano propuesto por Cooper y
Herskovitz [8] como medida de evaluacion. En el caso de conjuntos de datos incom-
pletos, se implementa la primera etapa del algoritmo EM (Expectation) con la cual
se completa el conjunto de datos (infiere los datos faltantes). Este conjunto completo
generado es posteriormente usado para aprender la estructura de la red Bayesiana de
manera automatica, utilizando el algoritmo propuesto en este trabajo de investigacion
y el algoritmo de tres fases para conjuntos de datos completos propuesto por Cheng
[3].
1.1 Definicion del Problema
De manera sencilla, una red Bayesiana es un grafo acıclico dirigido (DAG por
sus siglas en ingles, Directed Acyclic Graph) en donde los nodos representan variables
aleatorias y los arcos entre variables representan relaciones de causalidad. Las redes Ba-
yesianas modelan una distribucion probabilıstica fundamental contenida en el conjunto
de datos y nos permiten razonar bajo situaciones de incertidumbre en donde solo se
sabe que ciertos eventos han ocurrido con un determinado valor, y se desea saber como
estos eventos modifican la probabilidad de ocurrencia de los valores que otros eventos
pueden tomar dentro de la red.
La construccion de una red Bayesiana implica dos tareas: especificar las relaciones
de causalidad entre pares de variables y especificar el grado de dependencia de dichas
relaciones. Para realizar la construccion de la red Bayesiana a traves de medios no
automaticos se requiere de la ayuda del experto de dominio. De esta manera, el experto
puede indicar cuales son las relaciones de causalidad que deben existir entre las variables
del proceso que se modela. Sin embargo, aun con la ayuda del experto, esta tarea puede
ser muy tediosa y tomar mucho tiempo ya que el proceso a modelar puede contener un
gran numero de variables.
El aprendizaje automatico de la estructura de la red Bayesiana a partir de un con-
junto de datos ha sido propuesto como una alternativa para dar solucion al problema
de construccion. Sin embargo, los dos enfoques existentes presentan ventajas y desven-
tajas. En el caso del enfoque basado en busqueda y evaluacion, el espacio de busqueda
es inmenso debido a la gran cantidad de soluciones posibles que deben ser evaluadas
para determinar la mejor red. Aun cuando cierto conocimiento de dominio puede ser
utilizado para reducir el espacio de busqueda (e.g. indicar una ordenacion de nodos,
especificar relaciones de causalidad entre pares de variables, etc.) y disminuir la difi-
cultad de la tarea a realizar, la complejidad del problema puede seguir siendo grande.
Otro problema que presenta este enfoque es determinar que medida de evaluacion de
las redes candidatas es apropiada. Por lo general, los metodos basados en este enfoque
suelen tomar mucho tiempo de computo y convergen lentamente hacia una solucion.
3
En el caso del enfoque basado en analisis de dependencias, se busca explorar las
relaciones de independencia e independencia condicional entre las variables del proceso
para ir construyendo la estructura. Estas relaciones por lo general se detectan calcu-
lando la informacion mutua1 entre pares de variables. Sin embargo, cuando se debe
determinar la independencia condicional entre pares de variables, el problema puede
presentar explosion combinatoria debido a que el numero de nodos necesarios para de-
terminar dicha independencia puede ser muy grande. En este caso, cierto conocimiento
de dominio (e.g. numero maximo de variables causales de alguna otra variable, es-
pecificar causalidad entre pares de variables, etc.) como en el enfoque de busqueda y
evaluacion puede ayudar a disminuir la complejidad del problema. Este enfoque suele
converger de manera mas rapida hacia una solucion aunque no necesariamente ello
implica que la solucion que se encuentra sea mejor que en el anterior enfoque.
El problema se complica para ambos enfoques cuando el conjunto de datos a partir
del cual se desea aprender la estructura de la red Bayesiana esta incompleto. Se puede
intentar aprender la red a partir de dichos datos o realizar algun proceso de inferencia
que nos permita determinar como se deben considerar a esos datos.
Las soluciones que encuentren las tecnicas basadas en cada uno de estos enfoques
deben ser coherentes con la distribucion probabilıstica fundamental que intentan mode-
lar. Es decir, las relaciones o lazos entre pares de variables deben reflejar las relaciones
que existen en el conjunto de datos, de otra manera, la solucion propuesta no servira de
mucho ya que no se podran realizar procesos de inferencia que nos permitan realizar
razonamientos bajo incertidumbre con cierto grado de confianza.
1.2 Objetivo
El objetivo principal de esta investigacion es proveer un algoritmo que aprenda de
manera automatica la estructura de una red Bayesiana a partir de un conjunto de datos.
Debido a que algunos registros dentro del conjunto de datos pueden estar incompletos,
tambien se tiene como objetivo implementar un algoritmo que realice la inferencia de
los valores faltantes en cada registro y proporcione un conjunto de datos completos.
Para lograr este objetivo general se plantean los siguientes objetivos especıficos:
Desarrollar un algoritmo basado en el enfoque de busqueda y evaluacion que
aprenda de manera automatica la estructura de una red Bayesiana a partir de
un conjunto completo de datos. A este algoritmo lo hemos llamado Simulated
Annealing and Bayesian Score, SABS .
Desarrollar un algoritmo de pre-procesamiento que reciba un conjunto incompleto
1En teorıa de informacion, la informacion mutua es usada para representar la ganancia de infor-macion esperada al enviar un sımbolo y recibir otro.
4
de datos e infiera los valores faltantes proporcionando un conjunto completo de
datos de salida.
Aplicar el algoritmo de pre-procesamiento a un conjunto incompleto de datos y
con el conjunto completo de datos generado, aprender la estructura de la red
Bayesiana usando el algoritmo SABS .
Implementar el algoritmo de tres fases de Cheng basado en el enfoque de anali-
sis de dependencias con el objetivo de aprender estructuras de redes Bayesianas
y comparar los resultados obtenidos por este, con los resultados obtenidos por
SABS.
Aplicar el algoritmo de pre-procesamiento a un conjunto de datos incompletos
y con el conjunto de datos completos generado, aprender la estructura de la red
Bayesiana usando el algoritmo de tres fases de Cheng.
1.3 Hipotesis
En la presente investigacion se plantean dos hipotesis. La primera considera que un
algoritmo para el aprendizaje automatico de la estructura de una red Bayesiana basado
en el enfoque de busqueda y evaluacion puede ser construido. Esta hipotesis plantea el
uso del algoritmo de recocido simulado como tecnica de busqueda y optimizacion y el
criterio Bayesiano como medida de evaluacion.
En la segunda hipotesis de esta investigacion se argumenta que un enfoque simple
basado en conteo de frecuencias puede ser usado para completar un conjunto incom-
pleto de datos, y posteriormente construir la estructura de la red Bayesiana utilizando
el algoritmo SABS propuesto y el algoritmo de tres fases de Cheng, obteniendo repre-
sentaciones de redes Bayesianas muy cercanas a los modelos reales.
Con este trabajo se busca responder a las siguientes preguntas:
¿Cual es el desempeno del algoritmo SABS cuando el conjunto de datos esta com-
pleto?
¿Cual es el desempeno del algoritmo SABS cuando el conjunto de datos esta in-
completo?
¿Cual es el desempeno del algoritmo de tres fases de Cheng cuando se utiliza un
conjunto de datos que ha sido pre-procesado con el algoritmo de inferencia?
¿Se puede determinar si algun algoritmo es mejor que el otro en cuanto a las
soluciones que encuentran?
5
¿Existe una manera de integrar los dos enfoques, de tal manera que se obtenga
un algoritmo con mejor desempeno?
¿Bajo que circunstancias un algoritmo es mejor que el otro?
Debemos mencionar que el desempeno de cada uno de los algoritmos puede ser
evaluado en base a varios factores. Uno de ellos es considerar la calidad de las repre-
sentaciones que el algoritmo descubre. Es decir, la cantidad de arcos correctos, arcos
erroneos y arcos faltantes contenidos en la estructura de red Bayesiana descubierta con
respecto a la estructura real de dicha red.
Sin embargo, al utilizar este criterio de desempeno, se debe conocer de manera
anticipada la estructura real de la red Bayesiana, de manera que podamos realizar
comparaciones con los resultados obtenidos por los algoritmos. Es por esto, que para
la presente investigacion se utilizan dos redes Bayesianas que en la literatura de apren-
dizaje de estructuras de redes Bayesianas han sido tomadas como estandar. Estas son
la red ASIA [25] y ALARM [2]. La primera red pertenece a un dominio medico simple
ficticio y la segunda pertenece a un dominio del mundo real de complejidad moderada.
Los conjuntos de datos utilizados fueron generados por Cheng et. al. [3] mediante una
tecnica Monte Carlo llamada modelo logico probabilıstico [19]. Estos conjuntos de datos
constan de 10, 000 registros cada uno, y son distribuidos con el programa computacional
Power Constructor.
1.4 Alcances
El problema de aprendizaje automatico de la estructura de una red Bayesiana a
partir de un conjunto de datos ha sido limitado al problema de aprender la estructura
de la red cuando se provee una ordenacion de nodos y un maximo de padres por nodo.
La ordenacion de nodos reduce la complejidad del problema restringiendo el numero de
estructuras posibles y por tanto acortando el espacio de busqueda. El numero maximo
de padres reduce la complejidad del problema, sin embargo, ha sido demostrado que el
problema de encontrar la mejor estructura de red del conjunto de redes posibles cuando
el numero de padres es mayor de 1 (k > 1) es NP-Hard [4].
1.5 Aporte de la Investigacion
La aportacion principal de este trabajo de investigacion al campo de estudio de
las redes Bayesianas, y en especıfico al topico de aprendizaje de la estructura es:
Se presenta un algoritmo para el aprendizaje de la estructura de redes Bayesianas
con base en el enfoque de busqueda y evaluacion. El espacio de posibles soluciones
6
se explora utilizando el algoritmo de recocido simulado y las redes Bayesianas
candidatas se evaluan bajo el criterio Bayesiano. Mediante una distribucion de
informacion mutua (calculada para cada variable con respecto a las demas y
cumpliendo con la ordenacion de nodos) y el proceso conocido como sampling-
importance resampling, la busqueda es guiada para favorecer nuevas estructuras
que tienen mayor dependencia con la estructura actual.
1.6 Organizacion de la Tesis
La presente investigacion se encuentra organizada de la siguiente manera. En el
capıtulo 2 se presentan los antecedentes sobre redes Bayesianas, los fundamentos ne-
cesarios para el entendimiento del problema en contexto y trabajo relacionado sobre
aprendizaje de la estructura de redes Bayesianas. El capıtulo 3 presenta los algorit-
mos implementados en esta investigacion. El primero de ellos es una propuesta de este
trabajo y busca aprender la estructura de redes Bayesianas a partir de conjuntos de
datos completos. El segundo algoritmo es una implementacion de la primera etapa del
algoritmo EM y realiza procesos de inferencia para completar un conjunto de datos que
esta incompleto. Por ultimo, el algoritmo de tres fases de Cheng es tambien presen-
tado en este capıtulo. En el capıtulo 4 se detalla la metodologıa que se siguio en esta
investigacion y los experimentos que se plantearon para demostrar el funcionamien-
to del algoritmo propuesto. En el capıtulo 5 se presentan los resultados obtenidos en
forma breve, ası como el analisis y discusion de estos. El capıtulo 6 se presentan las
conclusiones y los trabajo futuros que de esta investigacion se desprenden. Por ultimo,
el apendice A presenta en detalle el resultado de los experimentos planteados dentro
de esta investigacion, y en el apendice B se muestra un ejemplo de como determinar la
red Bayesiana mas probable de acuerdo a un conjunto de datos.
7
8
Capıtulo 2
Marco Teorico
En este capıtulo se presentan los conceptos teoricos relacionados con la presente
investigacion. Primeramente se da una introduccion de los conceptos basicos de teorıa
de probabilidad y teorıa de grafos. A continuacion se introducen las redes Bayesianas, su
definicion, caracterısticas y los problemas que presenta su construccion. Posteriormente,
se describen los dos conceptos fundamentales mediante los cuales se provee una solucion
alternativa al problema de aprender la estructura de redes Bayesianas, el algoritmo de
recocido simulado y la medida de evaluacion criterio Bayesiano. Por ultimo se presentan
los dos enfoques existentes en la literatura sobre el aprendizaje de redes Bayesianas y
para cada uno de ellos se detallan los principales trabajos realizados.
2.1 Conceptos Basicos de Teorıa de Probabilidad
En 1933, Andrei Kolmogorov [22] desarrollo un conjunto de definiciones teoricas
de probabilidad que sirven de fundamentos matematicos para todas las aplicaciones
de probabilidad. Kolmogorov demostro que el resto de la teorıa de probabilidad puede
construirse bajo estos fundamentos. En la seccion 2.1.1 se definen primeramente las
funciones de probabilidad y posteriormente los denominados axiomas de probabilidad.
2.1.1 Funciones de Probabilidad
La teorıa de probabilidad se relaciona con experimentos que tienen un conjunto
de resultados diferentes. El conjunto de todos estos resultados es denominado espacio
muestral. Este espacio muestral puede ser finito o infinito. En el caso de un espacio
muestral finito (se concentrara nuestra atencion en este tipo unicamente), cada sub-
conjunto del espacio es llamado evento. Un subconjunto conteniendo exactamente un
solo elemento es llamado evento elemental. Una vez que el espacio muestral ha sido
identificado, la funcion de probabilidad se define de la siguiente manera:
Definicion 2.1 Funcion de probabilidad
Suponga que se tiene un espacio muestral Ω conteniendo n distintos elementos. Esto
9
es,
Ω = x1, x2, . . . , xn
Una funcion que asigna un numero real P(X) a cada evento X ⊆ Ω es llamada
funcion de probabilidad del conjunto de subconjuntos de Ω, si satisface las siguientes
condiciones:
1. 0 ≤ P (xi) ≤ 1 para 1 ≤ i ≤ n.
2. P (x1) + P (x2) + . . . + P (xn) = 1.
3. Para cada evento X = xi1, xi1, . . . , xik que no es un evento elemental,
P (X) = P (xi1) + P (xi2) + . . . + P (xik).
El par (Ω, P ) es llamado espacio de probabilidad.
De manera frecuente solo se dice que P es una funcion de probabilidad de Ω en
vez de decir que es una funcion de probabilidad del conjunto de subconjuntos de Ω.
Definicion 2.2 Axiomas de probabilidad
Dejese que (Ω, P ) sea un espacio de probabilidad. Entonces
1. P (Ω) = 1.
2. 0 ≤ P (X) ≤ 1 para cada X ⊆ Ω
3. Para X y Y ⊆ Ω tal que X ∩ Y = Ø,
P (X ∪ Y ) = P (X) + P (Y ).
Notar que estos axiomas solo definen probabilidades a priori y no probabilidades
condicionales. Estas ultimas se definen a continuacion en la seccion 2.1.2.
2.1.2 Probabilidad Condicional e Independencia
Uno de los conceptos mas importantes en teorıa de probabilidad son las probabi-
lidades condicionales. Estas se definen de la siguiente manera:
Definicion 2.3 Probabilidades condicionales
Dejese que X y Y sean eventos tales que P (Y ) 6= 0. Entonces la probabilidad condicional
de X dado Y, denotada por P (X|Y ), esta dada por
P (X|Y ) =P (X ∩ Y )
P (Y ). (2.1)
10
La intuicion inicial para la probabilidad condicional viene de considerar las proba-
bilidades que son proporciones. En el caso de proporciones, P (X|Y ), como se expresa
en la definicion 2.3, es la fraccion de elementos en Y que tambien estan en X. Por ejem-
plo, si n es el numero de elementos en el espacio muestral, nY el numero de elementos
en Y , y nXY el numero de elementos en X ∩ Y . Entonces,
P (X|Y ) = P (X∩Y )P (Y )
= nXY /nnY /n
= nXY
nY,
que es la fraccion de elementos en Y que tambien estan en X. En cuanto al significado,
P (X|Y ) es la probabilidad de que ocurra X dado que se sabe que Y ha ocurrido. La
ecuacion 2.1 es tambien conocida como la regla del producto. En la seccion 2.1.3 se
abundara sobre esta regla para la definicion del teorema de Bayes.
Cuando el conocimiento de la ocurrencia de un evento no dice nada con respecto
a la ocurrencia de otro, se dice que dichos eventos son independientes. La definicion de
independencia se formaliza a continuacion:
Definicion 2.4 Independencia
Dos eventos X y Y son independientes si alguna de las dos condiciones siguientes se
presenta:
1. P (X|Y ) = P (X) y P (X) 6= 0, P (Y ) 6= 0.
2. P(X) = 0 o P(Y) = 0.
Notar que la definicion establece que los dos eventos son independientes aun cuan-
do esta se encuentra basada en la probabilidad condicional de X dado Y . La razon
es que la independencia es simetrica. Esto es, si P (X) 6= 0 y P (Y ) 6= 0, entonces
P (X|Y ) = P (X) si y solo si P (Y |X) = P (Y ). Resulta trivial probar que X y Y son
independientes si y solo si P(X∩Y) = P(X)P(Y)
P (X|Y ) = P (X∩Y )P (Y )
= P (X)P (Y )P (Y )
= P (X).
2.1.3 Teorema de Bayes
Por decadas las probabilidades condicionales de eventos de interes han sido calcu-
ladas de probabilidades conocidas usando el teorema de Bayes. Para definir de manera
precisa este teorema, primeramente se expresara en forma diferente la ecuacion 2.1
conocida como la regla del producto. Esto es,
P (X ∩ Y ) = P (X|Y )P (Y ). (2.2)
De manera similar se tiene que
11
P (Y ∩ X) = P (Y |X)P (X). (2.3)
Debido a que se sabe que P (X ∩ Y ) = P (Y ∩ X), se iguala la parte derecha de ambas
ecuaciones para obtener
P (X|Y )P (Y ) = P (Y |X)P (X). (2.4)
Por lo tanto, la definicion formal del teorema de Bayes se muestra a continuacion:
Teorema 2.5 (Bayes)
Dados dos eventos X y Y tal que P (X) 6= 0 y P (Y ) 6= 0, se tiene que
P (X|Y ) =P (Y |X)P (X)
P (Y ). (2.5)
Ademas, dados n eventos exhaustivos y mutuamente excluyentes X1, X2, . . . , Xn
tal que P (Xi) 6= 0 para toda i, se tiene que para 1 ≤ i ≤ n,
P (Xi|Y ) =P (Y |Xi)P (Xi)
P (Y |X1)P (X1) + P (Y |X2)P (X2) + . . . + P (Y |Xn)P (Xn). (2.6)
2.1.4 Variables Aleatorias y Probabilidad Conjunta
Definicion 2.6 Variables Aleatorias
Dado un espacio de probabilidad (Ω, P ), una variable aleatoria X es una funcion de Ω.
Una variable aleatoria X se define como un sımbolo que representa cualquier valor
de un conjunto de valores posibles llamado espacio de X. Una variable aleatoria se dice
que es discreta si su espacio es finito o contable. La notacion X=x es generalmente
usada en expresiones probabilısticas y denota el conjunto de todos los elementos e ∈ Ω
que X puede tomar.
Definicion 2.7 Distribucion de probabilidad conjunta
Dejese que un conjunto de n variables aleatorias V = X1, X2, . . . , Xn sean especifi-
cadas tal que cada Xi tiene un espacio infinito contable. Una funcion que asigna un
numero real P (X1 = x1, X2 = x2, . . . , Xn = xn) a cada combinacion de valores de las
xi’s, tal que el valor de xi es escogido del espacio de Xi es llamada una distribucion
de probabilidad conjunta de la variable aleatoria en V, si esta satisface las siguientes
condiciones:
1. Para cada combinacion de los valores de las xi’s,
0 ≤ P (X1 = x1, X2 = x2, . . . , Xn = xn) ≤ 1.
12
2. Se tiene∑
x1,x2,...,xn
P (X1 = x1, X2 = x2, . . . , Xn = xn) = 1.
La notacion∑
x1,x2,...,xnsignifica la sumatoria conforme las variables x1, x2, . . . , xn
toman todos los posibles valores en sus espacios correspondientes.
2.2 Introduccion a Grafos
De manera informal, un grafo es un conjunto de vertices o nodos los cuales estan
conectados por lıneas o flechas llamados arcos. Si dichas conexiones son no direccionadas
o estan en ambos sentidos, se dice que el grafo es no dirigido. En caso de que tales
conexiones sean dirigidas o en un solo sentido, se dice que el grafo es dirigido.
Figura 2.1: Grafo dirigido o digrafos.
Los grafos son abstracciones muy utiles para numerosos problemas en areas como
investigacion de operaciones, ciencias computacionales, ingenierıa electrica, economıa,
matematicas, fısica, quımica, comunicaciones, teorıa de juegos, probabilidad, etc.
A continuacion se define un tipo particular de grafos llamados grafos dirigidos o
digrafos. El interes de esta definicion radica en el hecho de que los digrafos son la forma
de representacion de las redes Bayesianas. De igual manera, se definiran los conceptos
de adyacencia, trayectoria, ciclos y orden topologico relacionados con redes Bayesianas
y por tanto con grafos.
2.2.1 Grafos Dirigidos
Los grafos dirigidos (digrafos) son estructuras en donde los enlaces entre nodos se
representan mediante arcos con una direccion fija. La definicion formal se presenta a
continuacion.
13
Definicion 2.8 Digrafo
Un grafo dirigido o digrafo, es un par G = (V, E) donde V es un conjunto cuyos
elementos son llamados vertices, y E es un conjunto de pares ordenados de elementos
de V. Los vertices son llamados nodos y los elementos de E son llamados arcos. Para
el arco dirigido (v→w) en E, v es el padre y w el hijo; (v, w) se representa en el
diagrama con una flecha de v a w.
La figura 2.1 muestra un digrafo y los conjuntos V y E estan dados por:
V = 1, 2, 3, 4, 5, 6, 7,
E = (1,2), (2,3), (5,2), (3,5), (4,5), (5,7), (6,4), (6,7).
2.2.2 Adyacencia en Grafos
El concepto de adyacencia es importante para el estudio de redes Bayesianas ya
que su representacion utiliza este concepto. De manera formal, la adyacencia en un
grafo se define a continuacion.
Definicion 2.9 Adyacencia
Los arcos de un digrafo G = (V, E) inducen una relacion llamada adyacencia, A,
en el conjunto de vertices. Si v y w son elementos de V, entonces A(v, w) (se lee, w
es adyacente a v) si y solo si (v→w) esta en E. En otras palabras, A(v, w) significa
que w puede ser alcanzado desde v moviendonos a traves de un arco en G.
En la figura 2.1, A(1, 2) (2 es adyacente a 1) es una relacion de adyacencia ya que
el nodo 2 puede ser alcanzado desde el nodo 1.
2.2.3 Trayectorias en Grafos
Las trayectorias en grafos definen caminos que conectan a dos nodos. El concepto
de trayectoria es muy util en diversas aplicaciones, incluyendo algunas que se relacionan
con transporte de personas, mensajes electronicos, llamadas telefonicas, trafico, lıquidos
o gases en tuberıas, por mencionar solo algunos.
En este caso, es de interes definir este concepto ya que dentro del estudio de redes
Bayesianas es deseable conocer en un determinado momento si existe una trayecto-
ria que conecte a dos nodos en particular, u obtener todas aquellas trayectorias que
conectan a dichos nodos. En el capıtulo 3, se definiran dos tipos de trayectorias de
particular interes en redes Bayesianas y especıficamente para el aprendizaje de la es-
tructura, trayectorias abiertas y cerradas.
14
Definicion 2.10 Trayectoria
Una trayectoria de v a w en un digrafo G = (V, E) es una secuencia de arcos
v0v1, v1v2, ..., vk−1vk, tal que v=v0 y w=vk. La longitud de la trayectoria es k. Un vertice
v por sı solo es considerado una trayectoria de longitud cero de v a sı mismo. Una
trayectoria sencilla es una trayectoria tal que v0, v1, ..., vk son todos distintos. Los
nodos v1, v2..., vk−1 son llamados nodos interiores.
En la figura 2.1, una trayectoria de v a w, donde v=6 y w=5 es: (6→4), (4→5),
(5→2), (2→3), (3→5). Una trayectoria sencilla para los mismos vertices es: (6→4),
(4→5). Las longitudes de las trayectorias son k=5 y k=2, respectivamente.
Definicion 2.11 Relaciones de parentesco
Dado un digrafo acıclico G = (V, E) y los nodos X y Y en V, X es llamado padre, Πi,
de Y si existe un arco de X a Y, y Y es llamado hijo de X. Y es llamado descendiente
(di) de X y X es llamado ancestro de Y si existe una trayectoria de X a Y, y Y es
llamado no-descendiente, ndi, de X si Y no es un descendiente de X.
2.2.4 Ciclos en Grafos
Definicion 2.12 Ciclo en un digrafo
Para un digrafo, un ciclo es una trayectoria no vacıa tal que el primero y ultimo vertice
son el mismo. Un ciclo sencillo es un ciclo en donde ningun vertice se repite excepto
por el primero y el ultimo.
En el grafo de la figura 2.1, los vertices 2, 3, 5 forman un ciclo ya que cada uno
de estos nodos puede ser alcanzado siguiendo trayectorias sobre estos mismos nodos.
2.2.5 Orden Topologico
Definicion 2.13 Orden topologico
Si G = (V, E) es un digrafo de n vertices, el orden topologico de G se define como
la asignacion de distintos enteros 1, . . ., n a los vertices de V, llamados numeros
topologicos, tal que para cada arco (v→w) ∈ E, el numero topologico de v es menor
que el numero topologico de w. El orden topologico inverso es similar, excepto que para
cada arco (v→w) ∈ E el numero topologico de v es mayor que el de w.
El grafo de la figura 2.1 no tiene orden topologico ya que esta propiedad es exclusiva
de los grafos que no contienen ciclos.
15
2.2.6 Representacion Computacional de Grafos
Hasta el momento se han definido los grafos y la manera en que estos se representan
mediante puntos para los vertices y lıneas con flecha para los arcos. En esta seccion se
discutiran dos maneras utiles de representar los grafos en un sistema computacional.
Representacion matricial
Hagase G = (V, E) para un grafo con n = |V |, m = |E| y V = X1, X2, ..., Xn. G
puede ser representado por una matriz A = (aij) de n×n, llamada matriz de adyacencias
de G. A se define de la siguiente manera:
aij =
1 Si (Xi → Xj) ∈ E
0 otro caso
para 1 ≤ i, j ≤ n. La representacion matricial del grafo de la figura 2.1 se muestra a
continuacion.
A =
0 1 0 0 0 0 0
0 0 1 0 0 0 0
0 0 0 0 1 0 0
0 0 0 0 1 0 0
0 1 0 0 0 0 1
0 0 0 1 0 0 1
0 0 0 0 0 0 0
Representacion en listas de adyacencias
Una alternativa a la representacion matricial de adyacencias es un arreglo indexado
por numero de vertice conteniendo listas enlazadas, llamada lista de adyacencias. Para
cada vertice vi, la i-esima posicion en el arreglo contiene una lista con informacion
sobre todos los arcos de G que salen de vi.
La ventaja de la lista de adyacencias es que los arcos que no existen en G, no
existen en la representacion tampoco. Si G no tiene muchos arcos (mucho menos de
n2), la lista puede ser procesada rapidamente. Notese que si los elementos dentro de la
lista aparecen en diferente orden, la estructura todavıa representa el mismo grafo. La
figura 2.2 muestra la representacion de lista de adyacencias para el grafo de la figura
2.1.
16
Figura 2.2: Representacion de un grafo como lista de adyacencias.
2.3 Redes Bayesianas
Las redes Bayesianas, redes de creencias o redes causales como tambien se les lla-
ma, proveen un poderoso formalismo para razonar bajo incertidumbre [31]. Debido a su
naturaleza, las redes Bayesianas proveen una representacion completa y no redundante,
lo que les permite manejar dominios con muchas variables. Aun cuando en su concepto
original estas redes fueron disenadas principalmente para codificar el conocimiento de
expertos humanos, sus raıces estadısticas rapido sugirieron el uso de metodos de apren-
dizaje para extraer su estructura y probabilidades condicionales directamente de bases
de datos.
De manera formal, una red Bayesiana (BN por sus siglas en ingles, Bayesian Net-
work) es un grafo acıclico dirigido (DAG) en el cual los nodos representan variables
aleatorias y los arcos representan dependencias condicionales entre dichas variables.
Una BN para un conjunto de variables X = X1, . . . , Xn consiste de una estructura
de red MS que codifica un conjunto de relaciones de independencia condicional de las
variables en X , y un conjunto MP de distribuciones de probabilidad locales asociadas
con cada variable. En conjunto, estos componentes definen la distribucion de proba-
bilidad conjunta de X . Los nodos en MS estan en correspondencia uno a uno con
las variables en X . Se usa Xi para denotar a la variable y al nodo correspondiente, y
Πi para denotar los padres (nodos con arcos que inciden en Xi) del nodo Xi en MS,
ası como las variables correspondientes a esos padres [17].
En las secciones siguientes se hablara sobre las caracterısticas de las redes Bayesia-
nas, los tipos de redes de acuerdo a su estructura y algunos otros conceptos importantes
17
Figura 2.3: Red Bayesiana de 4 nodos, 5 arcos y 2 valores por cada variable.
dentro de su estudio como la condicion de Markov, la regla de la cadena, independencia
y d-separacion.
2.3.1 La Condicion de Markov
En redes Bayesianas, la condicion de Markov establece basicamente que un nodo
es independiente (ver definicion 2.4) de aquellos nodos que no son sus descendientes
dados sus padres. La definicion formal se presenta a continuacion:
Definicion 2.14 Condicion de Markov
Suponiendo que se tiene una distribucion de probabilidad conjunta MP de las variables
aleatorias en un conjunto V y un DAG G = (V, E). Se dice que (G, MP ) satisface la
condicion de Markov si para cada variable Xi ∈ V, Xi es condicionalmente indepen-
diente del conjunto de todos sus no descendientes, ndi, dado el conjunto de todos sus
padres, Πi. De acuerdo a lo anterior y a la notacion de la definicion 2.11 se tiene lo
siguiente:
IP (Xi, ndi|Πi).
Cuando (G, MP ) satisface la condicion de Markov, se dice que G y MP satisfacen la
condicion de Markov entre si. Si Xi es un nodo raız (nodo cuyo conjunto de padres
Πi es ∅), la condicion de Markov significa que Xi es independiente de ndi. Esto es,
IP (Xi, ndi) [28].
18
2.3.2 La Regla de la Cadena para BNs
Una red Bayesiana provee una descripcion completa del dominio. Cada elemento de
la distribucion de probabilidad conjunta (en adelante se abreviara como distribucion
conjunta, ver definicion 2.6) puede ser calculado de informacion de la red [37]. Una
entrada generica en la distribucion conjunta es la probabilidad de una conjuncion de
asignaciones particulares a cada variable tal que P (X1 = x1∧. . .∧Xn = xn). Se usara la
notacion P (x1, . . . , xn) como abreviacion. El valor de esta asignacion esta dado por:
P (x1, . . . , xn) =n
∏
i=1
P (xi|πi), (2.7)
donde πi denota los valores especıficos de las variables en Πi (padres del nodo Xi). De
este modo, cada elemento en la distribucion conjunta esta representado por el produc-
to de los elementos apropiados de las tablas de probabilidad condicional (CPTs) en
la red Bayesiana. Las CPTs por lo tanto proveen una representacion separada de la
distribucion conjunta [37].
La ecuacion 2.7 define lo que significa una red Bayesiana, pero no explica como
construirla de tal manera que la distribucion conjunta resultante sea una representacion
buena del dominio dado. Sin embargo, esta ecuacion implica ciertas relaciones de inde-
pendencia condicional que pueden ser usadas para guiar la construccion de la estructura
de la red. Ahora, se escribira la ecuacion 2.7 en terminos de probabilidades condicionales
usando la regla del producto (ver definicion 2.3, ecuacion 2.1):
P (x1, . . . , xn) = P (xn|xn−1, . . . , x1)P (xn−1, . . . , x1). (2.8)
Entonces se repite el proceso reduciendo cada probabilidad conjuntiva a una probabili-
dad condicional y a una probabilidad conjuntiva mas pequena. El resultado es un gran
producto como se muestra:
P (x1, . . . , xn) = P (xn|xn−1, . . . , x1)P (xn−1|xn−2, . . . , x1) · · · (2.9)
P (x2|x1)P (x1)
P (x1, . . . , xn) =n
∏
i=1
P (xi|xi−1, . . . , x1) (2.10)
Esta identidad es verdadera para cualquier conjunto de variables aleatorias y es llamada
regla de la cadena [37]. Comparada con la ecuacion 2.7, se ve que la especificacion de
la distribucion conjunta es equivalente a la aseveracion de que para cada variable Xi
en la red
P (Xi|Xi−1, . . . , X1) = P (Xi|Πi), (2.11)
19
asumiendo que Πi ⊆ Xi−1, . . . , X1. Esta ultima condicion es satisfecha al identificar
los nodos en cualquier orden que sea consistente con el orden parcial implıcito en la
estructura de la grafica.
Lo que la ecuacion 2.11 dice es que la red Bayesiana es una representacion correcta
del dominio solo si cada nodo es condicionalmente independiente de sus predecesores
en la ordenacion de nodos (ver seccion 2.3.3, mas adelante), dados sus padres. Por lo
tanto, para construir una red Bayesiana con la estructura correcta para el dominio, se
debe escoger padres para cada nodo de tal manera que esta propiedad se mantenga
[37]. Intuitivamente, el conjunto de padres del nodo Xi debe contener todos los nodos
en X1, . . . , Xi−1 que tienen influencia directa sobre Xi.
2.3.3 Densidad y Ordenacion de Nodos en BNs
Ademas de ser una representacion completa y no redundante del dominio, una
red Bayesiana casi siempre es mucho mas compacta que la distribucion conjunta. Esta
propiedad es la que le permite manejar dominios con muchas variables. La densidad
de las redes Bayesianas es un ejemplo de una propiedad muy general de los sistemas
llamada estructura local. En los sistemas con estructura local, cada subcomponente
interactua directamente con solo un numero limitado de otros componentes, sin im-
portar el numero total de estos. La propiedad de estructura local esta asociada con un
crecimiento lineal en complejidad en vez de exponencial. En el caso de las redes Baye-
sianas, es razonable suponer que en la mayorıa de los dominios cada variable aleatoria
esta directamente influenciada por k variables a lo mucho. Si asumimos n variables
aleatorias booleanas, entonces la cantidad de informacion necesaria para especificar ca-
da tabla de probabilidad condicional sera a lo mucho de 2k numeros, y la red completa
podra ser especificada por n2k numeros. En contraste, la distribucion conjunta contiene
2n numeros. En el caso de los dominios en donde cada variable puede estar influenciada
por todas las demas, especificar las tablas de probabilidad condicional requerira la mis-
ma cantidad de informacion que la necesaria para especificar la distribucion conjunta.
Este tipo de redes se conocen como completamente conectadas [37].
Aun en dominios localmente estructurados, construir una red Bayesiana con tal
estructura resulta difıcil. Se requiere no solo de que cada variable este directamente
influenciada por otras, sino que tambien la topologıa de la red refleje dichas influencias
con el conjunto apropiado de padres. Debido a la forma en que los procedimientos de
construccion operan, una variable que influencia a otra debe ser agregada primero si
es que esta se convertira en padre de la variable que directamente influencia. Por lo
tanto, el orden correcto en el cual los nodos deben ser agregados debe incluir primero
a los nodos raıces, y despues a las variables que estos influencian, y ası sucesivamente
hasta llegar a los nodos hoja, que son nodos que no tienen influencia causal sobre otras
variables. A esto se le llama ordenacion de nodos [37].
20
Para la red Bayesiana de la figura 2.3, una ordenacion de nodos correcta estarıa
dada por: V = H,B,L, F, C. Este no es el unico orden correcto posible. Otro serıa:
V = H,L,B, F, C.
2.3.4 Diferentes Estructuras de BNs
Una red Bayesiana puede tener tres tipos de estructuras dependiendo del dominio
que se desea modelar. La estructura mas simple son los arboles, donde los nodos tienen
un solo padre, excepto por los nodos raız. Otro tipo de estructura es conocida como
poli-arbol y se caracteriza porque existe solo una trayectoria no direccionada entre
cualquier par de nodos de la red. Los poli-arboles pueden ser vistos como varios arboles
conectados. La estructura mas compleja es la red multiconectada que puede modelar a
la mayorıa de los dominios. Esta estructura puede tener mas de una trayectoria entre
pares de variables de la red. La figura 2.4 muestra estos diferentes tipos de estructuras.
Figura 2.4: Diferentes estructuras de redes Bayesianas: (a) Arbol, (b) Poli-arbol, (c) Redmulticonectada.
2.3.5 Independencia Condicional en BNs
Se ha mencionado que una red Bayesiana expresa la independencia condicional
de un nodo y sus predecesores dados sus padres, y esta independencia es usada para
disenar metodos de construccion de las redes. De manera general, dos condiciones nos
permiten determinar la independencia condicional de un nodo [37]. Estas se presentan
a continuacion:
1. Un nodo es condicionalmente independiente de sus no descendientes dados sus
padres (Ver figura 2.5a).
21
2. Un nodo es condicionalmente independiente de todos los demas nodos en la red
dados sus padres, sus hijos y los padres de sus hijos. Esto se conoce como sabana
de Markov (Ver figura 2.5b).
Figura 2.5: Representacion de la sabana de Markov : (a) X es condicionalmente independi-ente de Z dado U . (b) X es condicionalmente independiente de cualquier otronodo dados U , Y y Z. Los nodos en U , Y y Z forman la sabana de Markov deX.
Sin embargo, es necesario saber si existen condiciones de independencia mas ge-
nerales. Por ejemplo, dada una red Bayesiana, es posible saber si un conjunto de nodos
X es independiente de otro conjunto Y , dado un conjunto de nodos E como evidencia?
La respuesta a esta pregunta la provee un concepto denominado d-separacion.
d-separacion
Un conjunto de nodos E d-separa a dos conjuntos de nodos X y Y si cada trayec-
toria (ver definicion 2.10) no dirigida (ignorando el sentido de las flechas) de un nodo
en X a un nodo en Y esta bloqueada dado E [36]. Una trayectoria esta bloqueada dado
un conjunto de nodos E si existe un nodo Z en la trayectoria para el cual una de las
tres condiciones siguientes se presenta:
1. El nodo Z esta contenido por el conjunto de nodos evidencia (Z ⊆ E) y tiene una
flecha en la trayectoria entrando al nodo y otra saliendo de este, X → Z → Y .
En esta configuracion, al nodo se le conoce como lineal (Ver figura 2.6a).
2. El nodo Z esta contenido por el conjunto de nodos evidencia (Z ⊆ E) y tiene am-
bas flechas en la trayectoria saliendo de este, X ← Z → Y . En esta configuracion,
al nodo se le conoce como divergente (Ver figura 2.6b).
22
3. El nodo Z y sus descendientes no estan contenidos por el conjunto de nodos
evidencia ¬(Z ⊆ E), ¬(d(Z) ⊆ E) y ambas flechas en la trayectoria entran a
este, X → Z ← Y . En esta configuracion, al nodo se le conoce como convergente
(Ver figura 2.6c).
Figura 2.6: Tipos de nodos de acuerdo a su configuracion en la red Bayesiana: (a) NodoLineal. (b) Nodo Divergente. (c) Nodo Convergente.
Geiger y Pearl [16] probaron que el concepto de d-separacion puede revelar todas
las relaciones de independencia condicional que estan codificadas en una red Bayesiana.
De acuerdo a las relaciones de dependencia o independencia condicional de una red
Bayesiana, se presentan las siguientes definiciones:
Definicion 2.15 Mapa de Dependencias (D-Map)
Para un modelo probabilıstico M, un grafo G es un mapa de dependencias (D-Map) de
M si cada relacion de dependencia de M puede ser expresada en G. Un grafo sin arcos
es un D-Map trivial ya que cada nodo es independiente de los demas.
Definicion 2.16 Mapa de Independencias (I-Map)
Para un modelo probabilıstico M, un grafo G es un mapa de independencias (I-Map)
de M si cada relacion de independencia derivada de G es verdadera en M. Un grafo
completo en donde cada nodo esta conectado con el resto de los nodos es un I-Map
trivial ya que no contiene relaciones de independencia.
Definicion 2.17 Mapa de Independencias Mınimo(Min I-Map)
Un grafo G es un mapa mınimo de independencias (Min I-Map) de un modelo M si
G es un I-Map de M y al remover cualquier arco de G se obtiene un grafo que no es
I-Map de M.
Definicion 2.18 Mapa Perfecto (P-Map)
Un grafo G es un mapa perfecto (P-Map) de M si es D-Map e I-Map de M al mismo
tiempo.
23
2.4 Recocido Simulado para Optimizacion
El algoritmo de recocido simulado (SA por sus siglas en ingles, Simulated Annea-
ling) es un tecnica que ha atraıdo atencion significativa por su conveniencia para ser
aplicado a problemas grandes de optimizacion, especialmente aquellos en donde un
extremo global esta escondido entre muchos extremos locales [44].
Las ideas que forman la base de recocido simulado fueron publicadas primeramente
por Metropolis et. al. [27] en 1953 en un algoritmo para simular el enfriamiento de
materiales en banos calientes, un proceso conocido como recocido. Este procedimiento
basicamente consiste en que si un material solido es calentado mas alla de su punto
de fusion y posteriormente enfriado hasta regresar a su estado solido, las propiedades
estructurales del material dependeran de la velocidad de enfriamiento [33].
El algoritmo de Metropolis es un algoritmo de cadena de Markov de tipo Monte
Carlo (MCMC por sus siglas en ingles, Markov Chain Monte Carlo) que simula el
cambio en energıa del sistema cuando este se somete a un proceso de enfriamiento hasta
que converge a un estado estable o estado congelado. Treinta anos despues, Kirkpatrick
et. al. [21] sugirieron que este tipo de simulacion podrıa ser usada para buscar las
soluciones posibles de un problema de optimizacion con el objetivo de converger a una
solucion optima. Este enfoque puede ser visto como una variante de la tecnica heurıstica
de busqueda local en la cual un subconjunto de soluciones posibles es explorado al
moverse de una solucion actual a una solucion en la vecindad de manera repetida.
2.4.1 El Algoritmo de Metropolis
En su forma original, el algoritmo de recocido simulado esta basado en la ana-
logıa entre la simulacion del proceso de recocido de solidos y el problema de resolver
problemas de optimizacion grandes.
En la fısica del estado solido, el recocido denota un proceso fısico en el cual un
solido es calentado incrementando su temperatura a un valor maximo (de manera que
todas las partıculas del solido se acomoden aleatoriamente en el estado lıquido), seguido
por un proceso de enfriamiento al disminuir lentamente la temperatura. De esta manera,
todas las partıculas se acomodan en los estados de mınima energıa de una configuracion
regular si es que la maxima temperatura fue suficientemente alta y el enfriamiento
suficientemente lento. El algoritmo de Metropolis se explica a continuacion.
Comenzando en el maximo valor de temperatura, la fase de enfriamiento del pro-
ceso de recocido puede ser descrita como sigue: en cada valor de temperatura T , al
solido se le permite alcanzar equilibrio termico, caracterizado por una probabilidad de
estar en un estado con energıa E dado por la distribucion de Boltzmann:
P (E) =1
Z(T )exp
(
−E
kBT
)
, (2.12)
24
donde Z(T ) es un factor de normalizacion conocido como funcion de particion el cual
depende de la temperatura T , y kB es la constante de Boltzmann. El factor
exp
(
−E
kBT
)
, (2.13)
es conocido como el factor de Boltzmann. Conforme la temperatura decrece, la dis-
tribucion de Boltzmann se concentra en los estados con menos energıa y finalmente,
cuando la temperatura se aproxima a cero, solo los estados de mınima energıa tienen
una probabilidad de ocurrencia diferente de cero. Sin embargo, es bien sabido que si el
enfriamiento es muy rapido, es decir, al solido no se le permite alcanzar equilibrio termi-
co para cada valor de temperatura, estructuras amorfas inestables pueden alcanzarse
en vez de los estados de mınima energıa.
Para simular la evolucion hacia el equilibrio termico de un solido para un valor de
temperatura fijo T , Metropolis et. al. [27] propusieron un metodo Monte Carlo que gen-
era secuencias de estados del solido de la siguiente manera: dado un estado actual del
solido caracterizado por la posicion de sus partıculas, una pequena perturbacion, aleato-
riamente generada, es aplicada mediante un pequeno desplazamiento de una partıcula
aleatoriamente seleccionada. Si la diferencia de energıa, ∆E, entre el estado actual y
el estado perturbado es negativa, es decir, la perturbacion resulta en un menor estado
de energıa del solido, entonces el proceso continua con el nuevo estado. Si ∆E ≥ 0,
entonces la probabilidad de aceptacion del estado perturbado esta dada por
exp
(
−∆E
kBT
)
. (2.14)
Esta regla de aceptacion de nuevos estados es conocida como el criterio de Metropo-
lis. Siguiendo este criterio, el sistema eventualmente alcanza equilibrio termico, es decir,
despues de un gran numero de perturbaciones, usando el criterio de aceptacion antes
mencionado, la distribucion de probabilidad de los estados se aproxima a la distribucion
Boltzmann, dada por la ecuacion 2.12.
2.4.2 El Algoritmo de Recocido Simulado
El algoritmo de Metropolis tambien puede ser usado para generar secuencias de
configuraciones de un problema de optimizacion combinatoria [21]. En este caso, las
configuraciones asumen el rol de los estados del solido, mientras que la funcion de
costo C, y el parametro de control c, toman los roles de energıa y temperatura, res-
pectivamente. El algoritmo de recocido simulado puede entonces ser visto como una
secuencia de algoritmos de Metropolis evaluados a una secuencia decreciente de valores
del parametro de control.
Inicialmente, el parametro de control es alto y se genera una secuencia de con-
figuraciones del problema combinatorio. De manera similar al algoritmo de mejora
25
iterativa, se define un mecanismo de generacion de forma que dada una configuracion
i, otra configuracion j pueda ser obtenida al elegir aleatoriamente un elemento de la
vecindad de i. Lo anterior corresponde a la pequena perturbacion en el algoritmo de
Metropolis. Si decimos que ∆E = Cj − Ci, entonces la probabilidad de j de ser la
proxima configuracion en la secuencia es 1, si ∆C ≤ 0, y exp(−∆Cc
), si ∆C > 0 (el
criterio Metropolis). Ası, existe una probabilidad diferente de cero de continuar con
una configuracion de mayor costo que la configuracion actual. Este proceso continua
hasta que el equilibrio es alcanzado, esto es, hasta que la distribucion de probabilidad
de la configuracion se aproxima a la distribucion Boltzmann. El parametro de control
es entonces disminuido en pasos, permitiendole al sistema alcanzar equilibrio termico
para cada paso y generar una secuencia de configuraciones de la manera previamente
descrita. El algoritmo termina cuando c alcanza un valor muy pequeno para el cual,
virtualmente, no se aceptan nuevos estados. La configuracion final es tomada como la
solucion del problema.
Simulacion termodinamica Optimizacion combinatoria
Estados del sistema Posibles solucionesEnergıa CostoCambio de estado Soluciones en la vecindadTemperatura Parametro de controlEstado estable Solucion heurıstica
Tabla 2.1: Mapeo de caracterısticas de termodinamica a optimizacion combinatoria.
La tabla 2.1 muestra el mapeo de caracterısticas de los trabajos de Metropolis et.
al. [27] y Kirkpatrick et. al [21].
2.4.3 Implementacion del Algoritmo de Recocido Simulado
Dada una funcion de costo C(z), y un estado (solucion) inicial z0, el algoritmo bus-
ca mejorar la solucion actual perturbando aleatoriamente z0. El algoritmo de Metropolis
es usado como criterio de aceptacion o rechazo de los nuevos estados a una temperatura
T . Los pasos del algoritmo se muestran a continuacion:
1. Perturbar z aleatoriamente y calcular el cambio en costo, ∆C.
2. Si ∆C ≤ 0, aceptar el nuevo estado.
3. Si ∆C > 0, aceptar el nuevo estado con probabilidad
P (∆C) = exp
(
−∆C
T
)
,
26
Esto representa el ciclo interno del algoritmo de recocido simulado. El criterio de
aceptacion es implementado generando un numero aleatorio, R ∈ [0, 1] y comparando-
lo con P (∆C). Si R < P (∆C), entonces el nuevo estado es aceptado. Para cualquier
temperatura, el ciclo interno debe prolongarse lo suficiente para que el sistema alcance
un estado estable [21].
Esquema de enfriamiento
El ciclo externo del algoritmo es conocido como el esquema de enfriamiento y
especifica la razon de decremento de la temperatura. El esquema de enfriamiento es uno
de los aspectos mas crıticos de la implementacion del algoritmo de recocido simulado.
Muchas variantes han sido presentadas desde la introduccion de este algoritmo en 1982.
Dos clases principales de tipos de esquemas de enfriamiento son distinguidas por van
Laarhoven y Aarts [44]:
Numero de ciclos internos variable (longitud de cadenas de Markov) y decremento
de temperatura fija.
Numero de ciclos internos fijo y decremento de temperatura variable.
Sin embargo, basado en los resultados presentados por Malhotra et. al. [26], un
esquema de enfriamiento hıbrido en el cual tanto la temperatura como el ciclo interno
del algoritmo varıan continuamente a traves del proceso de recocido es usado en [11, 12].
El ciclo externo se comporta nominalmente como un factor de decremento constante,
Ti+1 = αTi, (2.15)
donde α = 0.90. La temperatura dentro del ciclo interno puede variar proporcional-
mente con el valor optimo de la funcion de costo.
Un criterio para el ciclo interno que emplea el numero de grados de libertad del
sistema y la temperatura actual del sistema fue propuesto por Devadas y Newton
[11]. Estos investigadores observaron que a altas temperaturas, el equilibrio se logra de
forma mas rapida, de manera que introdujeron una funcion que reduce gradualmente
el numero de estados intentados en el ciclo interno para cada valor de temperatura. La
funcion siguiente es utilizada para determinar el numero de iteraciones del ciclo interno,
Nin = Ndof
[
2 + 8
(
1 −log(T − Tf )
log(T0 − Tf )
)]
, (2.16)
donde Ndof es el numero de grados de libertad del sistema.
La temperatura inicial debe ser escogida de tal manera que el sistema tenga sufi-
ciente energıa para visitar todo el espacio posible de soluciones. Un enfoque es simple-
mente escoger un valor de temperatura arbitrario e intentar un numero de transiciones
27
de estados. El sistema esta lo suficientemente caliente si un alto porcentaje (e.g. 80 %)
de los estados de transicion son aceptados. Si la eleccion inicial de temperatura arroja
cualquier valor menor de este porcentaje, T0 puede ser escalada linealmente para repe-
tir el proceso. Una eleccion inicial de temperatura que arroje una excesiva aceptacion
de estados (e.g. >95 %) es tambien contraproducente (computacionalmente es menos
eficiente), indicando que existe demasiada energıa en el sistema, por lo que T0 debe ser
escalada para lograr un 80 % de nivel de aceptacion.
2.5 Criterio Bayesiano
En esta seccion se describe el criterio Bayesiano propuesto por Cooper y Her-
skovitz [8]. Este criterio es utilizado posteriormente por el algoritmo SABS propuesto
en esta investigacion para el aprendizaje de la estructura de redes Bayesianas.
Primero se mencionara que un modelo de red Bayesiana M esta compuesto por
una estructura de red conformada por nodos y por relaciones de dependencia e inde-
pendencia entre dichos nodos, MS, ası como por probabilidades condicionales, MP ,
entre pares de nodos por lo que M = (MS,MP ). Considerando que el problema que
se desea resolver es encontrar un modelo M dado un conjunto de datos D, este se puede
ver como encontrar la red mas probable dado el conjunto de datos [8].
Considerese que D represente un conjunto de datos, X represente un conjunto de
variables contenidas en D, y MSiy MSj
dos estructuras de red Bayesiana conteniendo
exactamente las variables en X . Mediante el calculo de P (MSi|D)/P (MSj
|D) se puede
saber que estructura es mas probable de acuerdo a sus probabilidades posteriores.
Para calcular la razon de las probabilidades posteriores, se debe calcular P (MSi,D) y
P (MSj,D) usando la siguiente equivalencia:
P (MSi|D)
P (MSj|D)
=
P (MSi,D)
P (D)
P (MSj,D)
P (D)
=P (MSi
,D)
P (MSj,D)
. (2.17)
Ahora se debe derivar una formula para el calculo de P (MS,D). Esta formula se
deriva introduciendo cinco suposiciones que se describen a continuacion en la seccion
2.5.1.
2.5.1 Suposiciones del Criterio Bayesiano
1. El proceso que genero el conjunto de datos puede ser modelado de manera pre-
cisa como una red Bayesiana conteniendo solo las variables en X , las cuales son
discretas.
De acuerdo a lo que esta suposicion establece, solo se deben considerar varia-
bles discretas. Otra consideracion que establece esta suposicion es que una red
28
Bayesiana (la estructura y las probabilidades condicionales) es suficiente para
capturar cualquier distribucion de probabilidad sobre las variables en el conjunto
de datos.
La aplicacion de la suposicion 1 arroja
P (MS,D) = P (MS)
∫
MP
P (D|MS,MP )f(MP |MS)dMP , (2.18)
donde
MP → Vector cuyos valores denotan las asignaciones de probabilidad
condicional asociadas con la estructura MS de la red Bayesiana.
f → Funcion de densidad de probabilidad condicional sobre MP
dada MS.
La integral es sobre todos los valores posibles de asignacion a MP . Por lo tanto,
se esta integrando sobre todas las posibles redes Bayesianas con estructura MS.
2. Los registros en el conjunto de datos ocurren independientemente dado un modelo
de red Bayesiana.
Esta suposicion es equivalente a asumir que la red Bayesiana que genera los datos
es estatica, es decir, no cambia conforme los datos son generados. Por tanto, se
puede expresar la ecuacion 2.18 como sigue:
P (MS,D) = P (MS)
∫
MP
[
m∏
h=1
P (Ch|MS,MP )
]
f(MP |MS)dMP , (2.19)
donde m es el numero de registros en D y Ch es el h-esimo registro en D.
3. Los registros del conjunto de datos son completos, esto es, no existen registros en
donde alguna variable no contenga valores.
De acuerdo a la suposicion anterior, la ecuacion 2.19 puede ser escrita de la
siguiente manera:
P (MS,D) = P (MS)
∫
MP
[
n∏
i=1
qi∏
j=1
ri∏
k=1
P (xi = vik|πij,MP )αijk
]
f(MP |MS)dMP ,
(2.20)
donde
29
n = Numero de variables en el conjunto de datos.
qi = |πi|. Numero de instanciaciones diferentes de los
padres del nodo xi.
Vi = (vi1, . . . , viri) Lista de posibles valores del nodo xi.
ri = |Vi| Numero de valores diferentes que toma el nodo xi.
πij = j-esimo elemento de la lista de instanciaciones
de los padres del nodo xi.
αijk = Numero de casos en D en los cuales xi = vik y
los padres del nodo estan en la j-esima
instanciacion.
Si se dice que θijk denota la probabilidad condicional P (xi = vik|πij,MP ), se debe
conocer a una asignacion de probabilidades numericas para θijk, desde k=1, . . . , ri,
como distribucion de probabilidad, la cual representa la lista (θij1, . . . , θijri). Notar
que los valores de xik para k=1, . . . , ri, son mutuamente exclusivos y exhaustivos,∑
k θijk = 1. Ademas, si para un valor de xi y πij se hace que f(θij1, . . . , θijri)
denote la funcion de densidad de probabilidad sobre (θij1, . . . , θijri), llamamos a
f(θij1, . . . , θijri) una distribucion de probabilidad de segundo orden ya que es una
distribucion de probabilidad sobre una distribucion de probabilidad.
Dentro de esta investigacion se ha contemplado el aprendizaje de estructuras de
redes Bayesianas a partir de conjuntos de datos completos e incompletos, sin em-
bargo, para derivar una formula que nos permita seleccionar la mejor red, se debe
partir del supuesto de que el conjunto de datos es completo. Por tanto, si el conjun-
to de datos presenta algunos valores faltantes, dichos valores deben ser completa-
dos de manera previa y posteriormente aplicar la formula que se derivara mediante
las presentes suposiciones. En la seccion 3.3 se presentara el algoritmo de inferen-
cia basado en la primera etapa del algoritmo EM [10] (Expectation-Maximization
por sus siglas en ingles) que recibe un conjunto de datos incompletos e infiere los
valores faltantes en base a conteos de frecuencia, proporcionando como salida un
conjunto de datos completo.
4. Para 1 ≤ i, i′ ≤ n, 1 ≤ j ≤ qi, 1 ≤ j′ ≤ qi′ , si ij 6= i′j′ entonces la distribucion
f(P (xi|πij)) es marginalmente independiente de la distribucion f(P (xi′|πi′j′)).
Esta suposicion puede ser expresada equivalentemente como
f(MP |MS) =n
∏
i=1
qi∏
j=1
f(θij1, . . . , θijri). (2.21)
La suposicion anterior establece que nuestro conocimiento acerca de los valores
de la distribucion de probabilidad de segundo orden f(θij1, . . . , θijri), no esta in-
30
fluenciada por nuestro conocimiento de los valores de otras distribuciones de pro-
babilidad similares. Esto es, las distribuciones son marginalmente independientes.
5. La distribucion f(θij1, . . . , θijri) es uniforme para 1 ≤ i ≤ n, 1 ≤ j ≤ qi.
Esta suposicion establece que inicialmente, antes de ver los datos, somos indiferen-
tes respecto a dar alguna asignacion de valores a las probabilidades condicionales
θij1, . . . , θijrisobre otra. Por tanto f(θij1, . . . , θijri
)=Cij para alguna constante
Cij.
El resultado final dadas las suposiciones anteriores se muestra en la ecuacion 2.22.
Esta ecuacion nos permite calcular P (MS,D) usando P (MS) combinada con simple
enumeracion de registros en el conjunto de datos. Para observar una derivacion detallada
paso a paso donde se obtiene como resultado la ecuacion 2.22 a partir de la ecuacion
2.21, consultar la referencia [8].
P (MS,D) = P (MS)n
∏
i=1
qi∏
j=1
(ri − 1)!
(Nij + ri − 1)!
ri∏
k=1
αijk!, (2.22)
donde Nij =∑ri
k=1 αijk.
2.6 Aprendizaje de Redes Bayesianas
Desde los anos 1980’s, las redes Bayesianas se han convertido en una representacion
muy popular para la codificacion de conocimiento experto incierto en sistemas expertos
[18]. En anos recientes, el aprendizaje automatico de la estructura de redes Bayesianas
se ha convertido en uno de los topicos de investigacion mas activos debido a la dificultad
de identificar relaciones causales entre variables aleatorias del proceso a modelar. El
proceso de identificacion de relaciones entre variables puede ser realizado por un experto
de dominio, sin embargo, para dominios muy complejos en donde pueden existir decenas
o cientos de variables aleatorias interviniendo en el proceso, la tarea se vuelve casi
imposible, resultando en un proceso extremadamente lento y tedioso.
Dos enfoques para la construccion automatica de la estructura de redes Bayesianas
a partir de un conjunto de datos D = x1, . . . , xm se pueden identificar de acuerdo a
los algoritmos propuestos en la literatura, algoritmos basados en busqueda y evaluacion
y algoritmos basados en analisis de dependencias. En esta seccion se describen ambos
enfoques y se presentan los trabajos relacionados con cada uno de ellos.
2.6.1 Enfoque de Busqueda y Evaluacion
El enfoque de busqueda y evaluacion conceptualiza el problema de aprender au-
tomaticamente la estructura de una red Bayesiana como una busqueda en el espacio
31
posible de soluciones. La mejor estructura sera aquella que mejor se ajuste a los datos.
Basicamente, se comienza con una estructura vacıa (un digrafo sin arcos) a la cual se
van agregando arcos. Conforme se obtiene una estructura nueva, esta es evaluada para
saber si es mejor que la anterior. En caso de ser mejor, la nueva estructura reemplaza
a la actual, y en caso contrario, se intentan otras estructura agregando otros arcos.
Este proceso continua hasta que ninguna estructura generada es mejor que la actual.
Debido a que el aprendizaje de la estructura de redes Bayesianas usando el enfoque de
busqueda y evaluacion es NP-Hard [5], la mayorıa de los algoritmos, si no es que todos,
utilizan metodos heurısticos para explorar el espacio de soluciones.
Espacio de busqueda de la red mas probable
Considerese el problema de encontrar la estructura de red mas probable, MS,
que maximiza P (MS|D). Para un conjunto de datos D, P (MS,D) es proporcional
a P (MS|D), y por tanto encontrar la MS que maximiza P (MS|D) es equivalente a
encontrar la MS que maximiza P (MS,D). Se puede maximizar P (MS,D) aplicando
exhaustivamente la ecuacion 2.22 para cada MS.
En funcion del numero de variables, el numero de estructuras posibles crece expo-
nencialmente, de tal manera que una enumeracion exhaustiva de todas las estructuras
de red no es posible en muchos dominios. Robinson [34] derivo la siguiente funcion
recursiva para determinar el numero de estructuras posibles que contienen n nodos:
f(n) =n
∑
i=1
(−1)i+1
(
n
i
)
2i(n−1)f(n − i), f(1) = f(0) = 1. (2.23)
Para n=5, el numero de estructuras posibles es 29, 000; y para n=10, es aproxi-
madamente 4.2×1018. En general, como funcion de n, el numero de estructuras posibles
crece exponencialmente. Claramente, necesitamos un metodo para localizar la MS que
maximiza P (MS|D) que sea mas eficiente que enumerar exhaustivamente todas las
estructuras posibles.
Trabajos relacionados
Varios trabajos de aprendizaje de la estructura de redes Bayesianas han sido de-
sarrollados bajo este enfoque.
Chow y Liu, 1968
Chow y Liu [6] desarrollaron un algoritmo de construccion de arboles. Este al-
goritmo toma una distribucion de probabilidad P como entrada y construye una
estructura de arbol en O(n2) pasos, donde n es el numero de nodos. Chow y
Liu probaron que la distribucion de la estructura resultante P tree es la mejor
32
aproximacion de P . Un punto interesante sobre este algoritmo es que posee cier-
tas caracterısticas de ambos enfoques de construccion de redes Bayesianas. Aun
cuando la idea general del algoritmo es encontrar la estructura que presente la
mejor evaluacion de acuerdo al concepto de entropıa cruzada de Kullback-Leibler
[23], termina por realizar analisis de pares de nodos el cual es un metodo usado
en el enfoque de analisis de dependencias.
Rebane y Pearl, 1987
Rebane y Pearl [32] extendieron el algoritmo de Chow y Liu para poli-arboles.
Probaron que cuando la distribucion de probabilidad tiene un mapa perfecto
(P-Map) y el mapa tiene una estructura de poli-arbol, su algoritmo siempre en-
cuentra el mapa perfecto, es decir, la estructura correcta. Tambien desarrollaron
un metodo para encontrar la direccion de los arcos en el grafo identificando nodos
convergentes.
Herskovitz y Cooper, 1991
Herskovitz y Cooper [20] desarrollaron un algoritmo que usa la entropıa como
medida de evaluacion. El problema de aprender la estructura de la red Bayesiana
es visto como aproximar la funcion de probabilidad conjunta de los datos usando
una estructura de red Bayesiana que tenga mınima perdida de informacion (en-
tropıa maxima). El metodo de busqueda usado es de tipo greedy y se requiere de
ordenacion de nodos. La complejidad de este algoritmo es O(n4) donde n es el
numero de nodos en la red. Este algoritmo ha sido probado usando el conjunto
de datos de la red ALARM conteniendo 10,000 registros y es capaz de encontrar
la estructura con 2 arcos faltantes y dos arcos extras.
Cooper y Herskovitz, 1992
Cooper y Herskovitz [9] desarrollaron un algoritmo al cual denominaron K2.
Este algoritmo, a partir de un conjunto de datos y una ordenacion de nodos como
entrada, construye la estructura de la red Bayesiana. El algoritmo K2 utiliza como
medida de evaluacion el criterio Bayesiano (BS por sus siglas en ingles, Bayesian
Score). El objetivo de K2 es encontrar la estructura de la red MS mas probable
dado un conjunto de datos D, esto es, maximizar la probabilidad P(MS|D). El
metodo de busqueda usado es de tipo greedy e igualmente ha sido probado usando
el conjunto de datos de la red ALARM conteniendo 10,000 registros donde fue
capaz de encontrar la estructura correcta con solo un arco faltante y un arco
extra.
Heckerman et. al., 1994
Heckerman et. al. [18] desarrollaron otro algoritmo basado en el enfoque de
busqueda y evaluacion. Al estudiar las propiedades de consistencia y suposiciones
33
de otros metodos basados en este enfoque, encontraron dos suposiciones, llamadas
modularidad de parametros y equivalencia de eventos, las cuales han sido igno-
radas por otros investigadores. Al utilizar estas suposiciones con las suposiciones
hechas por otros investigadores, Heckerman et. al. mostraron que un metodo di-
recto para combinar conocimiento de los usuarios e informacion estadıstica puede
obtenerse.
Lam y Bacchus, 1994
El algoritmo de Lam y Bacchus [24] se basa en el principio de Longitud de Descrip-
cion Mınima (MDL por sus siglas en ingles, Minimum Description Length). Este
algoritmo usa MDL como medida de evaluacion de redes candidatas y mediante
una busqueda heurıstica, intenta minimizar esta medida. La importancia de este
trabajo radica principalmente en que no se requiere de una ordenacion de nodos
y puede realizar la orientacion de los arcos utilizando unicamente metodos de
busqueda y evaluacion. Este algoritmo fue probado tambien con un conjunto de
datos de la red ALARM encontrando la estructura correcta menos tres arcos y
dos arcos erroneamente orientados.
Wong y Xiang, 1994
El algoritmo de Wong y Xiang [47, 48] es un algoritmo de aprendizaje de re-
des Markovianas basado en entropıa. En [48], Wong y Xiang probaron que su
algoritmo siempre puede aprender una red Markoviana que es I-Map del modelo
fundamental, y cuando el modelo fundamental es una red sencillamente conecta-
da, se garantiza que un I-Map es construido.
Singh y Valorta, 1995
Singh y Valorta [39] desarrollaron un algoritmo hıbrido llamado CB que emplea
tanto el enfoque de busqueda y evaluacion como el de analisis de dependencias.
CB primero emplea una version modificada del algoritmo PC [41] para encontrar
una ordenacion de nodos y entonces usa una version modificada del algoritmo
K2 [9] para aprender la red Bayesiana. CB ha sido probado con datos de la red
ALARM y puede generar una estructura con dos arcos faltantes, dos arcos extra
y dos arcos erroneamente orientados.
Acid y Campos, 1996
Acid y Campos [1] desarrollaron el algoritmo BENEDICT basado en entropıa.
Este algoritmo requiere de una ordenacion de nodos y emplea una metodo de
busqueda heurıstica. Sin embargo, usa una medida de entropıa diferente para
medir la proximidad entre la estructura aprendida y los datos. Despues de ob-
tener una estructura usando la busqueda heurıstica, BENEDICT analiza las
independencias condicionales implıcitas en la estructura mediante el concepto de
34
d-separacion (ver seccion 2.3.5), y calcula la diferencia entre estas independencias
condicionales implıcitas y las independencias condicionales reales de los datos. Por
tanto, BENEDICT utiliza una medida de entropıa que es la suma de los resulta-
dos de un grupo de pruebas de independencia condicional. BENEDICT ha sido
probado con datos de la red ALARM y puede generar una estructura con cuatro
arcos faltantes y cinco arcos extras comparado con la estructura verdadera para
un conjunto de 3,000 casos.
Friedman y Goldszmidt, 1996
El algoritmo propuesto por Friedman y Goldszmidt [13] usa dos tipos diferentes
de medidas de evaluacion para aprender redes Bayesianas, MDL y BS. La im-
portancia de este trabajo es que puede aprender redes Bayesianas y la estructura
local de las distribuciones de las probabilidades al mismo tiempo. Los autores
demostraron que su metodo tiene mejor desempeno que aquellos metodos que
ignoran las estructuras locales. Este algoritmo puede orientar los arcos usando
solamente metodos de busqueda y evaluacion.
Suzuki, 1996
El algoritmo de Suzuki [43] utiliza como medida de evaluacion el principio de
MDL. La importancia de este trabajo es que a diferencia de otros metodos, este
algoritmo no utiliza busqueda heurıstica y garantiza que la estructura optima es
encontrada. Debido a que el espacio de busqueda es enorme, Suzuki desarrollo
una tecnica denominada Branch and Bound, la cual calcula un lımite inferior
despues de que un arco es agregado a la estructura y determina si se debe seguir
la busqueda sobre dicha rama. Este algoritmo ha sido probado con conjuntos de
casos pequenos de la red ALARM (100, 200, 500 y 1,000) y ha demostrado ser
muy eficiente, sin embargo, para conjuntos de datos grandes dicha eficiencia se
ve severamente comprometida.
Wallace et. al., 1996
El algoritmo WKD desarrollado por Wallace et. al. [45] descubre la estructura de
redes Bayesianas usando el principio de longitud de mensaje mınimo (MML por
sus siglas en ingles, Minimum Message Length), una medida similar a MDL. Los
autores usan datos de siete pequenos dominios para mostrar que sus resultados
se comparan favorablemente con los del algoritmo PC. WKD no requiere de
ordenacion de nodos.
2.6.2 Enfoque de Analisis de Dependencias
El enfoque basado en analisis de dependencias busca aprender la estructura de
la red Bayesiana identificando las relaciones de dependencia (relaciones causales) en-
35
tre pares de variables de acuerdo a alguna prueba (e.g. informacion mutua) dado un
conjunto de datos D = X1, . . . , Xm. De igual manera, busca identificar las relaciones
de independencia condicional (CI por sus siglas en ingles, Conditional Independence)
entre pares de variables de acuerdo al concepto de d-separacion (ver seccion 2.3.5).
Generalmente, el enfoque basado en analisis de dependencias es mas eficiente que
el enfoque de busqueda y evaluacion para redes no muy densamente conectadas (redes
con pocos arcos), ya que puede obtener la estructura correcta cuando ciertas condiciones
se cumplen. Sin embargo, muchos algoritmos basados en este enfoque requieren de un
numero exponencial de pruebas de CI y de pruebas de CI de alto orden (pruebas de CI
con conjuntos de corte de muchos nodos).
Trabajos relacionados
Algunos de los trabajos anteriores basados en este enfoque incluyen los siguientes:
Wermuth y Lauritzen, 1983
El algoritmo propuesto por Wermuth y Lauritzen [46] requiere de una ordenacion
de nodos y para cada par de nodos aplica una prueba de CI. Si la prueba establece
una dependencia, se agrega un arco entre dichos nodos. Este algoritmo garantiza la
obtencion de un I-map del conjunto de datos de entrada, pero tiene la desventaja
de requerir de muchas pruebas de CI de alto orden.
Pearl, 1988
Pearl [30] propuso un algoritmo que requiere de un conjunto de datos grande
y una ordenacion de nodos y mediante un metodo de busqueda propio, evita
realizar pruebas de CI de alto orden. Sin embargo, debido a que trata de encontrar
la sabana de Markov (ver seccion 2.3.5) de cada nodo, debe considerar todos
los posibles subconjuntos de los nodos previos en la ordenacion, por lo que es
exponencial en el numero de pruebas de CI que realiza.
Fung y Crawford, 1990
El algoritmo denominado Constructor propuesto por Fung y Crawford [15] es
similar al algoritmo propuesto por Pearl [30]. Sin embargo, este algoritmo en vez
de encontrar una red Bayesiana, trata de encontrar una red de Markov por lo que
no requiere ordenacion de nodos. Aun cuando este algoritmo evita realizar muchas
pruebas de CI innecesarias, todavıa presenta el problema de numero exponencial
de CI’s. Una diferencia entre este algoritmo y otros algoritmos basados en el
enfoque de analisis de dependencias radica en el hecho de que este algoritmo utiliza
diferentes umbrales para las pruebas de CI. Mediante la tecnica de validacion
cruzada prueba diferentes redes generadas para diferentes umbrales y selecciona
la mejor.
36
Spirtes et. al., 1990
El algoritmo SGS propuesto por Spirtes et. al. [40] no necesita ordenacion de
nodos y puede orientar automaticamente los arcos de la estructura aprendida
usando pruebas de CI.
Srinivas et. al., 1990
El algoritmo SRA propuesto por Srinivas et. al. [42] es una extension del algorit-
mo propuesto por Pearl [30]. Este algoritmo no requiere una ordenacion de nodos
total sino parcial y permite algunas otras especificaciones de conocimiento de do-
minio. Cuando realiza la busqueda de nodos para ser agregados a la estructura,
usa la informacion de ordenacion parcial y utiliza un metodo heurıstico para de-
cidir cual nodo debe agregarse. Al igual que su antecesor, requiere de un numero
exponencial de pruebas de CI.
Spirtes y Glymour, 1991
El algoritmo PC de Spirtes y Glymour [41] es una mejora del algoritmo SGS.
Esta mejora consiste en hacer mas eficiente la construccion de redes Bayesianas
de conjuntos de datos que tienen modelos fundamentales espaciados (modelos que
tienen muchos arcos). Como muchos otros algoritmos, el algoritmo PC tambien ha
sido probado usando conjuntos de datos de la red ALARM. Usando 10,000 casos
de esta red y sin ordenacion de nodos, el algoritmo puede aprender la estructura
correcta de la red excepto por tres arcos faltantes y dos arcos extras.
Cheng et. al., 1997
Cheng et. al. [3] propusieron un algoritmo de tres fases basado en pruebas de CI.
En su primera fase, el algoritmo realiza pruebas de informacion mutua identifi-
cando aquellos enlaces con valores superiores a cierto umbral (e.g. ε=0.01, aunque
este valor puede variarse a conveniencia), los cuales son ordenados de mayor a
menor. En base a esta lista de enlaces, se aplica el algoritmo de Chow y Liu para
aproximar la estructura de la red Bayesiana. Como segunda fase, los pares que
no fueron agregados en la primera fase son agregados si es que no existen un
conjunto dado que d-separe a dichos nodos. En la tercera fase, todos los arcos
en donde existe mas de una trayectoria entre los nodos son verificados mediante
pruebas de independencia condicional. En caso de que dichos nodos sean indepen-
dientes condicionalmente dado un cierto conjunto de nodos, el arco es removido.
La importancia de este trabajo es que a este algoritmo se le puede o no propor-
cionar una ordenacion de nodos. Mediante pruebas usando conjuntos de datos de
la red ALARM, este algoritmo encontro la estructura correcta excepto por un
arco faltante cuando se proporciono ordenacion de nodos. Cuando la ordenacion
de nodos no se proporciono, el resultado fue la estructura correcta excepto por
dos arcos faltantes y cuatro arcos que no pudieron ser orientados. En la seccion
37
3.2 se explica a profundidad el funcionamiento de este algoritmo.
2.7 Resumen
En este capıtulo se ha presentado los conceptos teoricos fundamentales sobre re-
des Bayesianas. En primera instancia, se ha hecho una introduccion a los conceptos de
probabilidad y de teorıa de grafos relacionados con las redes Bayesianas. Se definio una
red Bayesiana como un grafo acıclico dirigido (DAG) en donde los nodos representan
variables aleatorias y los arcos entre nodos representan relaciones de dependencia o
causalidad. Otro concepto importante en redes Bayesianas es la ordenacion de nodos.
Mediante este concepto se pueden simplificar el problema de aprendizaje de la estruc-
tura de dichas redes al proporcionar informacion de dominio que restringe relaciones
de causalidad entre pares de nodos. Existen tres tipo de redes Bayesianas de acuerdo
a su estructura, arboles, poli-arboles y redes multiconectadas. Los arboles son redes en
donde cada nodo tiene solamente un padre. Los poli-arboles tienen como caracterıstica
principal la existencia de una unica trayectoria posible, y las redes multiconectadas son
un tipo de red Bayesiana de estructura mas compleja en donde pueden existir varias
trayectorias entre pares de nodos y modelan la mayorıa de los problemas de diversos
dominios. Se ha establecido el concepto de d-separacion. Este concepto nos permite
obtener las relaciones de independencia condicional para cualquier red Bayesiana bajo
las condiciones de configuracion de nodos lineales, convergentes y divergentes.
En la seccion 2.4 se ha presentado la teorıa sobre el algoritmo de recocido simulado.
Este algoritmo es base para el algoritmo propuesto en el capıtulo 3 como metodo de
solucion al problema del aprendizaje de la estructura de redes Bayesianas. Recocido
simulado tiene sus orıgenes en los trabajos de Metropolis et. al. [27] y fue propuesto
por Kirkpatrick et. al [21]. En su forma original, el algoritmo de recocido simulado
esta basado en la analogıa del proceso de recocido de solidos y el problema de resolver
problemas de optimizacion grandes.
Por ultimo, en la seccion 2.5 se presento una medida de evaluacion denominada
criterio Bayesiano. Esta medida propuesta por Cooper y Herskovitz [8] puede ser uti-
lizada para evaluar estructuras de red MS y encontrar aquella que es mas probable de
acuerdo a un conjunto de datos D.
38
Capıtulo 3
Algoritmos de Aprendizaje de Redes Bayesianas
Como se menciono en la seccion 2.6, existen dos enfoques para el aprendizaje
de redes Bayesianas mediante conjuntos de datos, busqueda y evaluacion y analisis de
dependencias. En este capıtulo se presentara primeramente, un algoritmo desarrollado
en esta investigacion que forma parte del primer enfoque y al cual hemos nombrado
SABS. Posteriormente, se presentara un algoritmo de la literatura perteneciente al
enfoque de analisis de dependencias, el algoritmo de tres fases de Cheng para conjuntos
de datos completos. Por ultimo, se presentara otro algoritmo tambien desarrollado
como parte de esta investigacion y el cual infiere los valores faltantes de conjuntos de
datos incompletos. Este algoritmo es posteriormente utilizado como algoritmo de pre-
procesamiento para aprender la estructura de redes Bayesianas a partir de conjuntos de
datos incompletos, tanto por el algoritmo SABS, como por el algoritmo de tres fases.
3.1 El Algoritmo SABS
El algoritmo SABS es un algoritmo que busca la red Bayesiana mas probable
utilizando el criterio Bayesiano como medida de evaluacion y recocido simulado como
metodo de busqueda. Primeramente, se presentara la forma en que se evaluan las redes
candidatas de acuerdo al criterio Bayesiano y posteriormente se realizara la introduc-
cion del algoritmo.
3.1.1 Evaluacion de BNs usando el Criterio Bayesiano
En la seccion 2.5 se presento la medida de evaluacion llamada Criterio Bayesiano
la cual fue propuesta por Cooper y Herskovitz [8]. Esta medida propone evaluar redes
Bayesianas candidatas y seleccionar aquella que sea mas probable de acuerdo a los
datos, P (MS,D).
Si se asume que se puede especificar un ordenamiento de nodos sobre las n varia-
bles, tal que si Xi precede a Xj en el orden, entonces no se permiten estructuras en
las cuales existe un arco de Xj a Xi. Dada tal ordenacion de nodos como restriccion,
39
la complejidad del problema disminuye ya que el espacio de busqueda de posibles solu-
ciones se recorta, sin embargo, existen todavıa 2(n2) = 2n(n−1)/2 posibles estructuras de
red Bayesiana. Si se hace g(n)=2n(n−1)/2, para valores grandes de n no es factible aplicar
la ecuacion 2.22 para cada una de las g(n) posibles estructuras. Por lo tanto, ademas
de una ordenacion de nodos, se asumiran probabilidades iguales sobre MS. Esto es,
inicialmente, antes de observar cualquier dato en D, se cree que todas las estructuras
son igualmente probables. En tal caso, modificando acorde a esto la ecuacion 2.22 se
obtiene:
P (MS,D) = c
n∏
i=1
qi∏
j=1
(ri − 1)!
(Nij + ri − 1)!
ri∏
k=1
αijk!, (3.1)
donde c = 1/g(n) es la probabilidad a priori P (MS), para cada MS. En el apendice B
se presenta un ejemplo para determinar la estructura de red Bayesiana mas probable
mediante el uso de la ecuacion 3.1. Para maximizar la ecuacion 3.1, es suficiente con
encontrar el conjunto de padres Πi, de cada variable que maximice el segundo producto
interno.
maxMS[P (MS,D)] = c
n∏
i=1
max
[
qi∏
j=1
(ri − 1)!
(Nij + ri − 1)!
ri∏
k=1
αijk!
]
, (3.2)
donde la maximizacion toma lugar sobre todos los posibles conjuntos de padres Πi de
Xi que son consistentes con la ordenacion de nodos.
Considerese la generalizacion de la ecuacion 3.2. Dejese que ΠSi sean los padres
de Xi en MS, denotados como ΠSi → Xi. Asumir que P (MS) puede ser calculada
como P (MS) =∏n
i=1 P (ΠSi → Xi). De este modo, para todos los pares de variables
Xi y Xj distintos, nuestro conocimiento de que Xi tiene algun conjunto de padres
es independiente de nuestro conocimiento de que Xj tiene algun conjunto de padres.
Usando esta suposicion de independencia, se pueden expresar la ecuacion 2.22 como
P (MS,D) =n
∏
i=1
P (ΠSi → Xi)
qi∏
j=1
(ri − 1)!
(Nij + ri − 1)!
ri∏
k=1
αijk!, (3.3)
donde la probabilidad P (ΠSi → Xi) puede ser calculada directamente o derivada usando
metodos adicionales (e.g. asumir que la presencia de un arco en ΠSi → Xi es marginal-
mente independiente de la presencia de otros arcos).
Suponiendo como anteriormente se menciono que se tiene una ordenacion de nodos,
la ecuacion 3.3 puede ser expresada como
maxMS[P (MS,D)] =
n∏
i=1
maxΠi
[
P (Πi → Xi)
qi∏
j=1
(ri − 1)!
(Nij + ri − 1)!
ri∏
k=1
αijk!
]
, (3.4)
40
donde la maximizacion a la derecha de la ecuacion 3.4 es realizada sobre todos los
posibles Πi consistentes con la ordenacion de nodos.
Partiendo de la ecuacion 3.2, del supuesto de que a priori todas las estructuras son
igualmente probables, y de una ordenacion de nodos, la siguiente ecuacion se plantea
para evaluar la probabilidad de una estructura y determinar la mejor.
f(Xi, Πi) =
qi∏
j=1
(ri − 1)!
(Nij + ri − 1)!
ri∏
k=1
αijk!, (3.5)
donde αijk se calcula relativo a Πi siendo los padres de Xi y relativo al conjunto de
datos D.
La ecuacion 3.5 requiere del calculo de factoriales cuyos resultados son numeros
muy grandes que no tienen representacion en un lenguaje computacional, a menos que
se utilicen metodos numericos, lo cual hace lento el proceso de calculo. Por lo anterior,
la siguiente ecuacion equivalente es usada de manera practica
f(Xi, Πi) =
qi∑
j=1
[
log(ri − 1) − log(Nij + ri − 1) +
ri∑
k=1
log(αijk)
]
. (3.6)
3.1.2 Descripcion del Algoritmo
SABS es un algoritmo que trata de encontrar nodo por nodo la combinacion de
padres que maximicen el criterio Bayesiano de dicho nodo, lo que implica a su vez
que se busca maximizar el criterio Bayesiano de toda la red, aplicando el algoritmo de
recocido simulado como metodo de busqueda. El procedimiento principal se muestra en
la tabla 3.1.
SABS (D, ε)V = (X1 ≺ . . . ≺ Xn); E = ; G = (V,E)(im, p) ← infoMutua(D,G)for each Xi=X1 ∈ V to Xn
G ← recocido(G,D, Xi, im, pi, Πi, Πmax)end forG ← eliminacion(D,G, ε)return (G)
Tabla 3.1: Procedimiento principal del algoritmo SABS.
El algoritmo SABS inicia calculando la informacion mutua entre pares de nodos
mediante el procedimiento infoMutua. Posteriormente, el algoritmo de recocido simu-
lado es ejecutado nodo por nodo tratando de maximizar el criterio Bayesiano de cada
41
uno de estos, y por ultimo, SABS ejecuta un procedimiento de eliminacion en donde se
remueven de la estructura de la red Bayesiana aquellos arcos que son redundantes.
Calculo de informacion mutua
El procedimiento de calculo de informacion mutua se muestra en la tabla 3.2.
Este procedimiento genera una matriz de n × n en donde n representa el numero de
variables (nodos) de la estructura de la red Bayesiana, i representa los renglones y j
representa las columnas. La informacion mutua se calcula para toda Xj que sea mayor
en la ordenacion de nodos que la variable Xi. Es decir, si i < j, usamos la ecuacion 3.7
para el calculo y almacenamos el valor en la casilla correspondiente sumando tambien
el valor calculado para la casilla [i-1,j]. Con lo anterior, estamos formando una matriz
con distribucion de informacion mutua acumulada para cada variable Xj, y ello nos
permitira generar nuevas estructuras de red Bayesiana guiando la busqueda basados en
dicha distribucion.
infoMutua(D,G)V = (X1 ≺ . . . ≺ Xn); E = ; G = (V,E)for each Xi=X1 ∈ V to Xn
for each Xj = Xi+1 ∈ V to Xn
if Xi = X1 thenim(Xi → Xj) ← IM (Xi → Xj,D)
elseim(Xi → Xj) ← im(Xi−1 → Xj) + IM(Xi → Xj,D)
if Xj = Xi+1 thenp(Xj) ← im(Xi → Xj)
end forend forreturn (im, p)
Tabla 3.2: Procedimiento para el calculo de informacion mutua.
Las ecuaciones 3.7 y 3.8 denotan el calculo de informacion mutua e informacion
mutua condicional entre pares de variables, respectivamente. En la seccion 3.2.1 se
presentara el aprendizaje de redes Bayesianas mediante el calculo de informacion mutua
e informacion mutua condicional por lo que se abundara mas sobre estas ecuaciones.
IM(Xi, Xj) =∑
xi,xj
P (xi, xj) log
[
P (xi, xj)
P (xi)P (xj)
]
. (3.7)
42
IMCOND(Xi, Xj|C) =∑
xi,xj ,c
P (xi, xj, c) log
[
P (xi, xj|c)
P (xi|c)P (xj|c)
]
. (3.8)
Implementacion del algoritmo de recocido simulado
El algoritmo de recocido simulado se presenta en la tabla 3.3. Este algoritmo recibe
un grafo G de entrada, el conjunto de datos D, el nodo Xi sobre el cual se va a correr
el algoritmo, la tabla de informacion mutua im, la sumatoria de informacion mutua
de todos los nodos con respecto a Xi, pi, el conjunto de padres del nodo Xi, Πi, y el
maximo de padres que cualquier nodo puede tener Πmax.
Basicamente, el algoritmo de recocido simulado que se ha implementado evalua de
uno por uno los nodos tratando de encontrar el conjunto de padres que maximicen su
evaluacion de acuerdo al criterio Bayesiano. Como primer paso, el algoritmo inicializa
los parametros mostrados en la tabla 3.4 y calcula el numero de iteraciones del ciclo
interno (longitud de la cadena de Markov). Posteriormente genera una nueva estruc-
tura a partir de la estructura actual. Esta nueva estructura es evaluada mediante la
funcion fcnObj que implementa la ecuacion 3.6. El procedimiento aceptaIntento acepta
o rechaza la nueva estructura si esta presenta una mejor evaluacion que la estructura
actual o en caso contrario la acepta acorde con el criterio Metropolis. En caso de ser
aceptada, la nueva estructura reemplaza a la estructura actual y reemplaza tambien a
la mejor estructura obtenida si su evaluacion es superior. Al termino de la ejecucion del
primer ciclo externo (primera cadena de Markov), se verifica el porcentaje de aceptacion
de estructuras. Si este porcentaje es menor a 80 % (determinado heurısticamente, sin
embargo, puede variar dependiendo de cada problema), la temperatura inicial se in-
crementa linealmente mediante la ecuacion 3.12, o en caso contrario, si es superior a
95 % (tambien seleccionado de forma heurıstica), la temperatura inicial se decrementa
conforme a la ecuacion 3.13 y el proceso de recocido se inicia nuevamente. El algoritmo
de recocido simulado termina cuando se alcanza un maximo de ciclos externos (maxi-
mo numero de cadenas de Markov) especificados de antemano, o cuando relativamente
pocos estados son aceptados.
La tabla 3.4 muestra la descripcion y los valores iniciales de los parametros del
algoritmo de recocido simulado. Las ecuaciones 3.9 a 3.13 muestran como se realiza el
calculo de algunos de estos parametros una vez que el algoritmo se esta ejecutando.
La ecuacion 3.9 muestra el calculo de la temperatura final. Este valor de tempe-
ratura final Tf , esta en funcion del parametro α del algoritmo y del maximo numero
de cadenas de Markov que el algoritmo puede ejecutar.
Tf = T0αmaxChains. (3.9)
Mediante la ecuacion 3.10 se realiza el calculo del factor de decremento (df ) de la
43
recocido(G,D, Xi, im, p, Πi, Πmax)V = (X1 ≺ . . . ≺ Xn); G = (V,E); Inicializar variables.while (enRecocido)
Tf ← Calcular con ecuacion 3.9costUCadena ← cEval; cadenaCnt ← 0while (noCambio < limiteNoCambio) and (cadena ≤ maxCadenas)
df ← Calcular de acuerdo a ecuacion 3.10.longCadena ← Calcular de acuerdo a ecuacion 3.11.j ← 0while j < longCadena
Gnew ← generaVecino(G, Xi, n, im, p, Πmax)nEval ← fcnobjt(Gnew, Xi, n)if aceptaIntento(cEval, nEval, T ) then
T ← T (nEval/cEval)cEval ← nEvalG ← Gnew
if cEval ≥ bEval thenbEval ← cEvalGbest ← G
end ifedoAceptados ← edoAceptados + 1
end ifj ← j + 1if cadenaCnt = 1 then
if edosAceptados/longCadena < 0.8 thenT, T0 ← Calcular de acuerdo a ecuacion 3.12Inicializar edosAceptados, noCambio; break
elseif edosAceptados/longCadena > 0.95 thenT, T0 ← Calcular de acuerdo a ecuacion 3.13Inicializar edosAceptados, noCambio; break
elseenRecocido ← false
end ifend if
end whileif costUCadena < cEval then
noCambio ← noCambio + 1costoUCadena ← cEval; T ← αT
end whileend whilereturn Gbest
Tabla 3.3: Implementacion del algoritmo de recocido simulado.
44
Parametros Valor Descripcion
maxChains 100 Maximo de cadenas de Markov.limiteNoCambio 10 Maximo permitido de cadenas de Markov sin mejora.
longCadena 0 Cantidad de iteraciones para c/cadena de Markov.T0, T 2000 Temperatura inicial, temperatura variable.
Tf 0 Temperatura final.α 0.9 Decremento de temperatura constante.
Ndof 2 Grados de libertad del sistema (2 Dimensiones).df 0 Factor de decremento para cadenas de Markov.
Tabla 3.4: Descripcion y valores iniciales de los parametros del algoritmo de recocido simu-
lado.
longitud de las cadenas de Markov (ciclo interno) [11]. El objetivo principal que persigue
este factor es propiciar que se realicen menos calculos cuando practicamente la mayorıa
de los estados son aceptados. Esto ocurre generalmente al inicio del algoritmo, cuando
la temperatura es alta, por lo que en este momento este factor provoca que la longitud
de la cadena de Markov sea pequena. Sin embargo, a temperaturas pequenas y cuando
la razon de estados aceptados e intentos es pequena, este factor provoca que la longitud
de la cadena de Markov sea grande de manera que se explore con mayor diversidad y
con mas intentos el espacio de soluciones.
df =
110
+ 910
[
1 −[
log10(T−Tf )
log10(T0−Tf )
]]
, si (T − Tf ) > 0
1, si (T − Tf ) ≤ 0(3.10)
La ecuacion 3.11 calcula la longitud de la cadena de Markov, la cual representa
la cantidad de iteraciones que se realizan dentro del ciclo interno del algoritmo de
recocido simulado. Este parametro esta en funcion del factor de decremento df como
se menciono con anterioridad. Las ecuaciones 3.12 y 3.13 denotan la manera en que
se realizan los escalamientos lineales de temperatura cuando el algoritmo se encuentra
ejecutando la primera cadena de Markov y la cantidad de estados aceptados fueron
pocos o demasiados.
longCadena = Ndof [2 + 8(df ) + 0.5] . (3.11)
T0 = T0
[
1 +
[
0.8 −edosAceptados
longCadena
]]
. (3.12)
T0 = T0
[
1 +
[
0.95 −edosAceptados
longCadena
]]
. (3.13)
45
Generacion de nuevas estructuras
La generacion de una nueva estructura de red Bayesiana a partir de la estructura
actual, se realiza por el procedimiento generaVecino que se muestra en la tabla 3.5.
Este procedimiento guıa la busqueda de nuevas estructuras haciendo uso de la ma-
triz con distribucion de informacion mutua acumulada generada por el procedimiento
infoMutua. Debido a que el procedimiento recocido analiza un nodo Xj a la vez, el pro-
cedimiento generaVecino solo altera arcos para dicho nodo, es decir, agrega o remueve
arcos de padres Xi posibles del nodo Xj.
Haciendo uso de la distribucion de informacion mutua acumulada, se selecciona
un nodo Xi (de los padres posibles de Xj). Esta seleccion se realiza de la siguiente
manera. Primero se obtiene un numero aleatorio con distribucion uniforme r ∈ [0, 1)
y posteriormente se selecciona el padre correspondiente de acuerdo a la distribucion
de informacion mutua acumulada. Una vez que se ha identificado al posible padre, de
existir ya un arco (Xi → Xj), este es removido. En caso que entre (Xi, Xj) no exista
un arco, este se agrega. Cuando el nodo Xj alcanza el numero maximo de padres,
solo se permite remover arcos. Este proceso de seleccion es conocido como Sampling-
Importance Resampling (SIR por sus siglas en ingles) [35].
Figura 3.1: Seleccion de un nodo padre usando la distribucion de informacion mutua acu-
mulada.
La figura 3.1 ilustra el proceso de seleccion de un padre mediante el uso de la dis-
tribucion de informacion mutua acumulada. Podemos apreciar que si deseamos generar
una nueva estructura en donde se agregue o remueva algun padre para el nodo Xn,
es el nodo Xi el que posee una ventana de probabilidad mas amplia debido a que su
informacion mutua es alta. Esto sin embargo, no indica que tal nodo sea con seguridad
seleccionado.
46
generaVecino(G = (V,E), Xi, im, p, Πi, Πmax)terminar ← falsewhile (not terminar)
num ← random numberfor each Xk=X1 ∈ V to Xi
tnum ←[
im(Xi)p(Xk)
]
if num ≤ tnum thenXj ← Xk
breakend if
end forif (Xi → Xj) ∈ E then
E ← E - (Xi → Xj)terminar ← true
elseif |Πi| < Πmax then
E ← E ∪ (Xi → Xj)terminar ← true
end ifend if
end whilereturn G
Tabla 3.5: Procedimiento de generacion de redes Bayesianas candidatas.
Aceptacion o rechazo de nuevas estructuras
aceptaIntento(cEval, nEval, T )
if (nEval > cEval)
aceptar ← true
else
if (random < exp(−(nEval − cEval)/T ))
aceptar ← true
else
aceptar ← false
return (aceptar)
Tabla 3.6: Funcion de aceptacion o rechazo de nuevas estructuras de red Bayesiana.
47
El procedimiento aceptaIntento se muestra en la tabla 3.6. Este procedimiento
recibe las evaluaciones (de acuerdo al criterio Bayesiano) de las redes Bayesianas actual
y candidata y acepta la nueva estructura si su evaluacion es mejor que la evaluacion
de la estructura actual. En caso contrario, acepta la nueva estructura de acuerdo al
criterio de Metropolis denotado por la ecuacion 2.14.
Eliminacion de arcos redundantes
Por ultimo, el procedimiento eliminacion se muestra en la tabla 3.7. Este procedi-
miento se ejecuta despues del algoritmo de recocido simulado y su objetivo es eliminar
aquellos arcos que pudieron ser agregados de manera erronea. Basicamente, en este
procedimiento se analiza de uno en uno todos los arcos contenidos en la estructura de
la red Bayesiana representada por G, y para cada arco (Xi → Xj), se verifica si existen
otros caminos abiertos entre ambos nodos. En tal caso, el arco es removido y se procede
a buscar un conjunto de corte C que pueda d-separar a dichos nodos.
eliminacion(D,G, ε)for each Xi=X1 ∈ V to Xn
for each Xj=Xi+1 ∈ V to Xn
if (Xi → Xj) ∈ E thenremove(E, (Xi → Xj))openPaths ← findAllOpenPaths(G, Xi, Xj)if not openPaths = ∅ then
C = findCutSet(G, Xi, Xj)if IMCOND(Xi, Xj|C) > ε then
insert(E, (Xi → Xj))end if
elseinsert(E, (Xi → Xj))
end ifend if
end forend forreturn (G)
Tabla 3.7: Procedimiento para eliminacion de arcos redundantes.
Posteriormente se aplica una prueba de independencia condicional IMCOND(Xi, Xj|C)
usando la ecuacion 3.8 y si el resultado indica que la informacion mutua entre ambos
nodos dado el conjunto de corte es superior a un umbral de ε=0.01, el arco es agregado
nuevamente a la estructura de la red. En caso contrario, el arco se remueve definitiva-
mente y se continua el mismo proceso para los demas arcos. Idealmente, el valor del
48
umbral de informacion mutua debe ser cero para considerar independencia entre los
nodos, sin embargo, es sumamente difıcil alcanzar este valor. Por tanto, el valor del
umbral en este trabajo de investigacion ha sido ajustado para ε=0.01. Este umbral
puede variar, haciendolo mas estricto conforme se aproxima a cero. La red Bayesiana
regresada por este procedimiento es la red final que el algoritmo SABS entrega como
resultado de la construccion automatica de la estructura de la red Bayesiana a partir
de un conjunto de datos.
3.1.3 Analisis de Complejidad
En esta seccion se analiza la complejidad del algoritmo SABS. Primeramente, se
analiza la complejidad de cada uno de los algoritmos que en conjunto conforman a SABS
y posteriormente se presentan ciertas condiciones que determinan la convergencia del
algoritmo.
El algoritmo SABS se presento en la tabla 3.1. Este algoritmo primeramente rea-
liza el calculo de la informacion mutua mediante la cual guıa la busqueda de nuevas
estructuras de red que son evaluadas bajo el criterio Bayesiano. La funcion de calculo
de informacion mutua se presento en la tabla 3.2. Esta funcion calcula la informacion
mutua entre pares de variables y asumiendo que n representa la cantidad de variables
de la estructura de la red Bayesiana, entonces la complejidad de la funcion es O(n2) ya
que requiere de n(n−1)2
operaciones.
La funcion generaVecino que se muestra en la tabla 3.5 implementa la generacion
de estructuras de red Bayesiana vecinas a la estructura actual. Esta funcion forma
parte del algoritmo SABS pero su complejidad no puede ser determinada ya que su
comportamiento es estocastico.
La funcion eliminacion que se muestra en la tabla 3.7 es ejecutada posterior al
algoritmo principal de recocido simulado y tiene como objetivo eliminar aquellos arcos
que pudieron ser previamente agregados de manera erronea. Para propositos del analisis
de la complejidad, el peor caso para esta funcion esta dado cuando el grafo G de entrada
que representa la red Bayesiana es un grafo acıclico dirigido totalmente conectado.
Esto es, el nodo con mayor precedencia es padre de todos los demas nodos, el segundo
nodo de mayor precedencia es padre de los nodos con menor precedencia a este, y
ası sucesivamente. Asumiendo el peor caso y considerando que n representa la cantidad
de variables de la estructura de la red Bayesiana, entonces la complejidad de esta
funcion es tambien O(n2) ya que requiere de n(n−1)2
operaciones.
En la tabla 3.3 se muestra la funcion recocido cuyo contenido implementa el al-
goritmo de recocido simulado para el aprendizaje de la estructura de redes Bayesianas,
y funcion principal del algoritmo SABS. La complejidad de esta funcion no puede ser
determinada debido a que su comportamiento es estocastico y por tanto la complejidad
del algoritmo SABS tampoco puede ser acotada, sin embargo, experimentalmente se de-
49
termino un cierto numero de evaluaciones tras las cuales la funcion se aborta y entrega
el mejor resultado que hasta ese momento haya obtenido. Tal numero de evaluaciones
se encuentra determinado por la ecuacion 3.14.
Evalsi = Xi ∗ 50 + 700. (3.14)
3.2 El Algoritmo de Tres Fases
El algoritmo de tres fases [3] es un algoritmo basado en el enfoque de analisis de
dependencias que implementa tres fases mediante las cuales construye la estructura de
una red Bayesiana a partir de un conjunto de datos completos y una ordenacion de
nodos1.
En la primera fase, el algoritmo realiza pruebas de informacion mutua entre todos
los pares de nodos identificando aquellos cuyo valor resultante sea mayor de un ε=0.01.
Posteriormente ordena dichos pares de nodos de mayor a menor explorandolos en este
orden y agrega el arco correspondiente a la estructura si y solo si no existen trayectorias
abiertas entre dichos nodos. En esta fase se obtiene una estructura inicial y algunos
arcos pueden no ser agregados. En la segunda fase, el algoritmo examina en orden los
pares de nodos que quedaron pendientes en la fase anterior y los agrega solo si no existe
un conjunto de nodos que d-separe a los nodos cuyo arco se desea agregar. En caso de
existir dicho conjunto, el arco no es agregado. Esta fase se conoce como engrosamiento
de la estructura y algunos arcos pueden ser agregados erroneamente, pero todos los
arcos correctos son agregados. Por ultimo, la tercera fase examina todos y cada uno de
los arcos que conectan a dos nodos en la estructura actual para los cuales existe mas
de una trayectoria abierta. El arco se remueve temporalmente y se busca un conjunto
de corte que d-separe a ambos nodos. En caso de que los nodos sean condicionalmente
independientes dado el conjunto de corte, el arco es removido definitivamente y se
continua analizando otros arcos. En caso contrario, el arco es restaurado e igualmente
se continua analizando otros arcos.
3.2.1 Aprendizaje de BNs usando Informacion Mutua
De acuerdo a teorıa de la informacion, la informacion mutua es un concepto muy
util para medir la cantidad de informacion compartida entre dos variables aleatorias.
Este termino, en estricto sentido matematico, fue definido en 1949 por Shannon y
Weaver [38]. Para entender la nocion de informacion, considerese esta como la respuesta
a una pregunta. La cantidad de informacion contenida en la respuesta depende de
1Cheng et. al. tambien proponen un algoritmo para el aprendizaje de redes Bayesianas a partir deconjuntos de datos completos para el cual no es necesario proporcionar una ordenacion de nodos, sinembargo, en este trabajo solo se hara mencion del algoritmo que si requiere dicha ordenacion.
50
nuestro conocimiento previo. A menos conocimiento, mas informacion que esta nos
provee [37].
En redes Bayesianas, si dos nodos son dependientes, el saber el valor de un nodo nos
proporciona cierta informacion sobre el valor de otro nodo. La ganancia de informacion
puede entonces ser medida usando este concepto de tal manera que se pueda identificar
si dos nodos son dependientes y que tan cercana es su relacion. La informacion mutua
entre dos nodos Xi, Xj se define como
I(Xi, Xj) =∑
xi,xj
P (xi, xj) log
[
P (xi, xj)
P (xi)P (xj)
]
, (3.15)
y la informacion mutua condicional esta definida como
I(Xi, Xj|C) =∑
xi,xj ,c
P (xi, xj, c) log
[
P (xi, xj|c)
P (xi|c)P (xj|c)
]
, (3.16)
donde C es un conjunto de nodos. Cuando I(Xi, Xj) es menor de un cierto umbral ε,
se dice que Xi, Xj son marginalmente independientes. Cuando I(Xi, Xj|C) es menor de
un cierto umbral ε, se dice que Xi, Xj son condicionalmente independientes dado C.
3.2.2 Descripcion del Algoritmo
El algoritmo de tres fases con ordenacion de nodos propuesto por Cheng et. al. [3]
toma como entrada un conjunto de datos D y una ordenacion de nodos completa. El
proceso de construccion esta basado en el analisis de dependencias usando teorıa de la
informacion. Como salida, el algoritmo proporciona la estructura de la red Bayesiana.
El algoritmo supone las siguientes condiciones:
Las variables aleatorias son discretas.
El conjunto de datos D es completo, es decir, no existen valores faltantes.
Los registros ocurren independientemente dado un modelo probabilıstico funda-
mental de los datos.
El conjunto de datos D es lo suficientemente grande para usar pruebas de inde-
pendencia condicional que arrojen valores confiables.
A continuacion se definen ciertos terminos utilizados por el algoritmo y posterior-
mente se explicara en detalle cada una de las fases de dicho algoritmo.
Definicion 3.1 Nodos activos
Un nodo esta activo en una trayectoria si la configuracion del nodo es lineal o divergente
en dicha trayectoria. Ver figuras 2.6a y 2.6b.
51
Definicion 3.2 Nodos inactivos
Un nodo esta inactivo en una trayectoria si la configuracion del nodo es convergente en
dicha trayectoria. Ver figura 2.6c.
Definicion 3.3 Trayectoria abierta
Una trayectoria abierta es aquella en donde todos los nodos de dicha trayectoria estan
activos.
Definicion 3.4 Trayectoria cerrada
Una trayectoria cerrada es aquella en donde al menos uno de los nodos de dicha trayec-
toria no esta activo.
Fase 1: Construccion Preliminar de la Estructura
PhaseI (D, ε)
V = X1 ≺ . . . ≺ Xn; E = = L = ; G = (V,E)
for each Xi = X1 to Xn
for each Xj = Xi+1 to Xn
if IM (Xi, Xj) > ε then
L ← add(Xi → Xj)
end if
end for
end for
sort(L, ↓)
for each (Xi, Xj) ∈ L
if not connected(Xi, Xj) then
E ← add(Xi → Xj)
L ← remove(Xi → Xj)
end if
end for
return (G, L)
Tabla 3.8: Implementacion de la Fase I del algoritmo de tres fases.
1. Iniciar con un grafo G = (V , E), donde V = X1, . . . , Xn y E = L = .
2. Para cada par de nodos (Xi, Xj) donde (Xi→Xj) ∈ V y Xi 6= Xj, calcular la
informacion mutua I(Xi, Xj) usando la ecuacion 3.15 e insertar en L aquellos
pares cuya informacion mutua sea mayor de un cierto umbral ε=0.01. Ordenar
los pares (Xi, Xj) en L de mayor a menor valor de informacion mutua.
52
3. Tomar el primer par de nodos que no haya sido analizado previamente (Xi, Xj)
de la lista L. Si no existe una trayectoria abierta entre Xi y Xj, agregar el arco
correspondiente a E y eliminar de L a (Xi, Xj).
4. Regresar al paso anterior a menos que ya hayamos examinado todos los pares de
nodos en L.
El pseudo-codigo de esta fase se muestra en la tabla 3.8. El proposito de esta fase
es encontrar un bosquejo lo mas aproximado posible a la estructura correcta de la red
Bayesiana. En esta fase solo se realizan calculos de informacion mutua entre pares de
nodos, no hay pruebas de independencia condicional involucradas. El razonamiento al
efectuar esta prueba es que si el valor de informacion mutua entre pares de variables es
grande, ello indicarıa muy probablemente una conexion directa entre dichas variables.
Esto fue demostrado por Chow y Liu [6] para arboles.
Fase 2: Engrosamiento de la Estructura
1. Tomar el primer par de nodos que no se haya analizado previamente en esta fase
(Xi, Xj) de L. Encontrar un conjunto de corte que pueda d-separar a dichos nodos
en G. Mediante una prueba de CI, determinar si los nodos son condicionalmente
independientes dado el conjunto de corte. Si la respuesta es afirmativa, ir al
paso 2 de esta fase; de lo contrario, conectar el par de nodos agregando el arco
correspondiente en E.
PhaseII (D,G, L, ε)
for each (Xi, Xj) ∈ L
C ← findCutSet(G, Xi, Xj)
if IM (Xi, Xj|C) > ε
E ← add(Xi → Xj)
end if
end for
return (G)
Tabla 3.9: Implementacion de la Fase II del algoritmo de tres fases.
2. Regresar al paso anterior y tomar el siguiente par de nodos, a menos que ya se
haya analizado toda la lista L.
En esta fase, el algoritmo examina todos aquellos pares de nodos que quedaron
en L despues de la fase 1 con la intencion de encontrar conjuntos de corte de mınima
cardinalidad. Posteriormente, realiza una prueba de CI entre dichos nodos dado el
53
conjunto de corte para determinar si se debe o no agregar el respectivo arco a la
estructura. Cabe mencionar que en esta fase es posible que algunos arcos sean agregados
erroneamente. La razon de esto es que algunos arcos reales pueden todavıa faltar hasta
el final de esta fase y ello puede evitar que se encuentre un conjunto de corte adecuado
para determinar si dos nodos son condicionalmente independientes. El pseudo-codigo
de la segunda fase y del procedimiento para encontrar conjuntos de corte entre dos
nodos se muestran en las tablas 3.9 y 3.11, respectivamente.
Fase 3: Adelgazamiento de la Estructura
1. Para cada arco (Xi→Xj) en E, si existen otras trayectorias abiertas entre estos
nodos, remover dicho arco de E temporalmente. Encontrar un conjunto de corte
que pueda d-separar a los nodos (Xi, Xj). Si los nodos son condicionalmente
independientes dado el conjunto de corte encontrado, remover el arco (Xi→Xj)
de E permanentemente; de lo contrario agregar el arco (Xi→Xj) a E nuevamente.
PhaseIII (D,G, ε)
for each Xi=X1 ∈ V to Xn
for each Xj=Xi+1 ∈ V to Xn
if (Xi → Xj) ∈ E then
remove(E, (Xi → Xj))
openPaths ← findAllOpenPaths(G, Xi, Xj)
if not openPaths = ∅ then
C = findCutSet(G, Xi, Xj)
if IMCOND(Xi, Xj|C) > ε then
insert(E, (Xi → Xj))
end if
else
insert(E, (Xi → Xj))
end if
end if
end for
end for
return (G)
Tabla 3.10: Implementacion de la Fase III del algoritmo de tres fases.
En la tercera fase, el algoritmo analiza los nodos con arcos directos entre sı que
tambien estan conectados por otras trayectorias. La tarea de esta fase es identificar los
arcos que pudieron ser agregados de manera erronea en la fase anterior. Al remover
54
el arco directo, el algoritmo busca un conjunto de corte de mınima cardinalidad que
pueda d-separar a los nodos y realiza una prueba de CI. Si el resultado de la prueba
arroja un valor de informacion mutua mayor a ε, es decir, I(Xi, Xj|C) > ε, significa
que existe una gran dependencia entre dichos nodos y por tanto el arco directo debe
restablecerse. Este procedimiento continua hasta que todos los arcos directos han sido
examinados. El pseudo-codigo de esta fase se muestra en la tabla 3.10.
findCutSet(G, Xi, Xj)
openPaths ← Encontrar todas las trayectorias abiertas entre Xi y Xj
closePaths ← Encontrar todas las trayectorias cerradas entre Xi y Xj
while openPaths 6= ∅
while |oneNode(openPaths)| 6= ∅
• Almacenar los nodos en tales trayectorias en cutSet.
• Remover de openPaths y closePaths las trayectorias bloqueadas.
• Encontrar las trayectorias que se abren en closePaths por los
nodos en cutSet y moverlas a openPaths. Acortar tales
trayectorias, removiendo los nodos que tambien estan en cutSet.
end while
if openPaths 6= ∅
• Encontrar un nodo que bloquee el maximo numero de trayectorias
e incluirlo en cutSet.
• Remover de openPaths y closePaths las trayectorias que se
bloquean por este nodo.
• Encontrar las trayectorias que se abren en closePaths por este
nodo y moverlas a openPaths. Acortar tales trayectorias,
removiendo los nodos que tambien estan en cutSet.
end if
end while
return (cutSet)
Tabla 3.11: Procedimiento de busqueda de conjuntos de corte entre pares de nodos.
3.2.3 Analisis de Complejidad
En esta seccion se expresara la complejidad del algoritmo de tres fases de Cheng
en base al numero de pruebas de independencia condicional que requiere.
Supongase que un conjunto de datos tiene n variables, que el maximo numero
posible de valores de un atributo es r, y que una variable puede tener k padres a lo
mucho. De la ecuacion 3.15 se puede saber que cada calculo de informacion mutua
requiere de O(r2) operaciones basicas (tales como logaritmo, multiplicacion, division),
55
y de la ecuacion 3.16 se puede saber que cada calculo de informacion mutua condicional
requiere de O(rk+2) operaciones basicas ya que el conjunto de corte tendra a lo mucho
k nodos. Si un nodo puede tener un numero arbitrario de padres, la complejidad de las
pruebas de informacion mutua condicional es O(rn) en el peor de los casos. Claramente,
una sola prueba de independencia condicional puede ser exponencial en el numero de
operaciones basicas. Existen otros costos computacionales en el algoritmo, por ejemplo,
ordenar los pares de nodos de acuerdo a su informacion mutua, lo cual puede realizarse
en n log n operaciones usando el algoritmo quicksort.
Ahora, debido a que la primera fase requiere del calculo de informacion mutua
entre cualquier par de nodos, se requiere de n(n−1)2
calculos de informacion mutua por
lo que su complejidad es O(n2). En la segunda fase, el algoritmo trata de verificar si
debe agregar arcos a la red. Cada decision requiere de una prueba de independencia
condicional y por tanto necesita de O(n2) pruebas de independencia condicional. En la
tercera fase, el algoritmo trata de remover arcos que pudieron ser agregados erronea-
mente en las dos fases anteriores. De nuevo, cada decision requiere de una prueba
de independencia condicional y O(n2) pruebas de independencia condicional son nece-
sarias. Por tanto, la complejidad del algoritmo de tres fases de Cheng requiere de O(n2)
pruebas de independencia condicional [3].
3.3 El Algoritmo de Inferencia
Una suposicion comun hecha por los algoritmos de aprendizaje automatico de la
estructura de redes Bayesiana, es que el conjunto de datos D es completo. La razon
principal de esta suposicion es que dada la existencia de datos incompletos, el apren-
dizaje Bayesiano exacto es intratable, es decir, su complejidad es exponencial conforme
la cantidad de valores faltantes aumenta [9]. Desafortunadamente, la mayorıa de los
conjuntos de datos rara vez son completos.
En esta seccion se presenta un algoritmo que recibe un conjunto de datos in-
completo y mediante conteo de frecuencias infiere los datos faltantes. Este algoritmo
corresponde a la primera etapa del algoritmo EM [10]. Se comenzara por recordar que
en la seccion 2.3 se definio de manera formal a una red Bayesiana y se establecio a X =
X1, . . . , Xn como el conjunto de variables aleatorias que en la red son representadas
por nodos con arcos reflejando las relaciones de dependencia entre dichas variables.
En la seccion 2.6.2 se especifico que dicha estructura se puede aprender de acuerdo a
un conjunto de datos D = X1, . . . , Xm. El algoritmo que se implementa, consiste en
realizar un proceso de inferencia sobre el conjunto de datos DINC (conjunto de datos
incompletos), e instanciar los valores faltantes de cada registro de acuerdo a la frecuen-
cia de ocurrencia de los valores completos del registro, dada cierta instanciacion de los
valores faltantes.
56
inf (DCOM, DINC)for each record i ∈ DINC
xk ← Valores de las variables completas en DINC[i]Φ ← Variables con valores faltantes de DINC[i]Inicializar → statesCnt, statesAcmfor each j ∈ (combinacion de estados en Φ)
for each record r ∈ DCOM
if (xk ∪ state(Φ, j) = DCOM[r])statesCnt [j] ← statesCnt [j] + 1
end ifend for
end forsel ← random(1, size(DINC))for each j ∈ (combinacion de estados en Φ)
statesAcm ← statesAcm + statesCnt [j]if (statesAcm > sel)
stateSel ← j; breakend if
end forD ← add(xk ∪ state(Φ, stateSel))
end forreturn (DCOM ∪ D)
Tabla 3.12: Algoritmo de inferencia para conjuntos incompleto de datos.
El objetivo del algoritmo de inferencia es completar el conjunto de datos incom-
pletos DINC, de manera que el conjunto de datos resultante D pueda ser usado por
cualquier algoritmo de construccion de redes Bayesianas a partir de datos completos.
Solo se consideran variables aleatorias discretas y se denota con ri el numero posible de
valores que puede tomar la variable Xi, ası como xk = x1k, . . . , xnk denota el vector
de un registro conteniendo las instancias de las variables aleatorias Xi que no contienen
valores faltantes y Φ = X1, . . . , Xn el vector de un registro de las variables que si
presentan datos incompletos. Este vector Φ contiene los nombres de las variables aleato-
rias y no alguna instancia de estas. Los pasos que sigue este algoritmo de inferencia o
pre-procesamiento como tambien lo hemos llamado se muestran a continuacion:
1. Para cada registro del conjunto de datos DINC hacer lo siguiente:
2. Obtener los vectores xk y Φ.
3. Para cada posible estado de las variables en el vector Φ, contar la frecuencia de
ocurrencia de dicha combinacion de valores en conjunto con los valores en xk sobre
57
los registros completos del conjunto de datos DCOM y guardar dicho conteo.
4. Seleccionar aleatoriamente (de acuerdo a la frecuencia de ocurrencia) uno de los
estados posibles de las variables con valores faltantes Φ y en conjunto con xk
agregar dicha combinacion a D.
5. Regresar al paso 2 para el siguiente registro con datos incompletos, de lo contrario
terminar.
La tabla 3.12 muestra el pseudo-codigo de los pasos anteriormente descritos.
Basicamente, este algoritmo recibe un conjunto de datos particionado en datos com-
pletos DCOM y datos incompletos DINC. Para cada registro del conjunto de datos
incompletos, el algoritmo obtiene el vector Φ con los nombres de las variables con datos
faltantes en dicho registro, ası como el conjunto de valores de las variables de dicho
registro que si contienen valores instanciados, xk. Para cada combinacion posible de
valores de las variables en Φ en conjunto con los valores instanciados en xk, el algo-
ritmo busca dentro de los registros de datos completos la cantidad de veces que esta
instanciacion completa se presenta. Una vez realizado lo anterior, se escoge de manera
aleatoria una de las combinaciones posibles de Φ. Esta seleccion aleatoria se realiza de
acuerdo a la proporcion de conteos encontrados en la busqueda de dicha combinacion de
valores en los datos completos. Posteriormente, dicha combinacion se agrega al conjun-
to de datos D. Al final, el algoritmo regresa la union de D que anteriormente era DINC
pero ahora sus valores han sido instanciados, y DCOM, el conjunto de datos completos
que se recibio.
3.3.1 Analisis de Complejidad
En esta seccion se analiza la complejidad del algoritmo de inferencia de conjuntos
de datos incompletos inf que se muestra en la tabla 3.12.
Se comenzara por mencionar que este algoritmo se implemento teniendo en cuen-
ta que dentro del conjunto de datos de entrada, no mas de la mitad de los registros
contienen datos incompletos. Ası mismo, se considero que existe un valor s que de-
fine una cantidad maxima de variables con datos incompletos para todos los registros.
Ahora, considerese a m1 como la cantidad de registros completos y m2 la cantidad
de registros incompletos que se encuentran contenidos en el conjunto de datos y por
tanto m = m1 + m2. Sin embargo, el peor caso para este algoritmo se presenta cuando
m1 = m2, por lo que entonces se puede decir que m1 = m2 = m2
bajo dicha situacion.
Para instanciar cada valor faltante de cada registro del conjunto de datos incom-
pleto, el algoritmo selecciona aleatoriamente entre las varias combinaciones de valores
posibles que pueden tomar las variables con valores faltantes. Dicha seleccion aun cuan-
do es aleatoria, esta sesgada para favorecer a aquellas combinaciones que con mayor
58
frecuencia se presentan en los registros de datos completos. Por tanto, si asumimos que
el numero de valores diferentes que cada variable aleatoria puede tomar esta dado por
r, se requiere de rs(m2+2m4
) operaciones para instanciar todos los valores faltantes en
el conjunto de datos incompleto. En consecuencia, la complejidad del algoritmo de la
figura 3.12 es O(rsm2).
3.4 Enfoques similares a SABS
En esta seccion se presenta una descripcion sobre dos trabajos de la literatura del
aprendizaje de la estructura de redes Bayesianas que tienen particular similitud con la
presente investigacion. Mencionaremos tales similitudes, ası como sus diferencias.
Friedman et. al. [14] presentan un algoritmo que denominan “Sparse Candidate”.
Este algoritmo inicia buscando relaciones de dependencia fuertes entre pares de va-
riables. La fuerza de la dependencia puede ser medida mediante informacion mutua o
correlacion, lo cual se argumenta y coincidimos en esta investigacion, no es una idea
nueva. Por ejemplo, el algoritmo de Chow y Liu [6] usa informacion mutua para cons-
truir estructuras de red de tipo arbol que maximizan la probabilidad de esta. Para
Friedman et. al. [14] sin embargo, este enfoque no es suficiente ya que no son tomadas
en cuenta interacciones complejas entre las variables. Basados en este argumento, sugie-
ren que para cada variable Xi, se busque un conjunto de variables Y1, . . . , Yk que sean
los padres candidatos mas prometedores para la variable Xi, y entonces restringir la
busqueda a redes en las cuales solo esas variables pueden ser padres de Xi. El enfoque
referido se conoce como divergencia de Kullback-Liebler [23], y es una definicion alterna
de informacion mutua en donde el valor de esta, entre un par de variables X y Y , es
la distancia entre la distribucion P (X,Y ) y la distribucion P (X)P (Y ), la cual asume
que X y Y son independientes.
Por otra parte, Heckerman [18] presenta un trabajo en donde se describe un en-
foque Bayesiano para el aprendizaje de redes Bayesianas mediante la combinacion de
conocimiento previo y datos estadısticos. Su enfoque es derivado de un conjunto de
suposiciones presentadas en [8], ası como la suposicion de probabilidad equivalente, que
establece que los datos no deben ayudar en discriminar estructuras de red que repre-
sentan la misma asercion de independencia condicional. De acuerdo a las suposiciones
anteriores, y a la medida de evaluacion propuesta en [8], Heckerman [18] introduce una
nueva medida de evaluacion de redes Bayesianas candidatas a la cual llama BDe. Pos-
teriormente, en este trabajo se identifican y describen varios metodos polinomiales y
heurısticos de busqueda de la estructura de redes Bayesianas como son busqueda local,
busqueda iterativa y recocido simulado y por ultimo se realizan experimentos en donde
se evalua la eficiencia y el comportamiento de la medida Bayesiana propuesta en [8] y
la medida BDe para los algoritmos de busquedas antes mencionados.
59
En el presente trabajo de investigacion se ha hecho uso tambien del concepto
de informacion mutua, sin embargo, aquı se ha usado este concepto para crear una
distribucion de informacion mutua acumulada que nos permita guiar la busqueda al
momento de aplicar el algoritmo de recocido simulado. Esta distribucion es creada para
cada variable con respecto a los demas posibles padres con lo cual se provee una ventana
mas amplia de seleccion a aquellas variables que tiene mayor informacion mutua entre
si. Esto permite que los nodos de las nuevas estructuras que se generan al explorar
el espacio de busqueda, contengan mayormente como padres, a aquellos nodos con los
cuales la relacion de dependencia es mas fuerte.
En cuanto al metodo de exploracion del espacio de soluciones y evaluacion de
nuevas estructuras, en esta investigacion hacemos uso del algoritmo de recocido simula-
do y el criterio Bayesiano. Inicialmente, como se menciono con anterioridad, se genera
una distribucion de informacion mutua acumulada entre pares de variables. Esta dis-
tribucion es utilizada por el algoritmo de recocido simulado para guiar la busqueda
y generar nuevas estructuras, las cuales son evaluadas mediante el criterio Bayesiano.
Esta medida de evaluacion resulta particularmente util ya que debido a las suposiciones
en las que se basa (consultar referencia [8]), permite evaluar de manera separada a cada
nodo y por tanto evitar tiempo de computo para pequenos cambios en la red. Otras
consideraciones como proveer una ordenacion de nodos y restriccion del numero del
numero de padres para cada nodo son tomadas en cuenta en la presente investigacion.
Finalmente, una etapa de eliminacion de arcos es realizada despues del algoritmo de
recocido simulado con la intencion de remover enlaces redundantes.
Muchos trabajos en el campo de aprendizaje de la estructura de redes Bayesianas
utilizan conceptos y tecnicas que han sido propuestos o utilizados por otros autores,
sin embargo, el uso que se hace de ellos y la combinacion con otras tecnicas, permiten
que cada trabajo se convierta en una aportacion a este campo de estudio.
3.5 Resumen
En este capıtulo se han presentados dos algoritmos que aprenden la estructura de
una red Bayesiana. El primero de ellos, SABS, es una contribucion de esta investigacion.
El segundo, el algoritmo de tres fases, es un algoritmo de la literatura que sera utilizado
para realizar comparaciones de resultados en los capıtulos 4 y 5.
En la seccion 3.1 se presento el algoritmo SABS el cual busca aprender la estructura
de una red Bayesiana a partir de un conjunto de datos completos. SABS pertenece
al enfoque de busqueda y evaluacion y utiliza el algoritmo de recocido simulado como
metodo de busqueda y optimizacion y el criterio Bayesiano como medida de evaluacion
la cual trata de maximizar. Como ultima fase del algoritmo SABS se efectua una fase
de eliminacion de arcos redundantes aplicando pruebas de independencia condicional.
60
La complejidad de este algoritmo no puede ser determinada debido a su naturaleza
estocastica.
En la seccion 3.2 se presenta el algoritmo de tres fases perteneciente al enfoque
de analisis de dependencias. Este algoritmo se explico a detalle y la importancia de
su presentacion se debe a que sera utilizado en los capıtulos 4 y 5 para comparar los
resultados de las estructuras de redes Bayesianas aprendidas por este y por el algoritmo
SABS. La complejidad de este algoritmo es O(n2).
Finalmente, en la seccion 3.3 se presento un algoritmo que infiere los valores fal-
tantes en conjuntos de datos incompletos tomando en cuenta para cada registro todos
los atributos con valores instanciados. Este algoritmo corresponde a la etapa Expecta-
tion del algoritmo EM [10]. La complejidad de este algoritmo es O(rsm2).
61
62
Capıtulo 4
Metodologıa y Diseno de Experimentos
En este capıtulo se presenta la metodologıa que se siguio para realizar el analisis
del desempeno de los algoritmos presentados en esta investigacion. Esta metodologıa
incluye la explicacion detallada de los problemas de prueba que fueron seleccionados
de la literatura, ası como la forma en que se generaron conjuntos de datos de prueba
para cada uno de estos problemas. Finalmente, se establecen los experimentos que se
plantearon para la obtencion de resultados por parte de cada uno de los algoritmos
presentados en esta investigacion y las medidas que nos permitieron conocer cual fue
el desempeno de cada uno de estos.
4.1 Metodologıa General
En esta investigacion se presenta un algoritmo que aprende la estructura de una
red Bayesiana a partir de un conjunto de datos completos, y se implementa la primera
etapa del algoritmo EM [10] que toma como entrada un conjunto de datos incompletos y
a partir de estos realiza un proceso de inferencia para proporcionar a cualquier algoritmo
de aprendizaje de redes Bayesianas, el conjunto de datos completos que necesita para
su funcionamiento.
El objetivo principal al proponer un algoritmo que aprende la estructura de una
red Bayesiana es evitar el largo y tedioso proceso que se requiere al realizar esto de
forma manual. Claramente, lo deseable es que la red Bayesiana construida por cualquier
algoritmo modele el proceso en cuestion lo mas apegado a la distribucion probabilıstica
fundamental de los datos que se utilizan. Sin embargo, se debe tener en cuenta que
cuando modelamos un proceso, no se conoce la estructura de la red Bayesiana ya que
esto es lo que se desea construir. Por lo tanto, una de las formas mas comunes utilizada
por los investigadores del campo de aprendizaje estructural de redes Bayesianas es
utilizar modelos y conjuntos de prueba estandar. Estos modelos nos permiten comparar
nuestros resultados con los de estos conjuntos y determinar la eficacia de lo metodos
que se proponen. La metodologıa seguida en esta investigacion fue la siguiente:
1. Analisis de los algoritmos de aprendizaje de la estructura de redes Bayesianas :
63
Se encontro que dentro del aprendizaje de redes Bayesianas existen dos enfoques
claramente marcados. El primero se conoce como busqueda y evaluacion y consiste
en utilizar metodos de busqueda heurıstica para explorar el espacio de soluciones
de estructuras de redes Bayesianas y evaluarlas de acuerdo a cierta metrica. Al
final, se selecciona aquella estructura de red que mejor evaluacion presenta. El
segundo enfoque conocido como analisis de dependencias busca construir la es-
tructura de la red Bayesiana realizando pruebas de independencia e independencia
condicional entre pares de nodos (ver seccion 2.6 para la explicacion detallada de
ambos enfoques).
2. Algoritmo de aprendizaje propuesto y algoritmo seleccionado de la literatura: En
esta investigacion se propuso un algoritmo que busca aprender la estructura de
una red Bayesiana y esta basado en el enfoque de busqueda y evaluacion. Este algo-
ritmo se denomino SABS y utiliza como metodo de busqueda y optimizacion el al-
goritmo de recocido simulado, y como medida de evaluacion el criterio Bayesiano.
SABS busca explorar el espacio de posibles soluciones de manera aleatoria anali-
zando nodo por nodo y maximizando el criterio Bayesiano de cada uno de estos,
lo que a su vez maximiza el criterio Bayesiano de toda la red. El algoritmo se-
leccionado de la literatura para propositos de comparacion de resultados fue el
algoritmo de tres fases de Cheng el cual esta basado en el enfoque de analisis
de dependencias. Este algoritmo requiere de una ordenacion de nodos y como su
nombre lo indica consta de 3 fases mediante las cuales busca aprender la estruc-
tura de las redes Bayesianas.
3. Manejo de conjuntos de datos incompletos : Tanto el algoritmo propuesto como
el algoritmo seleccionado de la literatura solo contemplan el manejo de conjuntos
de datos completos. Se implemento desarrollo la primera etapa del algoritmo EM
que recibe de entrada un conjunto de datos incompleto y mediante inferencia
en base a conteos de frecuencia, completa el conjunto de datos. Este algoritmo
puede complementar a cualquiera de los dos anteriores algoritmos ejecutandose
como fase de pre-procesamiento cuando el conjunto de datos es incompleto.
4. Implementacion de los algoritmos : El algoritmo SABS y el algoritmo de inferen-
cia de datos incompletos fueron programados utilizando el lenguaje computa-
cional Java. El programa computacional Power Constructor desarrollado por
Cheng implementa su algoritmo de tres fases, sin embargo, el codigo fuente no
esta disponible por lo que tuvo que ser igualmente programado utilizando el
lenguaje Java.
5. Generacion de conjuntos de datos incompletos : Se desarrollo e implemento en
Java un generador de conjuntos de datos incompletos. Este generador toma como
64
entrada un conjunto de datos completo y selecciona aleatoriamente registros de
dicho conjunto a los cuales se les instancian valores desconocidos. El porcentaje
de datos incompletos es variable y los atributos seleccionados varıan tambien
aleatoriamente entre 1 y 4.
6. Problemas de prueba: Se busco dentro de la literatura de aprendizaje de redes
Bayesianas, conjuntos de prueba estandar para la comparacion de los resultados
obtenidos por los algoritmos implementados en esta esta investigacion. Se en-
contraron varios conjuntos, pero entre ellos se selecciono la red ASIA y la red
ALARM. La red ASIA es una red Bayesiana ficticia de 8 nodos y 8 arcos, y la
red ALARM es un ejemplo del mundo real que consta de 37 nodos y 46 arcos. En
las secciones 4.2.1 y 4.2.2 se explican a detalle cada uno de estos conjuntos.
7. Experimentacion: Se plantearon varios experimentos para cada uno de los algo-
ritmos implementados en este trabajo de investigacion. Estos experimentos con-
sistieron en la construccion de la estructura de la red Bayesiana a partir tanto de
conjuntos de datos completos como incompletos, usando el algoritmo SABS, el al-
goritmo de tres fases y el algoritmo de inferencia. Se utilizaron varios tamanos de
los conjunto de datos, ası como varios tamanos de cantidad de datos incompletos.
8. Finalmente se presenta el analisis de los resultados obtenidos tanto por algoritmo
de aprendizaje de la estructura de redes Bayesianas propuesto en esta investi-
gacion, como por el algoritmo de tres fases de Cheng para conjuntos de datos
completos e incompletos. Este analisis contemplo la cantidad de arcos correc-
tos, arcos faltantes y arcos erroneos que cada uno de los algoritmos encuentra.
Adicionalmente, para el caso de conjuntos de datos incompletos que fueron gener-
ados a partir de conjuntos de datos completos removiendo aleatoriamente valores
en algunos atributos seleccionados tambien de manera aleatoria, se compararon
los porcentajes de valores obtenidos por el algoritmo de inferencia para dichos
atributos contra los porcentajes de valores existentes en los conjuntos de datos
completos.
4.2 Problemas de Prueba
Dentro de la literatura existen varios conjuntos comunmente usados por los in-
vestigadores, sin embargo, entre ellos la red ASIA y la red ALARM son de las mas
utilizadas. Dentro de nuestra investigacion usamos estas redes para las cuales su estruc-
tura es conocida con la intencion de comparar los resultados obtenidos por el algoritmo
propuesto.
65
4.2.1 La Red Bayesiana ASIA
La red ASIA (tambien conocida como Chest Clinic) propuesta por Lauritzen y
Spiegelhalter [25] es una pequena red Bayesiana que calcula la probabilidad de que
un paciente padezca tuberculosis, cancer de pulmon o bronquitis, basado en diferentes
factores (e.g. si el paciente ha viajado recientemente al continente Asiatico o no).
La red Bayesiana ASIA es una red que consta de 8 nodos y 8 arcos. De manera
breve, la problematica planteada en este modelo contempla que la falta de aliento
tambien conocida como disnea o dyspnoea puede deberse a factores como tuberculosis,
cancer de pulmon, bronquitis, combinacion de algunos de estos factores o ninguno
de ellos. Haber visitado recientemente el continente asiatico incrementa el riesgo de
tuberculosis, mientras que fumar es sabido provoca cancer de pulmon o bronquitis. Los
resultados de una prueba de rayos X del torax del paciente no discriminan entre cancer
de pulmon y tuberculosis, como tampoco la presencia o ausencia de disnea. La figura
4.1 muestra una grafica conteniendo la estructura de esta red.
Figura 4.1: Estructura de la red Bayesiana ASIA.
En la tabla 4.1 se muestra los nodos que componen la estructura de la red ASIA.
Entre menor es el numero del nodo, mayor es la precedencia que este tiene. Esto es
importante ya que tanto el algoritmo SABS como el algoritmo de tres fases requieren de
una ordenacion de nodos. Esto quiere decir que el nodo 0 puede ser padre de cualquiera
de los 7 nodos restantes, pero de estos, ninguno puede ser padre del nodo 0. La misma
situacion se presente con el nodo 1 y los nodos del 2 al 7, y ası sucesivamente para el
resto de ellos.
66
Nodo Nombre Descripcion Valores
0 Visit to Asia? ¿Visito Asia recientemente? Si, No
1 Smoking? ¿Fuma? Si, No
2 Tuberculosis ¿Padece Tuberculosis? Si, No
3 Lung Cancer ¿Padece Cancer de pulmon? Si, No
4 Bonchitis ¿Padece Bronquitis? Si, No
5 Tuberculosis or Cancer ¿Padece Tuberculosis o Cancer? Si, No
6 XRay Result Resultado de rayos X Pos., Neg.
7 Dyspnoea ¿Padece Dyspnoea? Si, No
Tabla 4.1: Atributos que conforman la estructura de la red Bayesiana ASIA.
4.2.2 La red Bayesiana ALARM
La red ALARM (A Logical Alarm Reduction Mechanism) propuesta por Beinlich
et. al. [2] es la red Bayesiana de mas amplio uso en el area de aprendizaje estructural de
redes Bayesianas. Esta red es un ejemplo de una aplicacion de las redes Bayesianas en el
mundo real y muchos investigadores la usan para evaluar sus algoritmos de aprendizaje.
Esta red es un sistema de diagnostico medico para monitoreo de pacientes en la sala de
operaciones que consta de 8 nodos de diagnostico, 16 de descubrimiento y 13 variables
intermedias para un total de 37.
La figura 4.2 muestra la estructura de la red Bayesiana ALARM. La tabla 4.2
enumera los diversos atributos que la componen, ası como los diferentes valores que
cada uno de ellos puede tomar. Por limitaciones de espacio solo se muestra en la tabla
la primera letra de cada valor, pero sus significado son los siguientes: T=True, F=False,
L=Low, N=Normal, H=High, E=Esophageal, O=OneSided, Z=Zero.
67
Fig
ura
4.2
:E
structu
rade
lared
Bay
esiana
ALA
RM
.68
Nodo Nombre Descripcion Valores
0 ErrCauter Error in HR reading due to elect. device T,F
1 ErrLowOutput Error in HR reading due to low cardiac output T,F
2 Disconnect Disconnected ventilation tube T,F
3 KinkedTube Kinked ventilation tube T,F
4 Intubation Intubation status N,E,O
5 PulmEmbolus Pulmonary embolus T,F
6 Shunt Shunt N,H
7 InsuffAnesth Insufficient anesthsia or analgesia T,F
8 Anaphylaxis Anaphylaxis T,F
9 LVFailure Left-ventricular failure T,F
10 Hypovolemia Hypovolemia T,F
11 StrokeVolume Stroke volume L,N,H
12 LVEDVolume Left ventricular end diastolic volume L,N,H
13 MinVolSet Minute volume calculated L,N,H
14 VentMach Minute ventilation measure at the ventilator Z,L,N,H
15 VentTube Ventilation measured at endotracheal tube Z,L,N,H
16 VentLung Pulmonary ventilation Z,L,N,H
17 VentAlv Alveolar ventilation Z,L,N,H
18 ArtCO2 Arterial carbon dioxide content L,N,H
19 MinVol Minute volume measured Z,L,N,H
20 ExpCO2 Carbon-dioxide content of expired gas Z,L,N,H
21 Press Ventilation pressure Z,L,N,H
22 FiO2 Fraction of oxygen in inspired gas L,N
23 PVSat Pulmonary-artery oxygen saturation L,N,H
24 SaO2 Arterial-blood oxygen saturation L,N,H
25 PAP Pulmonary artery pressure L,N,H
26 TPR Total peripheral resistance L,N,H
27 Catechol Catecholamine level N,H
28 HR True heart rate L,N,H
29 HRSat Heart rate obtained from oxymeter L,N,H
30 HREKG Heart rate obtained from electrocardiogram L,N,H
31 HRBP Heart rate obtained from blood pressure monitor L,N,H
32 CO Cardiac output L,N,H
33 BP Blood pressure L,N,H
34 History History of left ventricular failure T,F
35 PCWP Pulmonary capillary wedge pressure L,N,H
36 CVP Central venous pressure L,N,H
Tabla 4.2: Atributos que conforman la estructura de la red Bayesiana ALARM.
69
4.3 Generacion de Conjuntos de Datos de Prueba
Los conjuntos de datos completos tanto para la red ASIA como para la red
ALARM constan de 10,000 casos respectivamente, y fueron tomados del trabajo rea-
lizado por Cheng et. al. [3]. Estos datos fueron generados usando una tecnica Monte
Carlo llamada muestreo logico probabilıstico propuesta por Henrion [19].
4.3.1 Algoritmo de Generacion de Conjuntos Incompletos
Los conjuntos de datos incompletos fueron generados a partir de los conjuntos de
datos completos mencionados anteriormente. El algoritmo de generacion de conjuntos
de datos incompletos se muestra en la tabla 4.3.
CasosInc(D, percent,maxnodes, n)
DINC ← D,m ← |D|
r ← m ∗ percent
for each i = 1 to r
row ← ⌊random ∗ m⌋ + 1
nodes ← ⌊random ∗ maxnodes⌋ + 1
for each j = 1 to nodes
node ← ⌊random ∗ n⌋ + 1
assign(DINC [row][node], ‘?’)
end for
end for
return D
Tabla 4.3: Algoritmo para la generacion de conjuntos de datos incompletos.
El algoritmo de la tabla 4.3 toma como entrada el conjunto de datos completos D,
el porcentaje de datos incompletos que se desea generar percent, el numero maximo de
nodos por registro a los cuales se les va a remover su valor actual maxnodes, y el numero
de variables del conjunto de datos n. Posteriormente, el algoritmo selecciona un registro
del conjunto de datos de manera aleatoria y tambien de manera aleatoria selecciona
el numero de variables a las cuales removera su valor. Este numero de variables oscila
entre uno y cuatro, es decir, para cada registro se modifican al menos una variable
pero no mas de cuatro. Todo este proceso se repite para la cantidad de registros que
representa el porcentaje de datos seleccionado.
Finalmente, el algoritmo regresa el conjunto de datos incompleto. Dentro de este
conjunto, los valores desconocidos se identifican con un signo ‘?’. Este signo es reconoci-
do por el algoritmo de inferencia lo que indica que el valor verdadero debe ser estimado
en base a conteos de frecuencia cuando dicho algoritmo es ejecutado.
70
Nodos/Atributos
Registro 0/A 1/S 2/T 3/L 4/B 5/E 6/X 7/D
r1 2 2 2 2 2 2 1 2
r2 2 2 2 2 3 2 2 3
r3 1 2 3 2 2 3 3 2
r4 2 2 2 2 2 2 2 3
r5 2 3 2 2 3 2 2 2
r6 2 2 2 2 1 2 2 2
r7 2 3 2 2 3 2 2 3
r8 2 3 2 2 3 2 2 3
Tabla 4.4: Ejemplo de un conjunto de datos completo para la red Bayesiana ASIA.
Nodos/Atributos
Registro 0/A 1/S 2/T 3/L 4/B 5/E 6/X 7/D
r1 2 2 2 2 2 2 1 2
r2 2 2 2 2 3 2 2 3
r3 1 ? 3 2 ? 3 ? 2
r4 2 2 2 2 2 2 2 3
r5 ? 3 ? ? 3 ? 2 2
r6 2 2 2 2 1 2 2 2
r7 2 3 2 2 3 2 2 3
r8 2 3 2 2 3 2 2 3
Tabla 4.5: Ejemplo de un conjunto de datos incompleto para la red Bayesiana ASIA.
Las tablas 4.4 y 4.5 muestran un ejemplo de un conjunto de datos completo para la
red Bayesiana ASIA y el conjunto de datos incompleto generado mediante el algoritmo
CasosInc respectivamente. Se puede apreciar que el porcentaje de casos incompletos
en este conjunto es de 25 % ya que los registros r3 y r5 muestran algunos atributos con
valores desconocidos instanciados.
4.3.2 Analisis de complejidad
En esta seccion se analiza la complejidad del algoritmo que se muestra en la
tabla 4.3. Como ya se explico anteriormente, este algoritmo genera conjuntos de datos
incompletos a partir de un conjunto de entrada completo.
Primeramente, r esta determinado por el valor resultante de la multiplicacion
(m∗percent). En m esta contenida la cantidad de casos en el conjunto de datos completo
71
y percent contiene el porcentaje de casos que se desean con valores faltantes para
algunas variables y que puede oscilar entre 0 y 1. El peor caso para el algoritmo esta dado
cuando el valor de percent es 1, por lo que entonces el valor de r = m. El numero
maximo de nodos a los cuales se les puede instanciar un valor desconocido para cada
registro del conjunto de datos es maxnodes. Esta variable puede oscilar entre 1 y n, la
cantidad de variables en el conjunto de datos. Por lo anterior, se puede establecer que
la complejidad del algoritmo CasosInc estrictamente hablando es O(mn).
Sin embargo y como se hara constar posteriormente, durante nuestra experi-
mentacion fijamos el valor de maxnodes en 4 y un maximo de 0.5 para la variable
percent, por lo que la complejidad del algoritmo se establece como O(2m) para los
experimentos realizados.
4.4 Experimentos
Dentro de la presente investigacion se plantearon varios experimentos con la inten-
cion de determinar la eficiencia de los algoritmos implementados. Estos experimentos
basicamente se dividieron de acuerdo a los conjuntos de datos que se utilizaron, es de-
cir, conjuntos completos e incompletos. Recuerdese que el algoritmo SABS aprende la
estructura de una red Bayesiana a partir de conjuntos de datos completos, y el algorit-
mo de inferencia completa un conjunto con valores faltantes de manera que pueda ser
usado por cualquier otro algoritmo de aprendizaje de redes Bayesianas. Los resultados
de cada uno de los experimentos se presentan en forma resumida en las secciones 5.1.1
y 5.1.2 y el detalle de estos puede ser apreciado en el apendice A.
Debemos mencionar que para todos los experimentos que involucran pruebas de
independencia condicional se utilizo un umbral de ε=0.01, es decir, todo resultado cuyo
valor sea menor a este umbral es interpretado como independencia condicional entre los
nodos evaluados dado el conjunto de corte utilizado. Otro parametro que permanecio fijo
durante la ejecucion de los algoritmos es el numero maximo de padres que cada nodo
puede tener. Este valor se fijo en maxparents=4. Los parametros con los cuales se
sintonizo el algoritmo de recocido simulado que es parte del algoritmo SABS se muestran
en la tabla 3.4, sin embargo, se fijo un numero maximo de evaluaciones por nodo de
acuerdo a la ecuacion 3.14 determinada experimentalmente. Para los nodos desde 1 a
maxparent, el algoritmo de aprendizaje SABS realiza una busqueda exhaustiva para
determinar su conjunto de padres.
Todos los experimentos se realizaron en una computadora con sistema operativo
Windows XP de 1.4Ghz de velocidad y con 128 Mbytes de RAM. Los conjuntos de
datos fueron almacenados en una base de datos de MsAccess.
72
4.4.1 Experimentos con Conjuntos de Datos Completos
En esta seccion se describen los experimentos que se realizaron utilizando conjun-
tos de datos completos exclusivamente.
Se realizaron 10 experimentos con diversos conjuntos de datos. Dichos conjuntos
consistieron de 1k, 3k y 5k casos seleccionados aleatoriamente de un conjunto de 10k,
ademas del conjunto completo de 10k casos. Los experimentos plantearon los problemas
de aprender las estructura de las redes Bayesianas ASIA y ALARM presentadas en la
seccion 4.2 de este capıtulo. Se utilizaron tanto el algoritmo SABS propuesto, como
el algoritmo de tres fases. Posteriormente se compararon los resultados obtenidos por
cada uno de estos, los cuales son presentados en el capıtulo 5. Los experimentos fueron
los siguientes:
Experimento 1: Se realizaron 10 ejecuciones independientes del algoritmo SABS
con un conjunto de 1k casos de la red ASIA.
Experimento 2: Se realizaron 10 ejecuciones independientes del algoritmo SABS
con un conjunto de 3k casos de la red ASIA.
Experimento 3: Se realizaron 10 ejecuciones independientes del algoritmo SABS
con un conjunto de 5k casos de la red ASIA.
Experimento 4: Se realizaron 10 ejecuciones independientes del algoritmo SABS
con un conjunto de 10k casos de la red ASIA.
Experimento 5: Se realizaron 10 ejecuciones independientes del algoritmo de
tres fases con un conjunto de 5k casos de la red ASIA y una ejecucion del mismo
algoritmo para el conjunto de 10k de la misma red.
Experimento 6: Se realizaron 10 ejecuciones independientes del algoritmo SABS
con un conjunto de 1k casos de la red ALARM.
Experimento 7: Se realizaron 10 ejecuciones independientes del algoritmo SABS
con un conjunto de 3k casos de la red ALARM.
Experimento 8: Se realizaron 10 ejecuciones independientes del algoritmo SABS
con un conjunto de 5k casos de la red ALARM.
Experimento 9: Se realizaron 10 ejecuciones independientes del algoritmo SABS
con un conjunto de 10k casos de la red ALARM.
Experimento 10: Se realizaron 10 ejecuciones independientes del algoritmo de
tres fases con un conjunto de 5k casos de la red ALARM y una ejecucion del
mismo algoritmo para el conjunto de 10k de la misma red.
73
4.4.2 Experimentos con Conjuntos de Datos Incompletos
Los experimentos de esta seccion estuvieron enfocados a demostrar la viabilidad y
eficiencia del algoritmo de aprendizaje de redes Bayesianas SABS, cuando se ejecuta una
etapa de inferencia a un conjunto de datos incompleto de manera previa. A diferencia
de la seccion anterior, en esta serie de experimentos solo se utilizaron conjuntos de datos
de 5k casos para aprender la estructura de la red Bayesiana ASIA. Los experimentos
se realizaron tanto para el algoritmo SABS como para el algoritmo de tres fases y el
porcentaje de casos incompletos vario con porcentajes de 10%, 20 %, 30 %, 40 % y 50 %.
Los experimentos fueron los siguientes:
Experimento 11: Se seleccionaron aleatoriamente un conjunto de 5k casos del
conjunto de 10k de la red ASIA. Se genero un conjunto con 10 % de valores
faltantes del conjunto de 5k casos. Se aplico el algoritmo de inferencia y poste-
riormente el algoritmo SABS de aprendizaje. El proceso se repitio en 10 ocasiones
y se registraron los resultados.
Experimento 12: Se seleccionaron aleatoriamente un conjunto de 5k casos del
conjunto de 10k de la red ASIA. Se genero un conjunto con 20 % de valores
faltantes del conjunto de 5k casos. Se aplico el algoritmo de inferencia y poste-
riormente el algoritmo SABS de aprendizaje. El proceso se repitio en 10 ocasiones
y se registraron los resultados.
Experimento 13: Se seleccionaron aleatoriamente un conjunto de 5k casos del
conjunto de 10k de la red ASIA. Se genero un conjunto con 30 % de valores
faltantes del conjunto de 5k casos. Se aplico el algoritmo de inferencia y poste-
riormente el algoritmo SABS de aprendizaje. El proceso se repitio en 10 ocasiones
y se registraron los resultados.
Experimento 14: Se seleccionaron aleatoriamente un conjunto de 5k casos del
conjunto de 10k de la red ASIA. Se genero un conjunto con 40 % de valores
faltantes del conjunto de 5k casos. Se aplico el algoritmo de inferencia y poste-
riormente el algoritmo SABS de aprendizaje. El proceso se repitio en 10 ocasiones
y se registraron los resultados.
Experimento 15: Se seleccionaron aleatoriamente un conjunto de 5k casos del
conjunto de 10k de la red ASIA. Se genero un conjunto con 50 % de valores
faltantes del conjunto de 5k casos. Se aplico el algoritmo de inferencia y poste-
riormente el algoritmo SABS de aprendizaje. El proceso se repitio en 10 ocasiones
y se registraron los resultados.
Experimento 16: Se seleccionaron aleatoriamente un conjunto de 5k casos del
conjunto de 10k de la red ASIA. Se genero un conjunto con 10 % de valores
74
faltantes del conjunto de 5k casos. Se aplico el algoritmo de inferencia y poste-
riormente el algoritmo de tres fases. El proceso se repitio en 10 ocasiones y se
registraron los resultados.
Experimento 17: Se seleccionaron aleatoriamente un conjunto de 5k casos del
conjunto de 10k de la red ASIA. Se genero un conjunto con 20 % de valores
faltantes del conjunto de 5k casos. Se aplico el algoritmo de inferencia y poste-
riormente el algoritmo de tres fases. El proceso se repitio en 10 ocasiones y se
registraron los resultados.
Experimento 18: Se seleccionaron aleatoriamente un conjunto de 5k casos del
conjunto de 10k de la red ASIA. Se genero un conjunto con 30 % de valores
faltantes del conjunto de 5k casos. Se aplico el algoritmo de inferencia y poste-
riormente el algoritmo de tres fases. El proceso se repitio en 10 ocasiones y se
registraron los resultados.
Experimento 19: Se seleccionaron aleatoriamente un conjunto de 5k casos del
conjunto de 10k de la red ASIA. Se genero un conjunto con 40 % de valores
faltantes del conjunto de 5k casos. Se aplico el algoritmo de inferencia y poste-
riormente el algoritmo de tres fases. El proceso se repitio en 10 ocasiones y se
registraron los resultados.
Experimento 20: Se seleccionaron aleatoriamente un conjunto de 5k casos del
conjunto de 10k de la red ASIA. Se genero un conjunto con 50 % de valores
faltantes del conjunto de 5k casos. Se aplico el algoritmo de inferencia y poste-
riormente el algoritmo de tres fases. El proceso se repitio en 10 ocasiones y se
registraron los resultados.
4.5 Evaluacion de Resultados
Un punto de suma importancia es definir como se evaluaran los resultados obtenidos
por los algoritmos. Debido a que nuestra intencion es aprender la estructura de las re-
des Bayesianas a partir de conjuntos de datos, se seleccionaron modelos y conjuntos
de datos estandar de la literatura. Mediante la utilizacion de estos modelos, se puede
hacer una comparacion visual y numerica de los resultados obtenidos y determinar que
tan buenos o malos son. Por lo anterior, la evaluacion de los resultados se realizo de
acuerdo a los tres siguientes conceptos:
Arcos Correctos: Los arcos correctos son aquellos arcos que el algoritmo de
aprendizaje encuentra y que realmente existen en la estructura de la red Bayesiana
estandar.
75
Arcos Faltantes: Los arcos faltantes son aquellos arcos que el algoritmo de
aprendizaje no encuentra y que realmente existen en la estructura de la red
Bayesiana estandar.
Arcos Erroneos: Los arcos erroneos son aquellos arcos que el algoritmo de apren-
dizaje encuentra y que no existen realmente en la estructura de la red Bayesiana
estandar.
Por supuesto, resulta logico desear que los algoritmos de aprendizaje no agreguen
arcos erroneos o agreguen los menos posibles. En el caso de la red ASIA, el reto es
descubrir los 8 arcos existentes y en la red ALARM los 46.
Para el caso de conjuntos de datos incompletos en donde se utiliza el algoritmo
de inferencia, los resultados fueron evaluados adicionalmente presentando los valores
reales que toma cada uno de los atributos de los conjuntos de datos completo y completo
inferidos.
4.6 Resumen
En este capıtulo se ha presentado la metodologıa seguida para la realizacion de los
experimentos. Primeramente, se definieron los modelos y conjuntos de prueba que se
utilizaron para la realizacion de los experimentos. Los conjuntos seleccionados fueron
la red ASIA que se compone de 8 nodos y 8 arcos y la red ALARM cuya estructura
posee 37 nodos y 46 arcos. Cada uno de los conjuntos de datos del modelo respectivo
constan de 10k casos completamente instanciados y para generar los conjuntos de datos
incompletos se implemento un algoritmo que genera instancias incompletas en cierto
porcentaje de los datos y cuya complejidad es O(mn). Se definieron 20 experimentos, 10
para la experimentacion con datos completos y 10 para datos incompletos. En el caso
de los conjuntos de datos completos, se utilizaron muestras de 1k, 3k, 5k y 10k casos
y el objetivo fue aprender la estructura de las redes Bayesianas ASIA y ALARM. Este
proceso se repitio en 10 ocasiones y se registraron los resultados tanto del algoritmo
propuesto SABS como del algoritmo de tres fases, aunque para este ultimo solo se
utilizaron conjuntos de 5k y 10k. En el caso de conjuntos de datos incompletos, solo se
utilizaron muestras de 5k casos. Aleatoriamente fueron removidos el 10 %, 20 %, 30 %,
40 % y 50 % de los datos y posteriormente fueron completados utilizando el algoritmo
de inferencia. Como paso siguiente, los algoritmos de aprendizaje SABS y de tres fases
se aplicaron para aprender las estructuras de las redes Bayesianas.
76
Capıtulo 5
Resultados Obtenidos, Analisis y Discusion
En este capıtulo se presentan primeramente los resultados de la experimentacion
realizada para comprobar el funcionamiento del algoritmo de aprendizaje de la estruc-
tura de redes Bayesianas y del algoritmo para inferir valores en conjuntos de datos
incompletos. Posteriormente se presenta el analisis y discusion de dichos resultados,
ası como la comparacion con respecto a los resultados obtenidos por el algoritmo de
tres fases.
5.1 Resultados de Experimentacion
De acuerdo a la metodologıa planteada en el capıtulo 4, los experimentos se divi-
dieron basicamente en dos grupos. En el primero se busco aprender la estructura de las
redes Bayesianas ASIA y ALARM a partir de conjuntos de datos completos de 1k, 3k,
5k y 10k casos. El objetivo principal de esta serie de experimentos fue determinar que
tan eficientes y robustos son los algoritmos al numero de casos. En el segundo grupo
de experimentos se contemplo el problema adicional de aprender la estructura de la
red ASIA tomando en cuenta que los conjuntos de datos fueron completados usando
el algoritmo de inferencia. Para reproducir estos escenarios, se generaron conjuntos de
datos incompletos de diversos porcentajes, 10 %, 20 %, 30 % 40 % y 50 % y previo a
ejecutar los algoritmos de aprendizaje se realizo una fase de pre-procesamiento para
completar los datos.
5.1.1 Conjuntos de Datos Completos
En las tablas 5.1 y 5.2 se muestra un comparativo de los resultados obtenidos
para los experimentos 1 al 10. En dichos experimentos se busca aprender la estructura
de las redes Bayesianas ASIA y ALARM mediante los algoritmos SABS y tres fases
utilizando conjuntos de datos de varios tamanos. Ambas tablas se encuentran divididas
en dos grandes columnas, la primera para el algoritmo SABS y la segunda para el
algoritmo de tres fases en donde a su vez se muestra la cantidad de datos utilizados,
77
el numero de ejecuciones, la cantidad de arcos correctos encontrados (C), los arcos
faltantes (F) y los arcos erroneamente agregados (E) por cada uno de los algoritmos.
SABS Tres fases
Datos Ejec. C F E Datos Ejec. C F E
10k 10 7 1 0 10k 10 7 1 0
5k 10 7 1 0 5k 4 7 1 0
5 7 1 1
1 6 2 2
3k 5 7 1 0
3 7 1 1
2 6 2 0
1k 4 7 1 0
5 6 2 1
1 6 2 2
Tabla 5.1: Sıntesis comparativa de experimentos del algoritmo SABS y el algoritmo de tres
fases para la red ASIA.
SABS Tres fases
Datos Ejec. C F E Datos Ejec. C F E
10k 2 45 1 0 10k 10 45 1 0
6 44 2 ≤ 3
2 44 2 > 3
5k 1 45 1 6 5k 5 45 1 ≤ 3
9 44 2 > 3 3 45 1 > 3
1 46 0 4
1 46 0 3
3k 5 45 1 ≤ 3
2 45 1 > 3
1 44 2 ≤ 3
2 44 2 > 3
1k 2 43 3 4
8 44 2 > 3
Tabla 5.2: Sıntesis comparativa de experimentos del algoritmo SABS y el algoritmo de tres
fases para la red ALARM.
78
La tabla 5.1 sumariza los resultados obtenidos al aprender la estructura de la
red ASIA utilizando el algoritmo SABS y conjuntos de datos de 1k, 3k, 5k y 10k,
y el algoritmo de tres fases para conjuntos de 5k y 10k casos completos. La tabla 5.2
sumariza los resultados obtenidos al aprender la estructura de la red ALARM utilizando
el algoritmo SABS y conjuntos de datos de 1k, 3k, 5k y 10k, y el algoritmo de tres fases
para conjuntos de 5k y 10k casos completos.
En la tabla 5.2 se puede observar por ejemplo que cuando el conjunto de datos
consistio de 5k casos completos, el algoritmo SABS aprendio la estructura de la red
Bayesiana ALARM en una ocasion detectando 45 arcos correctos, y agregando erronea-
mente 6. En 9 ejecuciones aprendio dicha estructura detectando 44 arcos correctos y
agregando para diversas ejecuciones mas de 3 arcos erroneos. En comparacion, el algo-
ritmo de tres fases para la misma red Bayesiana, descubrio en 5 ocasiones la estructura
correcta excepto por un solo arco, agregando 3 o menos arcos erroneos para diversas
ejecuciones. En otra ocasion, este mismo algoritmo descubrio la misma estructura solo
que la cantidad de arcos erroneos que agrego fue mayor de 3. En ejecuciones individua-
les, el algoritmo de tres fases descubrio la estructura correcta, pero agrego 4 y 3 arcos
erroneos, respectivamente. La descripcion detallada de cada uno de estos experimentos
se presenta en la seccion A.1.1 del apendice A.
79
5.1.2 Conjuntos de Datos Incompletos
La tabla 5.3 sumariza los resultados de los experimentos 11 al 20. Dicha tabla
presenta la misma estructura descrita para la tabla 5.1, con la excepcion de que el
numero de casos del conjunto de datos es 5k, y para la primer columna de cada algoritmo
se muestra el porcentaje de casos incompletos utilizado. Ası, se puede observar por
ejemplo que cuando el porcentaje de casos incompletos fue de 30 %, el algoritmo SABS
descubrio en dos ocasiones 7 de los 8 arcos de la estructura de la red ASIA, agregando
solo un arco erroneo, y en tres ocasiones descubrio esta misma estructura sin agregar
arcos de mas. En comparacion, el algoritmo de tres fases descubrio en 4 ocasiones 7 de
los 8 arcos de la estructura y agrego en dichas ocasiones un arco erroneo y solamente en
una ocasion descubrio esa misma estructura sin arcos de mas. La descripcion detallada
de cada uno de estos experimentos se presenta en la seccion A.1.2 del apendice A.
SABS Tres fases
% Inc. Ejec. C F E % Inc. Ejec. C F E
10 % 1 7 1 0 10 % 3 7 1 1
3 7 1 1 1 7 1 0
1 5 3 4 1 6 2 2
20 % 2 7 1 1 20 % 4 7 1 1
1 6 2 2 1 7 1 0
2 7 1 0
30 % 2 7 1 0 30 % 4 7 1 1
3 7 1 1 1 7 1 0
40 % 3 7 1 1 40 % 4 7 1 1
1 7 1 0 1 6 2 2
1 8 0 1
50 % 2 7 1 1 50 % 5 7 1 1
2 7 1 0
1 6 2 2
Tabla 5.3: Sıntesis comparativa de experimentos del algoritmo SABS y el algoritmo de tres
fases para la red ASIA.
5.2 Analisis y Discusion de Resultados
Los experimentos de la seccion 5.1.1 que se explican en detalle en la seccion A.1.1
del apendice A, pretendieron demostrar la robustez del algoritmo SABS para aprender
la estructura de la red Bayesiana a partir de conjuntos de datos completos de diferentes
80
tamanos. Es posible apreciar que en todos los casos el algoritmo recupero la mayorıa de
los arcos de las redes Bayesianas utilizadas y la cantidad de arcos erroneos agregados
fue mınima.
El algoritmo SABS tardo aproximadamente 3, 9, 15 y 30 minutos en converger
a una solucion para los experimentos del uno al cuatro, respectivamente. En todos
los casos el numero de evaluaciones realizadas fue de aproximadamente 3,000. Esto
se debe a que de acuerdo a las condiciones de inicializacion del algoritmo de recocido
simulado, no fue posible encontrar cadenas sucesivas sin mejora por lo que el algoritmo
constantemente reinicio su valor de intentos sin mejorar y solo termino cuando alcanzo el
valor de intentos maximos por nodo.
En el experimento cinco, se intento aprender la estructura de la red Bayesiana
ASIA mediante el uso del algoritmo de tres fases usando dos conjuntos de datos com-
pletos de 5k y 10k casos. Para el primer conjunto se realizaron diez corridas y en el
mejor de los casos el algoritmo encontro todos los enlaces excepto por el arco (0→2)
como se menciono con anterioridad. Los arcos faltantes y erroneos que se agregan en
las demas ejecuciones son producto de la debilidad que poseen los algoritmos basados
en pruebas de CI cuando los conjuntos de datos no son lo suficientemente grandes.
Recuerdese que una de las suposiciones que realiza el algoritmo de tres fases es que
el conjunto de datos es lo suficientemente grande para que las pruebas de CI sean
confiables. Si se disminuye el tamano de los conjuntos de datos, el algoritmo tiende a
crear redes que estan muy densamente conectadas, el tiempo de convergencia aumenta
y los resultados no son muy buenos. Para el conjunto de 10k vemos sin embargo, que
el algoritmo de tres fases recupero la estructura correcta excepto por el arco (0→2).
El tiempo de convergencia del algoritmo para el conjunto de 5k casos fue en
promedio de 6 segundos, y 8 segundos para el conjunto de 10k casos. Esto sin lugar
a dudas representa una ventaja sobre el algoritmo SABS el cual oscila en el rango de
minutos y no segundos.
Los experimentos seis a diez representaron mayor complejidad para los algoritmos
ya que la estructura de red Bayesiana que se debio aprender fue mas compleja. El
tiempo de convergencia del algoritmo SABS fue en promedio de 1, 3, 5 y 10 horas para
los experimentos 6, 7, 8 y 9 respectivamente, y el numero de evaluaciones promedio
fue de 55,000. En todos los experimentos, los resultados arrojaron el descubrimiento
de al menos 43 de los 46 arcos correctos y en ninguna ocasion se agregaron mas de
8 arcos erroneos. En el mejor de los casos, la red Bayesiana correcta fue descubierta
excepto por el arco (4→19). El desempeno del algoritmo de tres fases con el conjunto
de 5k casos en el experimento 10 fue muy similar al desempeno del algoritmo SABS en
cuanto a la estructura descubierta, sin embargo, en cuanto al tiempo de convergencia
la diferencia es grande ya que al algoritmo de tres fases solo le tomo en promedio 3
minutos. Para el conjunto de 10k casos, el algoritmo de tres fases tardo 5 minutos y
descubrio la estructura correcta excepto por el arco (4→19).
81
En cuanto a los experimentos con conjuntos de datos incompletos, tanto el al-
goritmo SABS como el algoritmo de tres fases mostraron buenos resultados cuando
previamente se ejecuto el algoritmo de inferencia para completar el conjunto de datos.
Las figuras en detalle que se muestran en la seccion A.1.2, revelan para cada experi-
mento las aproximaciones realizadas por el algoritmo de inferencia para cada uno de los
valores que pueden tomar los atributos de las redes Bayesianas. En cada caso vemos que
los valores reales e inferidos son muy similares y por tanto los resultados que obtienen
los algoritmos de aprendizaje de redes Bayesianas asemejan a la estructura deseada.
Los graficas fueron obtenidas mediante el conteo de los diferentes valores que
puede tomar cada uno de los atributos de la red Bayesiana, tanto para el conjunto
completo real, como para el conjunto completado mediante inferencia de cada una de
las 5 ejecuciones. Dichos valores fueron promediados y divididos entre el tamano del
conjunto de datos, que en este caso fue de 5k. Esto nos proporciono en promedio el
porcentaje de veces que un valor determinado se presento para cierto atributo de manera
real y nos permitio compararlo con el mismo valor posterior al proceso de inferencia.
Los resultados de los experimentos demuestran que aun cuando el algoritmo SABS
converge de manera mas lenta que el algoritmo de tres fases, las soluciones que este
provee son buenas. En general, el tiempo de convergencia de SABS es mas lento que
el algoritmo de tres fases debido a la mecanica de busqueda de la estructura de la red.
Mientras que SABS utiliza como metodo de busqueda recocido simulado y evalua cada
red de acuerdo al criterio Bayesiano dentro de un espacio exponencial de soluciones,
el algoritmo de tres fases explora las caracterısticas de independencia e independencia
condicional de los nodos, lo cual en todas las ocasiones le toma menos tiempo. Sin
embargo, el algoritmo de tres fases no es confiable cuando el numero de casos es pequeno
ya que las pruebas de CI requieren de conjuntos de datos grandes.
5.3 Resumen
En este capıtulo se presentaron los resultados de los experimentos realizados con
el algoritmo propuesto SABS y el algoritmo de tres fases para el aprendizaje de la
estructura de redes Bayesianas, y del algoritmo de inferencia de conjuntos de datos
incompletos. En la primera serie de experimentos para conjuntos de datos completos,
se realizo una comparacion de los resultados de ambos algoritmos de aprendizaje en
cuanto a la calidad de las estructuras que descubre cada uno de ellos en base a los arcos
correctos, faltantes y erroneos. Se utilizaron los modelos de redes Bayesianas ASIA y
ALARM que son estandar en la literatura para la prueba de algoritmos de aprendizaje
de redes Bayesianas y diversos tamanos de conjuntos, con lo que se demostro que el
algoritmo SABS propuesto obtiene buenas soluciones.
En la segunda serie de experimentos solo se utilizo el modelo ASIA y se generaron
82
conjuntos de datos incompletos que posteriormente fueron completados mediante el
algoritmo de inferencia. Se demostro que los conjuntos inferidos son muy aproximados
a los conjuntos completos reales lo que permite a los algoritmos de aprendizaje obtener
buenas soluciones.
83
84
Capıtulo 6
Conclusiones y Trabajo Futuro
En esta investigacion se ha propuesto un algoritmo que aprender la estructura de
una red Bayesiana a partir de un conjunto de datos completos. Este algoritmo llamado
SABS esta basado en el enfoque de busqueda y evaluacion y utiliza recocido simula-
do y criterio Bayesiano como metodos de busqueda y evaluacion respectivamente. El
algoritmo SABS analiza nodo por nodo tratando de maximizar el criterio Bayesiano
de cada uno de estos, lo que a su vez maximiza el de toda la red. Cuando el algo-
ritmo no mejora la solucion actual para cierto nodo o alcanza un numero maximo de
evaluaciones, regresa la configuracion actual como solucion y procede a examinar el
siguiente nodo. Una vez analizados todos los nodos, el algoritmo ejecuta una fase en
donde intenta eliminar arcos redundantes, es decir, arcos que sean condicionalmente
independientes dado cierto conjunto de corte. El algoritmo regresa como solucion la
estructura de red Bayesiana encontrada por esta ultima fase.
De manera similar, se implemento un algoritmo para inferencia de valores faltantes
en un conjunto de datos incompletos. Este algoritmo consiste en la primera etapa del
algoritmo de Expectation-Maximization y el objetivo es analizar el comportamiento y
comparar los resultados obtenidos del algoritmo propuesto SABS y el algoritmo de tres
fases de Cheng cuando los datos faltantes del conjunto son inferidos.
Se ha verificado el funcionamiento del algoritmo mediante una serie de experi-
mentos, tanto para conjuntos de datos completos como incompletos encaminados a la
comparacion de los resultados obtenidos con el algoritmo de tres fases. Este algoritmo
esta basado en el enfoque de analisis de dependencias y es famoso en la literatura por
los buenos resultados que obtiene, ası como la rapidez de convergencia. En comparacion
con el algoritmo de tres fases, el algoritmo SABS es lento, sin embargo, las estructuras
de red que aprende son muy similares y solo difieren por algunos arcos. Para algunos
experimentos, las mismas soluciones fueron encontradas por ambos algoritmos.
Como posibles extensiones a este trabajo y nuevas lıneas de investigacion se pro-
ponen las siguientes:
Debido a la naturaleza del algoritmo SABS, la exploracion de los nodos es inde-
pendiente por lo que un esquema distribuido en donde diferentes procesos exploren
85
de manera simultanea un nodo a la vez es factible. Este esquema en paralelo dis-
minuirıa el tiempo de convergencia del algoritmo.
Extender el algoritmo SABS para el aprendizaje de redes Bayesianas cuando no
se proporciona una ordenacion de nodos.
El algoritmo de tres fases utiliza como primer etapa el algoritmo de Chow y Liu
lo que proporciona una muy buena aproximacion de la red Bayesiana final. El
algoritmo SABS podrıa implementar como primera etapa este mismo algoritmo
de manera que el espacio de busqueda para el algoritmo de recocido simulado se
disminuya.
Para el presente trabajo se utilizo como medida de evaluacion de las redes Baye-
sianas candidatas el criterio Bayesiano, sin embargo, existen otras medidas que
podrıan intentarse bajo el esquema propuesto por el algoritmo SABS como son
MDL, ganancia de informacion, etc.
86
Bibliografıa
[1] S. Acid and L.M. Campos. BENEDICT: An algorithm for learning probabilistic
belief networks. In Proceedings of the Sixth International Conference IPMU’96,
1996.
[2] I.A. Beinlich, H.J. Suermondt, R.M. Chavez, and G.F. Cooper. The ALARM
monitoring system: A case study with two probabilistic inference techniques for
belief networks. In Proceedings of the Second European Conference on Artificial
Intelligence in Medicine, pages 247–256, 1989.
[3] J. Cheng, D. Bell, and W. Liu. Learning Bayesian networks from data: An effi-
cient approach based on information theory. In Proceedings of the Sixth ACM
International Conference on Information and Knowledge Management, 1997.
[4] D.M. Chickering. A transformational characterization of equivalent Bayesian net-
work structures. 1995.
[5] D.M. Chickering, D. Geiger, and D. Heckerman. Learning Bayesian networks is NP-
Hard. Technical report, Microsoft Research, Microsoft Corporation, 1994. Tech-
nical Report MSR-TR-94-17.
[6] C.K. Chow and C.N. Liu. Approximating discrete probability distributions with
dependence trees. IEEE Transactions on Information Theory, 14(3):462–467, 1968.
[7] G.F. Cooper. The computational complexity of probabilistic inference using
Bayesian belief networks. Artificial Intelligence, 42:393–405, 1990.
[8] G.F. Cooper and E. Herskovits. A Bayesian method for constructing Bayesian
belief networks from databases. In Proceedings of the Conference on Uncertainty
in Artificial Intelligence, pages 86–94, 1991.
[9] G.F. Cooper and E. Herskovitz. A Bayesian method for the induction of probabi-
listic networks from data. Machine Learning, 9:309–347, 1992.
[10] A.P. Dempster, N.M. Laird, and D.B. Rubin. Maximum likelihood from incomplete
data via the EM algorithm. Journal of Royal Statistical Society, 39:1–38, 1977.
87
[11] S. Devadas and A.R. Newton. Topological optimization of multiple-level array
logic. IEEE Transactions on Computer-Aided Design, 6(6):915–941, 1987.
[12] T. Elperin. Monte Carlo structural optimization in discrete variables with annea-
ling algorithm. International Journal for Numerical Methods, 26:815–821, 1988.
[13] N. Friedman and M. Goldszmidt. Learning Bayesian networks with local structure.
In Proceedings of the Twelfth International Conference on Uncertainty in Artificial
Intelligence, 1996.
[14] N. Friedman, I. Nachman, and D. Peer. Learning Bayesian Network Structure
from Massive Datasets: The “Sparse Candidate” Algorithm. In Proceedings of the
Fifteenth International Conference on Uncertainty in Artificial Intelligence, pages
206–215, 1999.
[15] R.M. Fung and S.L. Crawford. Constructor: A system for the induction of pro-
babilistic models. In Proceedings of the Seventh National Conference on Artificial
Intelligence, 1990.
[16] D. Geiger and J. Pearl. Logical and algorithmic properties of conditional indepen-
dence. Technical report, Cognitive Systems Laboratory, UCLA, 1988. Technical
Report R-97.
[17] D. Heckerman. A tutorial on learning with Bayesian networks. Technical report,
Microsoft Research, Microsoft Corporation, March 1995. Technical Report MSR-
TR-95-06.
[18] D. Heckerman, D. Geiger, and D. Chickering. The combination of knowledge and
statistical data. Journal of Machine Learning, 20:197–243, 1995.
[19] M. Henrion. Propagating uncertainty in Bayesian networks by probabilistic logic
sampling. Uncertainty in Artificial Intelligence, 2:149–163, 1988.
[20] E. Herskovitz and G. Cooper. Kutato: An entropy-driven system for construc-
tion of probabilistic expert system from databases. In Proceedings of the Sixth
International Conference on Uncertainty in Artificial Intelligence, 1990.
[21] S. Kirkpatrick, C. Gelatt, and M. Vecchi. Optimization by simulated annealing.
Science, 220(4598):671–680, 1983.
[22] A.N. Kolmogorov. Foundations of the Theory of Probability , Chelsea, New York,
1950 (originalmente publicado en 1933 como Grundbegriffe der Wahrscheinlichkeit-
srechnung, Springer, Berlin).
88
[23] S. Kullback and R.A. Leibler. On information and sufficiency. Annals of Mathe-
matical Statistics, 22:76–86, 1951.
[24] W. Lam and F. Bacchus. Learning Bayesian belief networks: An approach based
on the MDL Principle. Computational Intelligence, 10(4):269–293, 1994.
[25] S.L. Lauritzen and D.J. Spiegelhalter. Local computations with probabilities on
graphical structures and their application to expert systems. Royal Statistics So-
ciety, 50(2):157–224, 1988.
[26] A. Malhotra and J.H. Oliver. Synthesis of spatially and intrinsically constrained
curves using simulated annealing. ASME Advanced on Design Automation, DE-
32:145–155, 1991.
[27] N. Metropolis, A.W. Rosenbluth, M.N. Rosenbluth, A.H. Teller, and E. Teller.
Equation of state calculation by fast computing machines. Journal of Chemistry
Physics, 21:1087–1091, 1953.
[28] R.E. Neapolitan. Learning Bayesian Networks. Artificial Intelligence. Prentice
Hall, 2003.
[29] J. Pearl. Fusion, propagation, and structuring in belief netwoks. Artificial Intelli-
gence, 1987.
[30] J. Pearl. Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, 1988.
[31] M. Ramoni and P. Sebastiani. Efficient Parameter Learning in Bayesian Networks
from Incomplete Databases. Technical report, Knowledge Media Institute, January
1997. Technical Report KMI-TR-41.
[32] G. Rebane and J. Pearl. The Recovery of causal poly-trees from statistical data.
In Proceedings of the Conference on Uncertainty in Artificial Intelligence, pages
222–228, 1987.
[33] C.R. Reeves. Modern Heuristic Techniques for Combinatorial Problems. Wiley,
1st edition, 1993.
[34] R.W. Robinson. Counting unlabeled acyclic digraphs. In Proceedings of the Fifth
Australian Conference on Combinatorial Mathematics, pages 28–43, Melbourne,
Australia, 1976.
[35] D.B. Rubin. Comment on “The calculation of posterior distributions by data
augmentation”. Journal of American Statistical Association, 82:543–546, 1987.
89
[36] S. Russell and P. Norvig. Artificial Intelligence: A Modern Approach. Prentice
Hall, 1st edition, 1995.
[37] S. Russell and P. Norvig. Artificial Intelligence: A Modern Approach. Prentice
Hall, 2nd edition, 2003.
[38] C.E. Shannon and W. Weaver. The mathematical theory of communication. Bell
System Technical Journal, 27:379–423 and 623–656, July and October 1949.
[39] M. Singh and M. Valorta. Construction of Bayesian networks from data: A brief
survey and an efficient algoritm. International Journal of Approximate Reasoning,
12:111–131, 1995.
[40] P. Spirtes, C. Glymour, and R. Scheines. Causality from probability. In G. McKee,
editor, Evolving knowledge in natural science and artificial intelligence, pages 181–
199. Pitman, 1990.
[41] P. Spirtes, C. Glymour, and R. Scheines. An algorithm for fast recovery of sparse
causal graphs. Social Science Computer Review, 9:62–72, 1991.
[42] S. Srinivas, S. Russell, and A. Agogino. Automated construction of sparse Bayesian
networks from unstructured probabilistic models and domain information. In
M. Henrion, R.D. Shachter, L.N. Kanal, and J.F. Lemmer, editors, Uncertainty
in artificial intelligence 5, Amsterdam: North-Holland, 1990.
[43] J. Suzuki. Learning Bayesian belief networks based on the MDL principle: An
efficient algorithm using the branch and bound technique. In Proceedings of the
International Conference on Machine Learning, 1996.
[44] P.J.M van Laarhoven and E.H.L Aarts. Simulated Annealing: Theory and Appli-
cations. Kluwet Academic, 1987.
[45] C. Wallace, K.B. Korb, and H. Dai. Causal discovery via MML. In Proceedings of
the thirteenth International Conference on Machine Learning (ICML’96). Morgan-
Kaufmann, 1996.
[46] N. Wermuth and S. Lauritzen. Graphical and recursive models for contingency
tables. Biometrika, 72:537–552, 1983.
[47] S.K.M. Wong and Y. Xiang. Construction of a Markov network from data for
probabilistic inference. Third International Workshop on Rough Sets and Soft
Computing, pages 562–569, 1994.
90
[48] Y. Xiang and S.K.M. Wong. Learning conditional independence relations from
a probabilistic model. Technical report, University of Regina, 1994. Technical
Report.
91
92
Apendice A
Detalle de resultados obtenidos
En este apendice se presentan en detalle los resultados obtenidos de la experi-
mentacion realizada para comprobar el funcionamiento del algoritmo de aprendizaje
de la estructura de redes Bayesianas, SABS, propuesto en esta investigacion, ası como
del algoritmo de tres fases de Cheng con el cual se realizan comparaciones. De igual
forma, se presentan los resultados que se obtuvieron al completar conjuntos de datos
incompletos al aplicar el algoritmo de inferencia. A partir de los conjuntos de datos
completos obtenidos por el algoritmo de inferencia, los dos algoritmos de aprendizaje
de redes Bayesianas, SABS y tres fases fueron aplicados en diferentes experimentos y
sus resultados son igualmente presentados en este apendice.
A.1 Resultados de Experimentacion
En el capıtulo 5 se presentaron de manera breve los resultados obtenidos por
los experimentos planteados para analizar y comparar el desempeno de los algoritmos
SABS y tres fases, ası como el algoritmo de inferencia de conjuntos incompletos. En esta
seccion se presentaran esos mismo resultados, pero con una explicacion mas detallada.
A.1.1 Conjuntos de Datos Completos
A continuacion se presentan los resultados de los experimentos realizados con
conjuntos de datos completos tanto para el algoritmo propuesto SABS como para el
algoritmo de tres fases. La descripcion de estos experimentos fue realizada en la seccion
4.4.
Experimento 1: Algoritmo SABS y red ASIA para 1k casos
En este experimento se utilizo el algoritmo SABS, la red Bayesiana ASIA y un
conjunto completo de datos de 1k casos. Los resultados de las diez ejecuciones del
algoritmo se muestran en la tabla A.1. En el mejor de los casos el algoritmo encontro la
93
estructura correcta excepto por el arco (0→2). Esta estructura fue encontrada en cuatro
repeticiones independientes del algoritmo (1,2,5,8) y se muestra en la figura A.1.
Ejecucion Arcos
C F E
1,2,5,8 7 1 (0→2) 0
3,4 6 2 (0→2);(5→7) 1 (6→7)
6,7,9 6 2 (0→2);(5→7) 1 (3→7)
10 6 2 (0→2);(5→7) 2 (3→6);(3→7)
Tabla A.1: Resultados de SABS para la red ASIA con 1k casos completos.
Figura A.1: Mejor red ASIA aprendida por SABS para 1k casos completos.
Experimento 2: Algoritmo SABS y red ASIA para 3k casos
En este experimento se utilizo el algoritmo SABS, la red Bayesiana ASIA y un
conjunto completo de datos de 3k casos. Los resultados de las diez ejecuciones del
algoritmo se muestran en la tabla A.2. En el mejor de los casos el algoritmo encontro la
estructura correcta excepto de nuevo por el arco (0→2). Esta estructura fue encontrada
en cinco repeticiones independientes del algoritmo (1,3,7,8,9) y se muestra en la figura
A.1.
Ejecucion Arcos
C F E
1,3,7,8,9 7 1 (0→2) 0
2,4,6 7 1 (0→2) 1 (3→6)
5 6 2 (0→2);(5→6) 0
10 6 2 (0→2);(5→7) 0
Tabla A.2: Resultados de SABS para la red ASIA con 3k casos completos.
94
Experimento 3: Algoritmo SABS y red ASIA para 5k casos
En este experimento se utilizo el algoritmo SABS, la red Bayesiana ASIA y un
conjunto completo de datos de 5k casos. Los resultados de las diez ejecuciones del
algoritmo se muestran en la tabla A.3, y para todas ellas el algoritmo encontro la
misma estructura que ha sido senalada en la figura A.1.
Ejecucion Arcos
C F E
1-10 7 1 (0→2) 0
Tabla A.3: Resultados de SABS para la red ASIA con 5k casos completos.
En las diez ejecuciones que se realizaron en este experimento, el algoritmo no
agrego arcos erroneos a la estructura, sin embargo, no fue capaz de encontrar el arco
(0→2). La razon para esto es que dicho arco no se encuentra soportado por los datos
por lo cual no es descubierto por el algoritmo. Recuerdese que para variables cuyo
numero de nodo es menor del numero maximo de padres, el algoritmo realiza busqueda
exhaustiva y por tanto la unica razon por la que dicho arco no se encuentra es porque
la ausencia de este resulta en una mejor evaluacion de acuerdo al criterio Bayesiano
del nodo 2.
Experimento 4: Algoritmo SABS y red ASIA para 10k casos
En este experimento se utilizo el algoritmo SABS, la red Bayesiana ASIA y un
conjunto completo de datos de 10k casos. Los resultados de las diez ejecuciones del
algoritmo se muestran en la tabla A.4. De igual forma, el algoritmo encontro siempre
la misma estructura mostrada en la figura A.1.
Ejecucion Arcos
C F E
1-10 7 1 (0→2) 0
Tabla A.4: Resultados de SABS para la red ASIA con 10k casos completos.
Al igual que para el experimento anterior con un conjunto de 5k casos completos,
en este experimento el algoritmo SABS fue capaz de encontrar la estructura correcta
excepto por el arco (0→2) sin agregar ningun arco erroneo.
95
Experimento 5: Algoritmo de tres fases y red ASIA
En este experimento se utilizo el algoritmo de tres fases, la red Bayesiana ASIA y
un conjunto completo de datos de 5k casos con el que se realizaron diez ejecuciones. Los
resultados de estas ejecuciones se muestran en la tabla A.5. Se puede observar que el
desempeno del algoritmo de tres fases es bueno aun cuando en una de las ejecuciones la
red Bayesiana aprendida carecio de dos arcos y dos arcos fueron agregados de manera
erronea.
Ejecucion Arcos
C F E
1,4,6,9 7 1 (0→2) 0
2,5,7,8,10 7 1 (0→2) 1 (3→6)
3 6 2 (0→2);(5→7) 2 (3→6);(3→7)
Tabla A.5: Resultados del algoritmo de tres fases para la red ASIA con 5k casos completos.
Los resultados de la ejecucion individual del algoritmo de tres fases utilizando un
conjunto de 10k casos completos se muestran en la tabla A.6. Solo una ejecucion del
algoritmo se realizo en esta ocasion ya que el experimento es totalmente determinıstico
debido a que no hubo seleccion aleatoria de los registros y por tanto el algoritmo siempre
alcanza la misma solucion. El arco (0→2) no es aprendido por el algoritmo debido a
que la informacion mutua entre dichos nodos es menor de ε=0.01 y por tanto no es
agregado a la estructura en ninguna de las dos primeras fases del algoritmo.
Ejecucion Arcos
C F E
1-10 7 1 (0→2) 0
Tabla A.6: Resultados del algoritmo de tres fases para la red ASIA con 10k casos completos.
Para las dos corridas planteadas dentro de este experimento, es decir, para con-
juntos de 5k y 10k casos completos, el algoritmo de tres fases encontro en el mejor de
los casos la misma estructura encontrada por el algoritmo SABS que se muestra en la
figura A.1.
Experimento 6: Algoritmo SABS y red ALARM para 1k casos
En este experimento se utilizo el algoritmo SABS, la red Bayesiana ALARM y
un conjunto completo de datos de 1k casos. Los resultados de las diez ejecuciones del
algoritmo se muestran en la tabla A.7. Las ejecuciones cuatro, nueve y diez arrojaron
96
los mejores resultados ya que en estos casos solo dos arcos no pudieron ser descubiertos
(4→19) y (18→27) y en cada caso solo cuatro arcos erroneos fueron agregados. La
figura A.2 muestra la red Bayesiana aprendida por el algoritmo para la ejecucion diez.
Experimento 7: Algoritmo SABS y red ALARM para 3k casos
En este experimento se utilizo el algoritmo SABS, la red Bayesiana ALARM y
un conjunto completo de datos de 3k casos. Los resultados de las diez ejecuciones del
algoritmo se muestran en la tabla A.8. La mejor estructura fue obtenida en la ejecucion
tres del algoritmo y se muestra en la figura A.3.
Experimento 8: Algoritmo SABS y red ALARM para 5k casos
En este experimento se utilizo el algoritmo SABS, la red Bayesiana ALARM y
un conjunto completo de datos de 5k casos. Los resultados de las diez ejecuciones del
algoritmo se muestran en la tabla A.9. La mejor estructura fue obtenida en la ejecucion
seis del algoritmo y se muestra en la figura A.4.
Experimento 9: Algoritmo SABS y red ALARM para 10k casos
En este experimento se utilizo el algoritmo SABS, la red Bayesiana ALARM y
un conjunto completo de datos de 10k casos. Los resultados de las diez ejecuciones
del algoritmo se muestran en la tabla A.10 y la mejor estructura encontrada puede
observarse en la figura A.5.
Experimento 10: Algoritmo de tres fases y red ALARM
En este experimento se utilizo el algoritmo de tres fases, la red Bayesiana ALARM
y un conjunto completo de datos de 5k casos con el que se realizaron diez ejecuciones.
Los resultados de estas ejecuciones se muestran en la tabla A.11. La mejor red Bayesiana
aprendida en esta serie de experimentos se muestra en la figura A.6.
Adicionalmente se realizo una ejecucion de este mismo algoritmo con un conjunto
de 10k casos completos y sus resultados se muestran en la tabla A.12. En esta ejecucion
el algoritmo de tres fases no agrego arcos erroneos a la estructura y solo fallo al descubrir
el arco (4→19). De acuerdo a los resultados de esta ejecucion, la informacion mutua
entre los nodos (4,19) sı es mayor de ε=0.01, sin embargo, al intentar agregar este arco
a la estructura en la fase I del algoritmo, ya existe otro camino abierto entre dichos
nodos por lo que el arco no se agrega. En la fase II el arco de igual forma no es agregado
ya que dado el nodo 16, los nodos (4,19) son condicionalmente independientes, es decir,
IM (4, 19|16) < ε. La figura A.7 muestra la estructura obtenida en esta ejecucion.
97
Ejecucion Arcos
C F E
1 43 3 (4→19);(18→27);(24→27) 4 (2→10);(5→19);(5→26);(23→27)
2 44 2 (4→19);(18→27) 5 (0→9);(0→21);(2→7);(8→23)
(9→26)
3 44 2 (4→19);(18→27) 5 (0→9);(4→10);(5→8);(5→14)
(8→36)
4 44 2 (4→19);(18→27) 4 (0→21);(1→9);(3→25);(6→35)
5 44 2 (4→19);(18→27) 8 (0→1);(1→7);(4→7);(5→19)
(7→36);(8→10);(8→16);(22→26)
6 44 2 (4→19);(18→27) 6 (2→26);(4→26);(5→21);(6→36)
(8→10);(13→35)
7 43 3 (4→19);(18→27);(22→23) 4 (1→6);(1→26);(3→10);(8→20)
8 44 2 (4→19);(18→27) 6 (12→30);(2→12);(5→19);(7→22)
(13→26);(22→25)
9 44 2 (4→19);(18→27) 4 (3→10);(5→8);(7→16);(9→23)
10 44 2 (4→19);(18→27) 4 (0→28);(1→10);(2→10);(2→30)
Tabla A.7: Resultados de SABS para la red ALARM con 1k casos completos.
Figura A.2: Mejor red ALARM aprendida por SABS para 1k casos completos.
98
Ejecucion Arcos
C F E
1 45 1 (4→19) 4 (0→2);(2→9);(5→10);(5→25)
2 45 1 (4→19) 6 (1→10);(1→21);(2→3);(5→8)
(8→14);(22→25)
3 45 1 (4→19) 1 (6→22)
4 45 1 (4→19) 3 (5→8);(7→9);(22→25)
5 45 1 (4→19) 3 (3→10);(6→26);(7→24)
6 44 2 (4→19);(18→27) 5 (1→23);(1→36);(5→8);(5→9)
(8→10)
7 44 2 (4→19);(18→27) 4 (0→34);(5→9);(5→23);(8→17)
8 45 1 (4→19) 3 (1→35);(2→9);(22→26)
9 44 2 (4→19);(18→27) 2 (1→25);(2→34)
10 45 1 (4→19) 3 (1→29);(1→34);(8→10)
Tabla A.8: Resultados de SABS para la red ALARM con 3k casos completos.
Figura A.3: Mejor red ALARM aprendida por SABS para 3k casos completos.
99
Ejecucion Arcos
C F E
1 44 2 (4→19);(18→27) 8 (2→8);(4→26);(5→7);(7→21)
(9→10);(9→26);(12→23);(22→25)
2 44 2 (4→19);(18→27) 4 (0→2);(4→7);(8→16);(9→26)
3 44 2 (4→19);(18→27) 4 (0→16);(2→10);(3→10);(5→7)
4 44 2 (4→19);(18→27) 6 (0→9);(2→11);(5→8);(5→9)
(9→20);(22→25)
5 44 2 (4→19);(18→27) 5 (1→2);(1→10);(3→10);(5→8)
(8→10);
6 45 1 (4→19) 6 (0→2);(0→7);(3→10);(4→26)
(5→7);(8→25)
7 44 2 (4→19);(18→27) 6 (0→21);(1→7);(3→6);(4→26)
(5→8);(9→26)
8 44 2 (4→19);(18→27) 7 (2→36);(3→10);(4→10);(5→18)
(7→10);(8→16);(9→31)
9 44 2 (4→19);(18→27) 7 (0→4);(0→9);(3→7);(3→26)
(4→7);(6→26);(10→31)
10 44 2 (4→19);(18→27) 4 (0→4);(3→7);(4→7);(5→9)
Tabla A.9: Resultados de SABS para la red ALARM con 5k casos completos.
Figura A.4: Mejor red ALARM aprendida por SABS para 5k casos completos.
100
Ejecucion Arcos
C F E
1,2 44 2 (4→19);(18→27) 0
3,8 45 1 (4→19) 0
4 44 2 (4→19);(18→27) 4 (0→21);(1→24);(8→12);(20→27)
5 44 2 (4→19);(18→27) 1 (5→17)
6 44 2 (4→19);(18→27) 1 (4→35)
7 44 2 (4→19);(18→27) 2 (5→26);(20→27)
9 44 2 (4→19);(18→27) 3 (0→32);(1→28);(20→27);
10 44 2 (4→19);(18→27) 5 (1→30);(5→36);(10→31);(13→25)
(20→27)
Tabla A.10: Resultados de SABS para la red ALARM con 10k casos completos.
Figura A.5: Mejor red ALARM aprendida por SABS para 10k casos completos.
101
Ejecucion Arcos
C F E
1 45 1 (4→19) 3 (11→33);(15→33);(21→33)
2 45 1 (4→19) 6 (11→33);(15→32);(20→33);(21→32)
(24→33);(26→32)
3 46 0 4 (7→33);(11→33);(15→32);(24→33)
4 46 0 3 (7→33);(18→33);(19→33)
5 45 1 (4→19) 5 (7→33);(20→32);(20→33);(21→32)
(23→33)
6 45 1 (4→19) 4 (7→33);(11→33);(21→33);(24→33)
7 45 1 (18→27) 3 (7→33);(17→33);(20→33)
8 45 1 (4→19) 1 (7→33)
9 45 1 (8→26) 2 (11→33);(24→33)
10 45 1 (4→19) 3 (7→33);(18→33);(24→33)
Tabla A.11: Resultados del algoritmo de tres fases para la red ALARM con 5k casos com-
pletos.
Figura A.6: Mejor red ALARM aprendida por el algoritmo de tres fases para 5k casos com-
pletos.
102
Ejecucion Arcos
C F E
1 45 1 (4→19) 0
Tabla A.12: Resultados del algoritmo de tres fases para la red ALARM con 10k casos com-
pletos.
Figura A.7: Mejor red ALARM aprendida por el algoritmo de tres fases para 10k casos
completos.
103
A.1.2 Conjuntos de Datos Incompletos
A continuacion se presentan los resultados de los experimentos realizados con con-
juntos de datos incompletos tanto para el algoritmo propuesto SABS como el algoritmo
de tres fases. La descripcion de estos experimentos fue realizada en la seccion 4.4.
Experimento 11: Algoritmo SABS y red ASIA para 5k casos y 10% casos
incompletos.
Para este experimento se genero un conjunto aleatorio de 5k casos con algunos
atributos (aleatoriamente entre 1 y 4 atributos) incompletos en el 10 % de los regis-
tros. Posteriormente se utilizo el algoritmo de inferencia para completar el conjunto de
datos y ejecutar el algoritmo SABS en cinco ocasiones de manera independiente. Los
resultados de las ejecuciones se muestran en la tabla A.13 en donde se puede observar
que en cuatro de las cinco, el algoritmo obtiene buenos resultados. La ejecucion cua-
tro unicamente recupera cinco de los ocho arcos y adicionalmente agrega cuatro arcos
erroneos. Este ultimo resultado no es bueno, sin embargo, en promedio se puede decir
que el algoritmo si recupera casi por completo la estructura de la red.
Ejecucion Arcos
C F E
1 7 1 (0→2) 0
2,3,5 7 1 (0→2) 1 (3→6)
4 5 3 (0→2);(5→6);(5→7) 4 (2→6);(2→7);(3→6);(3→7)
Tabla A.13: Resultados de SABS para la red ASIA con 5k casos y 10 % de casos incompletos.
En la figura A.8 se muestran los promedios de datos generados e inferidos por los
algoritmos dentro de este experimento para los valores 1 y 2 que toman los atributos
del conjunto de datos de la red ASIA, respectivamente.
En cada una de las sub-figuras, la primera serie corresponde a los promedios de
los datos reales de las cinco ejecuciones del algoritmo de inferencia para el conjunto
de 5k casos completos y la segunda a los datos inferidos. Si tomamos de ejemplo la
grafica de la izquierda de la figura A.8, se puede observar que en promedio el nodo
0 estuvo contenido en el 4.9 % de los casos para el conjunto completo, y el algoritmo
de inferencia recupera un valor muy cercano a este a partir del conjunto de datos
incompleto generado.
104
Experimento 12: Algoritmo SABS y red ASIA para 5k casos y 20% casos
incompletos.
Para este experimento se genero un conjunto aleatorio de 5k casos con algunos
atributos (aleatoriamente entre 1 y 4 atributos) incompletos en el 20 % de los regis-
tros. Posteriormente se utilizo el algoritmo de inferencia para completar el conjunto de
datos y ejecutar el algoritmo SABS en cinco ocasiones de manera independiente. Los
resultados de las ejecuciones se muestran en la tabla A.14. En las cinco ejecuciones, el
algoritmo fallo en recuperar el arco (0→2), sin embargo, en dos de ellas no agrego arcos
erroneos y en otras dos, solo agrego uno.
Ejecucion Arcos
C F E
1,3 7 1 (0→2) 1 (3→6)
2 6 2 (0→2);(5→7) 2 (2→7);(3→7)
4,5 7 1 (0→2) 0
Tabla A.14: Resultados de SABS para la red ASIA con 5k casos y 20 % de casos incompletos.
En la figura A.9 se muestran los promedios de datos generados e inferidos por los
algoritmos dentro de este experimento para los valores 1 y 2 que toman los atributos
del conjunto de datos de la red ASIA, respectivamente.
Experimento 13: Algoritmo SABS y red ASIA para 5k casos y 30% casos
incompletos.
Para este experimento se genero un conjunto aleatorio de 5k casos con algunos
atributos (aleatoriamente entre 1 y 4 atributos) incompletos en el 30 % de los regis-
tros. Posteriormente se utilizo el algoritmo de inferencia para completar el conjunto de
datos y ejecutar el algoritmo SABS en cinco ocasiones de manera independiente. Los
resultados de las ejecuciones se muestran en la tabla A.15. Aun cuando el porcentaje
de datos faltante fue del 30 % y tal cantidad de datos fue inferida, el algoritmo SABS
aprende casi completamente la estructura de la red ASIA. En las cinco ejecuciones, el
algoritmo de aprendizaje recupera siete de los ocho arcos y en tres de ellas agrega el
arco (3→6) erroneamente.
105
Ejecucion Arcos
C F E
1,4 7 1 (0→2) 0
2,3,5 7 1 (0→2) 1 (3→6)
Tabla A.15: Resultados de SABS para la red ASIA con 5k casos y 30 % de casos incompletos.
En la figura A.10 se muestran los promedios de datos generados e inferidos por los
algoritmos dentro de este experimento para los valores 1 y 2 que toman los atributos
del conjunto de datos de la red ASIA, respectivamente.
Experimento 14: Algoritmo SABS y red ASIA para 5k casos y 40% casos
incompletos.
Para este experimento se genero un conjunto aleatorio de 5k casos con algunos
atributos (aleatoriamente entre 1 y 4 atributos) incompletos en el 40 % de los registros.
Posteriormente se utilizo el algoritmo de inferencia para completar el conjunto de datos
y ejecutar el algoritmo SABS en cinco ocasiones de manera independiente. Los resul-
tados de las ejecuciones se muestran en la tabla A.16. Dentro de este experimento es
de notar que el algoritmo de aprendizaje recupero correctamente todos los arcos de la
estructura de la red Bayesiana en una de las ejecuciones, sin embargo, agrego un arco
erroneo.
Ejecucion Arcos
C F E
1,2,4 7 1 (0→2) 1 (3→6)
3 7 1 (0→2) 0
5 8 0 1 (3→6)
Tabla A.16: Resultados de SABS para la red ASIA con 5k casos y 40 % de casos incompletos.
La figura A.11 muestra los promedios de datos generados e inferidos por los algo-
ritmos dentro de este experimento para los valores 1 y 2 que toman los atributos del
conjunto de datos de la red ASIA, respectivamente.
Experimento 15: Algoritmo SABS y red ASIA para 5k casos y 50% casos
incompletos.
Para este experimento se genero un conjunto aleatorio de 5k casos con algunos
atributos (aleatoriamente entre 1 y 4 atributos) incompletos en el 50 % de los regis-
tros. Posteriormente se utilizo el algoritmo de inferencia para completar el conjunto de
106
datos y ejecutar el algoritmo SABS en cinco ocasiones de manera independiente. Los
resultados de las ejecuciones se muestran en la tabla A.17.
Ejecucion Arcos
C F E
1,4 7 1 (0→2) 1 (3→6)
2,3 7 1 (0→2) 0
5 6 2 (0→2);(5→7) 2 (3→6);(3→7)
Tabla A.17: Resultados de SABS para la red ASIA con 5k casos y 50 % de casos incompletos.
La figura A.12 muestra los promedios de datos generados e inferidos por los algo-
ritmos dentro de este experimento para los valores 1 y 2 que toman los atributos del
conjunto de datos de la red ASIA, respectivamente.
Figura A.8: Promedio de datos reales e inferidos en cinco ejecuciones para los valores 1 y 2
de los atributos de la red ASIA con un conjunto de 5k casos y 10 % de casos
incompletos en el experimento 11.
107
Figura A.9: Promedio de datos reales e inferidos en cinco ejecuciones para los valores 1 y 2
de los atributos de la red ASIA con un conjunto de 5k casos y 20 % de casos
incompletos en el experimento 12.
Figura A.10: Promedio de datos reales e inferidos en cinco ejecuciones para los valores 1 y
2 de los atributos de la red ASIA con un conjunto de 5k casos y 30% de casos
incompletos en el experimento 13.
Figura A.11: Promedio de datos reales e inferidos en cinco ejecuciones para los valores 1 y
2 de los atributos de la red ASIA con un conjunto de 5k casos y 40% de casos
incompletos en el experimento 14.
108
Figura A.12: Promedio de datos reales e inferidos en cinco ejecuciones para los valores 1 y
2 de los atributos de la red ASIA con un conjunto de 5k casos y 50% de casos
incompletos en el experimento 15.
Experimento 16: Algoritmo de tres fases y red ASIA para 5k casos y 10 %
casos incompletos.
Para este experimento se genero un conjunto aleatorio de 5k casos con algunos
atributos (aleatoriamente entre 1 y 4 atributos) incompletos en el 10 % de los registros.
Posteriormente se utilizo el algoritmo de inferencia para completar el conjunto de datos
y ejecutar el algoritmo de tres fases en cinco ocasiones de manera independiente. Los
resultados de las ejecuciones se muestran en la tabla A.18. Las figuras de los experimen-
tos 11 al 15 demostraron la eficiencia del algoritmo de inferencia de conjuntos de datos
incompletos. Aun cuando en este experimento y los siguientes se realizo un proceso
similar, las graficas correspondientes no se muestran por limitaciones de espacio.
Ejecucion Arcos
C F E
1,3,4 7 1 (0→2) 1 (3→6)
2 7 1 (0→2) 0
5 6 2 (0→2);(5→7) 2 (3→6);(3→7)
Tabla A.18: Resultados del algoritmo de tres fases para la red ASIA con 5k casos y 10 % de
casos incompletos.
Experimento 17: Algoritmo de tres fases y red ASIA para 5k casos y 20 %
casos incompletos.
Para este experimento se genero un conjunto aleatorio de 5k casos con algunos
atributos (aleatoriamente entre 1 y 4 atributos) incompletos en el 20 % de los registros.
Posteriormente se utilizo el algoritmo de inferencia para completar el conjunto de datos
109
y ejecutar el algoritmo de tres fases en cinco ocasiones de manera independiente. Los
resultados de las ejecuciones se muestran en la tabla A.19.
Ejecucion Arcos
C F E
1,2,3,4 7 1 (0→2) 1 (3→6)
5 7 1 (0→2) 0
Tabla A.19: Resultados del algoritmo de tres fases para la red ASIA con 5k casos y 20 % de
casos incompletos.
Experimento 18: Algoritmo de tres fases y red ASIA para 5k casos y 30 %
casos incompletos.
Para este experimento se genero un conjunto aleatorio de 5k casos con algunos
atributos (aleatoriamente entre 1 y 4 atributos) incompletos en el 30 % de los registros.
Posteriormente se utilizo el algoritmo de inferencia para completar el conjunto de datos
y ejecutar el algoritmo de tres fases en cinco ocasiones de manera independiente. Los
resultados de las ejecuciones se muestran en la tabla A.20.
Ejecucion Arcos
C F E
1,3,4,5 7 1 (0→2) 1 (3→6)
2 7 1 (0→2) 0
Tabla A.20: Resultados del algoritmo de tres fases para la red ASIA con 5k casos y 30 % de
casos incompletos.
Experimento 19: Algoritmo de tres fases y red ASIA para 5k casos y 40 %
casos incompletos.
Para este experimento se genero un conjunto aleatorio de 5k casos con algunos
atributos (aleatoriamente entre 1 y 4 atributos) incompletos en el 40 % de los registros.
Posteriormente se utilizo el algoritmo de inferencia para completar el conjunto de datos
y ejecutar el algoritmo de tres fases en cinco ocasiones de manera independiente. Los
resultados de las ejecuciones se muestran en la tabla A.21.
110
Ejecucion Arcos
C F E
1,2,3,5 7 1 (0→2) 1 (3→6)
4 6 2 (0→2);(5→7) 2 (3→6);(3→7)
Tabla A.21: Resultados del algoritmo de tres fases para la red ASIA con 5k casos y 40 % de
casos incompletos.
Experimento 20: Algoritmo de tres fases y red ASIA para 5k casos y 50 %
casos incompletos.
Para este experimento se genero un conjunto aleatorio de 5k casos con algunos
atributos (aleatoriamente entre 1 y 4 atributos) incompletos en el 50 % de los registros.
Posteriormente se utilizo el algoritmo de inferencia para completar el conjunto de datos
y ejecutar el algoritmo de tres fases en cinco ocasiones de manera independiente. Los
resultados de las ejecuciones se muestran en la tabla A.22.
Ejecucion Arcos
C F E
1-5 7 1 (0→2) 1 (3→6)
Tabla A.22: Resultados del algoritmo de tres fases para la red ASIA con 5k casos y 50 % de
casos incompletos.
111
112
Apendice B
Ejemplo de seleccion de la red Bayesiana mas
probable
En este apendice se presenta una ejemplificacion del uso de la ecuacion 3.1 utilizada
para determinar cual de varias estructuras de red Bayesiana es mas probable de acuerdo
al conjunto de datos.
P (MS,D) = cn
∏
i=1
qi∏
j=1
(ri − 1)!
(Nij + ri − 1)!
ri∏
k=1
αijk!, (B.1)
dondec : Probabilidad de MS de ser la red Bayesiana mas probable.
qi : Numero de instanciaciones diferentes de los padres del nodo i.
ri : Numero de valores diferentes que toma el nodo i.
αijk : Numero de casos en D en los cuales xi = vik y los padres del
nodo estan en la j-esima instanciacion.
Nij =∑ri
k=1 αijk.
Caso x1 x2 x3
1 presente ausente ausente
2 presente presente presente
3 ausente ausente presente
4 presente presente presente
5 ausente ausente ausente
6 ausente presente presente
7 presente presente presente
8 ausente ausente ausente
9 presente presente presente
10 ausente ausente ausente
Tabla B.1: Conjunto de datos de ejemplo.
113
La ecuacion B.1 re-escribe de nuevo la ecuacion 3.1. En la tabla B.1 se presenta un
conjunto de datos de diez registros para tres variables aleatorias x1, x2, x3 con los cuales
se ejemplificara el uso de la ecuacion B.1. La figura B.1 muestra dos redes Bayesianas
de las cuales se desea determinar cual de ellas es mas probable de acuerdo al conjunto
de datos que se muestra en la tabla B.1.
Figura B.1: Dos estructuras de red Bayesiana alternativas para caracterizar las dependenciasprobabilısticas entre las variables aleatorias de la tabla B.1.
Primeramente debemos mencionar que para el presente ejemplo no se hace uso de
la ordenacion de nodos. Esto naturalmente altera los calculos ya que de no existir dicha
ordenacion, la cantidad de estructuras de red Bayesiana posibles para las variables de
la tabla B.1 es 25 (de acuerdo a la formula de recursividad de Robinson mostrada
en la ecuacion 2.23). Por tanto, el valor de c para la ecuacion B.1 es 125
que es la
probabilidad de cada estructura de red Bayesiana ya que estamos asumiendo que todas
son igualmente probables.
Se denominara MS1a la red Bayesiana de la figura B.1a y MS2
a la red Bayesiana
de la figura B.1b. A continuacion se presenta el calculo de P(MS1,D) y P(MS2
,D).
P (MS1,D) =
1
25
[
(
(2 − 1)!5!5!
(10 + 2 − 1)!
)(
(2 − 1)!1!4!
(5 + 2 − 1)!
)3 (
(2 − 1)!0!5!
(5 + 2 − 1)!
)
]
P (MS1,D) = 8.91 × 10−11
P (MS2,D) =
1
25
[
(
(2 − 1)!5!5!
(10 + 2 − 1)!
)(
(2 − 1)!1!4!
(5 + 2 − 1)!
)3 (
(2 − 1)!2!3!
(5 + 2 − 1)!
)
]
P (MS2,D) = 8.91 × 10−12
Dadas las suposiciones hechas anteriormente, los datos de la tabla B.1 implican
que MS1es diez veces mas probable que MS2
.
114