Formula-Based Probabilistic Inference

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.

Appears in Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence (UAI2010)

References in corpus (4)

• Context-Specific Independence in Bayesian Networks
• Value Elimination: Bayesian Inference via Backtracking Search
• Approximate Inference Algorithms for Hybrid Bayesian Networks with Discrete Constraints
• AND/OR Importance Sampling

Cited by in corpus (6)

• Probabilistic Theorem Proving
• Approximation by Quantization
• Reasoning about Probabilities in Dynamic Systems using Goal Regression
• Variational hybridization and transformation for large inaccurate noisy-or networks
• Reasoning Under the Principle of Maximum Entropy for Modal Logics K45, KD45, and S5
• Approximate Lifted Inference with Probabilistic Databases