Master thesis

Miguel A. Artaso Landa.
An empirical comparison of Influence Diagrams algorithms. Dept. Artificial Intelligence. UNED, Madrid, Spain, 2014.
Supervisors: Prof. Manuel Luque Gallego, Prof. Francisco Javier Díez Vegas.

76 pages. PDF (4.750 KB), BibTeX entry.

Abstract

Probabilistic Graphical Models (PGMs) are widely used in many domains when reasoning with uncertainty. They are used to obtain the maximum expected utility and the optimal policy—the best decisions—in different scenarios. When dealing with real-world problems, the model built can be quite complex. As not all the algorithms perform the inference with the same efficiency, it is important to know which one is better to apply depending on the circumstances. Therefore it is important to compare the performance of the those algorithms for different models.

In this Master Thesis we compare four inference algorithms for influence diagrams (IDs): variable elimination, arc reversal, strong junction tree, and the conversion into a LIMID. For our experiments we have used OpenMarkov, an open software tool developed by the Research Centre for Intelligent Decision-Support Systems (CISIAD) of the UNED. The first algorithm was already implemented in this tool; the other three have been implemented by the author of this thesis. We have also programmed the generation of different IDs that have been used to compare the algorithms. We then have confronted the computational time and the memory used by the algorithms when facing these IDs and analysing the results of the experiments we give some recommendations about which algorithm to use depending on the structure of the model.