Learning tractable Bayesian networks in the space of elimination orders

Benjumeda Barquita, Marco Alberto, Bielza Lozoya, María Concepción ORCID: https://orcid.org/0000-0001-7109-2668 and Larrañaga Múgica, Pedro María ORCID: https://orcid.org/0000-0002-1885-4501 (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:
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

[thumbnail of INVE_MEM_2019_319080.pdf]
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

Type
Code
Acronym
Leader
Title
Government of Spain
080020-09
Unspecified
Unspecified
Cajal Blue Brain
Government of Spain
TIN2016-79684-P
Unspecified
Universidad Politécnica de Madrid
Avances en clasificación multidimensional y detección de anomalías con redes bayesianas
Madrid Regional Government
S2013/ICE-2845
CASI-CAM-CM
Unspecified
Conceptos y aplicaciones de los sistemas inteligentes
Horizon 2020
785907
HBP SGA2
École Polytechnique Fédérale de Lausanne
Human Brain Project Specific Grant Agreement 2
Government of Spain
TIN2013-41592-P
BES-2014-068637
Universidad Politécnica de Madrid
Unspecified

More information

Item ID: 63607
DC Identifier: https://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/...
Deposited by: Memoria Investigacion
Deposited on: 10 Nov 2020 11:27
Last Modified: 30 Nov 2022 09:00
  • 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