New methods and data structures for evaluating influence diagrams

This thesis addresses some drawbacks related to the evaluation of influence diagrams (ID), which is a class of probabilistic graphical model intended to solve decision problems. For that, different modifications in the classical ID framework are proposed. In particular, we propose the use of new data structures for representing the qualitative and quantitative information. Additionally, several algorithms using such data structures are proposed as well. In particular, the addressed problems are: - High computational cost: the intermediate potentials generated during the evaluation of IDs may be extremely large. As a consequence, the evaluation has a high computational cost in terms of memory space and time. For that, we propose the use of binary trees (BTs) instead of tables for representing and managing the potentials involved in IDs. The advantage of BTs resides in their capability of representing general forms of independence that cannot be structurally encoded by IDs. This is possible because some identical values in the potential can be grouped into a single one. This enhanced capability makes the representation of potentials even more compact. As this forms of Independence are quite frequent in large IDs representing real world decision problems, their evaluation should be more efficient. Additionally, if BTs are still extremely large, they can be pruned leading to faster but approximate solutions. We also explore different alternatives for reducing the computational cost of the evaluation assuming that the potentials are represented as tables. In particular, we propose different algorithms that aim to optimize the order the combinations and marignalizations with the potentials. - Inefficient evaluation of asymmetric decision problems: in many real decision problems, called asymmetric, the possible outcomes and decision options for some variables may depend on the past. For example, let us consider a decision problem where you have the option of doing a test, then any possible result for this test is meaningless if you have decided not doing it. An important drawback of IDs is related to their inability for efficiently representing and evaluating them. This happens because potentials might contain some impossible configurations (due to the asymmetries of the problem) that are not relevant for solving the decision problem. In this dissertation we propose the use BTs also for identifying these impossible configurations and avoiding unnecessary computations. - Incapacity to express imprecision: in the classical ID formalism, potentials are functions that assigns sharp (i.e., precise) values to each possible combination of states for a set of variables (e.g., the probability of X = x1 is 0.75). This might be an issue with real models, whose potentials are typically obtained from expert judgements or partially reliable data. We propose replacing the sharp values of potentials involved in an ID with intervals. Such generalization is called interval-valued potentials. An ID with this kind of potentials is an interval-valued ID and it can be seen as a collection of classical (i.e., precise) IDs consistent with the interval constraints. We also propose extensions of some of the classical algorithms for evaluating IDs with interval-valued potentials. We show that the best results are obtained with those using linear programming techniques.Tesis Univ. Granada. Programa Oficial de Doctorado en Tecnologías de la Información y la ComunicaciónEsta tesis doctoral ha sido financiada por el Ministerio de Economía y Competitividad y por el Fondo Europeo de Desarrollo Regional (FEDER) con los proyectos TIN2010-20900-C04-01, TIN2013-46638-C3-2-P y TIN2016-77902-C3-2-P, y por la beca FPI BES-2011-050604