TL;DR
This paper establishes a formal translation from the probabilistic logic programming language LPMLN to P-log, a language also designed for probabilistic reasoning. This work clarifies how these two languages, with seemingly similar goals but different underlying philosophies, handle probabilistic knowledge and inconsistencies, paving the way for cross-pollination of techniques and tools.
What Problem Does This Paper Address?
Artificial intelligence research has long sought to combine the power of logical reasoning with the uncertainty inherent in real-world data. This has led to the development of various probabilistic logic programming languages. Among these, P-log and LPMLN are notable for their foundation in Answer Set Prolog (ASP), a formalism that models rational agents' beliefs and can handle defaults and non-monotonic reasoning. While both P-log and LPMLN aim to integrate logic and probability, they differ in their philosophical underpinnings, particularly in how they address inconsistencies. P-log, for instance, assumes a consistent knowledge base and requires engineers to handle inconsistencies, while LPMLN is designed to provide a more robust way of resolving them. The relationship between these two languages, especially how they represent and reason about probabilistic information, remained unclear. This paper aims to bridge this gap by providing a formal translation from LPMLN to P-log, thereby shedding light on their similarities and differences.
Methods
The core contribution of this paper is a formal translation, denoted by $\tau$, from LPMLN programs to P-log programs. This translation is designed to be linear-time constructible and modular. The translation process involves several key steps:
- Handling Hard Rules: LPMLN's hard rules (preceded by 'a:') are translated into P-log rules that incorporate a mechanism to handle potential abnormalities or exceptions. This involves introducing auxiliary attributes like
ab(i)(indicating ruleiis abnormal) and using P-log's consistency-restoring rules (cr-rules) to manage these abnormalities. - Handling Soft Rules: LPMLN's soft rules (preceded by a weight
w:) are translated into P-log rules that use random selection. Auxiliary attributes likeselected(i)andsat(i)are introduced to manage the selection and satisfaction of these soft rules. The probability of selecting a soft rule is then mapped to a P-log probability atom. - Mapping Probabilistic Stable Models: A crucial aspect of the translation is establishing a bijection $\phi$ between the probabilistic stable models of an LPMLN program and the possible worlds of its corresponding P-log translation. This bijection ensures that the probabilities assigned to these worlds are preserved.
- Probability Preservation: The translation guarantees that for any atom
A, the probability ofAin the LPMLN program is equal to the probability ofAin the translated P-log program.
Datasets
Not discussed in the paper. The paper focuses on formal language translation and theoretical relationships rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Bridging Philosophical Divides: The paper demonstrates that despite differing philosophies on handling inconsistency, LPMLN and P-log can be formally related. This suggests that techniques developed for one language might be adaptable to the other.
- LPMLN's Inconsistency Resolution as P-log Defaults: The translation reveals how LPMLN's mechanisms for resolving inconsistencies in soft rules can be mapped to P-log's default reasoning capabilities through the use of auxiliary attributes and cr-rules.
- Probabilistic Stable Models as P-log Possible Worlds: The core insight is that the probabilistic stable models of an LPMLN program, which represent the most likely scenarios, directly correspond to the possible worlds of the translated P-log program.
- Modular and Linear-Time Translation: The efficiency and modularity of the translation are significant, implying that the theoretical relationship can be practically realized without prohibitive computational overhead.
Key Results
The main result is the definition of a linear-time constructible translation $\tau$ from any LPMLN program $M$ to a P-log program $\tau(M)$. This translation ensures that:
- There exists a bijection $\phi$ between the probabilistic stable models of $M$ and the possible worlds of $\tau(M)$.
- For any probabilistic stable model $W$ of $M$, its corresponding possible world $\phi(W)$ in $\tau(M)$ coincides on the atoms of $M$.
- The probability functions defined by $M$ and $\tau(M)$ coincide on the atoms of $M$.
This result is formalized in the "Main Theorem" and leads to the "Corollary 1," which states that the probability of any atom $A$ in an LPMLN program $M$ is equal to its probability in the translated P-log program $\tau(M)$. An example is provided to illustrate the translation of a simple LPMLN program into its P-log counterpart, demonstrating how the probabilistic stable models and their probabilities are preserved.
Limitations and Future Work
Limitations:
- The paper focuses on a simplified subset of LPMLN, specifically ground programs without double default negation or disjunction.
- The translation of LPMLN's soft rules relies on the concept of "selected" rules, and the paper acknowledges that the probability of a soft rule in LPMLN is not always directly proportional to its weight, especially when inconsistencies arise.
Future Work:
- Developing LPMLN Solvers: The authors plan to develop efficient inference engines for P-log and use the established translation to create LPMLN solvers.
- Comparing Solvers: They intend to compare the performance of LPMLN solvers derived from P-log with those based on existing LPMLN algorithms.
- Adapting Inference Methods: The paper suggests investigating the adaptation of inference methods from Markov Logic Networks (MLNs) and LPMLN to improve the efficiency of P-log solvers.
- Extending Translation: While the current translation is for a subset, future work might explore extending it to handle more complex LPMLN constructs.
Summary updated