期刊
ARTIFICIAL INTELLIGENCE
卷 274, 期 -, 页码 66-90出版社
ELSEVIER
DOI: 10.1016/j.artint.2018.11.007
关键词
Learning tractable models; Inference complexity; Bayesian networks; Treewidth estimation; Machine learning
资金
- Spanish Ministry of Science, Innovation and Universities through the Cajal Blue Brain [C080020-09]
- Spanish Ministry of Science, Innovation and Universities through the Cajal Blue Brain (Spanish partner of the Blue Brain initiative from EPFL)
- Regional Government of Madrid [TIN2016-79684-P, S2013/ICE-2845-CASI-CAM-CM]
- Fundacion BBVA grants
- European Union [785907]
- Spanish Ministry of Science, Innovation and Universities [BES-2014-068637]
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. (C) 2019 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据