Learning Optimal Bounded Treewidth Bayesian Networks via Maximum Satisfiability
Jeremias Berg, Matti Järvisalo, Brandon Malone · 2014
Bayesian network structure learning is the well-known computationally hard problem of finding a directed acyclic graph struc-ture that optimally describes given data. A learned structure can then be used for probabilistic inference. While exact infer-ence in Bayesian networks is in general NP-hard, it is tractable in networks with low treewidth. This provides good motiva-tions 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 algo-rithm for BTW-BNSL.