TL;DR
This paper introduces "formula-based" inference methods for probabilistic logic, which generalize traditional variable-based approaches. By operating directly on logical formulas rather than just truth assignments to variables, these new algorithms (FDC for exact inference and FIS for approximate inference) achieve significant performance gains, especially in domains with complex, large clauses.
What Problem Does This Paper Address?
Automated reasoning typically deals with determining logical entailment. However, real-world applications often involve uncertainty, necessitating probabilistic reasoning. While methods exist to combine logic and probability (e.g., probabilistic logic, Markov logic), efficient inference remains a major challenge. Traditional methods often struggle with the combinatorial explosion of truth assignments to variables, especially when logical formulas involve many variables or are complex. This paper addresses the need for more efficient probabilistic inference techniques that can better leverage the structure inherent in logical formulas.
Methods
The paper proposes two main algorithmic contributions:
- Formula Decomposition and Conditioning (FDC): This is an exact inference algorithm. It generalizes variable-based conditioning by allowing conditioning on arbitrary formulas, not just single variables. FDC works by recursively decomposing the problem based on these formula conditions. It also incorporates simplification techniques (like unit propagation, resolution, subsumption) and problem decomposition (based on the primal graph of the model) to prune the search space. FDC is presented as a general framework that can encompass existing methods like recursive conditioning and weighted model counting.
- Formula Importance Sampling (FIS): This is an approximate inference algorithm. It extends traditional variable-based importance sampling to the space of formulas. FIS uses an importance distribution over truth assignments to a set of formulas (rather than just variables) to draw samples. A key innovation is the use of model counting (the number of solutions to a formula) to compute importance weights. The authors argue that FIS, when using appropriate importance distributions, can achieve lower variance than variable-based importance sampling, leading to more accurate approximations for a given computational budget.
Datasets
The paper evaluates its methods on three classes of benchmark problems:
- Random networks: Generated with parameters (n, m, s) representing the number of variables, weighted clauses, and size of each weighted clause.
- QMR-DT medical diagnosis networks: A standard benchmark for probabilistic inference, adapted to use weighted clauses.
- Relational networks: Including Friends and Smokers networks and Entity Resolution networks (CORA), which involve first-order logic and are converted into propositional representations.
No new benchmarks were introduced; instead, existing, well-established benchmarks were used to compare against state-of-the-art methods.
Key Insights and Ideas
- Conditioning on Formulas is Powerful: The core insight is that conditioning on arbitrary logical formulas, not just single variables, can dramatically reduce the search space for probabilistic inference. This allows the algorithms to exploit logical equivalences and relationships between clauses more effectively.
- Model Counting for Approximate Inference: Harnessing model counting techniques for approximate inference via importance sampling is a novel contribution. This allows for more accurate estimation of probabilities by directly leveraging the structure of logical formulas.
- Formula-Based vs. Variable-Based: The paper demonstrates that formula-based approaches are not just a theoretical generalization but offer substantial practical advantages, especially as the complexity and size of logical clauses increase.
- FDC as a Unifying Framework: FDC's ability to generalize variable-based conditioning, weighted model counting, and other exact inference schemes highlights its potential as a foundational algorithm.
Key Results
- Exact Inference (FDC): FDC consistently outperformed variable-based methods (VDC, VE) and other state-of-the-art exact inference algorithms (ACE) on problems with larger clauses. For instance, in random networks, FDC showed significant speedups as clause size 's' increased. It was often the only algorithm capable of solving the largest instances in the CORA benchmark.
- Approximate Inference (FIS): FIS demonstrated superior performance (lower Sum KLD for a given time) compared to variable-based importance sampling (VIS), MC-SAT, and Gibbs sampling, particularly on domains with large clauses. This indicates that FIS provides more accurate approximations more efficiently.
Limitations and Future Work
- Heuristic Choice in FDC: The performance of FDC is sensitive to the heuristic used for selecting the formula to condition on. While the paper explored several heuristics, developing more robust and universally effective formula-ordering heuristics remains an open area.
- Approximate Model Counting: For FIS, the exact computation of model counts can be computationally expensive. The paper acknowledges the need for efficient approximate model counting techniques, which were used in experiments.
- Future Work: The authors suggest extending formula-based inference to other schemes like variable elimination, belief propagation, and MCMC sampling. They also envision developing "lifted" (higher-level) versions of these formula-based algorithms.
Summary updated