Full text
Preview |
PDF
- Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (2MB) | Preview |
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.
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 |
Preview |
PDF
- Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (2MB) | Preview |
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.
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 |