PDF de programación - MÉTODOS LOCALES Y DISTRIBUIDOS PARA LA CONSTRUCCIÓN DE REDES DE CREENCIA ESTÁTICAS Y DINÁMICAS

UNIVERSIDAD DE GRANADA

E.T.S. DE INGENIERÍA

INFORMÁTICA

Departamento de Ciencias de la Computación

e Inteligencia Artificial

MÉTODOS LOCALES Y DISTRIBUIDOS PARA
LA CONSTRUCCIÓN DE REDES DE CREENCIA

ESTÁTICAS Y DINÁMICAS

TESIS DOCTORAL

José Miguel Puerta Callejón

Granada, Septiembre de 2001

MÉTODOS LOCALES Y DISTRIBUIDOS PARA LA

CONSTRUCCIÓN DE REDES DE CREENCIA ESTÁTICAS Y

DINÁMICAS

MEMORIA QUE PRESENTA

JOSÉ MIGUEL PUERTA CALLEJÓN

PARA OPTAR AL GRADO DE DOCTOR EN INFORMÁTICA

SEPTIEMBRE 2001

DIRECTOR

LUIS MIGUEL DE CAMPOS IBÁÑEZ

DEPARTAMENTO DE CIENCIAS DE LA COMPUTACIÓN

E INTELIGENCIA ARTIFICIAL

E.T.S. DE INGENIERÍA INFORMÁTICA

UNIVERSIDAD DE GRANADA

La memoria titulada Métodos Locales y Distribuidos para la Construcción de
Redes de Creencia estáticas y dinámicas, que presenta D. José Miguel Puerta
Callejón para optar al grado de DOCTOR, ha sido realizada en el Departamento de
Ciencias de la Computación e Inteligencia Artificial de la Universidad de Granada
bajo la dirección del Doctor D. Luis Miguel de Campos Ibáñez.

Granada, Septiembre de 2001

El doctorando

El director

José Miguel Puerta Callejón

Luis Miguel de Campos Ibáñez

AGRADECIMIENTOS

En primer lugar he de mostrar mi más sincero agradecimiento al doctor Luis Miguel de
Campos Ibáñez, director de esta memoria, por el apoyo, los consejos, el estímulo que he
recibido en todo momento y sobre todo por su amistad, forjada a lo largo de estos años
de colaboración. Tengo clarísimo que sin su esfuerzo, ayuda y dedicación este trabajo
nunca hubiese visto la luz.

También quiero dar las gracias a S. Acid, A. Cano, J. M. Fernández, J. Huete, S. Moral
y al resto de miembros del grupo de investigación UTAI del departamento de Ciencias
de la Computación e I.A. de la Universidad de Granada su interés y su apoyo a lo largo
de estos años. Especialmente quiero agradecerle a Juan Huete su enorme interés, su
inestimable apoyo y su gran humanidad, gracias Juan por aguantarme todos estos años.
Quiero extender este agradecimiento al resto de miembros del Departamento de Ciencias
de la Computación e I.A. que de alguna manera se interesaron por la evolución de este
trabajo.

Cómo no, agradecer a mis compañeros de departamento F. Cuartero, P. Cuenca, J. A.
Gámez, A. Garrido, R. García, P. González, F. J. Gómez, J. A. Guerrero, M. López,
T. Olivares, F. J. Quiles, J.L. Sánchez, V. Valero y F. J. Vigo su apoyo, comprensión e
interés que mostraron a lo largo del desarrollo de esta memoria. No obstante, me gustaría
dar las gracias especialmente a J. A. Guerrero por la desinteresada ayuda que siempre me
ha ofrecido; a F. Cuartero, A. Garrido, F. J. Quiles y V. Valero por la enorme confianza
que siempre han depositado en mí y por sus consejos, siempre sabios.

Sin embargo, no tengo por más que destacar a José Antonio Gámez, compañero y sobre
todo amigo, amigo con mayúsculas; con compañeros como José Antonio de verdad que
da gusto tanto trabajar como ir a tomar alguna cosa en algún lugar. Gracias Jose, por
haber compartido todos estos años conmigo y esperemos que sigamos compartiendo por
muchos años más. También he de hacer mención aparte a Teresa Olivares, mi cuñada,
por estar siempre ahí, nunca poner mala cara y siempre estar dispuesta a echar una mano.

Quiero hacer extensiva mi gratitud al resto de mis compañeros del departamento de In-
formática de la Universidad de Castilla-La Mancha.

Por último, y muy especialmente, quiero dar las gracias a mi esposa, Elena, por su com-
prensión infinita, apoyo infatigable y enorme calidad humana. Espero compensarte algún
día todo este tiempo. A mi hija Ana, gracias por tus ganas de vivir y por recordarnos
lo que es más importante. A mis padres, por confiar en su “primogénito”, a mis abue-
los, hermanos, cuñados y sobrinos; y al resto de mi familia por ser todos como sois, no
cambiéis nunca.

AElenayAna.
Amifamilia.

MÉTODOS LOCALES Y DISTRIBUIDOS PARA LA

CONSTRUCCIÓN DE REDES DE CREENCIA ESTÁTICAS Y

DINÁMICAS

JOSÉ MIGUEL PUERTA CALLEJÓN

Índice General

Introducción

1 Redes de Creencia, Algoritmos de Aprendizaje y Redes de Creen-

2 Métodos de Búsqueda Local para el Aprendizaje de Redes de

Introducción . .

Creencia
. . .
2.1
2.2 Búsqueda en Entorno Variable . . .
. . .

2.2.1 Otras extensiones . . .

. . . .

. . . .

. . . .
. . . .
. . . .

. . . .
. . . .
. . . .

. . . .
. . . .
. . . .

. . . .
. . . .
. . . .

.
.
.

i

cia Dinámicas
1.1
. . . .
1.2 Redes de Creencia . . .

Introducción . .

1.3 Algoritmos de Aprendizaje . .

. . .

. . . .

. . . .

. . . .
. . . .

. . . .
. . . .

. . . .
. . . .

. . .
. . .

. . . .

. . . .

. . . .

. . . .
. . . .

. . . .
. . . .
. . . .

. . . .
. . . .
. . . .

cional .
. . .
1.3.1.1 Algoritmo PC . .

. . . .
. . . .
. . . .
. . . .
1.2.1 Axiomática de Independencia . . .
. . . .
1.2.2 Redes de Creencia como Modelos de Dependencias . . . .
. . . .
1.3.1 Algoritmos basados en relaciones de independencia condi-
. . . .
. . . .
1.3.2 Algoritmos basados en optimización de una medida . . . .
1.3.2.1 Medidas de Calidad de una Red de Creencia . .
1.3.2.2 Medidas Bayesianas . . .
. . . .
1.3.2.3 Medidas de Mínima Longitud de Descripción .
1.3.2.4 Medidas de Información .
. . . .
. . . .
1.3.2.5 Algoritmos de Búsqueda
1.3.3 Un algoritmo Híbrido basado en conjuntos mínimos d-se-
. . . .
. . . .
. . . .
. . . .
. . . .

. . . .
. . . .
1.4.1
. . . .
1.4.2 Conceptos básicos. Definición formal del modelo .
1.4.3 Aprendizaje de redes de creencia dinámicas . . . .

paradores. BENEDICT.

. . . .
. . . .
. . . .

. . . .
. . . .
. . . .

. .
. . .
. . .

. . . .
. . . .

. . . .
. . . .

. . . .

. . . .

1.4 Redes de Creencia Dinámicas
. . . .

Introducción .

.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.

1

9
9
10
11
13
19

19
21
25
26
28
28
29
30

33
36
36
41
43

45
45
47
49

ii

Índice General

. .

.

.

. . .

. . .

. . .

. . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

rigidos Acíclicos . . .

2.3 Métodos de Búsqueda Local en el espacio de Grafos Dirigidos Ací-
clicos
. . . .
2.3.1 Un Algoritmo de Búsqueda Local híbrido con Reinicio ba-
sado en Tests de Independencia Condicional y Conjuntos
Mínimos D-separadores
. . . .
2.3.2 Búsqueda en Entorno Variable en el espacio de Grafos Di-
. . . .
. . . .

. . . .
2.4 Métodos de Búsqueda Local en el espacio de Órdenes . . .

.
.
2.4.1 Método de Ascensión de Colinas en el espacio de Órdenes .
2.4.2 Búsqueda en Entorno Variable en el espacio de Órdenes
.
.
2.4.3 El Problema del Punto de Inicio en la Búsqueda. Heurística
. . . .
. . . .
. . . .
. . . .
2.6 Redefiniendo la vecindad para una ascensión de colinas en el espa-
. . . .
. . . .

. . . .
. . . .
2.5.1 Descripción de los experimentos . . .
2.5.2 Análisis de los experimentos .
. . . .

. . . .
2.5 Experimentación y Conclusiones . . .

cio de grafos dirigidos acíclicos
2.6.1 Análisis experimental .

. . . .
. . . .
. . . .
. . . .

. . .
. . .
. . .
. . .

. . . .
. . . .

. . . .
. . . .

. . .
. . . .

K2SN . .

. . .
. . .

. . . .

. . .

. . .

51

52

56
59
63
66

68
73
73
77

89
91

95
95
96
99

.
.
.
.

.
.

.
.
.

3 Métodos de Búsqueda Distribuidos para el Aprendizaje de Re-

. . .

. . .

. . . .

. . . .

. . . .

. . . .

. . .
. . .

. . . .
. . . .

Introducción . . .

néticos paralelos. El Modelo de Islas

des de Creencia
3.1
. . . .
3.2 Búsqueda en Entorno Variable Distribuida . .

diante Colonias de Hormigas .
. . . .
3.3.1 El Sistema de Colonias de Hormigas .

. . . .
. . . .
3.2.1 Esquema de inicialización de las búsquedas distribuidas
.
3.2.2 Un modelo de colaboración inspirado en los Algoritmos Ge-
. . . .
3.3 Aprendizaje Cooperativo y Distribuido de Redes de Creencia me-
. . . .
. . . .
El Sistema de Hormigas para el problema del via-
jante de comercio .
. . . .
El Sistema de Colonias de Hormigas para el pro-
. . . .
blema de la asignación cuadrática . . . .
3.3.1.3
Sistema Híbrido de Hormigas . .
. . . .
. . . .
3.3.1.4 Algoritmo General para Optimización basado en
. . . .
3.3.2 Aprendizaje de Redes de Creencia mediante Colonias de
. . . .
3.3.3 Aprendizaje de Redes de Creencia mediante Colonias de
. .

Hormigas en el espacio de Grafos Dirigidos Acíclicos

Hormigas en el espacio de Órdenes

Colonias de Hormigas . . .

. . . .
. . . .

. . .
. . .

3.3.1.1

3.3.1.2

. . . .

. . . .

. . . .

. . . .

. . .

. . .

. . .

.

. 103

. 106
. 107

. 107

. 110
. 110

. 112

. 113

. 120

Índice General

tema de Colonias de Hormigas . . .
3.5 Experimentación y Conclusiones . .

3.4 Un Sistema Distribuido Híbrido entre la Búsqueda VNS y el El Sis-
. . . .
. . . .
. . . .
. . . .

. . . .
. . . .
3.5.1 Descripción de los experimentos . .
3.5.2 Análisis de los resultados . .
. . . .

. . . .
. . . .
. . . .
. . . .

. . . .
. . . .
. . . .
. . . .

iii

. 122
. 125
. 125
. 125

4 Aprendizaje de Relaciones Temporales en Redes de Creencia

. . . .

. . .

. . .

. . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

porales .

. . . .
. . . .

. . . .
. . . .

Introducción . .

. . . .
.
. . . .
. . . .

4.3 Algoritmos locales basados en optimización de métricas

4.4 Algoritmos basados en relaciones de independencia condicional

4.3.1 Algoritmo TeReK2 . .
. . .
4.3.2 Algoritmo TeReBenedict . .

Dinámicas
. . . .
4.1
4.2 Definición formal del problema del aprendizaje de relaciones tem-
. . . .
. . . .
. . . .
. . . .
.
4.4.1 Algoritmo TeRePC . .
. . . .
4.4.2 Algoritmo de aprendizaje de relaciones temporales basado
. . . .
4.4.3 Algoritmo de aprendizaje de relaciones temporales basado
. . . .
. . . .
. . . .
. . . .
4.5.1 Refinando mediante la métrica BIC . . . .
. . . .
4.5.2 Refinando mediante el conjunto mínimo d-separador . . .
. . . .
. . . .

. . . .
4.4.4 Modificaciones de los Algoritmos ART y FART . .
. . . .
. . . .

4.6 Aprendizaje de redes de creencia dinámicas simples . . . .
4.7 Experimentación y Conclusiones . .
. . . .

en el subconjunto Manto de Markov parcial . . . .

en el con