New methods and data structures for evaluating influence diagrams

Abstract

Resumen Esta tesis aborda distintos problemas relacionados con la evaluación de diagramas de influencia (IDs), un tipo de modelo gráfico probabilístico para resolver problemas de decisión. Para ello, se proponen diferentes modificaciones en el marco clásico de los ID que consisten en el uso de nuevas estructuras de datos para representar tanto la información cualitativa como la cuantitativa. También se proponen varios algoritmos de evaluación que utilizan dichas estructuras. En particular, los problemas abordados son los siguientes: - Elevado coste computacional: los potenciales intermedios generados durante la evaluación pueden ser extremadamente grandes. Como consecuencia, la evaluación de IDs complejos tiene un elevado coste computacional en términos de memoria y tiempo. Para ello se propone el uso de árboles binarios (BTs) en lugar de tablas para representar los potenciales asociados a un ID. La ventaja de utilizar BTs reside en su capacidad para representar formas generales de independencia que no pueden ser representadas con otras estructuras (tablas, árboles numéricos). Esto es posible porque algunos valores idénticos del potencial se pueden agrupar. Con esto se consigue reducir el tamaño de los potenciales y por lo tanto mejorar la eficiencia. Además, si un BT es muy grande, se puede podar con lo que se aproxima el potencial (y por lo tanto la evaluación). También exploramos distintas alternativas para reducir el coste de la evaluación asumiendo que los potenciales están representados usando tablas. En concreto, proponemos distintos algoritmos evaluación que pretenden optimizar el orden de las combinaciones y marginalizaciones con los potenciales. - Evaluación ineficiente de problemas de decisión asimétricos: en muchos problemas de decisión, denominados asimétricos, los valores que una variable puede tomar dependen del pasado. Por ejemplo, consideremos un problema de decisión en que existe la posibilidad de realizar un test. Si se opta por no realizarlo, entonces cualquier resultado de dicho test no debe ser considerado en la evaluación. Un inconveniente importante de los IDs está relacionado con la incapacidad para representarlos y evaluarlos de forma eficiente. Esto se debe a que los potenciales pueden contener algunas configuraciones imposibles (debido a las asimetrías) que no son relevantes para resolver el problema. En esta tesis proponemos usar BTs también para identificar estas configuraciones imposibles y así evitar cálculos innecesarios. - Incapacidad para expresar imprecisión: en el formalismo clásico de los IDs, los potenciales son funciones que asignan valores precisos a cada combinación de estados para un conjunto de variables (por ejemplo, la probabilidad de X=x1 es 0.75). Esto puede ser un inconveniente al modelar problemas reales, donde los potenciales se suelen obtener a partir de valoraciones de los expertos o de datos parcialmente fiables. En esta tesis proponemos reemplazar los valores precisos en los potenciales por intervalos. Esta generalización se denomina potenciales con intervalos. Un ID con este tipo de potenciales se puede ver como una colección de IDs clásicos (precisos) consistentes con las restricciones impuestas por los intervalos. También se proponen extensiones de algunos algoritmos clásicos para poder evaluar IDs con intervalos. Los algoritmos que mejores resultados han dado son aquellos que se basan en técnicas de programación lineal. Summary 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.