Abstract
The integration of probabilistic reasoning with logic programming has led to the development of various formalisms, most notably P-log and $LP^{MLN}$. While both are rooted in Answer Set Programming (ASP), they differ fundamentally in their treatment of logical contradictions. This paper establishes a formal bridge between the two by providing a linear-time modular translation from $LP^{MLN}$ to P-log. The authors prove that $LP^{MLN}$ programs can be represented as P-log programs while preserving both the set of stable models and their associated probabilities. This result suggests that the "forgiving" semantics of $LP^{MLN}$ and the "strict" semantics of P-log are more closely related than previously understood, offering new avenues for cross-platform inference and solver optimization.
Introduction
In the field of Artificial Intelligence, the quest to unify symbolic logic with probabilistic uncertainty remains a central challenge. Answer Set Programming (ASP) has provided a robust foundation for declarative logic, but extending it to handle probabilities has resulted in several distinct dialects. Two of the most prominent are P-log and $LP^{MLN}$.
P-log was designed to extend ASP with causal and probabilistic reasoning, emphasizing a strict adherence to consistency. In contrast, $LP^{MLN}$ was inspired by Markov Logic Networks (MLNs), aiming to provide a weight-based approach where contradictions do not lead to failure but rather to less probable "worlds." This paper addresses the theoretical gap between these two systems, asking whether their differing philosophies represent fundamentally different expressive powers or merely different perspectives on the same underlying logic.
The Philosophical Divide: Strictness vs. Forgiveness
The primary distinction between P-log and $LP^{MLN}$ lies in their handling of inconsistency.
- P-log (The Strict Approach): P-log operates on the principle that a rational agent's knowledge base should be consistent. If a contradiction occurs—such as a robot being told it is in two places at once—P-log treats this as a violation of the model's integrity. To handle such cases, it employs "consistency-restoring" rules (cr-rules), which are only triggered when the standard rules fail to produce a valid answer set.
- $LP^{MLN}$ (The Forgiving Approach): $LP^{MLN}$ adopts a softer stance. By assigning weights to rules, it allows for the possibility that some rules may be violated. A "hard" rule is one with an infinite weight, while a "soft" rule has a finite weight. The system calculates the probability of a world based on the sum of the weights of the rules it satisfies. If rules conflict, the system simply assigns lower probabilities to the worlds that violate more (or more important) rules.
Methodology: The $\tau$ Translation
The authors propose a modular, linear-time translation, denoted as $\tau$, to convert $LP^{MLN}$ programs into P-log. This translation is significant because it demonstrates that the "forgiving" nature of $LP^{MLN}$ can be emulated within the "strict" framework of P-log.
1. Translating Hard Rules
In $LP^{MLN}$, hard rules must be satisfied if possible. The authors translate these into P-log by introducing "abnormality" atoms ($ab$). A hard rule in $LP^{MLN}$ becomes a rule in P-log that can be bypassed only through a consistency-restoring rule. This effectively allows P-log to "ignore" a hard rule only when it is the sole way to maintain logical consistency, mimicking the behavior of $LP^{MLN}$'s infinite weights.
2. Translating Soft Rules
Soft rules (rules with weight $w$) are handled using P-log’s random selection rules. The translation introduces an auxiliary predicate, selected(i), to determine whether a specific soft rule $i$ is active in a given world.
3. Weight-to-Probability Mapping
A critical component of the translation is the mathematical conversion of $LP^{MLN}$ weights into P-log probabilities. The probability $P$ that a soft rule is "selected" in the P-log version is defined by the mapping: $$P = \frac{e^w}{1 + e^w}$$ This ensures that as the weight $w$ in $LP^{MLN}$ increases, the probability of the rule being active in P-log approaches 1.
Key Results
The paper provides several formal proofs to validate the translation:
- Bijection of Models: The authors establish a one-to-one correspondence (bijection) between the probabilistic stable models of an $LP^{MLN}$ program and the possible worlds of its P-log translation.
- Probability Preservation: They demonstrate that for any atom or formula, the probability assigned to it by the $LP^{MLN}$ semantics is identical to the probability calculated by the P-log engine after translation.
- Computational Efficiency: The translation $\tau$ is modular and operates in linear time and space relative to the size of the input program. This means that adding a new rule to an $LP^{MLN}$ program only requires adding its specific translation to the P-log program, without needing to re-process the entire set.
Discussion and Limitations
While the translation proves the expressive equivalence of the two languages, it currently applies to a specific subset of $LP^{MLN}$. Specifically, the translation does not yet account for programs containing double negation or disjunction (OR statements) in the head of the rules.
Despite these limitations, the work has significant implications for the development of AI solvers. By showing that $LP^{MLN}$ can be compiled into P-log, researchers can now leverage existing P-log inference engines to solve $LP^{MLN}$ problems. Furthermore, it suggests that the philosophical differences between "strict" and "forgiving" logic are not barriers to compatibility, but rather different ways of organizing the same probabilistic information.
Conclusion
This research provides a unifying framework for two major probabilistic logic languages. By proving that $LP^{MLN}$ is essentially a subset of P-log (under the described translation), the authors have simplified the landscape of probabilistic ASP. Future work will likely focus on expanding this translation to the full $LP^{MLN}$ language and exploring whether the high-performance inference techniques used in Markov Logic Networks can be integrated back into P-log solvers.
Summary updated