PDF de programación - PROPAGACIÓN APROXIMADA DE INTERVALOS DE PROBABILIDAD EN GRAFOS DE DEPENDENCIAS

UNIVERSIDAD DE GRANADA

E.T.S. DE INGENIERÍA

INFORMÁTICA

Departamento de Ciencias de la Computación

e Inteligencia Articial

PROPAGACIÓN APROXIMADA DE INTERVALOS DE

PROBABILIDAD EN GRAFOS DE DEPENDENCIAS

TESIS DOCTORAL

Andrés Cano Utrera

Granada, junio de
.

PROPAGACIÓN APROXIMADA DE INTERVALOS DE

PROBABILIDAD EN GRAFOS DE DEPENDENCIAS

MEMORIA QUE PRESENTA

ANDRÉS CANO UTRERA

PARA OPTAR AL GRADO DE DOCTOR EN INFORMÁTICA

JUNIO
.

DIRECTOR

SERAFÍN MORAL CALLEJÓN

DEPARTAMENTO DE CIENCIAS DE LA COMPUTACIÓN

E INTELIGENCIA ARTIFICIAL

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

UNIVERSIDAD DE GRANADA

La memoria titulada Propagación aproximada de intervalos de probabilidad en grafos

de dependencias, que presenta D. Andrés Cano Utrera para optar al grado de DOCTOR,

ha sido realizada en el Departamento de Ciencias de la Computación e Inteligencia Articial

de la Universidad de Granada ba jo la dirección del Doctor D. Serafín Moral Callejón.

Granada, junio de
.

El doctorando

El director

Andrés Cano Utrera

Serafín Moral Callejón

AGRADECIMIENTOS

En primer lugar he de mostrar mi más profundo agradecimiento al doctor

D. Serafín Moral Callejón director de esta memoria por su apoyo constante.

Sin su ayuda, esfuerzo y dedicación nunca habría sido capaz de realizar este

traba jo.

También he de mostrar mi agradecimiento a mis compañeros Silvia Acid,

Juan Huete, Luis Miguel de Campos, José Enrique Cano y Juan Francisco

Verdegay por su apoyo y el grato ambiente de traba jo que siempre han

mantenido conmigo. Quiero también agradecer al resto de miembros del

grupo de investigación de "Tratamiento de la Incertidumbre en Inteligencia

Articial" el buen compañerismo que siempre han mostrado conmigo, y su

oferta de ayuda en cualquier momento.

También a mis compañeros de la sección de la Facultad de Ciencias de

nuestro departamento quiero darles las gracias por su gran compañerismo.

Especial mención merece el profesor Javier Mateos Delgado que me ayudó

bastante a la hora de congurar el estilo de imprenta de esta memoria.

Quiero hacer también extensiva mi gratitud al resto de miembros del depar-

tamento de Ciencias de la Computación, sobre todo por su interés especial

en que esta memoria saliese adelante.

Por otra parte agradezco a la Comunidad Económica Europea y concreta-

mente al proyecto ESPRIT III DRUMS II BRA 
 por el soporte eco-

nómico, mediante una beca de investigación, para los dos primeros años de

traba jo en esta memoria. También agradezco a la CICYT por su nanción

a través del proyecto "Entorno para el desarrollo de modelos grácos pro-

babilísticos (TIC -

-C-
)" que han permitido sufragar los gastos de

continuación y nalización de esta memoria.

Por último, y no por ello de menor importancia, no puedo dejar de dar las

gracias a mi familia y en especial a mis padres y esposa por su paciencia,

comprensión, apoyo moral e interés mostrados durante todo el tiempo que

ha durado la realización de este traba jo.

A mis padres

y

a Pilar

PROPAGACIÓN APROXIMADA DE INTERVALOS DE

PROBABILIDAD EN GRAFOS DE DEPENDENCIAS

ANDRÉS CANO UTRERA

Índice General

Introducción





Conjuntos Convexos e Intervalos de Probabilidad




.


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




. Representación de la Información Mediante Conjuntos Convexos de Probabili-

dades

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




..
Esperanzas inferiores y superiores . . . . . . . . . . . . . . . . . . . . . .




.. Operaciones básicas en conjuntos convexos . . . . . . . . . . . . . . . . .



.

Información Marginal y Condicional en Conjuntos Convexos . . . . . . . . . . .



. Conjuntos convexos y restricciones lineales . . . . . . . . . . . . . . . . . . . . .



.

Intervalos de probabilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 



..
Conjuntos convexos determinados por probabilidades inferiores y supe-

riores

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


.

Información 'a posteriori': Condicionamiento

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



.

Independencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 

 Propagación de Probabilidades Imprecisas



.


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

. Axiomática para la propagación de incertidumbre en estructuras grácas . . . . 

..
Modelos de dependencias

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

. Algoritmos de Propagación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 

..
Algoritmo de eliminación de variables

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

.. Algoritmos de propagación en árboles de grupos . . . . . . . . . . . . . . 

...
Obtención de un árbol de grupos . . . . . . . . . . . . . . . . . 

i

ii

Índice General

... Obtención de un grafo triangular . . . . . . . . . . . . . . . . . 

... Construcción del árbol de grupos . . . . . . . . . . . . . . . . . 

... Asignación de las valuaciones a los grupos del árbol

. . . . . . 

... Propagación en el árbol de grupos . . . . . . . . . . . . . . . . 

... Arquitectura de Shafer y Shenoy . . . . . . . . . . . . . . . . . 

... Arquitectura HUGIN . . . . . . . . . . . . . . . . . . . . . . . 


. Algoritmos de propagación para conocimiento general

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

..
Otros algoritmos de propagación de restricciones

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

. Propagación de conjuntos convexos usando relaciones de independencia . . . . . 

..
Particularización de la axiomática para conjuntos convexos de probabi-

lidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 


.. Algoritmos de propagación para conjuntos convexos

. . . . . . . . . . . 

.. Otros algoritmos de propagación de probabilidades imprecisas ba jo in-

dependencia fuerte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 

...
Algoritmos de propagación simbólica . . . . . . . . . . . . . . . 

... Algoritmos de propagación con intervalos de probabilidad . . . 

.. Algoritmos que hacen explícita la imprecisión de las probabilidades . . . 

. Experimentación: algoritmos heurísticos para la triangulación de grafos . . . . . 

 Algoritmos de Propagación Basados en Técnicas de Optimización Combi-

natoria



.


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

. Planteamiento del Problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 

. Enfriamiento simulado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 

..


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

.. Algoritmo de enfriamiento simulado . . . . . . . . . . . . . . . . . . . .

. Algoritmos genéticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 

. Algoritmos de enfriamiento simulado aplicados a la propagación de conjuntos

convexos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 

..
Algoritmo de búsqueda de puntos con alto factor de normalización . . .


.. Algoritmo de búsqueda de puntos con alto factor de normalización por

muestreo de Gibbs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


Índice General

iii

...
Aplicación de la técnica de enfriamiento simulado

. . . . . . .


.. Algoritmo de búsqueda de puntos con alto valor de t

y t

. . . . . . . .







...
Aplicación de la técnica de enfriamiento simulado

. . . . . . .




.. Algoritmo de búsqueda de puntos con alto valor de

y

. . . .



t

t






t

+t

t

+t











...
Aplicación de la técnica de enfriamiento simulado

. . . . . . .



.. Evaluación de los algoritmos . . . . . . . . . . . . . . . . . . . . . . . . .



...
Primer grupo de tests: Obtención de puntos con una combina-

ción de todos los algoritmos . . . . . . . . . . . . . . . . . . . .



...

Segundo grupo de tests: Obtención de puntos con el algoritmo

 usando enfriamiento simulado . . . . . . . . . . . . . . . . . .



. Algoritmos genéticos aplicados a la propagación de conjuntos convexos . . . . .



..
Búsqueda de puntos con alto factor de normalización . . . . . . . . . . .


..
.
Evaluación del algoritmo . . . . . . . . . . . . . . . . . . . . .


.. Búsqueda de todos los puntos extremos mediante la combinación de un

algoritmo genético y un algoritmo heurístico . . . . . . . . . . . . . . . .


. Conclusiones

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


 Árboles de Probabilidad e Independencias Asimétricas




.


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


.

Independencias asimétricas y árboles de probabilidad . . . . . . . . . . . . . . .


. Uso de árboles de probabilidad en la propagación en redes causales . . . . . . .


..
Construcción del árbol . . . . . . . . . . . . . . . . . . . . . . . . . . . .



.. Operaciones con árboles de probabilidad . . . . . . . . . . . . . . . . . .


...
Combinación de árboles en forma exacta . . . . . . . . . . . . .


... Marginalización en árboles de forma exacta . . . . . . . . . . .


... Combinación y Marginalización aproximadas . . . . . . . . . .


. Evaluación experimental

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


. Conclusiones

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


 Uso de Árboles de Probabilidad para Representar Intervalos de Probabili-

dad




.


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