TL;DR
This paper tackles the challenging problem of finding the "Most Probable Explanation" (MPE) in Probabilistic Answer Set Programming (PASP), a task that has remained open. The authors introduce three novel approaches: one based on knowledge compilation and algebraic model counting, and two logic-based encodings using Answer Set Programming (ASP) and ASP with Quantifiers (ASP(Q)). Their methods significantly outperform existing solvers, especially for complex, non-stratified programs.
What Problem Does This Paper Address?
In the realm of Artificial Intelligence, particularly in areas that combine logic and probability (Statistical Relational AI), understanding the most likely cause for observed evidence is crucial. Probabilistic Answer Set Programming (PASP) is a formalism designed for this. However, a core problem within PASP, known as the Most Probable Explanation (MPE), has been computationally challenging and largely unsolved. Given a PASP program and some observed evidence, MPE aims to find the underlying probabilistic "world" (a specific combination of probabilistic facts being true or false) that has the highest probability and either cautiously (true in all possible outcomes) or bravely (true in at least one possible outcome) explains the evidence. This paper addresses the need for efficient and effective methods to solve this MPE problem.
Methods
The paper proposes three distinct approaches to tackle the MPE problem:
- Algebraic Model Counting (AMC) based approach: This method leverages a technique called second-level algebraic model counting (2AMC). The PASP program and evidence are transformed into a propositional theory. This theory is then processed by a 2AMC framework, which essentially involves two layers of computation. The inner layer deals with specific answer sets and their relation to the evidence, while the outer layer iterates through possible worlds (combinations of probabilistic facts). This approach is implemented using the
aspmcsolver. - Answer Set Programming (ASP) for Upper MPE: For computing the "brave" or upper MPE state (where the evidence needs to be true in at least one outcome), the authors propose a direct ASP encoding. This encoding combines the probabilistic facts, the core logic of the PASP program, and a constraint to ensure the evidence is met. Optimal answer sets of this ASP program correspond to upper MPE states.
- ASP with Quantifiers (ASP(Q)) for Lower MPE: To compute the "cautious" or lower MPE state (where the evidence must be true in all outcomes), a more sophisticated approach using ASP with Quantifiers (ASP(Q)) is introduced. ASP(Q) extends ASP by allowing quantifiers over answer sets, enabling the modeling of more complex logical structures. This encoding uses existential and universal quantifiers to precisely capture the condition that the evidence must hold across all possible worlds derived from a selection of probabilistic facts. Optimal quantified answer sets in this framework correspond to lower MPE states.
Datasets
The paper describes two types of datasets used for evaluation:
- Stratified Datasets: These datasets consist of PASP programs where the underlying ASP is stratified. The authors generated instances based on the reachability problem using three graph structures: Barabási-Albert, Erdős-Rényi, and complete graphs. They also varied probabilities (fixed at 0.4 or random between 0.001 and 0.999).
- Non-Stratified Datasets: These are more complex datasets where each world can have multiple answer sets. Six different benchmarks were created, including variations of a problem involving probabilistic facts and rules related to a query atom
qr. Additionally, they included the well-known graph coloring (col) problem and the friend-smokers (smk) benchmark, also with fixed and random probabilities.
Key Insights and Ideas
- ASP(Q) as a Powerful Tool for Lower MPE: The introduction of ASP(Q) proves to be a highly effective way to model and solve the lower MPE problem. Its ability to quantify over answer sets naturally captures the "cautious entailment" requirement.
- ASP's Simplicity for Upper MPE: For the upper MPE problem, a standard ASP encoding is sufficient and efficient, demonstrating the versatility of ASP for different facets of the MPE task.
- Knowledge Compilation's Trade-offs: While knowledge compilation (used in the 2AMC approach) can be effective, its performance can be impacted by the grounding phase, especially when many probabilistic facts are not directly relevant to the evidence.
- Probability Values Matter for Performance: The specific probability values assigned to facts can significantly influence the runtime of certain solvers, particularly ASP(Q), which uses an upper-bound improving algorithm. Fixed probabilities often lead to better performance than random ones for this method.
- New Approaches Outperform Existing Ones: The proposed ASP(Q) and ASP-based methods, along with the 2AMC approach, consistently outperform existing solvers, especially on the more challenging non-stratified datasets.
Key Results
- Superior Performance on Non-Stratified Datasets: The proposed ASP(Q) + ASP approach demonstrated the best performance on non-stratified datasets, solving more instances and often much faster than other methods. For instance, on the
p3_fdataset, ASP(Q) could solve instances up to size 20, while other methods struggled beyond size 23. - Efficiency of ASP(Q) for Lower MPE: ASP(Q) was found to be particularly effective for computing lower MPE states, often outperforming the 2AMC approach (
aspmc) in terms of solvable instances and execution time. - Stratified Datasets Performance: On stratified datasets, where lower and upper MPE states coincide, the ASP-based approach was competitive, though PASTA was generally the slowest.
- Impact of Probability Distribution: For ASP(Q), fixed probabilities generally led to better performance than random probabilities on non-stratified datasets. This was not the case for PASTA, which is less sensitive to probability values.
Limitations and Future Work
- Computational Complexity: The MPE problem is inherently complex, and while the proposed methods offer significant improvements, they still face challenges with very large or complex programs. The
aspmcsolver, for example, sometimes encountered out-of-memory errors. - Time Limits: For some datasets and solvers (e.g., ASP(Q) on certain non-stratified instances), timeouts were a limiting factor, indicating that further optimization might be needed for extremely large problems.
- Future Work Directions: The authors suggest exploring different semantics for PASP, further speeding up execution times (e.g., through multi-shot approaches), and investigating the application of these techniques to other related problems in probabilistic reasoning. They also highlight the need for continued empirical evaluation across a wider range of benchmarks and problem types.
Summary updated