@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.