Learning tractable Bayesian networks in the space of elimination orders

Benjumeda Barquita, Marco Alberto and Bielza Lozoya, María Concepción and Larrañaga Múgica, Pedro María (2019). Learning tractable Bayesian networks in the space of elimination orders. "Artificial Intelligence", v. 274 ; pp. 66-90. ISSN 0004-3702. https://doi.org/10.1016/j.artint.2018.11.007.

Description

Title: Learning tractable Bayesian networks in the space of elimination orders
Author/s:
  • Benjumeda Barquita, Marco Alberto
  • Bielza Lozoya, María Concepción
  • Larrañaga Múgica, Pedro María
Item Type: Article
Título de Revista/Publicación: Artificial Intelligence
Date: September 2019
ISSN: 0004-3702
Volume: 274
Subjects:
Freetext Keywords: Learning tractable models; Inference complexity; Bayesian networks; Treewidth estimation; Machine Learning
Faculty: E.T.S. de Ingenieros Informáticos (UPM)
Department: Inteligencia Artificial
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (2MB) | Preview

Abstract

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.

Funding Projects

TypeCodeAcronymLeaderTitle
Government of Spain080020-09UnspecifiedUnspecifiedCajal Blue Brain
Government of SpainTIN2016-79684-PUnspecifiedUniversidad Politécnica de MadridAvances en clasificación multidimensional y detección de anomalías con redes bayesianas
Madrid Regional GovernmentS2013/ICE-2845CASI-CAM-CMUnspecifiedConceptos y aplicaciones de los sistemas inteligentes
Horizon 2020785907HBP SGA2École Polytechnique Fédérale de LausanneHuman Brain Project Specific Grant Agreement 2
Government of SpainTIN2013-41592-PBES-2014-068637Universidad Politécnica de MadridUnspecified

More information

Item ID: 63607
DC Identifier: http://oa.upm.es/63607/
OAI Identifier: oai:oa.upm.es:63607
DOI: 10.1016/j.artint.2018.11.007
Official URL: https://www.sciencedirect.com/science/article/pii/S0004370219300244
Deposited by: Memoria Investigacion
Deposited on: 10 Nov 2020 11:27
Last Modified: 10 Nov 2020 11:27
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM