A wide variety of models that combine logical and statistical knowledge can be expressed succinctly in the Probabilistic Logic Programming (PLP) paradigm. Specifically, models in standard statistical formalisms such as probabilistic graphical models (PGMs) (e.g. Bayesian Networks), can be easily encoded as PLP programs. For instance, Fig. 1(a) shows a program in PRISM, a pioneering PLP language [16]. A widget, represented by a random variable X, is tested by two different processes b1 and b2. The outcomes of these tests are represented by random variables Y and Z, respectively. In PRISM, a special predicate of the form msw(a,X) associates random variable X with a random process a. Consider the problem of determining the distribution of X given that Y and Z are identical. Note that evidence is defined as a constraint over instantiations of the random variables, in contrast to a specific instantiation as in traditional PGMs. However, such evidence can be easily specified in PLP (see predicate e/0). The probability of a specific instantiation of X can also be computed based on a PLP query (e.g. q(1) using predicate q/1). This simple example illustrates how logical clauses can be used to specify evidence and queries in PLP that go beyond what is possible in traditional PGMs. The Driving Problem. The expressiveness of PLP comes at a cost. Since PLP is an extension to traditional logic programming, inference in PLP is undecidable in general. Probabilistic inference for a large class of statistical models (e.g. Bayesian networks) is intractable. Even problems for which inference is tractable can be encoded in multiple ways in PLP, with different inference complexity. For instance, consider the PRISM program in Fig. 1(b). In that program, genlist/2 defines a list of the outcomes of N identically distributed random variables ranging over {a,b}. Predicate palindrome/1 tests, using a definite clause grammar definition, if a given list is a palindrome; and count as/2 tests if a given list contains k (not necessarily consecutive) “a”s. Using these predicates, consider the inference of the conditional probability of query(n, k) given evidence(n): i.e., the probability that an n-element palindrome has k “a”s.
1 % Model: Y and Z depend on X.
2 w(X,Y,Z)
:3 msw(a, X),
4 msw(b1(X), Y),
5 msw(b2(X), Z).
6 % Evidence: Y and Z are same.
7 e :- w(_,S,S).
8 % Query: value of X.
9 q(X) :- w(X,_,_).
10 % Domains:
11 values(a, [
(a) Bayesian Network PLP 1 % generate a list of N random variables. 2 genlist(N, L) :- (N=0 -> L= [] 3 ; msw(flip, N, X), 4 L = [X|L1], N1 is N-1, 5 genlist(N1, L1) ). 6 % Evidence: string is a palindrome. 7 evidence(N) :- genlist(N, L), palindrome(L). 8 % Query: string has K ’a’s 9 query(N, K) :- genlist(N, L), count_as(L, K). 10 % Check if a given list is a palindrome 11 palindrome(L) :- phrase(palindrome, L). 12 palindrome --> []. 13 palindrome --> [_X]. 14 palindrome --> [X], palindrome, [X]. 15 % Query condition: 16 count_as([], 0). 17 count_as([X|Xs], K) :18 K > 0, (X=a -> L is K-1; L=K), 19 count_as(Xs, L). 20 % Domains: 21 values(flip, [a,b]). 22 % Distribution parameters: 23 set_sw(flip, [0.5, 0.5]).
(b) Palindrome PLP
The conditional probability is well-defined according to PRISM’s distribution
semantics [
Approximate inference based on rejection sampling performs poorly,
rejecting a vast number of generated samples, since the likelihood of a string being
a palindrome decreases exponentially in N . Alternatives such as
MetropolisHastings-based Markov Chain Monte Carlo (MCMC) techniques [9, e.g.] do
not behave much better due to the fact that the chains exhibit poor
convergence (mixing), since most transitions lead to strings inconsistent with evidence.
Gibbs-sampling-based MCMC [
msw(a,X) msw(b1(X), Y) msw(b2(X), Z)
Y=Z
msw(a,X) msw(b1(X), Y)
Y ∈ {2, 3} msw(b2(X), Z)
Z ∈ {2, 3}, Z = Y 2 2 (a) Before Constraint Propagation (b) After Constraint Propagation Our Approach. We identify two basic problems that contribute to the difficulty of inference in PLPs. First is that the random variable dependencies are not explicit in the program but may vary based on the program’s control and data flow. The second is that evidence (and query) specifications may be complex rendering it difficult to predict whether a variable’s valuation will be consistent with the evidence (or lead to query’s success). We use constraint propagation both to uncover the hidden dependencies and to predict consistency with evidence. We explicitly construct symbolic derivations that abstract actual valuations of random variables and use a graphical structure to represent the derivations. We then provide inference algorithms, both approximate and exact, that compute the probability of a (possibly conditional) query based on this graphical structure.
Summary of Contributions. This paper describes a novel technique that addresses the problem of scalability of inference in PLPs. 1. The paper introduces a structure called an Ordered Symbolic Derivation Diagram to represent succinctly the set of possible derivations for a PLP query or evidence (Section 2). 2. The paper presents a likelihood-weighted sampling method based on OSDDs that can be used for approximate inference (Section 3). 3. The paper also presents an exact inference algorithm that operates directly on OSDDs. While this algorithm has relatively narrow applicability, it provides a powerful way to infer over large problem sizes without enumerating random variable valuations (Section 3).
We present experimental results which show the effectiveness of OSDD-based inference methods, as well as their cost (Section 4). Related work is discussed in detail in Section 5. The paper concludes with a discussion on the other uses of OSDDs for inference in PLPs. 2
In this paper, we use PRISM’s syntax and distribution semantics, but without the independence and mutual exclusion requirements on the explanations of a goal. Thus we consider PRISM programs with their intended model-theoretic semantics, rather than that computed by the PRISM system.
As stated in the Introduction, the dependencies between random variables implicit in the control and data flow of a PLP, and the impossibility of completely representing the set of all random variable valuations that are consistent with evidence contribute to the difficulty of inference in PLPs. To address these two problems, we devise an inference technique based on constraint propagation, to uncover hidden dependencies and predict evidence consistency. In the first step, we build derivations symbolically, instantiating random variables only when necessary. A symbolic derivation is a sequence of msw goals and constraints, as illustrated in Fig. 2(a) by the derivation for evidence “e” from example of Fig. 1(a).
In the second step, we propagate the constraints in a symbolic derivation,
resulting in possible restrictions on the domains of variables. For instance, in
the Bayesian Network (BN) example of Fig. 1(a), since the evidence demands
Y = Z, the domains of b1 and b2 get restricted to [
We illustrate the process of generating likelihood-weighted samples [
msw(b(3),X3) msw(b(2), X2)
X2=X1 msw(b(3), X3)
X3=X2 msw(b(1), X1)
X1=X3 2 2 2 1 msw(b(1),X1) msw(b(2), X2) X2 = X1 X26=X1
X3 = X1 msw(b(3), X3)
X3 6= X1 ∧
X3 = X2
X3 6= X1 ∧
X36= X2 (a) Selected Symbolic Derivations 1 1 (b) Symbolic Derivation Diagram 0 visiting msw(a,X), we notice no domain restrictions on X, and hence bind X to a random sample generated from a’s distribution. Assume the sample we drew is X=1. We then visit msw(b1(1), Y) to sample Y. However, since Y has a domain restriction Y ∈ {2, 3}, we generate a sample for Y such that Y ∈ {2, 3}. This is done by picking from {2, 3} uniformly, and multiplying the likelihood weight with the probability of the picked value. Assume we pick Y=2; then the current likelihood is set to 0.3, the probability of 2 in b1(1)’s distribution. Finally, we visit msw(b2(1),Z), whose two constraints restrict Z to {2}. Selecting Z=2, we multiply the likelihood weight of the current derivation with 0.5. Thus we generate a sample (X=1, Y=2, Z=2) consistent with evidence e with a likelihood weight of 0.15.
In summary, likelihood-weighted samples are drawn by (a) independently
sampling random variables whose valuations are unconstrained; (b) uniformly
sampling variables whose valuations have domain constraints; and (c) computing
the probability of the sample as the product of probabilities of values picked in
step (b). This procedure can be readily formalized; see [
Exact Inference. For certain class of programs and queries, symbolic
derivations can be directly used for exact inference. Fig. 4 shows the symbolic
derivation of evidence evidence(6) from the Palindrome example (Fig. 1(b)). Note
that only the constraints in the symbolic derivation determine whether a
concrete instance succeeds. Thus, if the distribution of flip is uniform, the three
constraints are each satisfied independently, resulting in 0.125 as the probability.
Such exact computation of probabilities is formalized in terms of measurability ;
a variable X with domain constraint η is said to be measurable if the size of X’s
domain (consistent with η) is independent of the valuation of other variables.
When a symbolic derivation diagram consists only of uniformly distributed
measurable variables, then the associated probability can be computed exactly. Such
exact computation is readily formalized as well; see [
2 % share a birthday. msw(flip, 5, X2) 3 same_birthday(N) :
4 person(N, P1), msw(flip, 4, X3) 5 % P1’s birthday is D msw(fXl4ip=, X33, X4) 768 pmPes1rws(\ob=n((PPN12,),,P2D)),, msw(flip, 2, X5) 9 % and so is P2’s.
X5 = X2 10 msw(b(P2), D).
11 msw(flip, 1, X6) 12 person(N, P) :
X6 = X1 13 % bind P, backtracking through 1..N
14 basics:for(P, 1, N). 2 15
16 % Distribution parameters: Fig. 4: Symbolic Derivation for ev- 17 set_sw(b(_), uniform(1,365)). idence “evidence(6)” in Palindrome Example Fig. 5: Birthday Collision PLP 4
We present the results of experiments using a prototype implementation of a likelihood-weighted sampler based on symbolic derivations. The prototype uses XSB Prolog to build symbolic derivations, propagate constraints and construct OSDDs; and a few modules written in C for maintaining the sampler’s state and dealing with random variable distributions. We used the following examples in the experiments.
– Grid BN is a Bayesian Network with Boolean random variables arranged in a 6 × 6 grid (with dependencies going left-to-right and top-to down). This simple structure was used to evaluate the effectiveness of our technique when the evidence probability is extremely low (˜10−12). – Ising Model is a well-known undirected graphical model. We used a 6 × 6 grid of Boolean random variables with factors on edges. The PRISM program independently generates values of terminal nodes of all edges, and ties them together by expressing equality constraints between shared variables of edges. – Palindrome, which is shown in Fig. 1(b), with evidence limited to strings of length 20, and query checking for a string with 4 “a”s. – Birthday Collision, shown in Fig. 5 (page 6), with population size of 6, i.e. query same birthday(6).
The first three examples involved conditional queries with low-likelihood evidence. The birthday collision example had an unconditional query. It should be noted that only the first example, Grid BN, can be evaluated in the PRISM system; the other examples have queries that violate PRISM’s mutual exclusion and independence assumptions and hence cannot be directly evaluated in that 0.06 6x6 grid BN 6x6 ising model lw-probability lw-variance exact answer lw-probability is-probability lw-variance is-variance system. Our inference procedure, however, removes PRISM’s assumptions and correctly evaluates the query probabilities for all the above examples.
The results of the experiments are shown in Fig. 6. Each subfigure plots the estimated probability and variance of the estimate(on log scale), for two samplers: the LW method described in this paper, and a simple independent sampler (with rejection sampling for conditional queries). Note that the LW sampler’s results show significantly lower variance in all the examples. For the Grid BN and Ising Model, the evidence probability was low enough that a rejection sampler was unable to draw a consistent sample. The LW sampler, however, was able to converge to a reasonable estimate of low variance in about 500,000 samples. Both examples generated a single symbolic derivation. We directly sampled from this instead of materializing a OSDD structure. For the Grid BN, node consistency was sufficient to derive domain restrictions. For the Ising model, we found that standard LW sampling (picking a restricted value uniformly and assigning a likelihood weight) generated a number of samples with extremely low weights. Instead the probabilites of the set of allowed values were normalized to create a new proposal distribution. This resulted in generating samples with higher likelihood weights.
For the Palindrome example, we get a single symbolic derivation and the LW sampler quickly converges to the actual probability, while the independent sampler fails to converge even after a million samples. However, node- and arcconsistency can discover no further domain restrictions; forward checking at sampling time generated all the restrictions for LW sampler. The unusual pattern of variance for independent sampler in the initial iterations is due to it not being able to generate consistent samples and hence not having an estimate for the answer probability. The birthday collision example produces a number of symbolic derivations which were incorporated in an explicit OSDD. Domain restrictions are discovered only via forward checking, and that too for only one variable. The results show smaller difference between independent sampling and LW sampling for this example, compared to the others. One interesting observation from this example was that independent sampling using the OSDD structure was significantly faster (up to 2×) than using the program directly. This is because the program’s non-deterministic evaluation has been replaced by a deterministic traversal through the OSDD.
Overheads. For all the examples, the time to construct the symbolic derivations, and propagate constraints was negligible (ranging from 4ms for Grid BN to 7ms for Birthday Collision, with XSB 3.5.0 on a 2.5GHz Intel Core 2 Duo machine). The overheads for sampling however were more pronounced. While an independent sampler picks values from the given distributions, the likelihoodweighting sampler needs to construct restricted domains to draw samples from. Consequently, our LW sampler takes up to 4× per sample as an independent sampler.
Comparison with PITA and ProbLog. We evaluated the exact inference procedures of PITA and ProbLog on the same examples. We used a timeout of 15 minutes for both systems. The exact inference algorithm of ProbLog using sentential decision diagrams was able to handle Grid BN instances of size up to 9 × 9. However, ProbLog’s inference does not scale beyond small problem sizes for the remaining three examples. In contrast, exact inference algorithm of PITA scaled much better. PITA could successfully compute the conditional probabilities for Grid BN (up to size 10 × 10), Ising model (up to 13 × 13) and Palindrome with n = 18. For the Ising model example, PITA’s inference completes but with numerical errors due to the low probability of evidence. Finally, PITA’s inference completed for the Birthday example with population size 2, but ran out of memory for larger population sizes. 5
Probabilistic Constraint Logic Programming [
cProbLog extends ProbLog with first-order constraints [
CLP(BN ) [
There has been a significant interest in the area of lifted inference as
exemplified by the work of [
The use of sampling methods for inference in PLPs has been widespread.
The evidence has generally been handled by heuristics to reduce the number
of rejected samples [
Adaptive sequential rejection sampling [
We presented a technique for inference in PLPs based on constructing a symbolic structure called OSDD using constraint propagation. The technique effectively performs inference without enumeration for a number of programs. The technique also uncovers the dependencies between random variables, which can then be exploited by more powerful inference techniques (e.g. Gibbs-sampling-based MCMC) that were inapplicable otherwise. However, for programs where symbolic derivations match one-to-one with concrete derivations, the technique offers no benefit. An important topic of future work is to statically analyze a program to determine when (and when not to) use this technique. OSSDs are constructed by exploiting the presence of explicit random variables due to msw’s in PRISM. Application to other (equally expressive) PLP languages remains to be explored. Finally, OSDDs introduce a style of inference where indistinguishable valuations of random variables are treated together; combining this with lifted inference that groups indistinguishable random variables together will improve the scalability of inference in PLPs.