Efficient learning of bounded-treewidth Bayesian networks from complete and incomplete data sets

DOI10.1016/J.IJAR.2018.02.004MaRDI QIDQ146614zbMATH OpenOpenAlexFDO

Authors Mauro Scanagatta, Giorgio Corani, M. Zaffalon, Jaemin Yoo, U. Kang, Mauro Scanagatta, Giorgio Corani, Jaemin Yoo, U. Kang

Publication date April 2018

Published in International Journal of Approximate Reasoning (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.02468

zbMATH Keywords

Bayesian networksstructural learningbounded treewidthincomplete data setsstructural EM

Mathematics Subject Classification ID

Bayesian inference (62F15) Learning and adaptive systems in artificial intelligence (68T05) Probabilistic graphical models (62H22)

Abstract: Learning a Bayesian networks with bounded treewidth is important for reducing the complexity of the inferences. We present a novel anytime algorithm (k-MAX) method for this task, which scales up to thousands of variables. Through extensive experiments we show that it consistently yields higher-scoring structures than its competitors on complete data sets. We then consider the problem of structure learning from incomplete data sets. This can be addressed by structural EM, which however is computationally very demanding. We thus adopt the novel k-MAX algorithm in the maximization step of structural EM, obtaining an efficient computation of the expected sufficient statistics. We test the resulting structural EM method on the task of imputing missing data, comparing it against the state-of-the-art approach based on random forests. Our approach achieves the same imputation accuracy of the competitors, but in about one tenth of the time. Furthermore we show that it has worst-case complexity linear in the input size, and that it is easily parallelizable.

Recommendations

• Efficient learning of Bayesian networks with bounded tree-width
• scientific article; zbMATH DE number 5968954
• Learning bounded tree-width Bayesian networks via sampling
• Approximate structure learning for large Bayesian networks
• Learning Bayesian Network Equivalence Classes from Incomplete Data

Cites work

• scientific article; zbMATH DE number 4103086 (Why is no real title available?)
• Bayesian Networks for Imputation
• Efficient structure learning of Bayesian networks using constraints
• Join-graph propagation algorithms
• Learning bounded tree-width Bayesian networks via sampling
• Modeling and Reasoning with Bayesian Networks
• Probabilistic graphical models.
• Random forest missing data algorithms
• The necessity of bounded treewidth for efficient inference in Bayesian networks

Cited in

(9)

• scientific article; zbMATH DE number 5968954 (Why is no real title available?)
• Learning bounded tree-width Bayesian networks via sampling
• Efficient learning of Bayesian networks with bounded tree-width
• Learning tractable Bayesian networks in the space of elimination orders
• Approximate structure learning for large Bayesian networks
• Being Bayesian about learning Gaussian Bayesian networks from incomplete data
• Bayesian network models for incomplete and dynamic data
• Towards an effective practice of learning from data and knowledge
• r.blip

Describes a project that uses

Uses Software

• missForest

This page was built for publication: Efficient learning of bounded-treewidth Bayesian networks from complete and incomplete data sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q146614)