PDF de programación - Carmen: una herramienta de software libre para modelos gráficos probabilistas

- TESIS DOCTORAL -

Carmen: una herramienta de software libre

para modelos gráficos probabilistas

Manuel Arias Calleja

Licenciado en Informática

Universidad Politécnica de Madrid

Departamento de Inteligencia Artificial

Universidad Nacional de Educación a Distancia

Septiembre de 2009

2

- TESIS DOCTORAL -

Departamento de Inteligencia Artificial

Universidad Nacional de Educación a Distancia

Carmen: una herramienta de software libre

para modelos gráficos probabilistas

Por: Manuel Arias Calleja

Licenciado en Informática

por la Universidad Politécnica de Madrid

Director de la Tesis: Francisco Javier Díez Vegas

Tribunal calificador

Presidente: Prof. Dr. Enrique Castillo Ron

Vocal 1: Prof. Dr. Pedro Larrañaga Múgica

Vocal 2: Prof. Dr. Andrés Cano Utrera

Vocal 3: Prof. Dr. Hilbert Johan Kappen

Secretaria: Profa Dra. Carmen Lacave Rodero

4

5

A mi hermana, Isabel

6

Resumen

En las últimas dos décadas se ha dado una proliferación de herramientas para la
construcción, manual o automática de Modelos Gráficos Probabilistas (MGPs). Las
herramientas disponibles están limitadas en su mantenibilidad, robustez y eficiencia.
Nuestra contribución principal es una nueva herramienta, llamada Carmen, que se ha
desarrollado desde cero y está basada en los principios de la ingeniería del software.
Carmen tiene un diseño detallado, una documentación y un conjunto de pruebas
sistemáticas para minimizar la presencia de errores.

El desarrollo de esta herramienta ha traido como consecuencia varias contribuciones
secundarias: primero, un nuevo patrón de diseño llamado permiso-ejecución, que permite
realizar operaciones en modelos complejos con múltiples restricciones; segundo, hemos
desarrollado un nuevo diseño, que desacopla los diferentes conceptos que constituyen un
MGP en partes distintas, permitiendo un mantenimiento posterior más sencillo; tercero,
hemos desarrollado una librería genérica de grafos que puede ser utilizada en otras
herramientas.

Nuestra segunda contribución principal es un método nuevo que mejora
significativamente el rendimiento en las operaciones básicas sobre potenciales de
variables discretas, tales como suma, multiplicación, marginalización y división. Hemos
demostrado también,
tanto teórica como empíricamente, que algunas operaciones
compuestas pueden ser realizadas de un modo mucho más eficiente si se ejecutan de
forma conjunta en lugar de secuencial. Esta mejora en las operaciones de bajo nivel nos
lleva a una reducción en el tiempo y en el espacio necesarios en algoritmos de alto nivel,
tales como eliminación de variables, propagación en árboles de cliques, etc.

Finalmente, la tercera contribución principal es un nuevo método para el análisis de
coste-efectividad. Los métodos actuales no pueden tratar con problemas que involucran
más de una decisión. Por este motivo, hemos desarrollado un nuevo método de
coste-efectividad, que puede ser aplicado tanto en árboles de decisión como en diagramas
de influencia. Nuestro método es capaz de manejar varias decisiones y devuelve la
estrategia óptima como un conjunto de intervalos para λ, un parámetro habitualmente
llamado disponibilidad a pagar, que representa la cantidad de dinero equivalente a una
unidad de efectividad.

II

III

Abstract

In the last two decades there has been a proliferation of computer tools for the
construction either manual or automatic of Probabilistic Graphical Models (PGMs). The
tools currently available are limited in their maintainability, robustness and efficiency. Our
main contribution is a new tool, called Carmen, which has been developped from scratch
and is based on the principles of software engineering. Carmen has detailed design, a
documentation, and a batch of systematic tests aimed at minimizing the presence of errors.
The development of this software tool has led to several secondary contributions: first,
a new design pattern called permission-execution, which permits to perform operations
on complex models with multiple constraints; second, we have developped a new design
which decouples the different concepts that make up a PGM in different parts, allowing
subsequent maintenance much easier; third, we have developped a general purpose graph
library that can be used in other tools.

Our second main contribution is a new method that significantly improves the
performance of basic operations on potentials of discrete variables such as addition,
multiplication, marginalization and división. We have also proved, theoretically and
empirically, that some compound operations can be performed much more efficiently if
they are executed all together rather tan sequentially. This improvement in the low-level
operations leads to a reduction in the time and space required by high-level algorithms,
such as variable elimination, clique tree propagation, etc.

Finally, the third main contribution is a new method for cost-effectiveness analysis.
Current methods can not deal with problems that involve more than one decision. For this
reason, we have developped a new method of cost-effectiveness, which can be applied
to both decision trees and influence diagrams. Our method is capable of handling several
decisions and returns the optimal strategy as a set of intervals for λ, a parameter usually
called willingness to pay wich represents the amount of money equivalent to a unit of
effectiveness.

IV

Índice general

.
.
.
.

.
.
.
.

.
.
. .

.
.
Resumen .
. .
Abstract
.
Agradecimientos
Conclusions .
.

.

.
.
. .
.
.

. .
.
.

.
.
. .
.
.

Introducción

.
.
Motivación .
. .
Objetivos
. .
Metodología .
.
.
Organización de la tesis .

.
.
. .
.
.

.
.
. .
.
.

I Preliminares

1. Estado de la técnica

I
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
III
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
IX
. . . . . . . . . . . . . . . . . . . . . . . . . . . . XI

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

1
1
2
3
5

7

9
9
9
12
14
31
32
32
33

1.1.

1.2.

.

.

.

.

.

Introducción a los MGPs . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.1. Grafos .
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.2. Probabilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.3. MGPs .
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.4. Otros MGPs para análisis de decisiones . . . . . . . . . . . . . .
Ingeniería del software . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.1. Paradigmas de desarrollo . . . . . . . . . . . . . . . . . . . . . .
1.2.2. Ciclo de vida . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.

V

VI

II Nuevos algoritmos

2. Operaciones con potenciales de variables discretas

ÍNDICE GENERAL

41

43
43
45
45
47
47
50
53
53
54
56
58
58
64
66
67
69

.

.

.

.

.

.

.

Introducción .

2.1.
. . . . . . . . . . . . . . . . . . . . . . . . .
2.2. Desplazamientos acumulados . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1. Desplazamientos y posiciones . . . . . . . . . . . . . . . . . . .
2.2.2. Ejemplo de desplazamientos acumulados
. . . . . . . . . . . . .
2.2.3. Cálculo de los desplazamientos acumulados . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
2.2.4. Complejidad computacional
2.3. Operaciones con desplazamientos acumulados . . . . . . . . . . . . . . .
2.3.1. Marginalización de potenciales . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
2.3.2. Multiplicación de potenciales
2.3.3. Proyección (condicionamiento)
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . .
2.4.1. Multiplicación simultanea de varios potenciales . . . . . . . . . .
2.4.2. Multiplicación y marginalización . . . . . . . . . . . . . . . . .
2.5. Trabajos relacionados e investigacíón futura . . . . . . . . . . . . . . . .
2.6. Conclusiones
. . . . . . . . . . . . . . . . . . . . . . . . .
2.7. Apéndice: Demostraciones . . . . . . . . . . . . . . . . . . . . . . . . .

2.4. Otras mejoras .

. .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

3.1.

3. Análisis de coste-efectividad
.

Introducción .
. . . . . . . . . . . . . . . . . . . . . . . . .
3.1.1. Tipos de análisis de coste-resultados . . . . . . . . . . . . . . . .
3.1.2. Comparación de intervenciones en el ACE . . . . . . . . . . . .
3.1.3. Método estándar de ACE probabilista . . . . . . . . . . . . . . .
3.2. Método para el ACE con varias decisiones . . . . . . . . . . . . . . . . .
3.2.1. Árboles de decisión . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.2. ACE con diagramas de influencia . . . . . . . . . . . . . . . . .

73
73
74
76
80
85
86
95
. . . . . . . . . . . . . . . . . . . . . . . . . 103

3.3. Discusión .

. .

. .

.

.

.

.

III Herramienta Carmen

105

4. Visión general de la herramienta Carmen

107
Introducción .
. . . . . . . . . . . . . . . . . . . . . . . . . 107
4.1.1. Otras herramientas de código abierto para MGPs . . . . . . . . . 108

4.1.

.

.

.

.

.

.

.

ÍNDICE GENERAL

VII

.

.

4.2. Especificaciones .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
4.2.1. Requisitos funcionales . . . . . . . . . . . . . . . . . . . . . . . 112
. . . . . . . . . . . . . . . . . . . . . 113
4.2.2. Requisitos no funcionales
4.3. Diseño arquitectónico . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
. . . . . . . . . . . . . . . . . . . . . . 116

4.3.1. Organización estructural

.
.

.
.

.
.

.
.

5. Grafos y modelos gráficos probabilistas

Introducción .
.

5.1.
5.2. Grafos .

121
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
5.2.1. Requisitos de la biblioteca de grafos . . . . . . . . . . . . . . . . 122
5.2.2. Modelo de análisis de grafos . . . . . . . . . . . . . . . . . . . .