Learning Optimal Bounded Treewidth Bayesian Networks via Maximum Satisfiability

Jeremias Berg, Matti Järvisalo, Brandon Malone
Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, PMLR 33:86-95, 2014.

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 this Paper

BibTeX
@InProceedings{pmlr-v33-berg14, title = {{Learning Optimal Bounded Treewidth Bayesian Networks via Maximum Satisfiability}}, author = {Berg, Jeremias and Järvisalo, Matti and Malone, Brandon}, booktitle = {Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics}, pages = {86--95}, year = {2014}, editor = {Kaski, Samuel and Corander, Jukka}, volume = {33}, series = {Proceedings of Machine Learning Research}, address = {Reykjavik, Iceland}, month = {22--25 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v33/berg14.pdf}, url = {https://proceedings.mlr.press/v33/berg14.html}, 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.} }
Endnote
%0 Conference Paper %T Learning Optimal Bounded Treewidth Bayesian Networks via Maximum Satisfiability %A Jeremias Berg %A Matti Järvisalo %A Brandon Malone %B Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2014 %E Samuel Kaski %E Jukka Corander %F pmlr-v33-berg14 %I PMLR %P 86--95 %U https://proceedings.mlr.press/v33/berg14.html %V 33 %X 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.
RIS
TY - CPAPER TI - Learning Optimal Bounded Treewidth Bayesian Networks via Maximum Satisfiability AU - Jeremias Berg AU - Matti Järvisalo AU - Brandon Malone BT - Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics DA - 2014/04/02 ED - Samuel Kaski ED - Jukka Corander ID - pmlr-v33-berg14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 33 SP - 86 EP - 95 L1 - http://proceedings.mlr.press/v33/berg14.pdf UR - https://proceedings.mlr.press/v33/berg14.html AB - 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. ER -
APA
Berg, J., Järvisalo, M. & Malone, B.. (2014). Learning Optimal Bounded Treewidth Bayesian Networks via Maximum Satisfiability. Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 33:86-95 Available from https://proceedings.mlr.press/v33/berg14.html.

Related Material