Abstract
LPMLN is a powerful knowledge representation and reasoning tool that combines the non-monotonic reasoning ability of Answer Set Programming (ASP) and the probabilistic reasoning ability of Markov Logic Networks (MLN). In this paper, we study the strong equivalence for LPMLN programs, which is an important tool for program rewriting and theoretical investigations in the field of logic programming. We present the notion of p-strong equivalence for LPMLN and a model-theoretical characterization for it. We investigate the relationships among p-strong equivalence and other existing notions, analyze computational complexities, and explore relationships with ASP extensions like weak constraints and ordered disjunctions. Finally, we investigate LPMLN program simplification and present syntactic conditions for p-strong equivalence between a rule and the empty program.
Introduction: The Challenge of Probabilistic Logic
In traditional logic programming, specifically Answer Set Programming (ASP), two programs are considered "strongly equivalent" if they yield the same set of stable models when combined with any arbitrary set of additional rules. This property is fundamental for program optimization, allowing for the substitution of complex code segments with simpler, equivalent ones without altering the global behavior.
However, the introduction of LPMLN—a formalism merging ASP's non-monotonicity with the probabilistic reasoning of Markov Logic Networks—adds a layer of complexity: rule weights. In LPMLN, rules are assigned weights that determine a probability distribution over stable models.
To be truly equivalent in this setting, two programs must not only produce the same stable models but also maintain the exact same probability distribution across those models, regardless of the context (the additional rules $R$ added to the system).
Defining p-Strong Equivalence
The core contribution of this research is the formalization of p-strong equivalence. Two programs $P$ and $Q$ are p-strongly equivalent if, for any program $R$, $P \cup R$ and $Q \cup R$ have the same stable models and identical probability distributions.
To characterize this, the authors extend the concept of SE-models (Strong Equivalence models) from ASP to the weighted domain. The semantics of LPMLN rely on calculating the weight of a program relative to an interpretation, which then determines the probability of a stable model.
The authors prove that p-strong equivalence can be verified by examining the weights of SE-models. Specifically, Theorem 3.23 establishes that two programs are equivalent if and only if they share the same SE-models and their weights satisfy a specific exponential scaling equation involving constants related to soft and hard rules.
Key Insights and Complexity
One of the most surprising findings is the "q-strong" collapse. The researchers investigated "qualitatively strong equivalence" (q-strong), where only the relative ordering of probabilities must be preserved. They discovered that q-strong equivalence is mathematically identical to p-strong equivalence; preserving the order effectively necessitates preserving the exact values.
Furthermore, the paper maps the computational complexity of these equivalences:
- co-NP-complete: Deciding p-strong, semi-strong, and sp-strong equivalence.
- $\Pi^p_2$: Deciding semi-uniform equivalence (equivalence under factual extensions).
Program Simplification and Solver Optimization
Beyond theoretical characterization, the paper provides practical tools for solver optimization. By identifying specific syntactic patterns—such as "valid" rules that are p-strongly equivalent to an empty program—the authors developed an algorithm for simplifying LPMLN programs. This allows for the elimination of redundant rules, significantly enhancing the performance of LPMLN solvers.
Conclusion and Future Work
While this work provides a robust framework for strong equivalence in LPMLN, several avenues remain open. A general necessary and sufficient condition for p-uniform equivalence in programs with "hard" rules (infinite weight) is still needed. Additionally, since qualitative relaxation proved equivalent to the strict version, future research may explore "approximate" strong equivalence, where probabilities are allowed to vary within a defined error bound ($\epsilon$).
Summary updated