Dissociation-Based Oblivious Bounds for Weighted Model Counting

Li Chou, Wolfgang Gatterbauer, Vibhav Gogate
Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, PMLR R16:865-874, 2018.

Abstract

We consider the weighted model counting task which includes important tasks in graphical models, such as computing the partition func- tion and probability of evidence as special cases. We propose a novel partition-based bounding al- gorithm that exploits logical structure and gives rise to a set of inequalities from which upper (or lower) bounds can be derived efficiently. The bounds come with optimality guarantees under certain conditions and are oblivious in that they require only limited observations of the structure and parameters of the problem. We experimentally compare our bounds with the mini-bucket scheme (which is also oblivi- ous) and show that our new bounds are often superior and never worse on a wide variety of benchmark networks.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR16-chou18a, title = {Dissociation-Based Oblivious Bounds for Weighted Model Counting}, author = {Chou, Li and Gatterbauer, Wolfgang and Gogate, Vibhav}, booktitle = {Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence}, pages = {865--874}, year = {2018}, editor = {Globerson, Amir and Silva, Ricardo}, volume = {R16}, series = {Proceedings of Machine Learning Research}, month = {06--10 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r16/main/assets/chou18a/chou18a.pdf}, url = {https://proceedings.mlr.press/r16/chou18a.html}, abstract = {We consider the weighted model counting task which includes important tasks in graphical models, such as computing the partition func- tion and probability of evidence as special cases. We propose a novel partition-based bounding al- gorithm that exploits logical structure and gives rise to a set of inequalities from which upper (or lower) bounds can be derived efficiently. The bounds come with optimality guarantees under certain conditions and are oblivious in that they require only limited observations of the structure and parameters of the problem. We experimentally compare our bounds with the mini-bucket scheme (which is also oblivi- ous) and show that our new bounds are often superior and never worse on a wide variety of benchmark networks.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Dissociation-Based Oblivious Bounds for Weighted Model Counting %A Li Chou %A Wolfgang Gatterbauer %A Vibhav Gogate %B Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2018 %E Amir Globerson %E Ricardo Silva %F pmlr-vR16-chou18a %I PMLR %P 865--874 %U https://proceedings.mlr.press/r16/chou18a.html %V R16 %X We consider the weighted model counting task which includes important tasks in graphical models, such as computing the partition func- tion and probability of evidence as special cases. We propose a novel partition-based bounding al- gorithm that exploits logical structure and gives rise to a set of inequalities from which upper (or lower) bounds can be derived efficiently. The bounds come with optimality guarantees under certain conditions and are oblivious in that they require only limited observations of the structure and parameters of the problem. We experimentally compare our bounds with the mini-bucket scheme (which is also oblivi- ous) and show that our new bounds are often superior and never worse on a wide variety of benchmark networks. %Z Reissued by PMLR on 04 October 2026.
APA
Chou, L., Gatterbauer, W. & Gogate, V.. (2018). Dissociation-Based Oblivious Bounds for Weighted Model Counting. Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R16:865-874 Available from https://proceedings.mlr.press/r16/chou18a.html. Reissued by PMLR on 04 October 2026.

Related Material