Anytime Inference in Probabilistic Logic Programs with Tp-Compilation

1 Introduction

Research on combining probability and logic for use with relational data has contributed many probabilistic logic programming (PLP) languages and systems such as PRISM [Sato, 1995], ICL [Poole, 2008], PITA [Riguzzi and Swift, 2011] and ProbLog [De Raedt et al., 2007; Fierens et al., 2013]. Inference algorithms for PLP often rely on a three step procedure: (1) transform the dependency structure of the logic program and the queries into a propositional formula, (2) compile this formula into a tractable target representation, and (3) compute the weighted model count (WMC) [Chavira and Darwiche, 2008] of the compiled formula. Step (1) is shared by exact inference [Fierens et al., 2013] and approximation techniques based on compiling selected subformulas or sampling [Renkens et al., 2014; Poon and Domingos, 2006]. It is well-known that this step is computationally expensive or even prohibitive for highly cyclic logic programs, as additional propositions are needed to break every cycle [Fierens et al., 2013]. This limits the applicability of the sequential approach in real-world domains with cyclic dependencies, such as gene interaction networks, social networks and the web. The most common solution is to use an approximate (simplified) logic program. Recently, the problem has also been addressed using lazy clause generation [Aziz et al., 2015], but only for exact inference.

The key contribution of this paper is TP-compilation, a novel inference technique for probabilistic definite clause programs that interleaves construction and compilation of the propositional formula for WMC (steps (1) and (2)). Our second contribution, and formal basis of TP-compilation, is the TcP operator that generalizes the TP operator from logic programming [Van Emden and Kowalski, 1976] to explicitly construct the formula. At any point, the WMC of the current formula provides a lower bound on the true probability, and we thus realize an anytime algorithm.

As in the purely logical setting, forward reasoning with the TcP operator allows one to answer multiple queries in parallel, which is not supported by earlier anytime PLP algorithms based on backward reasoning [Poole, 1993; De Raedt et al., 2007]. Furthermore, forward reasoning naturally handles cyclic dependencies. This avoids the need for additional propositions for breaking cycles and simplifies the compilation step. Finally, our approach is amenable to online inference. That is, when clauses are added to or deleted from the program, TP-compilation can update the already compiled formulas, which can cause significant savings compared to restarting inference from scratch. While forward reasoning is common in sampling-based inference approaches in probabilistic programming, e.g., [Milch et al., 2005; Goodman et al., 2008; Gutmann et al., 2011], these do not provide guaranteed lower or upper bounds on the probability of the queries.

We obtain an efficient realization of the TcP operator by representing formulas as Sentential Decision Diagrams (SDD) [Darwiche, 2011], which efficiently support incremental formula construction and WMC. While our approach can easily be extended to handle stratified negation, for ease of presentation we focus on definite clause programs which cover real-world applications such as biological and social networks and web-page classification tasks. An empirical evaluation in these domains demonstrates that TP-compilation outperforms state-of-the-art sequential approaches on these problems with respect to time, space and quality of results.

The paper is organized as follows. We review the necessary background in Section 2. Section 3 and 4 formally introduce the TcP operator and corresponding algorithms. We discuss experimental results in Section 5 and conclude in Section 6.

2 Background

We review the basics of (probabilistic) logic programming.

2.1 Logical Inference

A definite clause program, or logic program for short, is a finite set of definite clauses, also called rules. A definite clause is a universally quantified expression of the form h :- b1, ..., bn where h and the bi are atoms and the comma denotes conjunction. The atom h is called the head of the clause and b1, ..., bn the body. A fact is a clause that has true as its body and is written more compactly as h. If an expression does not contain variables it is ground.

Let A be the set of all ground atoms that can be constructed from the constants, functors and predicates in a logic program P. A Herbrand interpretation of P is a truth value assignment to all a ∈ A, and is often written as the subset of true atoms (with all others being false), or as a conjunction of atoms. A Herbrand interpretation satisfying all rules in the program P is a Herbrand model. The model-theoretic semantics of a logic program is given by its unique least Herbrand model, that is, the set of all ground atoms a ∈ A that are entailed by the logic program, written P |= a.

As running example we use a logic program that models a graph (see Figure 1). The facts represent the edges between two nodes in the graph (we ignore the probabilities at this moment) and the rules define whether there is a path between two nodes. Abbreviating predicate names by initials, the least Herbrand model is given by {e(b, a), e(b, c), e(a, c), e(c, a), p(b, a), p(b, c), p(a, c), p(c, a), p(a, a), p(c, c)}.

Figure 1: A (probabilistic) logic program modeling a graph.

The task of logical inference is to determine whether a program P entails a given atom, called query. The two most common approaches to inference are backward reasoning or SLD-resolution, which starts from the query and reasons back towards the facts [Nilsson and Maluszynski, 1995], and forward reasoning, which starts from the facts and derives new knowledge using the immediate consequence operator TP [Van Emden and Kowalski, 1976].

Definition 1 (TP operator) Let P be a ground logic program. For a Herbrand interpretation I , the TP operator returns

The least fixpoint of this operator is the least Herbrand model of P. Let T kP (∅) denote the result of k consecutive calls of the TP operator, ∆I i be the difference between T i-1 P (∅) and T iP (∅), and T ∞ P (∅) the least fixpoint interpretation of TP.

The least fixpoint can be efficiently computed using a seminaive evaluation algorithm [Nilsson and Maluszynski, 1995].

On our example, this results in:

T ∞ P (∅) = ⋃i ∆I i is the least Herbrand model as given above.

2.2 Probabilistic-Logical Inference

Most probabilistic logic programming languages (e.g. ICL, PRISM, ProbLog) are based on Sato's distribution semantics [Sato, 1995]. In this paper, we use ProbLog as it is the simplest of these languages.

A ProbLog program P consists of a set R of rules and a set F of probabilistic facts; an example is given in Figure 1. As common, we assume that no probabilistic fact unifies with a rule head. A ProbLog program specifies a probability distribution over its Herbrand interpretations, also called possible worlds. Every grounding fθ of a probabilistic fact p :: f independently takes value true (with probability p) or false (with probability 1-p). For ease of notation, we assume that F is ground.

A total choice C ⊆ F assigns a truth value to every (ground) probabilistic fact, and the corresponding logic program C ∪ R has a unique least Herbrand model; the probability of this model is that of C. Interpretations that do not correspond to any total choice have probability zero. The probability of a query q is then the sum over all total choices whose program entails q:

As enumerating all total choices entailing the query is infeasible, state-of-the-art ProbLog inference [Fierens et al., 2013] reduces the problem to that of weighted model counting. For a formula λ over propositional variables V and a weight function w(·) assigning a real number to every literal for an atom in V , the weighted model count is defined as

The reduction sets w(fi) = pi and w(¬fi) = 1 - pi for probabilistic facts pi :: fi, and w(a) = w(¬a) = 1 else. For a query q, it constructs a formula λ′ such that for every total choice C ⊆ F, C ∪ {λ′} |= q ↔ C ∪ R |= q. While λ′ may use variables besides the probabilistic facts, their values have to be uniquely defined for each total choice.

We briefly discuss the key steps of the sequential WMCbased approach, and refer to Fierens et al. [2013] for full details. First, the relevant ground program, i.e., all and only those ground clauses that contribute to some derivation of a query, is obtained using backward reasoning. Next, the ground program is converted into a propositional formula in Conjunctive Normal Form (CNF), which is finally passed to an off-the-shelf solver for weighted model counting.

The resources needed for the conversion step, as well as the size of the resulting CNF, greatly increase with the number of cycles in the ground program, as additional variables and clauses are introduced to capture the least Herbrand semantics of every cycle. For example, the conversion algorithm implemented in ProbLog returns, for the complete grounding of a fully connected graph with only 10 nodes, a CNF with 26995 variables and 109899 clauses.

For exact inference, it is common to compile the CNF into a target representation for which WMC is polynomial in the size of the representation. Anytime (approximate) inference constructs the full CNF first, and then incrementally compiles a set of chosen subformulas [Renkens et al., 2014].

3 The TcP Operator

We develop the formal basis of our approach that interleaves formula construction and compilation by means of forward reasoning. The main advantages are that (a) the conversion to propositional logic happens during rather than after reasoning within the least Herbrand semantics, avoiding the expensive introduction of additional variables and propositions, and (b) at any time in the process, the current formulas provide hard bounds on the probabilities.

Although forward reasoning naturally considers all consequences of a program, using the relevant ground program allows us to restrict the approach to the queries of interest. As common in probabilistic logic programming, we assume the finite support condition, i.e., the queries depend on a finite number of ground probabilistic facts.

We use forward reasoning to build a formula λa for every atom a ∈ A such that λa exactly describes the total choices C ⊆ F for which C ∪ R |= a. Such λa can be used to compute the probability of a via WMC, cf. Section 2.2, independently of their syntactic representation.

Definition 2 (Parameterized interpretation) A parameterized interpretation I of a ground probabilistic logic program P with probabilistic facts F and atoms A is a set of tuples (a, λa) with a ∈ A and λa a propositional formula over F.

For instance, in Figure 1, we can use λe(b,a) = e(b, a) as e(b, a) is true in exactly those worlds whose total choice includes that edge, and λp(b,c) = e(b, c) ∨ (e(b, a) ∧ e(a, c)) as p(b, c) is true in exactly those worlds whose total choice includes at least the direct edge or the two-edge path.

A naive approach to construct the λa would be to compute Ii = T ∞ R∪Ci (∅) for every total choice Ci ⊆ F and to set λa = ∨i:a∈Ii ∧f∈Ci f, that is, the disjunction explicitly listing all total choices contributing to the probability of a. Clearly, this requires a number of fixpoint computations exponential in |F|, and furthermore, doing these computations independently does not exploit the potentially large structural overlap between them.

Therefore, we introduce the TcP operator. It generalizes the TP operator to work on the parameterized interpretation and builds, for all atoms in parallel on the fly, formulas that are logically equivalent to the λa introduced above. For ease of notation, we assume that every parameterized interpretation implicitly contains a tuple (true,⊤), and, just as in regular interpretations, we do not list atoms with λa ≡ ⊥. 1

Definition 3 (TcP operator) Let P be a ground probabilistic logic program with probabilistic facts F and atoms A. Let I be a parameterized interpretation with pairs (a, λa). Then, the TcP operator is TcP(I) = {(a, λ′a ) | a ∈ A} where

Intuitively, where the TP operator (repeatedly) adds an atom a to the interpretation whenever the body of a rule defining a is true, the TcP operator adds to the formula for a the description of the total choices for which the rule body is true. In contrast to the TP operator, where a syntactic check suffices to detect that the fixpoint is reached, the TcP operator requires a semantic fixpoint check for each formula λa (which we write as I i ≡ TcP(I i-1 )).

Definition 4 (Fixpoint of TcP) A parameterized interpretation I is a fixpoint of the TcP operator if and only if for all a ∈ A, λa ≡ λ′a , where λa and λ′a are the formulas for a in I and TcP(I), respectively.

It is easy to verify that for F = ∅, i.e., a ground logic program P, the iterative execution of the TcP operator directly mirrors that of the TP operator, representing atoms as (a,⊤).

We use λia to denote the formula associated with atom a after i iterations of TcP starting from ∅. How to efficiently represent the formulas λa is discussed in Section 4.

In our example, the first application of TcP sets λ1e(x,y) = e(x, y) for (x, y) ∈ {(b, a), (a, c), (b, c), (c, a)}. These remain the same in all subsequent iterations. The second application of TcP starts adding formulas for path atoms, which we illustrate for just two atoms:

That is, the second step considers paths of length at most 1 and adds (p(b, c), e(b, c)) to the parameterized interpretation, but does not add a formula for p(c, c), as no total choices making this atom true have been found yet. Similarly, the third iteration adds information on paths of length at most 2:

Intuitively, TcP keeps adding longer sequences of edges connecting the corresponding nodes to the path formulas, reaching a fixpoint once all acyclic sequences have been added.

1 Thus, the empty set implicitly represents the parameterized interpretation {(true, ⊤)} ∪ {(a, ⊥)|a ∈ A} for a set of atoms A.

Correctness We now show that for increasing i, Tc iP (∅) reaches a least fixpoint where the λa are exactly the formulas needed to compute the probability for each atom by WMC.

Theorem 1 For a ground probabilistic logic program P with probabilistic facts F, rules R and atoms A, let λia be the formula associated with atom a in Tc iP (∅). For every atom a, total choice C ⊆ F and iteration i, we have:

Proof by induction: i = 1: easily verified. i → i + 1: easily verified for a ∈ F; for a ∈ A \ F, let C |= λi+1 a , that is, C |= ∨(a :- b1,...,bn)∈P (λib1 ∧ · · · ∧ λibn ). Thus, there is a a : - b1, . . . , bn ∈ P with C |= λibj for all 1 ≤ j ≤ n. By assumption, C ∪ R |= bj for all such j and thus C ∪ R |= a. □

Thus, after each iteration i, we have WMC(λia ) ≤ Pr(a).

Theorem 2 For a ground probabilistic logic program P with probabilistic facts F, rules R and atoms A, let λia be the formula associated with atom a in Tc iP (∅). For every atom a and total choice C ⊆ F, there is an i0 such that for every iteration i ≥ i0, we have

Proof: ←: Theorem 1. →: C ∪ R |= a implies ∃i0∀i ≥ i0 : a ∈ T iC∪R(∅). We further show ∀j : a ∈ T jC∪R(∅) → C |= λja by induction. j = 1: easily verified. j → j + 1: easily verified for a ∈ F; for other atoms, a ∈ T j+1 C∪R(∅) implies there is a rule a : - b1, . . . , bn ∈ R such that ∀k : bk ∈ T jC∪R(∅). By assumption, ∀k : C |= λjbk , and by definition, C |= λj+1 a . □

Thus, for every atom a, the λia reach a fixpoint λ∞a exactly describing the possible worlds entailing a, and the TcP operator therefore reaches a fixpoint where for all atoms Pr(a) = WMC(λ∞a ). 2 Using Bayes' rule, we can also compute conditional probabilities Pr(q|e) as WMC(λ∞q ∧ λ′e )/WMC(λ′e ) with λ′e = λ∞e for e = ⊤ and λ′e = ¬λ∞e for e = ⊥.

4 Algorithms

As in logical inference with TP, probabilistic inference iteratively calls the TcP operator until the fixpoint is reached. This involves incremental formula construction (cf. Definition 3) and equivalence checking (cf. Definition 4). Then, for each query q, the probability is computed as WMC(λq).

An efficient realization of our evaluation algorithm is obtained by representing the formulas in the interpretation I by means of a Sentential Decision Diagram (SDD) [Darwiche, 2011], as these efficiently support all required operations. Hence, we can replace each λa in Definition 3 by its equivalent SDD representation (denoted by Λa) and each of the Boolean operations by the Apply-operator for SDDs which, given ◦ ∈ {∨, ∧} and two SDDs Λa and Λb, returns an SDD equivalent with (Λa ◦ Λb).

2 The finite support condition ensures this happens in finite time.

4.1 TP-Compilation

The TcP operator is, by definition, called on I. To allow for different evaluation strategies, however, we propose a more fine-grained algorithm where, in each iteration, the operator is only called on one specific atom a, i.e., only the rules for which a is the head are evaluated, denoted by TcP(a, I i-1 ). Each iteration i of TP-compilation consists of two steps;

1. Select an atom a ∈ A.
2. Compute I i = TcP(a, I i-1 )

The result of Step 2 is that only the formula for atom a is updated and, for each of the other atoms, the formula in I i is the same as in I i-1 . It is easy to verify that TP-compilation reaches the fixpoint Tc∞P (∅) in case the selection procedure frequently returns each of the atoms in P.

4.2 Anytime Inference

Until now, we mainly focused on exact inference. Our algorithm is easily adapted for anytime inference as well.

Lower Bound

Following Theorem 1, we know that, after each iteration i, WMC(λia ) is a lower bound on the probability of atom a, i.e. WMC(λia ) ≤ Pr(a) = WMC(λ∞a ). To quickly increase WMC(λia ) and, at the same time, avoid a blow-up of the formulas in I, the selection procedure we employ picks the atom which maximizes the following heuristic value:

where SIZE(Λ) denotes the number of edges in SDD Λ and φa adjusts for the importance of a in proving queries.

Concretely, Step 1 of TP-compilation calls TcP(a, I i-1 ) for each a ∈ A, computes the heuristic value and returns the atom a′ for which this value is the highest. Then, Step 2 performs I i = TcP(a′ , I i-1 ). Although there is overhead involved in computing the heuristic value, as many formulas are compiled without storing them, this strategy works well in practice.

We take as value for φa the minimal depth of the atom a in the SLD-tree for each of the queries of interest. This value is a measure for the influence of the atom on the probability of the queries. For our example, and the query p(b, c), the use of φa would give priority to compile p(b, c) as it is on top of the SLD-tree. Without φa, the heuristic would give priority to compile p(a, c) as it has the highest probability.

Upper bound

To compute an upper bound, we select F ′ ⊂ F and treat each f ∈ F ′ as a logical fact rather than a probabilistic fact, that is, we conjoin each λa with ∧f∈F ′ λf . In doing so, we simplify the compilation step of our algorithm, because the number of possible total choices decreases. Furthermore, at a fixpoint, we have an upper bound on the probability of the atoms, i.e., WMC(λ∞a |λF ′) ≥ Pr(a), because we overestimate the probability of each fact in F ′ .

Randomly selecting F ′ ⊂ F does not yield informative upper bounds (they are close to 1). As a heuristic, we compute for each of the facts the minimal depth in the SLD-trees of the queries of interest and select for F ′ all facts whose depth is smaller than some constant d. Hence, we avoid the query to be deterministically true as for each of the proofs, i.e., traces in the SLD-tree, we consider at least one probabilistic fact. This yields tighter upper bounds. For our example, and the query path(b, c), both of the edges starting in node b are at a depth of 1 in the SLD-tree. Hence, it suffices to compile only them, and treat both other edges as logical facts, to obtain an upper bound smaller than 1.

4.3 Online Inference

An advantage of forward reasoning is that it naturally supports online, or incremental, inference. In this setting, one aims to reuse past computation results when making incremental changes to the model, rather than restarting inference from scratch. Our TcP operator allows for adding clauses to and removing clauses from the program.

For logic programs, we know that employing the TP operator on a subset of the fixpoint reaches the fixpoint, i.e. ∀I ⊆ T ∞ P (∅) : T ∞ P (I ) = T ∞ P (∅). Moreover, adding definite clauses leads to a superset of the fixpoint, i.e., T ∞ P (∅) ⊆ T ∞ P∪P ′(∅). Hence, it is safe to restart the TP operator from a previous fixpoint after adding clauses. Due to the correspondence established in Theorem 2, this also applies to TcP. For our example, we could add 0.1 : : e(a, b) and the corresponding ground rules. This leads to new paths, such as p(b, b), and increases the probability of existing paths, such as p(a, c).

When removing clauses, atoms in the fixpoint may become invalid. We therefore reset the computed fixpoints for all total choices where the removed clause could have been applied. This is done by conjoining each of the formulas in the parametrized interpretation with the negation of the formula for the head of the removed clause. Then, we restart the TcP operator from the adjusted parametrized interpretation, to recompute the fixpoint for the total choices that were removed. For our example, if we remove 0.5 : : e(b, c) and the rules containing this edge, we are removing a possible path from b to c and thus decreasing the probability of p(b, c).

5 Experimental Results

Our experiments address the following questions:

• Q1 How does TP-compilation compare to exact sequential WMC approaches?
• Q2 When is online TP-compilation advantageous?
• Q3 How does TP-compilation compare to anytime sequential approaches?
• Q4 What is the impact of approximating the model?

We compute relevant ground programs as well as CNFs (where applicable) following Fierens et al. [2013] and use the SDD package developed at UCLA 3 . Experiments are run on a 3.4 GHz machine with 16 GB of memory. Our implementation is available as part of the ProbLog package 4 .

3 http://reasoning.cs.ucla.edu/sdd/

4 http://dtai.cs.kuleuven.be/problog/

Exact Inference

We use datasets of increasing size from two domains:

Smokers. Following Fierens et al. [2013], we generate random power law graphs for the standard 'Smokers' social network domain.

Alzheimer. We use series of connected subgraphs of the Alzheimer network of De Raedt et al. [2007], starting from a subsample connecting the two genes of interest 'HGNC 582' and 'HGNC 983', and adding nodes that are connected with at least two other nodes in the graph.

The relevant ground program is computed for one specific query as well as for multiple queries. For the Smokers domain, this is cancer(p) for a specific person p versus for each person. For the Alzheimer domain, this is the connection between the two genes of interest versus all genes.

For the sequential approach, we perform WMC using either SDDs, or d-DNNFs compiled with c2d 5 [Darwiche, 2004]. For each domain size (#persons or #nodes) we consider nine instances with a timeout of one hour per setting. We report median running times and target representation sizes, using the standard measure of #edges for the d-DNNFs and 3 · #edges for the SDDs. The results are depicted in Figure 2 and 3 and provide an answer for Q1.

In all cases, our TP-compilation (Tp-comp) scales to larger domains than the sequential approach with both SDD (cnf SDD) and d-DNNF (cnf d-DNNF) and produces smaller compiled structures, which makes subsequent WMC

5 http://reasoning.cs.ucla.edu/c2d/

computations more efficient. The smaller structures are mainly obtained because our approach does not require auxiliary variables to correctly handle the cycles in the program. For Smokers, all queries depend on almost the full network structure, and the relevant ground programs - and thus the performance of TP-compilation - for one or all queries are almost identical. The difference between the settings for the sequential approaches is due to CNF conversion introducing more variables in case of multiple queries.

Online Inference

We experiment on the Alzheimer domain discussed above, and a variant on the smokers domain. The smokers network has 150 persons and is the union of ten different random power law graphs with 15 nodes each. We consider the multiple queries setting only, and again report results for nine runs.

We compare our standard TP-compilation algorithm, which compiles the networks for each of the domain sizes from scratch, with the online algorithm discussed in Section 4.3. The results are depicted in Figure 4 and provide an answer to Q2.

For the Alzheimer domain, which is highly connected, incrementally adding the nodes (Tcp-inc) has no real benefit compared to recompiling the network from scratch (Tp-comp) and, consequently, the cumulative time of the incremental approach (Tcp-inc-total) is higher. For the smokers domain, on the other hand, the incremental approach is more efficient compared to recompiling the network, as it only updates the subnetwork to which the most recent person has been added.

Anytime Inference

We consider an approximated (Papr ) as well as the original (Porg) model of two domains:

Genes. Following Renkens et al. [2012; 2014], we use the biological network of Ourfali et al. [2007] and its 500 connection queries on gene pairs. The original Porg considers connections of arbitrary length, whereas Papr restricts connections to a maximum of five edges.

WebKB. We use the WebKB 6 dataset restricted to the 100 most frequent words [Davis and Domingos, 2009] and with random probabilities from [0.01, 0.1]. Following Renkens et al. [2014], Papr is a random subsample of 150 pages. Porg uses all pages from the Cornell database. This results in a dataset with 63 queries for the class of a page.

We employ the anytime algorithm as discussed in Section 4.2 and alternate between computations for lower and upper bound at fixed intervals. We compare against two sequential approaches. The first compiles subformulas of the CNF selected by weighted partial MaxSAT (WPMS) [Renkens et al., 2014], the second approximates the WMC of the formula by sampling using the MC-SAT algorithm implemented in the Alchemy package 7 .

6 http://www.cs.cmu.edu/webkb/

Following Renkens et al. [2014], we run inference for each query separately. The time budget is 5 minutes for Papr and 15 minutes for Porg (excluding the time to construct the relevant ground program). For MC-SAT, we sample either 5,000 or 10,000 times per variable in the CNF, which yields approximately the same runtime as our approach. Results are depicted in Tables 1, 2 and Figure 5 and allow us to answer Q3 and Q4.

Table 1 shows that TP-compilation returns bounds for all queries in all settings, whereas WPMS did not produce any answer for Porg. The latter is due to reaching the time limit before conversion to CNF was completed. For the approximate model Papr on the Genes domain, both approaches solve a majority of queries (almost) exactly. Figure 5 plots the number of queries that reached a bound difference below different thresholds against the running time, showing that TP-compilation converges faster thanWPMS. Finally, for the Genes domain, Table 2 shows the number of queries where the result of MC-SAT (using different numbers of samples per variable in the CNF) lies within or outside the bounds computed by TP-compilation. For the original model, no complete CNF is available within the time budget; for the approximate model, more than two thirds of the results are outside the guaranteed bounds obtained by our approach.

7 http://alchemy.cs.washington.edu/

We further observed that for 53 queries on the Genes domain, the lower bound returned by our approach using the original model is higher than the upper bound returned by WPMS with the approximated model. This illustrates that computing upper bounds on an approximate model does not provide any guarantees with respect to the full model. On the other hand, for 423 queries in the Genes domain, TPcompilation obtained higher lower bounds with Papr than with Porg , and lower bounds are guaranteed in both cases.

In summary, we conclude that approximating the model can result in misleading upper bounds, but reaches better lower bounds (Q4), and that TP-compilation outperforms the sequential approaches for time, space and quality of result in all experiments (Q3).

6 Conclusions

We have introduced TP-compilation, a novel anytime inference approach for probabilistic logic programs that combines the advantages of forward reasoning with state-of-theart techniques for weighted model counting. Our extensive experimental evaluation demonstrates that the new technique outperforms existing exact and approximate techniques on real-world applications such as biological and social networks and web-page classification.

Acknowledgments

We wish to thank Bart Bogaerts for useful discussions. Jonas Vlasselaer is supported by the IWT (agentschap voor Innovatie door Wetenschap en Technologie). Guy Van den Broeck and Angelika Kimmig are supported by the Research Foundation-Flanders (FWO-Vlaanderen).