Formula-Based Probabilistic Inference

Vibhav Gogate, Pedro Domingos
Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, PMLR R8:218-227, 2010.

Abstract

Computing the probability of a formula given the probabilities or weights associated with other formulas is a natural extension of logical infer- ence to the probabilistic setting. Surprisingly, this problem has received little attention in the lit- erature to date, particularly considering that it in- cludes many standard inference problems as spe- cial cases. In this paper, we propose two algo- rithms for this problem: formula decomposition and conditioning, which is an exact method, and formula importance sampling, which is an ap- proximate method. The latter is, to our knowl- edge, the first application of model counting to approximate probabilistic inference. Unlike con- ventional variable-based algorithms, our algo- rithms work in the dual realm of logical formu- las. Theoretically, we show that our algorithms can greatly improve efficiency by exploiting the structural information in the formulas. Empiri- cally, we show that they are indeed quite pow- erful, often achieving substantial performance gains over state-of-the-art schemes.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR8-gogate10a, title = {Formula-Based Probabilistic Inference}, author = {Gogate, Vibhav and Domingos, Pedro}, booktitle = {Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence}, pages = {218--227}, year = {2010}, editor = {Grünwald, Peter and Spirtes, Peter}, volume = {R8}, series = {Proceedings of Machine Learning Research}, month = {08--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r8/main/assets/gogate10a/gogate10a.pdf}, url = {https://proceedings.mlr.press/r8/gogate10a.html}, abstract = {Computing the probability of a formula given the probabilities or weights associated with other formulas is a natural extension of logical infer- ence to the probabilistic setting. Surprisingly, this problem has received little attention in the lit- erature to date, particularly considering that it in- cludes many standard inference problems as spe- cial cases. In this paper, we propose two algo- rithms for this problem: formula decomposition and conditioning, which is an exact method, and formula importance sampling, which is an ap- proximate method. The latter is, to our knowl- edge, the first application of model counting to approximate probabilistic inference. Unlike con- ventional variable-based algorithms, our algo- rithms work in the dual realm of logical formu- las. Theoretically, we show that our algorithms can greatly improve efficiency by exploiting the structural information in the formulas. Empiri- cally, we show that they are indeed quite pow- erful, often achieving substantial performance gains over state-of-the-art schemes.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Formula-Based Probabilistic Inference %A Vibhav Gogate %A Pedro Domingos %B Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2010 %E Peter Grünwald %E Peter Spirtes %F pmlr-vR8-gogate10a %I PMLR %P 218--227 %U https://proceedings.mlr.press/r8/gogate10a.html %V R8 %X Computing the probability of a formula given the probabilities or weights associated with other formulas is a natural extension of logical infer- ence to the probabilistic setting. Surprisingly, this problem has received little attention in the lit- erature to date, particularly considering that it in- cludes many standard inference problems as spe- cial cases. In this paper, we propose two algo- rithms for this problem: formula decomposition and conditioning, which is an exact method, and formula importance sampling, which is an ap- proximate method. The latter is, to our knowl- edge, the first application of model counting to approximate probabilistic inference. Unlike con- ventional variable-based algorithms, our algo- rithms work in the dual realm of logical formu- las. Theoretically, we show that our algorithms can greatly improve efficiency by exploiting the structural information in the formulas. Empiri- cally, we show that they are indeed quite pow- erful, often achieving substantial performance gains over state-of-the-art schemes. %Z Reissued by PMLR on 04 October 2026.
APA
Gogate, V. & Domingos, P.. (2010). Formula-Based Probabilistic Inference. Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R8:218-227 Available from https://proceedings.mlr.press/r8/gogate10a.html. Reissued by PMLR on 04 October 2026.

Related Material