PDF de programación - DISEÑO Y VALIDACIÓN DE NUEVOS ALGORITMOS PARA EL TRATAMIENTO DE GRAFOS DE DEPENDENCIAS

UNIVERSIDAD DE GRANADA

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

Departamento de Ciencias de la Computación

e Inteligencia Artificial

DISE ÑO Y VALIDACI ÓN DE NUEVOS

ALGORITMOS PARA EL TRATAMIENTO

DE GRAFOS DE DEPENDENCIAS

TESIS DOCTORAL

Luis Daniel Hernández Molinero

Granada, Marzo de 1995
Esta Tesis Doctoral fue defendida el

19 de Mayo de 1995

obteniendo la calificación de

APTO CUM LAUDEM POR UNANIMIDAD

DISE ÑO Y VALIDACI ÓN DE NUEVOS

ALGORITMOS PARA EL TRATAMIENTO DE

GRAFOS DE DEPENDENCIAS

Luis Daniel Hernández Molinero

TESIS DOCTORAL

DIRECTORES:

Serafín Moral Callejón

Manuel Jorge Bolaños Carmona

Marzo 1995

Departamento de Ciencias de la Computación e Inteligencia Artificial

E.T.S. Ingeniería Informática

Universidad De Granada

La memoria titulada

Diseño y Validación de Nuevos Algoritmos para el

Tratamiento de Grafos de Dependencias.

que presenta D. Luis Daniel Hernández Molinero, para optar al grado de
Doctor en Matemáticas (especialidad en Ciencias de la Com-
putación), ha sido realizada en el Departamento de Ciencias de la Com-
putación e Inteligencia Artificial de la Universidad de Granada, bajo la
dirección del Dr. D. Serafín Moral Callejón y el Dr. D. Manuel Jorge
Bolaños Carmona.

Granada, Marzo de 1995.

Fdo: D. Luis Daniel Hernández Molinero.

Fdo: Dr. D. Serafín Moral Callejón.

Fdo: Dr. D. Manuel Jorge Bolaños Carmona.

A María Jesús y mi Familia.

Agradecimientos.

Quiero mostrar desde aquí mi agradecimiento y mi mas cordial saludo, y abrazo,
a todas aquellas personas que han colaborado, de algún u otro modo, al desarrollo
de esta memoria.

En primer lugar mi agradecimiento a los doctores Serafín Moral y Manuel Jorge
Bolaños, por sus consejos, apoyo, confianza y dirección durante el desarrollo de
esta memoria. Al Dr. Miguel Delgado Calvo-Flores que gracias a él pude conocer
a mi estimado compañero y amigo el Dr. Fernando Martín, que colaboró con su
ayuda y constancia en el término de esta tesis.

Igualmente agradezco al Dr. Jose Enrique Cano su apoyo, paciencia y colabora-
ción para llevar a buen fin el desarrollo informático de esta memoria. A Andres
Cano por sus sugerencias y ayudar en la salida de algunos resultados de esta
memoria, y, en general, a todos aquellos miembros del departamento de Ciencias
de la Computación e Inteligencia Artificial de la Universidad de Granada que,
de alguna forma, se interesaron por su desarrollo.

A mis compañeros de departamento el Dr. J. Manuel Cadenas, Fernando Jiménez,
Manuel Sánchez y Antonio Gómez por prestarme su tiempo y ayuda cuando la
necesité, y a todos mis compañeros del departamento de Informática y Sistemas
de la Universidad de Murcia, al que pertenezco, y que siguieron y se preocuparon
por la evolución de esta tesis en el grato ambiente de trabajo que formaron entre
todos.

En especial no puedo olvidar a mi esposa Maria Jesús, por comprender las situa-
ciones difíciles, su ayuda constante y su apoyo continuo que nunca faltó. Igual-
mente a mis padres por su gran apoyo, seguimiento y preocupación. Por último
a mis hermanos, cuñados y abuelas por su interés y los buenos momentos que
me hicieron pasar durante el desarrollo de esta memoria.

DISE ÑO Y VALIDACI ÓN DE NUEVOS

ALGORITMOS PARA EL TRATAMIENTO DE

GRAFOS DE DEPENDENCIAS

Luis Daniel Hernández Molinero

Contenidos

INTRODUCCI ÓN

Resumen Histórico y Bibliografía . . . . . . . . . . . . . . . . . . . . . . . . .

Objetivos de la Memoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Descripción por Capítulos . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 EL MODELO PROBABILÍSTICO

1.1 Necesidad de Modelizar la Incertidumbre

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

1.2 Aproximaciones a la Incertidumbre . . . . . . . . . . . . . . . . . . . . . . . .

1.3 Modelos de Dependencias. Representación.

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

1.3.1 Modelos de depedencias . . . . . . . . . . . . . . . . . . . . . . . . . .

1.3.2 Representación de modelos de dependencias . . . . . . . . . . . . . . .

1.4 El Modelo Probabilístico de Dependencias . . . . . . . . . . . . . . . . . . . .

1.4.1 Modelos probabilísiticos . . . . . . . . . . . . . . . . . . . . . . . . . .

1.4.2 Representación del modelo probabilístico . . . . . . . . . . . . . . . .

1.5 Métodos Exactos de Propagación . . . . . . . . . . . . . . . . . . . . . . . . .

1.5.1 Algoritmo para poliárboles

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

1.5.2 Métodos basados en condicionamiento . . . . . . . . . . . . . . . . . .

1.5.2.1 Método del condicionamiento global. . . . . . . . . . . . . . .

1.5.2.2 Método del condicionamiento local.

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

9

9

13

14

17

17

19

20

21

22

26

26

29

32

33

38

40

44

2

CONTENIDOS

1.5.3 Diagramas de influencia probabibilísticos

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

1.5.4 Métodos clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.5.4.1 Algoritmo de Lauritzen y Spiegelhalter.

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

1.5.4.2 Algoritmo Hugin.

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

1.5.4.3 Algoritmo Clustering de Shachter, Andersen y Szolovits.

. .

1.5.5 Ventajas e inconvenientes de los métodos exactos.

. . . . . . . . . . .

1.6 Métodos Aproximados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.6.1 Métodos basados en propagación hacia delante . . . . . . . . . . . . .

1.6.1.1 Método del muestreo lógico . . . . . . . . . . . . . . . . . . .

1.6.1.2

Integración de evidencia.

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

1.6.1.3 Ponderación de la evidencia.

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

1.6.1.4 Muestreo por importancia de Shachter y Peot.

. . . . . . . .

1.6.2 Métodos basados en cadenas De Markov . . . . . . . . . . . . . . . . .

1.6.2.1 Método de simulación estocástica o directa . . . . . . . . . .

1.6.2.2 Muestreadores de Gibbs . . . . . . . . . . . . . . . . . . . . .

1.6.3 Ventajas e inconvenientes de los métodos aproximados . . . . . . . . .

1.7 ANEXO. Algoritmos Complementarios.

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

1.7.1 Algoritmos utilizados en condicionamiento global . . . . . . . . . . . .

1.7.2 Algoritmos utilizados para el condicionamiento local. . . . . . . . . . .

1.7.3 Algoritmos utilizados por el método clustering de Lauritzen y Spiegel-
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

halter

2 EL PROBLEMA DE LA TRIANGULACI ÓN

2.1

Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2 Técnicas Más Conocidas de Triangulación . . . . . . . . . . . . . . . . . . . .

2.2.1 Métodos teóricos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46

50

52

56

59

63

65

66

67

69

69

70

71

71

73

76

77

77

79

80

83

83

84

86

CONTENIDOS

2.2.2 Métodos heurísticos determinísticos.

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

2.2.3 Métodos heurísticos estocásticos.

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

2.3 Nuevas Técnicas Heurísticas Determinísticas de Triangulación . . . . . . . . .

2.3.1 Consideraciones sobre los métodos conocidos.

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

2.3.2 Nuevos métodos y clasificación general.

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

2.4 Nuevas Técnicas Estocásticas de Triangulación Basadas en Programas Evolu-
tivos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.5 Un Método de Mejora General para el Problema de la Triangulación. . . . . .

3

86

88

89

89

90

93

99

2.6 Experimentación Comparativa y Resultados.

. . . . . . . . . . . . . . . . . . 103

2.6.1 Métodos considerados. . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

2.6.2 Redes consideradas para la experimentación.

. . . . . . . . . . . . . . 105

2.6.3 Datos contrastados.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

2.6.4 Resultados y su evaluación.

. . . . . . . . . . . . . . . . . . . . . . . . 107

2.7 Conclusiones y Estudios Futuros

. . . . . . . . . . . . . . . . . . . . . . . . . 109

2.8 ANEXO. Pseudocódigo Para Heurísticas Simples Iterativas.

. . . . . . . . . . 112

2.9 ANEXO. Tablas de Resultados y Gráficas Comparativas.

. . . . . . . . . . . 115

3 MUESTREO POR IMPORTANCIA

133

3.1

Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

3.2 Notación y Definiciones

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

3.3 Muestreo por Importancia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138

3.3.1 Muestreo por importancia aplicado a redes causales

. . . . . . . . . . 140

3.3.2 El algoritmo

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

3.3.3 Algunos casos particulares de funciones de selección de interés

. . . . 144

3.4 Estimación de P (xI|xE) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148

3.4.1 Algoritmos conocidos como casos particulares . . . . . . . . . . . . . . 149

4

CONTENIDOS

3.4.2 Nuevos algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152

3.5 Establecimiento del Orden en las Funciones de Selección . . . . . . . . . . . . 154

3.5.1 La entropía de Shanon como criterio inicial

. . . . . . . . . . . . . . . 154

3.5.2 La función de transmisión de información de Shanon como criterio . . 159

3.5.3 Establecimiento de órdenes a priori . . . . . . . . . . . . . . . . . . . . 162

3.6 Precomputación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165

3.7 Evaluación Experimental . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166

3.7.1 Experimentos y muestreadores considerados . . . . . . . . . . . . . . . 166

3.7.2 Algoritmos contrastados . . . . . . . . . . . . . . . . . . . . . . . . . . 167

3.7.3 Grafos considerados

. . . . . . . . . . . . . . . . . . . . . . . . . . . . 168

3.7.4 Datos contrastados .