On the Strong Equivalences for LPMLN Programs

Bin Wang, Jun Shen, Shutao Zhang, Zhizheng Zhang

TL;DR

This paper formalizes p-strong equivalence for $\text{LP}^{\text{MLN}}$, a powerful logic programming language that merges the non-monotonic reasoning of Answer Set Programming (ASP) with the probabilistic capabilities of Markov Logic Networks (MLN). By establishing a theoretical framework for when two probabilistic programs are interchangeable in any context, the authors provide the necessary tools for program simplification and more efficient solver implementations.

What Problem Does This Paper Address?

In traditional logic programming, two programs are "strongly equivalent" if they yield the same results when combined with any additional set of rules. This property is the "holy grail" for program optimization; it allows developers or compilers to swap a complex piece of code for a simpler one without worrying about the surrounding context.

While strong equivalence is well-understood for Answer Set Programming (ASP), $\text{LP}^{\text{MLN}}$ introduces a major complication: probability. In $\text{LP}^{\text{MLN}}$, rules have weights, and the "answers" (stable models) have associated probability degrees. 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 what other rules are added to the system. Before this paper, a rigorous model-theoretic characterization of this "probabilistic strong equivalence" was missing.

Methods

The authors extend the concept of SE-models (Strong Equivalence models)—a standard tool in ASP—to the weighted world of $\text{LP}^{\text{MLN}}$.

Key methodological steps include:

  • Defining p-strong equivalence: Establishing that 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.
  • Model-Theoretic Characterization: They prove that p-strong equivalence can be checked by looking at the weights of SE-models. Specifically, the weights of SE-models in one program must be a scaled version (using constants $c$ and $k$ related to soft and hard rules) of the weights in the other.
  • Relaxed Notions: They introduce "sp-strong equivalence" (for soft stable model semantics) and "p-uniform equivalence" (where programs are only extended by sets of facts, rather than arbitrary rules).
  • Complexity Mapping: The authors use reductions to propositional tautology checking to determine the computational difficulty of verifying these equivalences.

Datasets

This is a theoretical paper focused on formal logic and computational complexity. Consequently, it does not use empirical datasets or benchmarks. Instead, it utilizes illustrative, hand-crafted logic programs (e.g., Examples 2.1 through 7.2) to demonstrate specific edge cases and prove theorems.

Key Insights and Ideas

  • The "q-strong" Collapse: The authors investigated "qualitatively strong equivalence" (q-strong), where one only cares if the relative ordering of probabilities is preserved. Surprisingly, they discovered that q-strong equivalence is mathematically identical to p-strong equivalence. You cannot relax the requirement to just "preserving the order" without it effectively becoming "preserving the exact values."
  • Bridging Formalisms: The paper shows that $\text{LP}^{\text{MLN}}$ can act as a "lingua franca" for other ASP extensions. By translating ASP with weak constraints or ordered disjunctions into $\text{LP}^{\text{MLN}}$, researchers can use the results in this paper to study strong equivalence in those older domains.
  • Redundancy Patterns: The authors identified specific syntactic patterns (like TAUT and CONTRA) that make a rule "valid" or "semi-valid." A "valid" rule is p-strongly equivalent to an empty program, meaning it can be deleted entirely without any impact on the program's logic or probability distribution.

Key Results

  • Complexity Classes: The authors proved that deciding semi-strong, p-strong, and sp-strong equivalence is co-NP-complete. Deciding semi-uniform equivalence (equivalence under factual extensions) is slightly harder, sitting in $\Pi^p_2$.
  • Scaling Theorem: Theorem 3.23 provides the definitive test for p-strong equivalence: two programs are equivalent if and only if they share the same SE-models and their weights satisfy a specific exponential scaling equation.
  • Solver Optimization: The paper provides a concrete algorithm (Algorithm 1) for simplifying $\text{LP}^{\text{MLN}}$ programs by eliminating redundant rules based on five specific syntactic conditions (Table 9).

Limitations and Future Work

  • Uniform Equivalence Gap: While the authors provided a sufficient condition for p-uniform equivalence, they acknowledge that a general necessary and sufficient condition for programs containing "hard" rules (rules with infinite weight) remains elusive.
  • Approximate Equivalence: Since the "qualitative" relaxation (q-strong) failed to provide a simpler alternative to p-strong equivalence, the authors suggest that future work should explore "approximate" strong equivalence—where probabilities are allowed to differ within a small error bound ($\epsilon$).
  • Syntactic Discovery: The authors aim to automate the discovery of more complex syntactic conditions that imply strong equivalence, which would further enhance the speed of $\text{LP}^{\text{MLN}}$ solvers.

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