Probabilistic Constraint Logic Theories

Abstract

Probabilistic logic models are used ever more often to deal with the uncertain relations typical of the real world. However, these models usually require expensive inference procedures. Very recently the problem of identifying tractable languages has come to the fore. In this paper we consider the models used by the learning from interpretations ILP setting, namely sets of integrity constraints, and propose a probabilistic version of them. A semantics in the style of the distribution semantics is adopted, where each integrity constraint is annotated with a probability. These probabilistic constraint logic models assign a probability of being positive to interpretations. This probability can be computed in a time that is logarithmic in the number of ground instantiations of violated constraints. This formalism can be used as the target language in learning systems and for declaratively specifying the behavior of a system. In the latter case, inference corresponds to computing the probability of compliance of a system's behavior to the model.

-

Probabilistic logic models are gaining popularity due to their successful application in a variety of elds, such as natural language processing, information extraction, bioinformatics, semantic web, robotics and computer vision.

However, these models usually require expensive inference procedures. Very recently the problem of identifying tractable languages has come to the fore. Proposals such as Tractable Markov Logic [ 9 ], Tractable Probabilistic Knowledge Bases [ 25,17 ] and fragments of probabilistic logics [ 24,16 ] strive to achieve tractability by limiting the form of sentences.

In the ILP eld, the learning from interpretation setting [ 8,2,7 ] o ers advantages in terms of tractability with respect to the learning from entailment setting. In learning from interpretations, the logic theories are sets of integrity constraints and the examples are interpretations. The coverage problem there consists in verifying whether the constraints are satis ed in the interpretations. This problem is simpler than checking whether an atom follows from a logic program because the constraints can be considered in isolation: the interpretation satis es the constraints i it satis es all of them individually. A rst attempt to this problem was presented in [ 11,10 ] where authors described the algorithm LFI-ProbLog for learning ProbLog programs from partial interpretations.

Our aim is to consider a probabilistic version of sets of integrity constraints with a semantics in the style of the distribution semantics [ 23 ]. Each integrity constraint is annotated with a probability and a model assigns a probability of being positive to interpretations. This probability can be computed in a time that is logarithmic in the number of groundings of the constraints that are violated.

The formalism we propose, Probabilistic Constraint Logic Theories (PCLT), has a variety of applications. It can be used as the target language of a learning system, thus lifting the learning from interpretations ILP setting to the probabilistic case.

It is also useful for system veri cation or the problem of checking whether a system's behaviour is compliant to a speci cation [ 14 ].

The system's speci cation can be given in a number of ways. Speci cations based on logic are appropriate to many applications since they provide a nonambiguous semantics. Additionally, Computational Logic frameworks come with operational semantics with formal correctness properties, which can be used for veri cation; such a feature has motivated the mapping of heterogeneous specication formalisms onto ones based on computational logic [ 15 ]. For instance, the SCIFF framework [ 1 ], applied to veri cation of multi-agent systems, medical guidelines, electronic commerce, is composed of a language for speci cation with an abductive logic programming semantics, and a sound and complete proof procedure, so that behaviours found correct by the proof procedure are indeed correct according to the declarative semantics, and vice-versa.

The essence of many logic-based speci cation languages (including SCIFF) is to provide a form of integrity constraints: logic formulas that represent protocols, rules or guidelines, and are required to be satis ed by the system's behaviour.

A binary notion of compliance (where the behaviour is compliant if it satis es all the integrity constraints, and simply non-compliant otherwise) may not be suited to applications where some amount of non-compliance is inevitable, and quantifying non-compliance is more important than just detecting it. One form of exibility is to allow the designer to specify the integrity constraints as optional, and to express how important each constraint is. PCTL allows precisely this.

The paper is organized as follows. In Sect. 2, we recall the notion of Constraint Logic Theory, and in Sect. 3 we de ne PCLT. In Sect. 4 we show how to compute the probability of compliance given the compliance to each integrity constraint. Sect. 5 discusses PCLTs in more detail while Sect. 6 introduces an extended version of CLTs. Sect. 7 discusses related work. Finally, Sect. 8 concludes the paper with some remarks on future work. 2

Constraint Logic Theories

A Constraint Logic Theory (CLT) [ 7 ] T is a set of integrity constraints (ICs) C of the form

L1; : : : ; Lb ! A1; : : : ; Ah (1) where the Lis are logical literals. Their conjunction L1; : : : ; Lb is called the body of the IC and is indicated with Body(C). The Aj are logical atoms, where the semicolon stands for disjunction, thus A1; : : : ; Ah is a disjunction of atoms called the head of the IC and indicated with Head(C).

Together with a CLT T , we may have a background knowledge B on the domain which is a normal logic program that can be used to represent domainspeci c knowledge.

CLTs can be used to classify Herbrand interpretations, i.e., sets of ground facts, that represent for example the behaviour of the system undergoing veri cation. Given a Herbrand interpretation I (in the following it will be called simply interpretation), the given background knowledge B is used to complete the information in I. Basically, instead of simply considering I, we consider a model M (B [ I) which follows the Prolog semantics (i.e. Clark completion [ 4 ]) where I is interpreted as a set of ground facts. In this way, all the facts of I are true in M (B [ I), moreover M (B [ I) can contain new facts derived from I using B.

Given an interpretation I, a background knowledge B and a CLT T we can ask whether T is true in I given B. Formally, an IC C is true in an interpretation I given a background knowledge B, written M (B [ I) j= C, if for every substitution for which Body(C) is true in M (B [ I), there exists a disjunct in Head(C) that is true in M (B [ I). If M (B [ I) j= C we say that I satis es the constraint C given B; if M (B [ I) 6j= C we say that I does not satisfy C. If every IC of a CLT T is true in it, then T is true in an interpretation I given B and we write M (B [ I) j= T . We also say I satis es T given B or that I is positive given T and B.

If all the variables that appear in the head also appear in the body, then the logical clause is range-restricted. As shown in [ 5 ], the truth of a range-restricted IC in an interpretation I with range-restricted background knowledge B can be tested by asking the goal ?

Body(C); :Head(C): against a Prolog database containing the atoms of I as facts together with the rules of the normal program B. By :Head(C) we mean :A1; : : : ; :Ah so the query is ?

L1; : : : ; Lb; :A1; : : : ; :Ah: (2) If the query fails, C is true in I given B, otherwise C is false in I given B. If B is range-restricted, every answer to a query Q against B [ I completely instantiates Q, i.e., it produces an element of M (B [ I). So the queries :Aj are ground when they are called and no oundering occurs.

Example 1 (Bongard Problems). Introduced by the Russian scientist M. Bongard in his book [ 3 ], the Bongard Problems consist of a number of pictures, some positive and some negative, and is usually used in learning problems aimed at learning a description which correctly classify the most gures, i.e., at discriminating between the two classes.

The pictures contain di erent shapes with di erent properties, such as small, large, pointing down, . . . and di erent relationships between them, such as inside, above, . . . Figure 1 shows some of these pictures.

Each picture can be described by an interpretation. Consider the left picture. It consists of a large triangle that includes a small square that, in turn, includes a small triangle. This picture can be described using the interpretation Moreover, suppose you are given the background knowledge B: Thus M (B [ Il) will contain the atoms in(1; 0), in(2; 1) and in(2; 0). Given the IC

C1 = triangle(T ); square(S); in(T; S) ! false stating that a gure satisfying the IC cannot contain a triangle inside a square, C1 is false in Il given B because triangle 2 is inside square 1.

In the central picture instead C is true given B because the only triangle is outside any square, while in the rightmost picture C1 is false again because of the presence of triangles 3, 4 and 5 inside square 0. 3

Probabilistic Constraint Logic Programming

A Probabilistic Constraint Logic Theory (PCLT) is a set of probabilistic integrity constraints (PICs) of the form pi :: L1; : : : ; Lb ! A1; : : : ; Ah (3) Each constraint Ci is associated with a real value in [0; 1] which de nes its probability. A PCLT T is sometimes de ned also as a set f(C1; p1); : : : ; (Cn; pn)g. A PCLT T de nes a probability distribution on ground constraint logic theories called worlds in this way: for each grounding of each IC, we include the grounding in a world with probability pi and we assume all groundings to be independent. The notion of world as a theory is similar to the notion of world in ProbLog [ 6 ] where a world is a normal logic program. Let us assume that constraint Ci has ni groundings called Ci1; : : : ; Cini . Let us call the ICs Cij instantiations of Ci. Thus, the probability of a world w is given by the product:

m P (w) = Y Y where m is the number of PICs. P (w) so de ned is a probability distribution over the set of worlds W . The probability P ( jw; I) of the positive class given an interpretation I, a background knowledge B and a world w is de ned as the probability that I satis es w given B3. Its value is P ( jw; I) = 1 if M (B [ I) j= w and 0 otherwise. The probability P ( jI) of the positive class given an interpretation I and a background B is the probability of I satisfying a PCLT T given B. From now on we always assume B as given and we do not mention it again. P ( jI) is given by

P ( jI) = X P ( ; wjI) = X P ( jw; I)P (wjI) = w2W w2W

X w2W;M(B[I)j=w

P (w) (4) The probability P ( jI) of the negative class given an interpretation I is the probability of I not satisfying T and is given by 1 P ( jI).

Example 2 (Example 1 continued). Consider the PCLT

fC1 = 0:5 :: triangle(T ); square(S); in(T; S) ! falseg In the left picture of Figure 1, considering the interpretation

Il = ftriangle(0); large(0); square(1); small(1); inside(1; 0);

triangle(2); inside(2; 1)g

There are two di erent instantiations for the IC C1:

Under Il there are thus four possible worlds

3 B is omitted from the formula for the sake of brevity.

C11 = (C1; fT =0; S=1g)

C12 = (C1; fT =2; S=1g) f;; fC11g; fC12g; fC11; C12gg and for the rst two of them M (B [ Il) j= wi, thus P ( jIl) = P (w1) + P (w2) = 0:25 + 0:25 = 0:5. In the central picture there are four di erent instantiations for C1, thus we can build 16 worlds. The interpretation Ic is veri ed in all of them since the constraint is never violated irrespective of the instantiation, thus the probability is P ( jIc) = 1. Finally, the third gure has 8 di erent instantiations for IC C1 and so 256 di erent worlds. Only 32 worlds satisfy the interpretation Ir, and the probability is P ( jIr) = 0:125. 4

Inference with Probabilistic Constraint Logic Theories

Computing P ( jI) with Formula (4) is impractical as there is an exponential number of worlds. In fact, as seen in Example 2, the number of worlds is exponential in the number of instantiations because, in order to build each world, we must decide whether to include each instantiation of every IC in the world.

Practically, we can associate a Boolean random variable Xij to each instantiated constraint Cij : if Cij is included in the world Xij takes on value 1. Moreover, P (Xij ) = P (Cij ) = pi and P (Xij ) = 1 P (Cij ) = 1 pi. Let X be the set of the Xij variables. These variables are all mutually independent. A valuation is an assignment of a truth value to all variables in X. There is clearly a one to one correspondence between worlds and valuations. A valuation can be represented as a set containing Xij (if Cij is included in the corresponding world) or Xij (if Cij is not included in the corresponding world) for each Xij , and corresponds to the Boolean formula : Since all the Xij variables are independent, the probability of being true is m = ^ ^ i=1 Xij2

Xij

^ Xij2

Xij : m P ( ) = Y Y As seen above, we can assign to each world w a valuation w of X in this way: Xij 2 w i Cij 2 w and Xij 2 w i Cij 62 w.

Suppose a ground IC Cij is violated in I. The worlds where Xij holds in the respective valuation are thus excluded from the summation in Formula (4). We must keep only the worlds where Xij holds in the respective valuation for all ground constraints Cij violated in I. So I satis es all the worlds where the formula is true in the respective valuations, so

m = ^ ^

Xij i=1 M(B[I)6j=Cij P ( jI) = P ( ) = m Y(1 where ni is the number of instantiations of Ci that are not satis ed in I, since the random variables are all mutually independent. Since computing ab is O(log b), P ( jI) can be computed in a time that is logarithmic in the number of groundings of constraints that are violated.

Each constraint may have a di erent number of violated groundings, which may result in a larger weight associated with constraints with many groundings. However, the parameters should be learned from data in order to maximize the likelihood, so the parameters should be adjusted to take into account the number of groundings.

Example 3 (Example 2 continued). Consider the PCLT of Example 2. In the left picture of Figure 1 the body of C1 is true for the single substitution T =2 and S=1 thus n1 = 1 and P ( jIl) = 0:5. In the right picture of Figure 1 the body of C1 is true for three couples (triangle, square) thus n1 = 3 and P ( jIr) = 0:125. These results clearly correspond to those seen in Example 2. 5

Discussion

PCLT can be seen as de ning a conditional probability distribution over a random variable C representing the class, positive (+) or negative (-), given the value of the random variables A1; : : : ; An representing the Herbrand base.

In other words, we do not want to model the dependence among atoms of the Herbrand base but only the conditional dependence of the class given the value of the atoms, i.e., given an interpretation. Our aim is to build a discriminative model, rather than a generative model, similarly to what is done with conditional random elds [ 12 ] that focus on the relationship between class variables and input variables and do not model the relationship among input variables.

A PCLT de nes a Bayesian network of the form shown in Figure 2, with the variables associated to ground atoms that are all parents of the class variable. This model di ers from a naive Bayes model because there the input variables (ground atoms) are all children of the class variable. This is a signi cant di erence because the model in Figure 2 can have up to 2n parameters if n is the number of ground atoms.

The assumption of independence of the constraints may seem restrictive but PCLT can model any conditional probabilistic relationship between the class variable and the ground atoms. For example, suppose you want to model a general conditional dependence between the class atom and a Herbrand base containing two atoms: a and b. This dependence can be represented with the Bayesian network of Figure 3, where the conditional probability table (CPT) has four parameters, p1; : : : ; p4, so it is the most general. Let us call P 0 the distribution de ned by this network. In fact, consider the interpretation fg that assigns value false to each atom of the Herbrand base. The probability that the class variable assumes value + is P (C = +j:a; :b) = 1 (1 p1) = p1 since only constraint C1 is violated, so P (C = +j:a; :b) = P 0(C = +j:a; :b). Similarly we can show that for the other possible interpretations, the probability assigned to the positive class by the above PCLT coincide with the one assigned by the Bayesian network of Figure 3.

Modeling the dependence between C and a; b with the above PCLT is equivalent to representing the Bayesian network of Figure 3 with the Bayesian network of Figure 4, where a Boolean variable Xi represents whether constraint Ci is included in the world (i.e., if it is enforced) and a Boolean variable Yi whether constraint Ci is violated. Let us call P 00 the distribution de ned by this network. The conditional probability tables for nodes Xis are P 00(Xi = 1) = 1 pi, those X1 Y1

X2 Y2

C

X3 Y3

X4 Y4 a b for nodes Yis encode the deterministic functions

Y1 = X1 ^ :a ^ :b Y2 = X2 ^ :a ^ b Y3 = X3 ^ a ^ :b

Y4 = X4 ^ a ^ b and that for C encodes the deterministic function

C = :Y1 ^ :Y2 ^ :Y3 ^ :Y4 where C is interpreted as a Boolean variable with 1 corresponding to + and 0 to -. If we want to compute P 00(Cj:a; :b) we get P 00(Cj:a:b) =

X P 00(X1) : : : P 00(X4)P 00(Y1jX1; :a; :b) : : : P 00(Y4jX4; :a; :b) = p1

Y;X P 00(CjY1; Y2; Y3; Y4) =

X = p1

X2;X3;X4;Y2;Y3;Y4 P 00(Y2jX2; :a; :b) : : : P 00(Y4jX4; :a; :b) =

X

P 00(X2) : : : P 00(X4)

X2;X3;X4

P 00(CjY1 = 0; Y2 = 0; Y3 = 0; Y4 = 0) = p1 = p1

X2;X3;X4

P 00(X2) : : : P 00(X4) = P 00(Y2 = 0jX2; :a; :b) : : : P 00(Y4 = 0jX4; :a; :b) =

X

P 00(X2) : : : P 00(X4)P 00(CjY1 = 0; Y2; Y3; Y4) where X = fX1; : : : ; X4g and Y = fY1; : : : ; Y4g. Similarly, it is possible to show that P and P 00 coincide for the other possible interpretations. If we look at the network in Figure 4 we see that the X variables are mutually unconditionally independent, showing that it is possible to represent any conditional dependence of C from the Herbrand base by using independent random variables. Of course, not assuming independence may result in a ner modeling of the domain. However, this would preclude PCLTs' nice computational properties. Achieving tractability requires approximations and we think that constraint independence is a reasonable assumption, similar to the independence among probabilistic choices in the distribution semantics for PLP.

Moreover, PCLT can compactly encode the dependence because they can take advantage of context speci c independences [ 19 ]. For example, in the CPT in Table 1 the probability of C = + does not depend on b when a is true. This dependence can be encoded with PCLT are also related to Markov Logic Networks (MLNs) [ 20 ]: similarly to MLNs, PCLT encode constraints on the possible interpretations and the probability of an interpretation depends on the number of violated constraints. However, MLNs encode the joint distribution of the ground atoms and the class, while we concentrate on the conditional distribution of the class given the ground atoms. Given a PCLT, it is possible to obtain an equivalent MLN. For example, the MLN equivalent to the PCLT (6)-(9) is

p1) :a ^ :b ^ :C ln(p1) :a ^ :b ^ C

p2) :a ^ b ^ :C ln(p2) :a ^ b ^ C

p3) a ^ :b ^ :C ln(p3) a ^ :b ^ C

p4) a ^ b ^ :C ln(p4) a ^ b ^ C where C is an atom representing the class. If we compute the conditional probability of C given an interpretation I, we get the same results of the PCLT. In fact, consider the empty interpretation and call P 000 the distribution de ned by the MLN. We get where Z is the partition function. Similarly for the other interpretations. So PCLT are a specialization of MLNs that, by focusing on a simpler problem, allow better performance of inference algorithms. 6

Extensions of CLTs

Integrity constraints can be extended to logical formulas of the form

L1; : : : ; Lb ! 9 (ConjP1); : : : ; 9 (ConjPn); 8 :(ConjN1); : : : ; 8 :(ConjNm) (10) where the Lis are logical literals and their conjunction L1; : : : ; Lb represents the body of the IC (as in Section 2), while ConjPi (i = 1; : : : ; n) and ConjNj (j = 1; : : : ; m) are conjunctions of literals of the form A1; : : : ; Ak [ 13 ]. The semicolon stands for disjunction, thus 9(ConjP1); : : : ; 9(ConjPn); 8:(ConjN1); : : : ; 8:(ConjNm) is a disjunction of conjunctions of literals.

We will use Body(C) to indicate the body of the IC and Head(C) to indicate the formula 9(ConjP1); : : : ; 9(ConjPn); 8:(ConjN1); : : : ; 8:(ConjNm) and call them respectively the body and the head of C. All the formulas ConjPj in Head(C) can also be referred to as P disjuncts and all the formulas ConjNj in Head(C) as N disjuncts.

An IC C is true in an interpretation I given a background knowledge B, written M (B [ I) j= C, if for every substitution for which Body(C) is true in M (B [ I), there exists a disjunct in Head(C) that is true in M (B [ I).

Variables in the body are implicitly universally quanti ed with scope the entire formula; the quanti ers in the head apply to all the variables not appearing in the body.

The truth of an extended IC C in an interpretation I can be tested by running the query ? Body(C); :ConjP1; : : : ; :ConjPn; ConjN1; : : : ; ConjNm: against a Prolog database containing the clauses of B and the atoms of I as facts. If B is range-restricted, every answer to an atomic query Q against B [ I completely instantiates Q, i.e., it produces an element of M (B [ I). If the query nitely fails the IC is true in I. If the query succeeds, the IC is false in I.

This language extends clausal logic by allowing more complex formulas as disjuncts in the head of clauses. The ICs are more expressive than logical clauses, as can be seen from the query used to test them: for ICs we have the negation of conjunctions, while for clauses we have only the negation of atoms. 7

Related Work

The approach presented here refers to the distribution semantics [ 23 ]: a probabilistic theory de nes a distribution over non-probabilistic theories by assuming independence among the choices in probabilistic constructs. The distribution semantics has emerged as one of the most successful approaches in Probabilistic Logic Programming and underlies many languages such as Probabilistic Horn Abduction, Independent Choice Logic, PRISM, Logic Programs with Annotated Disjunctions and ProbLog.

In the distribution semantics, the aim is to compute the probability that a ground atom is true. However, performing such inference requires an expensive procedure that is usually based on knowledge compilation. For example, ProbLog [ 6 ] and PITA [ 21,22 ] build a Boolean formula and compile it into a Binary Decision Diagram from which the computation of the probability is linear in the size of the diagram. However, the compilation procedure is #P in the number of variables. On the contrary, computing the probability of the positive class given an interpretation in a PCLT is logarithmic in the number of variables. This places PCLTs in the recent line of research committed to identifying tractable probabilistic languages.

In addition, a probabilistic program in one of the languages under the distribution semantics de nes a probability distribution over normal logic programs called worlds. The distribution is extended to queries and the probability of a query is obtained by marginalizing the joint distribution of the query and the programs. Instead, PCLTs de ne a conditional probability distribution over a random variable C representing the class, given the value of a set of atoms (an interpretation).

Conclusions

We have proposed a probabilistic extension of constraint logic theories for which the computation of the probability of an interpretation being positive is logarithmic in the number of falsi ed constraints.

In the future we are going to develop a system for learning such probabilistic integrity constraints. A possible way is to exploit Limited-memory BFGS (LBFGS) [ 18 ] for tuning the parameters and constraint re nements for nding good structures. L-BFGS is an optimization algorithm in the family of quasi-Newton methods that approximates the BroydenFletcherGoldfarbShanno (BFGS) algorithm using a limited amount of computer memory.

Acknowledgement This work was supported by the \GNCS-INdAM".

References

1. Alberti , M. , Chesani , F. , Gavanelli , M. , Lamma , E. , Mello , P. , Torroni , P. : Veri able agent interaction in abductive logic programming: the S CIFF framework . ACM T. Comput. Log . 9 ( 4 ) ( 2008 ), iF: 2 . 766

2. Blockeel , H., De Raedt , L. , Jacobs , N. , Demoen , B. : Scaling up inductive logic programming by learning from interpretations . Data Min. Knowl. Discov . 3 ( 1 ), 59 { 93 ( 1999 )

3. Bongard , M.M. : Pattern Recognition . Hayden Book Co., Spartan Books ( 1970 )

4. Clark , K.L. : Negation as failure . In: Logic and Data Bases . pp. 293 { 322 ( 1977 )

5. De Raedt , L. , Dehaspe , L. : Clausal discovery . Machine Learning 26 ( 2-3 ), 99 { 146 ( 1997 )

6. De Raedt , L. , Kimmig , A. , Toivonen , H.: ProbLog: A probabilistic Prolog and its application in link discovery . In: 20th International Joint Conference on Arti cial Intelligence , Hyderabad, India (IJCAI-05) . vol. 7 , pp. 2462 { 2467 . AAAI Press, Palo Alto, California USA ( 2007 )

7. De Raedt , L., Van Laer , W.: Inductive constraint logic . In: Proceedings of the 6th Conference on Algorithmic Learning Theory (ALT 1995 ). LNAI, vol. 997 , pp. 80 { 94 . Springer, Fukuoka, Japan ( 1995 )

8. De Raedt , L., Dzeroski, S.: First-order jk-clausal theories are pac-learnable . Artif. Intell . 70 ( 1-2 ), 375 { 392 ( 1994 )

9. Domingos , P. , Webb , W.A. : A tractable rst-order probabilistic logic . In: Ho - mann, J., Selman , B. (eds.) 26th National Conference on Arti cial Intelligence , AAAI' 12 , Toronto, Ontario, Canada. AAAI Press ( 2012 )

10. Fierens , D. , den Broeck, G.V., Renkens , J. , Shterionov , D.S. , Gutmann , B. , Thon , I. , Janssens , G. , De Raedt , L. : Inference and learning in probabilistic logic programs using weighted boolean formulas . Theor. Pract. Log. Prog . 15 ( 3 ), 358 { 401 ( 2015 )

11. Gutmann , B. , Thon , I. , De Raedt , L. : Learning the parameters of probabilistic logic programs from interpretations . In: Gunopulos, D. , Hofmann , T. , Malerba , D. , Vazirgiannis , M. (eds.) European Conference on Machine Learning and Knowledge Discovery in Databases. LNCS , vol. 6911 , pp. 581 { 596 . Springer ( 2011 )

12. La erty , J., McCallum , A. , Pereira , F. : Conditional random elds: Probabilistic models for segmenting and labeling sequence data . In: 18th International Conference on Machine Learning . vol. 1 , pp. 282 { 289 ( 2001 )

13. Lamma , E. , Mello , P. , Riguzzi , F. , Storari , S. : Applying inductive logic programming to process mining . In: Proceedings of the 17th International Conference on Inductive Logic Programming , ILP 2007 . pp. 132 { 146 . No. 4894 in Lecture Notes in Arti cial Intelligence , Springer, Heidelberg, Germany ( 2008 ), http://dx.doi.org/10.1007/978-3- 540 -78469-2_ 16

14. Ly , L.T. , Maggi , F.M. , Montali , M. , Rinderle-Ma , S., van der Aalst, W.M.: Compliance monitoring in business processes: Functionalities, application, and toolsupport . Inform. Syst . 54 , 209 { 234 ( 2015 )

15. Montali , M. : Speci cation and Veri cation of Declarative Open Interaction Models: a Logic-Based Approach , LNBIP, vol. 56 . Springer ( 2010 )

16. Niepert , M. , den Broeck, G.V.: Tractability through exchangeability: A new perspective on e cient probabilistic inference . In: Brodley , C.E. , Stone , P. (eds.) 28th National Conference on Arti cial Intelligence , AAAI' 14 , Quebec City , Quebec, Canada. pp. 2467 { 2475 . AAAI Press ( 2014 )

17. Niepert , M. , Domingos , P. : Tractable probabilistic knowledge bases: Wikipedia and beyond . In: AAAI-14 Workshop on Statistical Relational Arti cial Intelligence . AAAI Workshops , vol. WS- 14 - 13 . AAAI Press ( 2014 )

18. Nocedal , J.: Updating quasi-newton matrices with limited storage . Mathematics of Computation 35 ( 151 ), 773 { 782 ( 1980 )

19. Poole , D. , Zhang, N.L. : Exploiting contextual independence in probabilistic inference . J. Artif. Intell. Res . 18 , 263 { 313 ( 2003 )

20. Richardson , M. , Domingos , P. : Markov logic networks . Mach. Learn . 62 ( 1-2 ), 107 { 136 ( 2006 )

21. Riguzzi , F. , Swift , T. : The PITA system: Tabling and answer subsumption for reasoning under uncertainty . Theor. Pract. Log. Prog . 11 ( 4 {5), 433 { 449 ( 2011 )

22. Riguzzi , F. , Swift , T. : Well-de nedness and e cient inference for probabilistic logic programming under the distribution semantics . Theor. Pract. Log. Prog . 13 ( Special Issue 02 - 25th Annual GULP Conference) , 279 { 302 ( 2013 )

23. Sato , T. : A statistical learning method for logic programs with distribution semantics . In: Sterling, L . (ed.) 12th International Conference on Logic Programming , Tokyo, Japan. pp. 715 { 729 . MIT Press, Cambridge, Massachusetts ( 1995 )

24. Van den Broeck, G.: On the completeness of rst-order knowledge compilation for lifted probabilistic inference . In: Shawe-Taylor , J., Zemel , R.S. , Bartlett , P.L. , Pereira , F.C.N. , Weinberger , K.Q . (eds.) Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems . pp. 1386 { 1394 ( 2011 )

25. Webb , W.A. , Domingos , P. : Tractable probabilistic knowledge bases with existence uncertainty . In: AAAI-13 Workshop on Statistical Relational Arti cial Intelligence . AAAI Workshops , vol. WS- 13 - 16 . AAAI Press ( 2013 )