Observatorio de I+D+i UPM

Memorias de investigación
Artículos en revistas:
Learning Bayesian networks with low inference complexity
Año:2019
Áreas de investigación
  • Ciencias de la computación y tecnología informática
Datos
Descripción
The computational complexity of inference is now one of the most relevant topics in the field of Bayesian networks. Although the literature contains approaches that learn Bayesian networks from high dimensional datasets, traditional methods do not bound the inference complexity of the learned models, often producing models where exact inference is intractable. This paper focuses on learning tractable Bayesian networks from data. To address this problem, we propose strategies for learning Bayesian networks in the space of elimination orders. In this manner, we can efficiently bound the inference complexity of the networks during the learning process. Searching in the combined space of directed acyclic graphs and elimination orders can be extremely computationally demanding. We demonstrate that one type of elimination trees, which we define as valid, can be used as an equivalence class of directed acyclic graphs and elimination orders, removing redundancy. We propose methods for incrementally compiling local changes made to directed acyclic graphs in elimination trees and for searching for elimination trees of low width. Using these methods, we can move through the space of valid elimination trees in polynomial time with respect to the number of network variables and in linear time with respect to treewidth. Experimental results show that our approach successfully bounds the inference complexity of the learned models, while it is competitive with other state-of-the-art methods in terms of fitting to data.
Internacional
Si
JCR del ISI
Si
Título de la revista
Artificial Intelligence
ISSN
0004-3702
Factor de impacto JCR
3,034
Información de impacto
posición 28 (Q1) en área Computer Science, Artificial Intelligence para Thomson Reuters Journal Citation Reports
Volumen
274
DOI
10.1016/j.artint.2018.11.007
Número de revista
Desde la página
66
Hasta la página
90
Mes
SEPTIEMBRE
Ranking
Esta actividad pertenece a memorias de investigación
Participantes
  • Autor: Marco Alberto Benjumeda Barquita (UPM)
  • Autor: Maria Concepcion Bielza Lozoya (UPM)
  • Autor: Pedro Maria Larrañaga Mugica (UPM)
Grupos de investigación, Departamentos, Centros e Institutos de I+D+i relacionados
  • Creador: Departamento: Inteligencia Artificial
S2i 2021 Observatorio de investigación @ UPM con la colaboración del Consejo Social UPM
Cofinanciación del MINECO en el marco del Programa INNCIDE 2011 (OTR-2011-0236)
Cofinanciación del MINECO en el marco del Programa INNPACTO (IPT-020000-2010-22)