Reducing the Cost of Probabilistic Knowledge Compilation

Giso H. Dal, Steffen Michels, Peter J. F. Lucas
Proceedings of The 3rd International Workshop on Advanced Methodologies for Bayesian Networks, PMLR 73:141-152, 2017.

Abstract

Bayesian networks (BN) are a popular representation for reasoning under uncertainty. The computational complexity of inference, however, hinders its applicability to many real-world domains that in principle can be modeled by BNs. Inference methods based on Weighted Model Counting (WMC) reduce the cost of inference by exploiting patterns exhibited by the probabilities associated with BN nodes. However, these methods require a computationally intensive compilation step in search of these patterns, limiting the number of BNs that are eligible based on their size. In this paper, we aim to extend WMC methods in general by proposing a scalable, compilation framework that is language agnostic, which solves this problem by partitioning BNs and compiling them as a set of smaller sub-problems. This reduces the cost of compilation and allows state-of-the-art innovations in WMC to be applied to a much larger range of Bayesian networks.

Cite this Paper

BibTeX
@InProceedings{pmlr-v73-giso-dal17a, title = {Reducing the Cost of Probabilistic Knowledge Compilation}, author = {Dal, Giso H. and Michels, Steffen and Lucas, Peter J. F.}, booktitle = {Proceedings of The 3rd International Workshop on Advanced Methodologies for Bayesian Networks}, pages = {141--152}, year = {2017}, editor = {Hyttinen, Antti and Suzuki, Joe and Malone, Brandon}, volume = {73}, series = {Proceedings of Machine Learning Research}, month = {20--22 Sep}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v73/giso-dal17a/giso-dal17a.pdf}, url = {https://proceedings.mlr.press/v73/giso-dal17a.html}, abstract = {Bayesian networks (BN) are a popular representation for reasoning under uncertainty. The computational complexity of inference, however, hinders its applicability to many real-world domains that in principle can be modeled by BNs. Inference methods based on Weighted Model Counting (WMC) reduce the cost of inference by exploiting patterns exhibited by the probabilities associated with BN nodes. However, these methods require a computationally intensive compilation step in search of these patterns, limiting the number of BNs that are eligible based on their size. In this paper, we aim to extend WMC methods in general by proposing a scalable, compilation framework that is language agnostic, which solves this problem by partitioning BNs and compiling them as a set of smaller sub-problems. This reduces the cost of compilation and allows state-of-the-art innovations in WMC to be applied to a much larger range of Bayesian networks.} }
Endnote
%0 Conference Paper %T Reducing the Cost of Probabilistic Knowledge Compilation %A Giso H. Dal %A Steffen Michels %A Peter J. F. Lucas %B Proceedings of The 3rd International Workshop on Advanced Methodologies for Bayesian Networks %C Proceedings of Machine Learning Research %D 2017 %E Antti Hyttinen %E Joe Suzuki %E Brandon Malone %F pmlr-v73-giso-dal17a %I PMLR %P 141--152 %U https://proceedings.mlr.press/v73/giso-dal17a.html %V 73 %X Bayesian networks (BN) are a popular representation for reasoning under uncertainty. The computational complexity of inference, however, hinders its applicability to many real-world domains that in principle can be modeled by BNs. Inference methods based on Weighted Model Counting (WMC) reduce the cost of inference by exploiting patterns exhibited by the probabilities associated with BN nodes. However, these methods require a computationally intensive compilation step in search of these patterns, limiting the number of BNs that are eligible based on their size. In this paper, we aim to extend WMC methods in general by proposing a scalable, compilation framework that is language agnostic, which solves this problem by partitioning BNs and compiling them as a set of smaller sub-problems. This reduces the cost of compilation and allows state-of-the-art innovations in WMC to be applied to a much larger range of Bayesian networks.
APA
Dal, G.H., Michels, S. & Lucas, P.J.F.. (2017). Reducing the Cost of Probabilistic Knowledge Compilation. Proceedings of The 3rd International Workshop on Advanced Methodologies for Bayesian Networks, in Proceedings of Machine Learning Research 73:141-152 Available from https://proceedings.mlr.press/v73/giso-dal17a.html.

Related Material