We introduce the language LPMLN that extends logic programs under the stable model semantics to allow weighted rules similar to the way Markov Logic considers weighted formulas. LPMLN is a proper extension of the stable model semantics to enable probabilistic reasoning, providing a way to handle inconsistency in answer set programming. We also show that the recently established logical relationship between Pearl's Causal Models and answer set programs can be extended to the probabilistic setting via LPMLN.
Logic programs under the stable model semantics is the language for Answer Set Programming (ASP). Many useful knowledge representation constructs are introduced into ASP, and several efficient ASP solvers are available. However, like many “crisp” logic approaches, adding a single rule may easily introduce inconsistency. Also, ASP is not well suited for handling probabilistic reasoning.
Markov Logic is a successful approach to combining first-order logic and probabilistic graphical models in a single representation. Syntactically, a Markov Logic Network (MLN) is a set of weighted first-order logic formulas. Semantically, the probability of each possible world is derived from the sum of the weights of the formulas that are true under the possible world. Markov Logic has shown to formally subsume many other SRL languages and has been successfully applied to several challenging applications, such as natural language processing and entity resolution. However, the logical component of Markov Logic is the standard first-order logic semantics, which does not handle the concept of rules as in ASP.
We introduce a simple approach to combining the two successful formalisms, which allows
for logical reasoning originating from the stable model semantics as well as probabilistic
reasoning originating from Markov Logic. LPMLN is a proper extension of the standard stable
model semantics, and as such embraces the rich body of research in answer set programming.
Interestingly, the relationship between LPMLN and Markov Logic is analogous to the
wellknown relationship between ASP and SAT
LPMLN provides a viable solution to inconsistency handling with ASP knowledge bases. For example, consider ASP knowledge base KB1 that states that Man and Woman are disjoint subclasses of Human.
The data about Jo is actually inconsistent, so under the (deterministic) stable model semantics, the combined knowledge base KB = KB1 [ KB2 [ KB3 is inconsistent, and may derive any conclusion. On the other hand, it is intuitive to view that one of the data sources may be wrong, and we still want to conclude that Jo is a Human. The same conclusion is obtained under the LPMLN semantics.
For another aspect of LPMLN, we consider how it is related to Pearl’s Probabilistic Causal
Models. Both answer set programs and Probabilistic Causal Models allow for
representing causality, but a precise relationship between them is established only in a recent
paper
Throughout this paper, we assume a first-order signature that contains no function constants of positive arity. There are finitely many Herbrand interpretations of .
A1; : : : ; Ak
Ak+1; : : : ; Am; not Am+1; : : : ; not An; not not An+1; : : : ; not not Ap
1 Strictly speaking, the relationship shown in that paper is between Pearl’s causal models and nonmonotonic causal
theories
A1 _ _ Ak
Ak+1 ^: : :^Am ^:Am+1 ^: : :^:An ^::An+1 ^: : :^::Ap :
A logic program is a finite set of rules. A logic program is called ground if it contains no variables.
We say that an Herbrand interpretation I is a model of a ground program if I satisfies all implications (2) in (as in classical logic). Such models can be divided into two groups: “stable” and “non-stable” models, which are distinguished as follows. The reduct of relative to I, denoted I , consists of “A1 _ _ Ak Ak+1 ^ ^ Am” for all rules (2) in such that I j= :Am+1 ^ ^ :An ^ ::An+1 ^ ^ ::Ap. The Herbrand interpretation I is called a (deterministic) stable model of if I is a minimal Herbrand model of I . (Minimality is in terms of set inclusion. We identify an Herbrand interpretation with the set of atoms that are true in it.)
The definition is extended to any non-ground program by identifying it with gr [ ], the ground program obtained from by replacing every variable with every ground term of .
The semantics was extended in many ways, e.g., allowing some useful constructs, such
as aggregates and abstract constraints (e.g.,
We say that an LPMLN program is ground if its rules contain no variables. We identify any LPMLN program P of signature with a ground LPMLN program gr [P], whose rules are obtained from the rules of P by replacing every variable with every ground term of . The weight of a ground rule in gr [P] is the same as the weight of the rule in P from which the ground rule is obtained.
By P we denote the logic program obtained from P by dropping the weights, i.e., P = fR j w : R 2 Pg. By PI we denote the set of rules in P which are satisfied by I.
3.2 Semantics of LPMLN A model of an MLN does not have to satisfy all formulas in the MLN. For each model, there is a unique maximal subset of the formulas that are satisfied by the model, and the weights of the formulas in that subset determine the probability of the model.
Likewise, a stable model of an LPMLN program does not have to be obtained from the whole program. Instead, each stable model is obtained from some subset of the program, and the weights of the rules in that subset determine the probability of the stable model. At first, it may not seem obvious if there is a unique maximal subset that derives such a stable model. Nevertheless, it follows from the following proposition that this is indeed the case, and that the subset is exactly PI . Proposition 1 For any logic program and any subset 0 of , if I is a (deterministic) stable model of 0 and I satisfies , then I is a (deterministic) stable model of as well.
The proposition tells us that if I is a stable model of a program, adding additional rules to this program does not affect that I is a stable model of the resulting program as long as I satisfies the rules added. On the other hand, it is clear that I is no longer a stable model if I does not satisfy at least one of the rules added.
Thus we define the weight of an interpretation I w.r.t. P, denoted WP(I), as
WP(I) = exp
X w:R 2 P
Ij=R
! w : Let SM[P] be the set fI j I is a stable model of PI g: Notice that SM[P] is never empty because it always contains the empty set. It is easy to check that the set ; always satisfies P ;, and it is the smallest set that satisfies the reduct (P ;);.
Using this notion of a weight, we define the probability of an interpretation I under P, denoted PrP[I], as follows. For any interpretation I,
PrP[I] = 8< lim PWP(I)
!1 J2SM[P] WP(J) :0 if I 2 SM[P]; otherwise: We omit the subscript P if the context is clear. We say that I is a (probabilistic) stable model of P if PrP[I] 6= 0.
The intuition here is similar to that of Markov Logic. For each interpretation I, we try to find a maximal subset (possibly empty) of P for which I is a stable model (under the standard stable model semantics). In other words, the LPMLN semantics is similar to the MLN semantics except that the possible worlds are the stable models of some maximal subset of P, and the probability distribution is over these stable models.
For any proposition A, PrP[A] is defined as:
PrP[A] =
X I: Ij=A
PrP[I]: PrP[A j B] =
PrP[A ^ B] :
PrP[B] (In place of “I j= A,” one might expect “I is a stable model of P that satisfies A.” The change does not affect the definition.)
Conditional probability under P is defined as usual. For propositions A and B,
The following example illustrates how inconsistency can be handled in LPMLN. Example 1 (handling inconsistency) Consider the example in Section 1. Recall that there are no deterministic stable models of KB. However, when we identify each rule as a hard rule under the LPMLN semantics (i.e., having as the weight), there are 3 probabilistic stable models (with non-zero probabilities) assuming that Jo is the only element in the domain. Let Z = 3e4 + 3e3 + e2 .
I0 = ; with probability lim
!1 e3 =Z = 0. I1 = fMan(Jo)g with probability lim !1 e3 =Z = 0.
I2 = fWoman(Jo)g with probability lim !1 e3 =Z = 0.
I3 = fHuman(Jo)g is not a stable model of KBI3 , so its probability is 0.
I4 = fMan(Jo); Human(Jo)g with probability lim !1 e4 =4Z==Z =13. 13 .
I5 = fWoman(Jo); Human(Jo)g with probability lim I6 = fMan(Jo); Woman(Jo)g with probability lim !1!e12 e=Z = 0.
I7 = fMan(Jo); Woman(Jo); Human(Jo)g with probability lim
Pr[Human(Jo) = t] = Pr[I4] + Pr[I5] + Pr[I7] = 1: for I4, KB3 is disregarded; for I5, KB2 is disregarded; for I7, the last rule of KB1 is disregarded.
P r[I4]+P r[I7] Pr[Human(Jo) = t j Man(Jo) = t] = P r[I1]+P r[I4]+P r[I6]+P r[I7] = 1.
Pr[Man(Jo) = t j Human(Jo) = t] = P r[IP4]r+[IP4]r+[IP5]r+[IP7]r[I7] = 32 .
Often an LPMLN program P consists of the set Ps of soft rules and the set of Ph of hard rules together, and there exists at least one stable model that is obtained from all hard rules plus some subset of soft rules. In this case, we may simply consider the weights of soft rules only in computing the probabilities of stable models. Let SM0[P] be the set and let
fI j I is a stable model of Ph [ (Ps)I g; Pr0P[I] = 8 <
J2SM0[P] :0
PWPs (I)
WPs (J) if I 2 SM0[P]; otherwise: Note the absence of lim in the definition of Pr0P[I]. Also unlike PrP[I], SM0[P] may be !1 empty, in which case Pr0P[I] is not defined.
Proposition 2 Let P = Ps [ Ph be an LPMLN program where Ps consists of soft rules and Ph consists of hard rules. If SM0[P] is not empty, for every interpretation I, PrP[I] coincides with Pr0P[I].
Thus the presence of at least one interpretation in SM0[P] implies that every other stable model of P (with non-zero probability) should also satisfy all hard rules in P. Note that Example 1 does not satisfy the nonemptiness condition of SM0[P], whereas the following example does.
Example 2 (LPMLN vs. MLN)
Consider a variant of the main example from
ConcertBooked; not Cancelled
Cancelled:
Since SM0[P] is not empty, in view of Proposition 2, the probability of the two stable models are as follows: eln0:2 I1 = fConcertBooked; Cancelledg, with PrP[I1] = eln0:2+eln0:8 = 0:2. eln0:8
I2 = fConcertBooked; LongDriveg, with PrP[I2] = eln0:2+eln0:8 = 0:8.
If this program is understood under the MLN semantics, say in the syntax : ConcertBooked : ConcertBooked ^ :Cancelled ! LongDrive ln 0:2 : Cancelled ln 0:8 : :Cancelled; there are three MLN models with non-zero probabilities:
I1 = fConcertBooked; Cancelledg with Pr[I1] = 0:2=1:4 ' 0:1429.
I2 = fConcertBooked; LongDriveg with Pr[I2] = 0:8=1:4 ' 0:5714.
I3 = fConcertBooked; Cancelled; LongDriveg with Pr[I3] = 0:2=1:4 ' 0:1429.
The presence of I3 is not intuitive (why have a long drive when the concert is cancelled?)
Remark. In some sense, the distinction between soft rules and hard rules in LPMLN is
similar to the distinction between consistency-restoring rules (CR-rules) and standard ASP rules
under CR-Prolog
Remark. This example also illustrates a correspondence between LPMLN and probabilistic
logic programming languages based on the distribution semantics
Example 3 It is well known that Markov Logic does not properly handle inductive definitions,2 while LPMLN gives an intuitive representation. For instance, consider that x may influence y if x is a friend to y, and the influence relation is a minimal relation that is closed under transitivity. : Friend(A; B) : Friend(B; C) 1 : Influences(x; y) : Influences(x; y)
Friend(x; y)
Influences(x; z); Influences(z; y): Note that the third rule is soft: a person does not always influence his/her friend. The fourth rule says if x influences z, and z influences y, we can say x influences y. On the other hand, we do not want this relation to be vacuously true.
Assuming that there are only three people A, B, C in the domain (thus there are 1 +
1 + 9 + 27 ground rules), there are four stable models with non-zero probabilities. Let Z =
e9 + 2e8 + e7.
2 “Markov Logic has the drawback that it cannot express (non-ground) inductive definitions.”
I2 = fFriend(A; B); Friend(B; C); Influence(A; B)g with probability e8=Z.
I3 = fFriend(A; B); Friend(B; C); Influence(B; C)g with probability e8=Z.
I4 = fFriend(A; B); Friend(B; C)g with probability e7=Z.
Thus we get
PrP[Influence(A; B) = t] = PrP[Influence(B; C) = t] = (e9 + e8)=Z = 0:7311.
PrP[Influence(A; C) = t] = e9=Z = 0:5344.
Increasing the weight of the soft rule yields higher probabilities for Influence(A; B) = t, Influence(B; C) = t, Influence(A; C) = t. Still, the first two have the same probability, and the third has less probability than the first two.
Note that the minimality of the influence relation is not expressible under the MLN semantics.
3.3 Relating LPMLN to ASP Any logic program under the stable model semantics can be turned into an LPMLN program by assigning the infinite weight to every rule. That is, for any logic program = fR1; : : : ; Rng, the corresponding LPMLN program P is f : R1; : : : ; : Rng. Theorem 1 For any logic program , the (deterministic) stable models of are exactly the (probabilistic) stable models of P whose weight is ek , where k is the number of all (ground) rules in . If has at least one stable model, then all stable models of P have the same probability, and are thus the stable models of as well.
The idea of softening rules in LPMLN is similar to the idea of “weak constraints” in ASP, which is used for certain optimization problems. A weak constraint has the form “ : Body [Weight : Level]:” The answer sets of a program plus a set of weak constraints are the answer sets of which minimize the penalty calculated from Weight and Level of violated weak constraints. However, weak constraints are more restrictive than weighted rules in LPMLN, and do not have a probabilistic semantics.
3.4 Completion: Turning LPMLN to MLN It is known that the stable models of a tight logic program coincide with the models of the program’s completion. This yielded a way to compute stable models using SAT solvers. The method can be extended to LPMLN so that their stable models along with the probability distribution can be computed using existing implementations of MLNs, such as Alchemy (http://alchemy.cs.washington.edu) and Tuffy (http://i.stanford.edu/ hazy/hazy/tuffy).
We define the completion of P, denoted Comp(P), to be the MLN which is the union of P and the hard rules : A !
_ w:A1;:::;Ak Body 2 P
A2fA1;:::;Akg
Body ^
^ A02fA1;:::;AkgnfAg :A0 ! for each ground atom A.
This is a straightforward extension of the completion from
Theorem 2 For any tight LPMLN program P such that SM0[P] is not empty, P (under the LPMLN semantics) and Comp(P) (under the MLN semantics) have the same probability distribution over all interpretations.
4 Embedding Pearl’s Probabilistic Causal Models in LPMLN
Notation: Following
As usual, a propositional formula is constructed from atoms, t, f, and propositional connectives, :, ^, _, !.
Definition 1 (structural theory) Assume that a finite set of propositional atoms is partitioned into a set of exogenous atoms U and a set of endogenous atoms V = fV1; : : : ; Vng. A Boolean structural theory is hU; V; F i, where F is a finite set of equations Vi = Fi, one for each endogenous atom Vi, and Fi is a propositional formula.
Definition 2 (causal diagram) The causal diagram of a Boolean structural theory hU; V; F i is the directed graph whose vertices are the atoms in U [ V and an edge goes from Vj to Vi if there is an equation Vi = Fi in the structural theory such that Vj occurs in Fi. We say that the structural theory is acyclic if its causal diagram is acyclic.
For any interpretation I and J of U [ V , we say that J 6=V I if J and I agree on all atoms in U and do not agree on some atoms in V .
Definition 3 (solution) Given a Boolean causal theory hU; V; F i, a solution (or a causal world) I is any interpretation of U [ V such that
I satisfies the equivalences Vi $ Fi for all equations Vi = Fi in F , and no other interpretation J such that J 6=V I satisfies all such equivalences Vi $ Fi. Definition 4 (causal model) A (Boolean) causal model hU; V; F i is an acyclic Boolean structural theory that has a unique solution for each realization (i.e., truth assignment) of U ; in other words, each truth assignment of U has a unique expansion to U [ V that is a solution. Definition 5 (probabilistic causal model) A probabilistic (Boolean) structural theory is a pair
hhU; V; F i; P (U )i where hU; V; F i is a Boolean structural theory, and P (U ) is a probability distribution over U . We assume that exogenous atoms are independent of each other. A Probabilisitic (Boolean) Causal Model (PCM) is a probabilistic structural theory (3) such that hU; V; F i is a causal model. The solutions of PCM (3) are the solutions of hU; V; F i. The probability of a solution I under the PCM M, denoted PM(I), is defined as P (U = I(U )).
Given a PCM M = hhU; V; F i; P (U )i, for any subset Y of V , we write YM(u) to denote the truth assignment of Y in the solution of M induced by u. The probability of Y = y is defined as
PM(Y = y) = Pfu j YM(u)=yg P (u): For any subset Y , Z of V , PM(Y = y j Z = z) is defined as
PM(Y = y j Z = z) =
Pfu j PYMf(uu)j Z=My(aun)d=ZzMg(uP)(=u)zg P (u) :
Consider, for example, the probabilistic causal model MF S for the Firing Squad
example
hhfU; W g; fC; A; B; Dg; F i; P (U; W )i F : C = U
A = C _ W B = C D = A _ B P (U = t) = p
P (W = t) = q
U denotes “The court orders the execution,” C denotes “The captain gives a signal,” A denotes “Rifleman A shoots,” B denotes “Rifleman B shoots,” D denotes “The prisoner dies,” and W denotes “Rifleman A is nervous.” There is a probability p that the court has ordered the execution; rifleman A has a probability q of pulling the trigger out of nervousness. The PCM has four solutions for each realization of U and W .
Solutions fU = f ; W = f ; C = f ; A = f ; B = f ; D = f g fU = f ; W = t; C = f ; A = t; B = f ; D = tg fU = t; W = f ; C = t; A = t; B = t; D = tg fU = t; W = t; C = t; A = t; B = t; D = tg Probability (1 p)(1 q) (1 p)q p(1 q)
pq
4.2 Embedding PCM in LPMLN
Since causal models assume propositional formulas, it is convenient to discuss the result by
first extending the syntax of LPMLN to weighted propositional formulas, that is of the form
w : F where F is a propositional formula and w is either a real number or the symbol .
We refer the reader to
Definition 6 (LPMLN representation) For any PCM M = hhU; V; F i; P (U )i, PM is the LPMLN program consisting of : Vi Fi for each equation Vi = Fi in M, and, for each exogenous atom Ui of M such that P (Ui = t) = p: (i) ln(p) : Ui and ln(1 p) : Ui if 0 < p < 1; (ii) : Ui if p = 1; (iii) : Ui if p = 0. For the Firing Squad example, assuming 0 < p; q < 1, PMF S is as follows: ln(1 ln(1 ln(p) : U
p) : ln(q) : W q) :
U W : C : A : B : D
U C _ W C A _ B: Theorem 3 The solutions of a probabilistic causal model M are identical to the stable models of PM and their probability distributions coincide.
Note that the acyclicity condition in PCM implies the tightness condition of its LPMLN program representation. Thus, using the completion method in Section 3.4, we can automate query answering for this domain using Alchemy.
Definition 7 (submodel) Given a Boolean causal model M = hU; V; F i, and a subset X of V , the submodel MX=x of M is the Boolean causal model obtained from M by replacing every equation Xi = Fi in the theory, where Xi 2 X, with Xi = xi. Given a PCM M = hM; P (U )i, MX=x = hMX=x; P (U )i.
For any PCM M = hhU; V; F i; P (U )i, let X, Y , Z be subsets of V . The probability of a counterfactual statement, represented as YX=x = y, is defined as
PM(YX=x = y) =
X fu j YMX=x (u)=yg
P (u):
The probability of a conditional counterfactual statement “Given Z is z, Y would have been y had X been x”, represented as YX=x = y j Z = z, is defined as
PM(YX=x = y j Z = z) =
Pfu j YMX=x (u) = y and ZM(u) = zg P (u) :
PfujZM(u)=zg P (u) For example, given that the prisoner is dead, what is the probability that the prisoner were (1 p)q not dead if rifleman A had not shot? This is asking: PM(DA=f = f j D = t) = 1 (1 p)(1 q) . 4.4 PCM Counterfactuals in LPMLN Counterfactual reasoning in PCM can be turned into LPMLN reasoning. The program LPMLN PtMwin consists of
: Vi Fi ^ :Do(Vi = t) ^ :Do(Vi = f) for each equation Vi = Fi in M, where Vi is a new symbol corresponding to Vi, and Fi is a formula obtained from F by replacing every occurrence of endogenous atoms W with W . rule : Vi
Do(Vi = t) (4) all rules in PM; rule for every Vi 2 V .
(Note that Do(Vi = t) is an atom, containing “=” as a part of the string.) Theorem 4 For any PCM M = hhU; V; F i; P (U )i and any subsets X; Y , Z of V , which are not necessarily disjoint from each other,
PM(YX=x = y j Z = z) = PrPtwin[Do(X=x)[Y
M where Do(X = x) is f : Do(Xi = xi) j i = 1; : : : ; jXjg. = y j Z = z];
Readers who are familiar with the twin network method for counterfactual reasoning
For the Firing Squad example, PtMwFinS is the union of PMF S and the set of rules : C U; not Do(C = t); not Do(C = f) : A C ; not Do(A = t); not Do(A = f) : A W; not Do(A = t); not Do(A = f) : B C ^ :Do(B = t) ^ :Do(B = f) : D (A _ B ) ^ :Do(D = t) ^ :Do(D = f) and rules (4) for Vi 2 fC; A; B; Dg. In accordance with Theorem 4,
PrPtMwFinS [f :Do(A=f )g[D = f j D = t] = 1 (1 (1 p)q p)(1 q) :
The LPMLN representation is similar to the one in
In
It is known that LPAD is related to several other languages. In
CP-logic
P-log
PrASP
While the study of more precise relationships between LPMLN and the above languages is future work, one notable distinction is that LPMLN uses Markov Logic as a monotonic basis, similar to the way ASP uses SAT as a monotonic basis. Most of the languages are meaningful only when the knowledge base is consistent, and thus do not address the inconsistency handling as in LPMLN.
LPMLN is a simple, intuitive approach to combine both ASP and MLNs. LPMLN provides a simple solution to inconsistency handling in ASP, especially when ASP knowledge bases are combined from different sources.
While MLN is an undirected approach, LPMLN is a directed approach, where the directionality comes from the stable model semantics. This makes LPMLN closer to Pearl’s causal models and ProbLog.
The work presented here calls for more future work. Obviously, there are many existing languages that we did not formally compare with LPMLN. While a fragment of LPMLN can be computed by existing implementations of and MLNs, one may design a native computation method for the general case. The close relationship between LPMLN and MLNs may tell us how to apply machine learning methods developed for MLNs to work with LPMLN programs. Acknowledgements We are grateful to Michael Bartholomew, Amelia Harrison, and the anonymous referees for their useful comments. This work was partially supported by the National Science Foundation under Grant IIS-1319794, South Korea IT R&D program MKE/KIAT 2010-TD-300404-001, and ICT R&D program of MSIP/IITP 10044494 (WiseKB). 3 http://www.krlab.cs.ttu.edu/papers/download/bg03.pdf