An empirical comparison of Influence Diagrams algorithms

Artaso Landa, Miguel Ángel. (2014). An empirical comparison of Influence Diagrams algorithms Master Thesis, Universidad Nacional de Educación a Distancia (España). Escuela Técnica Superior de Ingeniería Informática. Departamento de Inteligencia Artificial.

Ficheros (Some files may be inaccessible until you login with your e-spacio credentials)
Nombre Descripción Tipo MIME Size
Artaso_Landa_MiguelAngel_TFM.pdf Artaso_Landa_MiguelAngel_TFM.pdf application/pdf 4.66MB

Título An empirical comparison of Influence Diagrams algorithms
Autor(es) Artaso Landa, Miguel Ángel
Resumen Los Modelos Gráficos Probabilistas (MGP) son ampliamente usados en diferentes dominios donde hay que tratar con incertidumbre. Se emplean para obtener la máxima utilidad esperada y la política óptima, las mejores decisiones, en diferentes escenarios. Cuando se afrontan problemas de la vida real, el modelo final que los representa puede ser harto complicado. Debido a que no todos los algoritmos de inferencia son igual de eficientes, es importante saber cuál es mejor aplicar dependiendo de las circunstancias. Por lo tanto, es importante comparar la eficiencia de los algoritmos cuando ante diferentes modelos. En este Trabajo fin de máster, comparamos cuatro algoritmos para diagramas de influencia: eliminación de variables, inversión de arcos, árbol de uniones fuerte y conversión a LIMID. Para nuestros experimentos hemos utilizado OpenMarkov2, una herramienta de código abierto desarrollada por el Centro de Investigación sobre Sistemas Inteligentes de Ayuda a la Decisión (CISIAD) de la UNED. El primer algoritmo estaba ya implementado en esta herramienta; los demás han sido implementados por el autor de este trabajo. Además, hemos implementado la generación de diferentes diagramas de influencia, que después han sido utilizados para comparar los citados algoritmos. Después, hemos contrastado el tiempo y la memoria empleados por los algoritmos en la inferencia de estas redes y el análisis de los resultados nos ha llevado a dar algunas recomendaciones sobre qué algoritmo utilizar dependiendo de la estructura del modelo.
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 OpenMarkov1, 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.
Notas adicionales Trabajo de Fin de Máster. Máster Universitario en I.A. Avanzada: Fundamentos, Métodos y Aplicaciones. UNED
Materia(s) Ingeniería Informática
Palabra clave métodos gráficos probabilistas
redes bayesianas
diagramas de influencia
LIMID
algoritmos de inferencia
comparación empírica
probabilistic graphical models
bayesian networks
influence diagrams
inference algorithms
empirical comparison
Editor(es) Universidad Nacional de Educación a Distancia (España). Escuela Técnica Superior de Ingeniería Informática. Departamento de Inteligencia Artificial.
Director/Tutor Luque Gallego, Manuel
Díez Vegas, Francisco Javier
Fecha 2014-09-29
Formato application/pdf
Identificador bibliuned:master-ETSInformatica-IAA-Maartaso
http://e-spacio.uned.es/fez/view/bibliuned:master-ETSInformatica-IAA-Maartaso
Idioma eng
Versión de la publicación acceptedVersion
Nivel de acceso y licencia http://creativecommons.org/licenses/by-nc-nd/4.0
info:eu-repo/semantics/openAccess
Tipo de recurso master Thesis
Tipo de acceso Acceso abierto

 
Versiones
Versión Tipo de filtro
Contador de citas: Google Scholar Search Google Scholar
Estadísticas de acceso: 289 Visitas, 106 Descargas  -  Estadísticas en detalle
Creado: Wed, 14 Jul 2021, 17:49:47 CET