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 inference to the probabilistic setting. Surprisingly, this problem has received little attention in the literature to date, particularly considering that it includes many standard inference problems as special cases. In this paper, we propose two algorithms for this problem: formula decomposition and conditioning, which is an exact method, and formula importance sampling, which is an approximate method. The latter is, to our knowledge, the first application of model counting to approximate probabilistic inference. Unlike conventional variable-based algorithms, our algorithms work in the dual realm of logical formulas. Theoretically, we show that our algorithms can greatly improve efficiency by exploiting the structural information in the formulas. Empirically, we show that they are indeed quite powerful, 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 inference to the probabilistic setting. Surprisingly, this problem has received little attention in the literature to date, particularly considering that it includes many standard inference problems as special cases. In this paper, we propose two algorithms for this problem: formula decomposition and conditioning, which is an exact method, and formula importance sampling, which is an approximate method. The latter is, to our knowledge, the first application of model counting to approximate probabilistic inference. Unlike conventional variable-based algorithms, our algorithms work in the dual realm of logical formulas. Theoretically, we show that our algorithms can greatly improve efficiency by exploiting the structural information in the formulas. Empirically, we show that they are indeed quite powerful, 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 inference to the probabilistic setting. Surprisingly, this problem has received little attention in the literature to date, particularly considering that it includes many standard inference problems as special cases. In this paper, we propose two algorithms for this problem: formula decomposition and conditioning, which is an exact method, and formula importance sampling, which is an approximate method. The latter is, to our knowledge, the first application of model counting to approximate probabilistic inference. Unlike conventional variable-based algorithms, our algorithms work in the dual realm of logical formulas. Theoretically, we show that our algorithms can greatly improve efficiency by exploiting the structural information in the formulas. Empirically, we show that they are indeed quite powerful, 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