Abstract
Probabilistic answer set programming (PASP) combines rules, facts, and independent probabilistic facts. Often one restricts such programs so that every query yields a sharp probability value. This paper argues that PASP is most powerful when we embrace "credal semantics"—treating programs not as single probability distributions, but as sets of them. By doing so, we can model complex combinatorial problems and $NP^{NP}$-complete tasks where uncertainty and logical constraints intersect, moving beyond the limitations of traditional "sharp" probability values.
Introduction
Probabilistic Answer Set Programming (PASP) represents a significant advancement in the field of probabilistic logic programming. By integrating the declarative power of Answer Set Programming (ASP) with probabilistic reasoning, it allows for the modeling of domains characterized by both complex logical constraints and inherent uncertainty. However, a persistent challenge in the field has been the insistence on "sharp" semantics—the requirement that every query must return a single, exact probability value. This paper argues that such restrictions are unnecessary and often counterproductive, advocating instead for the adoption of credal semantics.
The Challenge of Sharp Probabilities
In traditional probabilistic logic programming, researchers often go to great lengths to ensure that a program defines a unique probability distribution. This typically involves imposing structural constraints, such as requiring the logic to be acyclic or ensuring that every set of probabilistic choices results in exactly one stable model. While this leads to a single probability for any given query (e.g., $P(X) = 0.75$), it sacrifices the very feature that makes ASP powerful: its ability to represent multiple possible solutions to a problem through multiple answer sets. Forcing a single distribution where multiple are naturally present can obscure the underlying logical structure.
Credal Semantics and Methodology
The author proposes a shift toward credal semantics. In this framework, a probabilistic logic program is interpreted as a set of probability distributions (a credal set). If a specific configuration of probabilistic facts leads to multiple answer sets, the semantics considers all possible ways to distribute probability mass among them. This results in the calculation of lower and upper probabilities (bounds) rather than a single sharp value.
To implement this, the paper suggests several key methodological refinements:
- Interpretation of Probabilistic Facts: Rather than simply including or discarding a fact based on its probability, the author suggests that a probabilistic fact $\alpha :: A$ implies $A$ is true with probability $\alpha$ and its strong negation ($\neg A$) is true with probability $1-\alpha$. This makes the logic more robust, particularly in the presence of constraints.
- Computational Strategy: The proposed approach for calculating these bounds involves a three-step pipeline: grounding the high-level logic into propositional rules, converting the program into Conjunctive Normal Form (CNF), and utilizing an adapted version of the DSHARPP algorithm. This algorithm branches on probabilistic facts and counts satisfying assignments to determine the upper and lower bounds.
Expressivity: Beyond Bayesian Networks
A significant portion of the work is dedicated to demonstrating the superior expressivity of PASP under credal semantics. While acyclic PASP programs are functionally equivalent to Bayesian Networks, general PASP can encode problems of much higher complexity.
For example, the paper discusses the "Strategic Company" problem, which is $NP^{NP}$-complete. This complexity class is higher than standard SAT problems, indicating that PASP can concisely model strategic interactions and recursive relationships—such as pathfinding in random graphs—that are difficult to express in standard probabilistic graphical models.
Key Insights and Algorithmic Path
The paper offers several profound insights into the nature of probabilistic reasoning:
- Post-Uncertainty Decisions: Lower and upper probabilities can be interpreted as the results of decisions made after uncertainty is resolved. The upper probability represents the maximum achievable outcome for an agent working toward a goal, while the lower probability represents the guaranteed outcome even in the face of an adversary.
- Mathematical Foundations: The author proves that the lower probability in this semantics is an "infinitely monotone Choquet capacity," providing a solid theoretical link to decision theory and imprecise probability.
- The Utility of Constraints: Constraints (rules with no head) serve as vital filters. In this semantics, if a probabilistic choice leads to an inconsistency (no answer sets), the program is flagged, alerting the modeler to potential issues rather than silently producing a result.
Conclusion and Future Directions
By bridging the gap between stable model semantics and credal sets, the paper provides a robust foundation for PASP. While the computational complexity of $NP^{NP}$-complete problems remains a challenge, the author identifies clear paths for future research, including the development of "selective grounders" that only expand necessary parts of the program and more advanced DPLL-based counting strategies. Ultimately, embracing the multiple answer sets of ASP allows for a more expressive and theoretically sound approach to probabilistic logic.
Summary updated