Doctoral dissertation

M. Arias Calleja.
Carmen: una herramienta de software libre para modelos gráficos probabilistas. Dpto. Inteligencia Artificial, UNED, Madrid, Spain, 2009.
Supervisor: Francisco Javier Díez Vegas.

248 pages, zip version (1.322 KB), BibTeX entry

pdf version (9.366 KB)

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 lambda, a parameter usually called willingness to pay wich represents the amount of money equivalent to a unit of effectiveness.