Statistical Statements in Probabilistic Logic Programming

Probabilistic Logic Programming (PLP) [19] extends Logic Programming (LP) by considering various probabilistic constructs. ProbLog [8] is an example of a PLP language based on the distribution semantics (PLPDS) [20]. This semantics assumes that every program has a two-valued well-founded model [24].

In giving a semantics to First-Order knowledge bases, Halpern [13] distinguishes statistical statements from statements about degrees of belief, and presents two examples: “the probability that a randomly chosen bird flies is 0.9” and “the probability that Tweety (a particular bird) flies is 0.9”. The first statement captures statistical information about the world while the second captures a degree of belief. The first type of statement is called “Type 1” while the latter “Type 2”. The first statement can be read as “90% of the population of birds flies”.

The distribution semantics allows statements stating that, if a specific x is a bird, then x flies with probability 0.9 (or it does not with probability 0.1). In fact, the semantics of general rules of the form 0.9::flies(X) :- bird(X). is given by the set of its ground instantiations of the form 0.9::flies(x) :- bird(x)., which has the just described meaning. In this paper, we aim at adding to PLPDS the possibility of expressing “Type 1” statements, exploiting for this purpose Probabilistic Answer Set Programming.

Answer Set Programming (ASP) [5] is a powerful rule-based language for knowledge representation and reasoning. An extension to ASP that manages uncertain data is Probabilistic Answer Set Programming (PASP). The credal semantics [6] assigns a probability range to every query to probabilistic answer set programs - instead of a sharp value as in PLPDS - where lower and upper probability bounds are computed by analyzing the stable models of every world.

“Type 1” statements are called “probabilistic conditionals” in [15], where they are given a semantics in terms of the principle of maximum entropy: the unique model with maximum entropy is chosen. Instead of selecting only one model, we keep all models at the cost of inferring a probability interval instead of a sharp probability. We think this is of interest because it avoids making the rather strong maximum entropy assumption.

We propose a new language, called PASTA for “Probabilistic Answer set programming for STAtistical probabilities”, where we exploit the credal semantics to take into account “Type 1” statements in PLPDS. In particular, probabilistic conditionals are converted into an ASP rule plus two constraints: the rule characterizes the elements of the domain while the constraints inject the statistical information on the possible stable models of every world. To perform exact inference under this semantics we developed an algorithm, taking the same name of the language, which returns lower and upper bounds for the probability of queries, and compared it with PASOCS [23]. The results show that, if we pre-process the input program into a form that allows reasoning about its structure, it is possible to obtain better performance on every program we tested.

The paper is structured as follows: in Sect. 2 we review the basic knowledge relative to ASP, PLPDS, the credal semantics, and probabilistic conditionals. In Sect. 3 we describe the PASTA language. In Sect. 4 we introduce an algorithm to perform exact inference on PASTA programs, that is experimentally tested in Sect. 5. Section 6 surveys related work and Sect. 7 concludes the paper.

A probabilistic conditional expresses statistical information about the world of interest, but we would like to avoid selecting a model making the maximum entropy assumption. We would rather consider all possible models and derive lower and upper bounds on the probability of queries using the credal semantics. Here, we consider “Type 1”/probabilistic conditionals of the formwith a lower (\(\varPi _l\)) and an upper (\(\varPi _u\)) bound, with the intuitive meaning that the fraction of As that are also Cs is between \(\varPi _l\) and \(\varPi _u\). Note that \(\varPi _l\) and \(\varPi _u\) can be vacuous, i.e., they can be respectively 0 and 1. We follow an approach based on the DS, so here worlds are ground programs. The meaning of the statement above is that the models of a world where the constraintdoes not hold should be excluded, where \(\textbf{X}\) is the vector of variables appearing in C and A.

We consider a program as being composed of regular rules, probabilistic facts, and conditionals of the previously described form, and we assign a semantics to it by translating it into a probabilistic answer set program. We call this language PASTA (Probabilistic Answer set programming for STAtistical probabilities). Probabilistic facts and rules appear unmodified in the probabilistic answer set program. The conditional \((C \mid A)[\varPi _l,\varPi _u]\) is transformed into three answer set rules. The first is a disjunctive rule of the form C;not_C:-A. We require this rule to be safe. Then, we introduce two integrity constraints that mimic Eq. 7 through aggregates: we count all the ground atoms that satisfy A (call this value ND) and A and C (call this value NN) and we impose that NN must be greater than or equal to \(100\cdot \varPi _l\) percent of ND and smaller than or equal to \(100\cdot \varPi _u\) percent of ND. The constraints are not generated if the bounds are vacuous. The conditional (fly(X) | bird(X))[0.6] of Example 2 is transformed into the rule and the constraint shown in Example 1. Finally, the probability interval of a query from a PASTA program is the probability interval of the query computed from the transformed probabilistic answer set program.

By rewriting probabilistic conditionals as ASP rules, computing the probability of a query requires performing inference in PASP. To the best of our knowledge, the only system that allows (exact) inference in probabilistic answer set programs with aggregates is PASOCS [23], an implementation of the algorithm presented in [6]. The algorithm computes the probability of a query by generating all possible worlds (\(2^n\), where n is the number of ground probabilistic facts in the program). For each world, it computes the brave and cautious consequences (there is no need to compute all the answer sets). If the query is present in the brave consequences of a world, that world contributes to the upper probability. If the query is also present in the cautious consequences, that world also contributes to the lower probability. Despite its simplicity, this algorithm relies on the generation of all the possible worlds and does not take advantage of the structure of a program. For example, in Example 3, with query fly(1), the probabilistic fact bird(1) must be true to get a contribution to the lower or upper probability, and so we can avoid generating the worlds where this fact is not present. Moreover, for both conditional and unconditional queries, we do not need to generate all the possible models for every world, we just need to check whether there is at least one model that satisfies the required constraints. To accommodate these ideas, we propose Algorithm 1, that we call PASTA like the language.

Consider first the problem of computing the probability of a query q (without evidence). We generate a non-probabilistic answer set program as follows. Every certain rule is kept unchanged. Every conditional is converted into three ASP rules as described in Sect. 3. Every ground probabilistic fact of the form P::f is converted into two rules of the form f(P1):- f. not_f(1-P1):- not f. where P1 is P \(\cdot 10^n\) (since ASP cannot manage floating point numbers). The atom f is then defined by a rule of the form 0{f}1. Function ConvertProbFactsAndConditionals performs these conversions. Let us call the resulting program \( PASP_p \). We then add to \( PASP_p \) a constraint (line 4) imposing that the query must be true, represented with :- not query. (for Example 3 it becomes :- not fly(1).). We are not interested in all possible solutions, but only in the cautious consequences projected over the ground probabilistic facts, since we want to extract the probabilistic facts that are true in every answer set. These will constitute the minimal set of probabilistic facts. Function ComputeMinimalSet computes this set. These facts can be set to true since they are always present in the answer sets when the query is true, and so when there is a contribution to the probabilities. In the worst case, the resulting set will be empty. If we consider Example 3 and query fly(1), the only atom (already converted as described before with \(n = 3\)) in this set will be bird(1,400), so the corresponding probabilistic fact must be always true. After this step, we add to \( PASP_p \) one integrity constraint for every element in the minimal set of probabilistic facts, to set them to true. Note that now \( PASP_p \) does not contain the constraint imposed on the query in the previous step. For Example 3 and query fly(1), we add :- not bird(1,400). to the program (line 9). Moreover, we add two more rules that indicate whether a model contains or not the query (line 11). For Example 3 and query fly(1) these are: q:- fly(1). nq:- not fly(1). Finally, we project the answer sets [12] to the probabilistic facts and atoms q and nq, since we need to consider only the truth values of the probabilistic facts to compute the probability of a world (line 13). The probabilistic facts present in the projected answer sets identify a world. Given an answer set, its probability (the probability of the world it represents) is given by the product of the probabilities of the probabilistic facts in it. Function ComputeContribution (line 18) computes the probability of every world and counts the models, the models where the query is true, the models where the query is false, the models where the query and evidence are true, and the models where the query is false and the evidence is true. For a query without evidence, the number of models where the query is true and the number of models where the query is false will only be either 0 or 1. To get the lower and upper probabilities, we apply Formulas 3. If we consider again Example 3 with query fly(1), two of the possible projective solutions are:

where, for the sake of brevity, b/2 stands for bird/2. These two solutions show that the world with 4 birds has at least one model where the query is true and at least one model where the query is false, so it only contributes to the upper probability with \(0.4 \cdot 0.4 \cdot 0.4 \cdot 0.4 = 0.0256\). Here, we also see the improvement given by computing the projective solutions: we only need to know whether the query is true or false in some models of a world, and not the exact number of models in which the query is true. For example, as shown in Example 1, the world with 4 birds has 5 models: 4 where the query is true and 1 where the query is false. However, to compute the probability bounds, it is not necessary to know the exact number: at most two stable models (one with the query true and one with the query false) for each world are needed instead of five. A difference with [23] is that PASOCS computes both brave and cautious consequences for every world, while PASTA computes projective solutions only once.

Consider now a conditional query. As before, we need to identify the minimal subset of probabilistic facts. However, we now add a constraint forcing the evidence (ev) to true instead of the query (line 6). We then add two more rules of the form e:- ev. and ne:- not ev. (line 15) and project the solutions also on the e and ne atoms (line 16). Finally, we analyse the resulting answer sets to compute the values that contribute to the lower (lp) and upper (up) probability, as described in Formulas 4 and 5.

We implemented Algorithm 1 with Python3 using clingo [11] to compute answer sets.¹ We performed a series of experiments to compare PASTA with PASOCS [23]. For PASOCS, we use the single threaded mode and select exact inference. For PASTA, the execution time includes both the computation of the minimal set of probabilistic facts and the computation of the projective solutions. Usually, the time required for the first operation is negligible with respect to the computation of the probability. We selected three different programs described in [25]. The first program, brd, is {(fly(X) | bird(X))[0.8,1],0.1::fly(1)} with an increasing number of probabilistic facts bird/1 with an associated probability of 0.5. The goal is to compute the probability of the query fly(1). The second program, mky, represents the pair of conditionals {(f(X) | h(X)) [0.2,1],(f(X,Y) | h(Y),r(X,Y))[0.9,1]}, with an increasing number of probabilistic facts h/1 and r/2, both with an associated probability of 0.5. The distribution of the facts r/2 follows a Barabási-Albert model, i.e., a graph, generated with the Python networkx package with parameter \(m_0\) (representing the number of edges to attach from a new node to existing nodes) set to 3 and an increasing number of nodes. We randomly selected half of the total number of nodes to generate the h/1 facts. The query is f(0),f(0,1). The third program, smk, represents the conditional {(smokes(Y) | smokes(X),friend(X,Y))[0.4,1]} with an increasing number of probabilistic facts friend/2 with an associated probability of 0.5, following the Barabási-Albert model. The query is smokes(I), where I is a random node. For both mky and smk, the results are averaged over 10 different programs, to make them more representative since the graph generation is not deterministic, and thus some instances can be easier to query. For all the three programs, the minimal set of probabilistic facts is empty, so the PASOCS and PASTA work on the same set of worlds. Inference times are shown in Fig. 1a. PASOCS on mky returned an internal error of the solver while parsing the program. In a second experiment, bird, we modify the brd program by removing 0.1::fly(1), and we ask two queries: fly(1), and fly(1) given that fly(2) has been observed. For these two experiments, the minimal set of probabilistic facts contains bird(1). Results are shown in Fig. 1b. Overall, with our solution we can manage a larger number of probabilistic facts. Moreover, the introduction of the minimal set of probabilistic facts gives a substantial improvement, as shown in Fig. 1b. However, both PASOCS and PASTA rely on the generation of all the worlds, which increase in an exponential way.

There are several PASP systems such as P-log [4], LPMLN [16], PrASP [17], and SMProbLog [22]: these aim at finding sharp probability values. We compare PASTA only with PASOCS [23] since, to the best of our knowledge, it is the only system that performs inference on probabilistic answer set programs with aggregates under the credal semantics. The solver proposed in [9] allows counting the answer sets of a given program, so, in principle, may be applied to perform inference in PASTA programs, however, aggregates are not allowed. The solution proposed in [2] adopts ASP techniques to perform inference in probabilistic logic programs but it is still focused on the computation of a sharp probability value. Statistical statements are considered also by [14] where a semantics is given by resorting to cross entropy minimization. Similarly to the case of [25], we differ because we do not select a specific model but we consider all the models consistent with the statements and we compare lower and upper bounds.

In this paper, we considered probabilistic conditionals as statistical statements - “Type 1” statements according to Halpern’s definition - and interpreted them under the credal semantics of probabilistic answer set programs. Our approach, called PASTA, includes both a language and an inference algorithm: the language is given a semantics by converting a probabilistic conditional into three ASP rules, one corresponding to the possible combinations of facts, and two constraints, one for the lower and one for the upper bound; the algorithm computes lower and upper probability values for conditional queries. On various programs, PASTA is able to handle a larger number of probabilistic facts than the state of the art solver for probabilistic answer set programs under the credal semantics. As future work, we plan to introduce abductive reasoning in this framework [3].