Learning Optimal Bounded Treewidth Bayesian Networks via Maximum Satisfiability
Abstract
Bayesian network structure learning is the well-known computationally hard problem of finding a directed acyclic graph structure that optimally describes given data. A learned structure can then be used for probabilistic inference. While exact inference in Bayesian networks is in general NP-hard, it is tractable in networks with low treewidth. This provides good motivations for developing algorithms for the NP-hard problem of learning optimal bounded treewidth Bayesian networks (BTW-BNSL). In this work, we develop a novel score-based approach to BTW-BNSL, based on casting BTW-BNSL as weighted partial Maximum satisfiability. We demonstrate empirically that the approach scales notably better than a recent exact dynamic programming algorithm for BTW-BNSL.
Cite
Text
Berg et al. "Learning Optimal Bounded Treewidth Bayesian Networks via Maximum Satisfiability." International Conference on Artificial Intelligence and Statistics, 2014.Markdown
[Berg et al. "Learning Optimal Bounded Treewidth Bayesian Networks via Maximum Satisfiability." International Conference on Artificial Intelligence and Statistics, 2014.](https://mlanthology.org/aistats/2014/berg2014aistats-learning/)BibTeX
@inproceedings{berg2014aistats-learning,
title = {{Learning Optimal Bounded Treewidth Bayesian Networks via Maximum Satisfiability}},
author = {Berg, Jeremias and Järvisalo, Matti and Malone, Brandon M.},
booktitle = {International Conference on Artificial Intelligence and Statistics},
year = {2014},
pages = {86-95},
url = {https://mlanthology.org/aistats/2014/berg2014aistats-learning/}
}