@inproceedings{BergJM:AISTATS2014,
author = {Jeremias Berg and Matti J\"arvisalo and Brandon Malone},
title = {Learning Optimal Bounded Treewidth Bayesian Networks via
Maximum Satisfiability},
editor = {Jukka Corander and Samuel Kaski},
booktitle = {Proceedings of the 17th International Conference on
Artificial Intelligence and Statistics (AISTATS 2014)},
series = {JMLR Workshop and Conference Proceedings},
volume = {33},
pages = {86--95},
year = {2014},
publisher = {JMLR},
}
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.