PDF《DNF Sampling for ProbLog Inference》

s implementation is targeted at overcom- ing these limitations. The syntax of a ProbLog program T is similar to that of a Prolog one: it consists of facts and relations between them, but in the case of ProbLog a label is attached to some of the facts. That is, the program can be split into a set of labelled facts, where each pi :: fi de?nes a fact fi with probability of occurrence pi, and a Prolog program using those facts, which encodes background knowledge (BK). We denote the set of all fi (without probability label) by LT . Probabilistic facts correspond to mutually independent random variables (RVs), which together de?ne a probability distribution over all ground logic programs L ? LT : P(L|T) = fi∈L pi fi∈LT \L (1 ? pi). (1) We use the term possible world to denote the least Herbrand model of such a subprogram L together with the background knowledge BK and, by slight abuse of notation, use L to refer to both the set of sampled facts and the corresponding world. Figure

1 shows a typical example of a probabilistic graph encoded in ProbLog. One can query the probability that a path exists between two nodes in the graph. As it can be noticed from the graph of Figure 1, there are several possible paths between two nodes. For example between nodes b and f, we have two possible paths: b → e → f and b → d → f. In ProbLog, querying for the probability of path(b, f) means asking for the probability that a randomly selected subgraph contains a path from b to f. Such subgraphs can contain the edges of the path b → e → f or those of the path b → d → f, but also all of them or even many 0.40 :: edge(a,b). 0.55 :: edge(a,c). 0.80 :: edge(b,e). 0.20 :: edge(b,d). 0.40 :: edge(c,d). 0.30 :: edge(e,f). 0.50 :: edge(d,f). 0.60 :: edge(d,g). 0.70 :: edge(f,h). 0.70 :: edge(g,h). path(X, Y) :- edge(X, Y). path(X, Y) :- edge(X, Z), path(Z, Y). (a) Probabilistic graph (b) ProbLog program Fig. 1. An example of a probabilistic graph and the corresponding ProbLog program. more. The success probability Ps(q|T) of a query q can now be de?ned as follows: Ps(q|T) = L?LT P(q|L) ・ P(L|T) (2) where P(q|L) is

1 if there is a substitution θ such that qθ is entailed by the union of L and the background knowledge (L ∪ BK |= qθ), and

0 otherwise. Equation (2) states that the success probability of the query path(b, f) can be calculated by summing the probabilities of all subgraphs which include at least one path connecting nodes b and f. As the number of subprograms to be considered is exponential in the number of probabilistic facts, this approach quickly becomes infeasible with increasing problem size. The ProbLog system therefore uses a di?erent approach, which will be discussed in Section 2.1. A second inference task in ProbLog is the identi?cation of the best proof or explanation of a query. An explanation, also called proof here, is a set of probabilistic facts α ∈ LT which satis?es the following properties [9]: 1. it is su?cient to account for q, i.e. BK ∪ α |= q, 2. it is not ruled out by the BK, i.e. BK ∪ α is consistent, 3. there is no β ? α such that

1 and

2 hold for β. In Equation (2), the sum goes over those subprograms that contain some proof of the query. When considering a speci?c explanation, this is further re- stricted to those subprograms containing all facts of that explanation. Therefore the probability of an explanation α is given by the following formula: P(α|T) = α?L?LT P(L|T) = fi∈α pi. (3) As there may exist many explanations α for a query q, the one with the highest probability is used to de?ne the explanation probability of q: Px(q|T) = maxα∈E(q) P(α|T) = maxα∈E(q) ci∈α pi, (4) where E(q) is the set of all explanations for query q. For our example, both probabilities as given in Equations (2) and (4) are easily computed even by hand: the success probability is Ps(path(b, f)|T1) = 0.316 (note that it is su?cient to consider the graph restricted to nodes b, e, d and f when listing subprograms for this query), and the explanation probability is max(0.8 ・ 0.3, 0.2 ・ 0.5) = max(0.24, 0.1) = 0.24, but for complex problems this could consume large amounts of time and memory. ProbLog therefore follows di?erent strategies to obtain success probabilities, which we will brie?y discuss next. 2.1 Exact Inference As iterating over possible subprograms as done in Equation (2) is infeasible for most programs, ProbLog'