

![0_image_0.png](0_image_0.png)

Figure 12: Bayesian networks these conditional distributions:

$$P(X_{1}=x_{1},\ldots,X_{N}=x_{N})^{55}=\prod_{i=1}^{N}P(X_{i}=x_{i}\mid\mathbf{\Pi}_{i}=\mathbf{u}_{i}).\tag{21}$$
$$\mathbf{\Phi}(\mathbf{\Phi})P_{G_{1}}(d\mid a,\,b)P_{G_{1}}(e\mid d)P_{G_{1}}(f\mid$$

Thus the graph G 1 in Figure 12 defines PG 1 (a, b, c, d, e, f) = PG 1 (a)PG 1 (b)PG 1 (c | a)PG 1 (d | a, b)PG 1 (e |d)PG 1 (f |d)
where a, b, c, d, e and f are values of corresponding random variables A, B, C, D, E and F , respectively. 56  As mentioned before, one of the basic tasks of Bayesian networks is to compute marginal probabilities. For example, the marginal distribution PG,(c,d) is computed either by (22) or (23) below.

$$P_{G_{1}}(c,d)=\sum_{a,b,c,f}P_{G_{1}}(a)P_{G_{1}}(b)P_{G_{1}}(c\,|\,a)P_{G_{1}}(d\,|\,a,b)P_{G_{1}}(e\,|\,d)P(f\,|\,d)\tag{22}$$ $$=\left(\sum_{a,b}P_{G_{1}}(a)P_{G_{1}}(b)P_{G_{1}}(c\,|\,a)P_{G_{1}}(d\,|\,a,b)\right)\left(\sum_{e,f}P_{G_{1}}(e\,|\,d)P_{G_{1}}(f\,|\,d)\right)\tag{23}$$  (23) is clearly more efficient than (22). Observe that if the graph were like $G_{2}$ in 
Figure 12, there would be no way to factorize computationslike (23) but to use (22) requiring exponentially many operations. The problem is that computing marginal probabilities is NP-hard in general, and factorization such as (23) is assured only when the graph is singly connected like G 1 , i.e. has no loop when viewed as an undirected graph. In such case, the computation is possible in O ( | V |) time where V is the set of vertices in the graph (Pearl, 1988). Otherwise, the graph is called multiply-connected , and might need exponential time to compute marginal probabilities. In the sequel, we show the following.

- For any discrete Bayesian network G defining a distribution P G ( x 1 , . . . , x N ), there is a

p arameterized logic program DBG for a predicate bn( ) such that PDBG(bn(x1,..,xN))