In this paper, we present a new knowledge representation and reasoning tool to handle uncertainty, inconsistencies, and preferences by combining the ideas of LPMLN and logic programming with ordered disjunction (LPOD). The former is an extension of Answer Set Programming (ASP) that is designed for handling uncertainty and inconsistencies in knowledge representation by incorporating the method in Markov Logic Networks (MLN). The latter is a logic formalism to represent preferences in ASP, which is a simple yet efective way to handle preferences. Firstly, we present a new knowledge representation language o-LPMLN that extends LPMLN by introducing ordered disjunctions. Then, we present an example to show the use of the language. Finally, we present an approach to computing o-LPMLN programs by translating them into regular LPMLN programs. Results obtained in this paper provide an alternative tool to handle inconsistencies, uncertainty, and preferences in a unified framework. Moreover, a by-product of the paper is that we present an approach to implementing LPOD via using LPMLN solvers.
LPMLN [
In many real-world applications, preferences are inevitable. For example, it
has been shown that many problems can be formulated as a qualitative
optimization problem [
In this paper, we present a new language o-LPMLN, which can be regarded as
an extension of LPMLN and LPOD. Since there are several usable LPMLN solvers,
the extension is expected to be a powerful knowledge representation and
reasoning tool for handling uncertainty, inconsistencies, and preferences. Firstly, we
define the syntax and semantics of the language o-LPMLN. Secondly, we present
an example to show the use of the language o-LPMLN. Thirdly, we present a
modular and linear-time constructible translation from o-LPMLN programs to
regular LPMLN programs, which provides an alternative approach to implementing
o-LPMLN by using existing LPMLN solvers [
In this section, we review the language of LPMLN and LPOD. Note that throughout this paper, we consider only finite ground logic programs, that is, logic programs containing no variables. And we assume the reader is familiar with the notions in ASP. 2.1
LPMLN An LPMLN program is a finite set of weighted rules w : r, where w is either a symbol denoting the “infinite weight” or a real number, and r is an ASP rule of the form h1 _ ::: _ hk b1; :::; bm; not c1; :::; not cn: (4) where hs, bs and cs are literals, _ is epistemic disjunction, and not is default negation. For an ASP rule r of the form (4), the head of r is head(r) = fhi j 1 i kg, the positive body of r is body+(r) = fbi j 1 i mg, the negative body of r is body (r) = fci j 1 i ng, and the literals occurred in r is lit(r) = head(r) [ body+(r) [ body (r). Therefore, an ASP rule r of the form (4) can also be abbreviated as “head(r) body+(r); not body (r)” or “head(r) body(r)”. An LPMLN rule w : r is called soft if w is a real number, and hard if w is . By M s and M h we denote the sets of all soft rules and hard rules in an LPMLN program M respectively. By M we denote the set of unweighted ASP counterpart of an LPMLN program M , i.e. M = fr j w : r 2 M g. An LPMLN program is called ground if its rules contain no variables. For a ground LPMLN program M , we use W (M ) to denote the weight degree of M , i.e. W (M ) = exp (∑w:r2M w).
A ground LPMLN rule w : r is satisfied by a consistent set X of ground
literals, denoted by X j= w : r, if X j= r by the notion of satisfiability in ASP.
An LPMLN program M is satisfied by X, denoted by X j= M , if X satisfies all
rules in M . By MX we denote the LPMLN reduct of an LPMLN program M w.r.t.
X, i.e. MX = fw : r 2 M j X j= w : rg. X is a stable model of the program M
if X is a stable model of MX and M h MX . And by SM (M ) we denote the
set of all stable models of an LPMLN program M . For an interpretation I, the
weight degree W (M; I) of I w.r.t. M is defined as
and if I 2 SM (M ), the probability degree P (M; I) of I w.r.t. M is defined as
For a literal l, the probability degree P (M; l) of l w.r.t. M is defined as
Note that in its original definitions [
W (M; I) = W (MIs) P (M; I) = P (M; l) =
W (M; I) X′2SM(M)W (M; X′)
∑ l2X;X2SM(M)
P (M; X) (5) (6) (7) 2.2
LPOD
Following Lee and Yang’s point [
Definition 1. ri, is defined as
For an LPOD rule r, its i-th option (1 i
o(r)), denoted by hi
body(r); not h1; :::; not hi 1: Definition 2. A split program of an LPOD P is obtained from P by replacing each rule in P o by one of its options.
Based on the above definitions, the semantics of an LPOD P is defined as
follows. A consistent set S of literals is a candidate stable model of P if it is
a stable model of a split program of P . By CSM (P ) we denote the set of all
candidate stable models of P . The satisfaction degree deg(I; r) of an LPOD rule
r w.r.t. an interpretation I is defined as
(8)
(9)
deg(I; r) =
{1;
if I ̸j= body(r);
(10)
minfk j hk 2 head(r) \ Ig; otherwise:
And the satisfaction degree deg(I; P ) of an LPOD P w.r.t. an interpretation I
is defined as the sum of satisfaction degrees of LPOD rules in P w.r.t. I, i.e.
deg(I; P ) = ∑r2P o deg(I; r). For a candidate stable model S of P , by Si(P ) we
denote the set of LPOD rules in P o that are satisfied by S at degree i. Based on
the notion of satisfaction degree, for two candidate stable model X and Y of P ,
Brewka [
X >ps Y , if deg(P; X) < deg(P; Y ).
For each pr 2 fc; i; p; psg, a candidate stable model X of P is a pr-preferred stable model if there is no candidate stable model Y of P such that Y >pr X. 3
o-LPMLN To handle preferences in LPMLN naturally, we extend LPMLN by introducing ordered disjunctions in this section, the obtained language is called o-LPMLN.
Syntactically, an o-LPMLN program M consists of two parts: the regular part M r and the ordered disjunction part M o, where M r is a regular LPMLN program, and M o consists of rules of the form (8) preceded by “ ”, called weighted ordered disjunctive rules (wo-rules for simplicity). A wo-rule is a hard rule, because we treat the preferences as some conditions that must be satisfied in solving problems. As a consequence, the preference criteria are used prior to certainty degrees in computing inference results of an o-LPMLN program, which will be shown later.
Similar to LPOD, we have the following definitions.
Definition 3. For a wo-rule : r, its i-th option (1 : ri, where ri is the i-th option of rule r. i o(r)) is defined as Definition 4. For an o-LPMLN program M , a split program of M is obtained by replacing each rule in M o by one of its options.
Semantically, a consistent set X of literals is a candidate stable model of M , if X is a stable model of a split program of M . By CSM (M ) we denote the set of all candidate stable models of M . The satisfaction degree deg(I; : r) of a wo-rule : r w.r.t. an interpretation I and the satisfaction degree deg(I; M ) of an o-LPMLN program M w.r.t. I are defined the same as in LPOD. Therefore, the preferred stable models of an o-LPMLN program M are defined the same as in LPOD, that is, for each pr 2 fc; i; p; psg, a candidate stable model X of M is a pr-preferred stable model if there is no candidate stable models Y of M such that Y >pr X. By pr-SM (M ) we denote the set of all pr-preferred stable models of M under a preference criterion pr 2 fc; i; p; psg.
In addition, the weight degree W (M; X) of a candidate stable model X w.r.t. an o-LPMLN program M is defined the same as in LP MLN, i.e. W (M; X) = W (M Xs ). And the probability degree Ppr(M; X) of a pr-preferred stable model X w.r.t. an o-LPMLN M is defined as follows
Ppr(M; X) = ∑Y 2pr-SM(M) W (M; Y )
W (M; X) (11) where pr 2 fc; i; p; psg. Here, we do not define the probability degree for any candidate stable model for two main reasons. Firstly, preferred stable models are used to model intended solutions of a problem, while non-preferred stable models are usually discarded. Hence, considering the probability of all candidate stable models is not useful practically. Secondly, many candidate stable models may satisfy the same subprogram, which means the probability defined for these stable models cannot measure the “importance” of a stable model appropriately. For the same reason, we define the probability degree Ppr(M; l) of a literal l w.r.t. an o-LPMLN program M as follows
∑ l2X;X2pr-SM(M) Ppr(M; l) =
Ppr(M; X) (12)
Following the above definitions, the steps of computing the inference results of an o-LPMLN program M are as follows 1. compute all candidate stable models of M ; 2. find all preferred stable models of M ; 3. compute weight and probability degrees of all preferred stable models; 4. compute the probability degrees of literals w.r.t. M .
Now we use an example to show the use of o-LPMLN in handling uncertain and inconsistent knowledge with preferences.
Example 1. This example is from the Example 1 in [
The question is where should I go today? The above eight sentences can be encoded in the following o-LPMLN program M , in which w stand for wet, r for rain, h for humid, c for cloudy, go_c for going to cinema, go_b for going to beach, s for sultriness, f for being fresh.
: :w : w : f : :f 4 : s 2 : r : h:
go_c; r: go_b; r: go_c; s:
go_b; s: h: c: (r1) (r2) (r3) (r4) (r5) (r6) (r7) 4 : c: 1 : :c: : go_b
f :w: : go_b _ go_c: : go_b; go_c: (r8) (r9) (r10) (r11) (r12) Each of rule (r1) - (r10) in M expresses some knowledge in above sentences, where (r5) - (r9) handle uncertain and inconsistent knowledge in a regular LPMLN style, and (r10) handles preferences in an LPOD style. Rules (r11) and (r12) means “I have to go to cinema or beach”. All candidate stable models of M are shown in Table 1. From the table, it is easy to check that the candidate stable models containing go_b (denoted by SMb) are preferred to those containing f aSnMdb:>wpr(dSeMnoft,edSMbybS>Mprf SaMndnSw,Mannwd rSeMspfec>tipvrelSy)M, in.we..fAorltehaocuhgphrb2otfhc;oif; pca;pnsdgi-, date stable models X = fr; s; c; f; h; :w; go_cg and Y = fr; s; c; w; h; :f; go_bg are the most probable stable models, we choose to go to beach, which shows the efect of preferences in decision making. If we arrange our trip based on the preferred stable models, the probability degree we are wet is greater than 0:83. Note that the exact probability degree is unknown, because we are not sure if it rains in some cases, which shows the abilty of LPMLN in reasoning over uncertain knowledge.
Computing o-LPMLN Programs In this section, we present a translation from o-LPMLN programs to LPMLN programs, which provides an alternative approach to implementing o-LPMLN.
In previous section, we rewrite an LPOD rule “a b:” in LPMLN as follows 2 : a: And we show that the above LPMLN program fails to capture the meaning of original LPOD rule. The gap between above LPOD and LPMLN rules is caused by following property of LPOD rules, called satisfaction chain property. Proposition 1. Let r be an LPOD rule in an LPOD P , if X is a candidate stable model of P , then X j= rk for any deg(X; r) k o(r), where rk is the k-th option of r.
Obviously, our LPMLN encoding of an LPOD rule cannot express the satisfaction chain property. Therefore, to compute LPOD rules in LPMLN, we need to encode not only the preferences but also satisfaction chain property expressed by the rule, which is the intuition of our translation method presented in this section. Definition 5. Given an o-LPMLN program M , its LPMLN counterpart (M ) consists of three parts, i.e. (M ) = M r [ 1(M o) [ 2(M o), where M r is the regular part of M , and the other two parts of (M ) are defined as follows 1(M o) = f : sh(r) j defined as follows
: r 2 M og, where sh(r) is a complete shift of r body(r); not h1; :::; not ho(r): (15) 2(M o) = f 1 : rk j : r 2 M o; and 1 k o(r)g.
Definition 5 presents a linear and modular translation from o-LPMLN to LPMLN, which uses the ideas in split program to express the satisfaction chain property of o-LPMLN rules. Lemma 1 shows that an o-LPMLN program and its LPMLN counterpart coincide on their (candidate) stable models.
Lemma 1. Given an o-LPMLN program M , (M ) is the LPMLN counterpart defined in Definition 5, a consistent set X of literals is a candidate stable model of M if it is a stable model of (M ).
Proof. The proof is divided into two parts, in the first part, we show that if X 2 CSM (M ) then X 2 SM ( (M )); in the second part, we show that if X 2 SM ( (M )) then X 2 CSM (M ). For an o-LPMLN program M , let M be a split program of M . For each wo-rule : r 2 M o, let : r be the corresponding LPMLN rule in M , and : sh(r) be the corresponding rule in 1(M o).
Part 1: For the split program M , without loss of generality, suppose X is a stable model of M . By the definition, for each wo-rule : r 2 M o, we have X j= head(r ) or X ̸j= body(r ), which means X ̸j= body(sh(r)), i.e. X j= : sh(r). Therefore, we can infer that X j= 1(M o), which means 1(M o) (M )X . By the definition of split program, we have (M r)h MX (M )X . Assume there is a proper subset X′ of X such that X′ j= (M )X , by above results, we have X′ j= MX , which contradicts with the premise that X is a stable model of M . Hence, X is a stable model of (M ).
Part 2: Suppose X is a stable model of (M ). By the definition, it is obvious that (M )X = M Xr [ 1(M o) [ f 1 : rk 2 2(M o) j deg(X; : r) k o(r)g. Let M (X) be a split program of M w.r.t. X, M (X) is constructed as follows – add all rules in M r to M (X); – for each o-LPMLN rule : r 2 M o, add r).
: rk to M (X), where k = deg(X; : It is clear that M (X) is a split program of M and X j= M (X). Assume there is a proper subset X′ of X such that X′ j= M (X). From the proof in Part 1, we have X′ j= M Xr [ 1(M o). By Proposition 1, it is clear that X′ j= (M )X , which contradicts with X 2 SM ( (M )). Hence, we can infer that X 2 CSM (M ).
Combining the above results, we have shown that CSM (M ) = SM ( (M )), Lemma 1 is proven.
Now we investigate the preference criteria in the context of LPMLN. Firstly, we introduce some notations. For an o-LPMLN program M and its LPMLN counterpart (M ), the weight degree W ( (M ); X; r) of X w.r.t. a wo-rule : r 2 M o is defined as
W ( (M ); X; : r) = W ( 2(f : rg)X ) (16) According to the satisfaction chain property for LPOD rules, we can obtain the relationship between satisfaction degree and weight degree defined in o-LPMLN , which is shown in Proposition 2.
Proposition 2. Given an o-LPMLN program M and its LPMLN counterpart (M ), for a candidate stable model X 2 CSM (M ) and a wo-rule : r 2 M o, the satisfaction degree deg(X; : r) of : r w.r.t. X can be derived from the weight degree W ( (M ); X; : r) of X w.r.t. : r, i.e.
deg(X; : r) = o(r) + 1 + ln(W ( (M ); X; : r)) (17)
Based on the results in Proposition 2, it is clear that the preferred stable model of an o-LPMLN program M can be computed from its LPMLN counterpart, which is shown in Theorem 1.
Theorem 1. Given an o-LPMLN program M and its LPMLN counterpart (M ), all computing results of M can be derived from the computing results of (M ), that is, – CSM (M ) = SM ( (M )); – for each candidate stable model X, W (M; X) = W (M r; X); – for each pr 2 fc; i; p; psg, pr-preferred stable models of M can be derived from the computing results of (M ).
Theorem 1 directly implies an approach to computing o-LPMLNs via
translating it into LPMLN programs and using existing LPMLN solvers, such as LPMLN2ASP
[
Corollary 1. Given an o-LPMLN program M and its LPMLN counterpart (M ), a consistent set X of literals is a ps-preferred stable model of M if X is a stable model of (M ), and there does not exist a stable model Y 2 SM ( (M )) such that W ( 2(M o); Y ) < W ( 2(M o); X).
Until now, we have shown an approach to computing o-LPMLN programs via using existing LPMLN solvers. Actually, it is easy to observe that our approach presented here can also be used to computing LPODs, since an LPOD can be viewed as an o-LPMLN program without soft rules. It is worth noting that although LPOD rules can be encoded in LPMLN, our extension of LPMLN cannot only be seen as a syntactic sugar. On the one hand, the ordered disjunction provides a way to express preferences in LPMLN, which is diferent from uncertain and inconsistent knowledge essentially. On the other hand, o-LPMLN introduces new criteria to evaluate stable models of an LPMLN program, which enriches the expressivity of LPMLN.
In addition, the LPMLN counterpart of an o-LPMLN program is linear-time constructible, which means the computational complexity of o-LPMLN is the same as that of LPMLN, and our extension of LPMLN does not increase the computational complexity. 5
Concerning related work, since LPOD is an earlier work on representing
preferences in ASP, there have been several formalisms presented after it, such as
Answer Set Optimization [
LPPOD [
In addition, Lee and Yang [
In this paper, we present an alternative knowledge representation and reasoning tool for handling inconsistencies, uncertainty, and preferences in a unified framework, which is an extension of LPMLN by introducing ordered disjunctions, called o-LPMLN. Our contributions are as follows. Firstly, we present the syntax and semantics of language o-LPMLN. Secondly, we present a translation from o-LPMLN to regular LPMLN programs. Using existing LPMLN solvers, the translation provides a method to implement o-LPMLN. As a by-product, the translation also provides a one-shot approach to implementing LPOD.
For the future, we plan to further study the combination of LPMLN and LPOD. For example, in this paper, we treat LPOD rules as hard rules in LPMLN, while this restriction should be relaxed in some cases, i.e. the preferences should be allowed to be dissatisfied, which will be discussed in further work. Moreover, we plan to develop an eficient o-LPMLN solver, and use o-LPMLN in more practical scenarios. 7
We are grateful to the anonymous referees for their useful comments. This work is supported by the National Key Research and Development Plan of China (Grant No.2017YFB1002801).