Universidad de Granada Digibug
 

Repositorio Institucional de la Universidad de Granada >
1.-Investigación >
Tesis >

Please use this identifier to cite or link to this item: http://hdl.handle.net/10481/48313

Title: New methods and data structures for evaluating influence diagrams
Authors: Cabañas de Paz, Rafael
Direction: Gómez Olmedo, Manuel
Cano Utrera, Andrés
Collaborator: Universidad de Granada. Departamento de Ciencias de la Computación e Inteligencia Artificial
Issue Date: 2017
Submitted Date: 9-May-2017
Abstract: 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.
Sponsorship: Tesis Univ. Granada. Programa Oficial de Doctorado en Tecnologías de la Información y la Comunicación
Esta 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.
Publisher: Universidad de Granada
Keywords: Estructuras de datos (Informática)
Tecnología de la información y comunicación (TIC)
Estadística bayesiana
Arboles de decisión
Diagramas estadísticos
UDC: 004
004.65
3304
URI: http://hdl.handle.net/10481/48313
ISBN: 9788491635215
Rights : Creative Commons Attribution-NonCommercial-NoDerivs 3.0 License
Citation: Cabañas de Paz, R. New methods and data structures for evaluating influence diagrams. Granada: Universidad de Granada, 2017. [http://hdl.handle.net/10481/48313]
Appears in Collections:Tesis

Files in This Item:

File Description SizeFormat
26505403.pdf4.07 MBAdobe PDFView/Open
Recommend this item

This item is licensed under a Creative Commons License
Creative Commons

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

 

Valid XHTML 1.0! OpenAire compliant DSpace Software Copyright © 2002-2007 MIT and Hewlett-Packard - Feedback

© Universidad de Granada