On the Strong Equivalences for LPMLN Programs

Bin Wang, Jun Shen, Shutao Zhang, Zhizheng Zhang

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.

An example of LPMLN rules with associated weights.

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 relationship between stable models, program weights, and resulting probabilities.

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

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. First of all, we present the notion of p-strong equivalence for LPMLN and present a model-theoretical characterization for the notion. And we investigate the relationships among the p-strong equivalence and other existing notions of strong equivalences for LPMLN. Then, we investigate several properties of the p-strong equivalence from the following four aspects. Firstly, we investigate two relaxed notions of the p-strong equivalence according to practical scenarios of program rewriting, and present corresponding characterizations for the notions. Secondly, we analyze the computational complexities of deciding strong equivalences for LPMLN programs. Thirdly, we investigate the relationships among the strong equivalences of LPMLN and two extensions of ASP: ASP with weak constraints and ordered disjunctions. Finally, we investigate LPMLN program simplification via the p-strong equivalence and present some syntactic conditions that decide the p-strong equivalence between a single LPMLN rule and the empty program. The contributions of the paper are as follows. Firstly, all of the results presented in this paper provide a better understanding of LPMLN programming, which helps us further explore the properties of LPMLN. Secondly, the relationships among the strong equivalences open a way to study the strong equivalences for some logic formalisms by translating into LPMLN. Thirdly, the program simplification can be used to enhance the implementations of the LPMLN solvers ...
BibTeX
@inproceedings{wang2019strong,
  author = {Bin Wang and Jun Shen and Shutao Zhang and Zhizheng Zhang},
  title = {{On the Strong Equivalences for LPMLN Programs}},
  booktitle = {Electronic},
  year = {2019},
  doi = {10.4204/eptcs.306.18},
}
Figure