
## 4.6 Inside Probability And Outside Probability For Logic Programs

In this subsection, we generalize the notion of inside probability and outside probability (Baker, 1979; Lari & Young, 1990) to logic programs.  Major computations in learn-naive(DB,G)
are those of two terms in Line 6, PDB(Gt | 0) and ESE(PB(Gt) Pmsw(S | 0) σi,v(S). Computational redundancy lurks in the naive computation of both terms. We show it by an example. Suppose there is a propositional program DB p = F p ∪ R p where F p = {a,b,c,d,m} and

$$R_{p}=\left\{\begin{array}{ll}\mbox{f}\leftarrow\mbox{a}\wedge\mbox{g}\\ \mbox{f}\leftarrow\mbox{b}\wedge\mbox{g}\\ \mbox{g}\leftarrow\mbox{c}\\ \mbox{g}\leftarrow\mbox{d}\wedge\mbox{h}\\ \mbox{h}\leftarrow\mbox{m}.\end{array}\right.\tag{10}$$

Here f is an observable atom. We assume that a, b, c, d and m are independent and also that {a, b} and {c, d} are pair-wise exclusive. Then the support set for f is calculated as ψ D B p (f) = {a ∧ c, a ∧ d ∧ m, b ∧ c, b ∧ d ∧ m }.

Hence, in light of (8), we may compute PDBp(f) as

$$P_{D B_{p}}({\mathfrak{f}})\,=\,P_{F_{p}}({\mathfrak{a}}\wedge{\mathfrak{c}})+\,P_{F_{p}}({\mathfrak{a}}\wedge{\mathfrak{d}}\wedge{\mathfrak{m}})+\,P_{F_{p}}({\mathfrak{b}}\wedge{\mathfrak{c}})+\,P_{F_{p}}({\mathfrak{b}}\wedge{\mathfrak{d}}\wedge{\mathfrak{m}}),$$
$$(11)$$

This computation requires 6 multiplications (because PF, (a A c) = PF, (a)PF, (c) etc.) and 3 additions. On the other hand, it is possible to compute PDBp (f) much more efficiently by factoring out common computations. Let A be a ground atom. Define the inside probability β ( A ) of A as

$$\beta(A)\ {\stackrel{\mathrm{def}}{=}}\ P_{D B}(\,A\ |\ \theta\,).^{24}$$
$$(12)$$

Then by applying Theorem A.1 in Appendix A to

$$c o m p(\,R_{p}\,)\vdash{\mathfrak{f}}\,\leftrightarrow\,(\,{\mathfrak{a}}\wedge{\mathfrak{g}}\,)\vee({\mathfrak{b}}\wedge{\mathfrak{g}}\,),\,{\mathfrak{g}}\,\leftrightarrow\,{\mathfrak{c}}\vee(\,{\mathfrak{d}}\wedge{\mathfrak{h}}\,),\,\,{\mathfrak{h}}\,\leftrightarrow\,{\mathfrak{m}}$$
$$\left(13\right)$$

which unconditionally holds in our semantics, and by using the independent and the exclusiveness assumption made on Fp, the following equations about inside probability are derived.

$$\left\{\begin{array}{l l l}{\beta(\mathbf{f}\,)}&{=}&{\beta(\mathbf{a})\beta(\mathbf{g})+\beta(\mathbf{b})\beta(\mathbf{g})}\\ {\beta(\mathbf{g})}&{=}&{\beta(\mathbf{c})+\beta(\mathbf{d})\beta(\mathbf{h})}\\ {\beta(\mathbf{h})}&{=}&{\beta(\mathbf{m})}\end{array}\right.$$
$$(\,14\,)$$

PDBp(f)(= β(f)) is obtained by solving (14) about β(f), for which only 3 multiplications and 2 additions are required.

It is quite straightforward to generalize (14) but before proceeding, look at a program DB n = {m} U {g:-m^m, g:-m} where g is an observable atom and m the only msw atom.

We have g → (m ∧ m) V m in our semantics, but to compute P(g) = P(m) P(m) + P(m) is clearly wrong as it ignores the fact that clause bodies for g, i.e. mAm and m are not mutually exclusive, and atoms in the clause body mAm are not independent (here P(.) = PDB s(.)).

Similarly, if we set a = b = c = d = m, the equation (14) will be totally incorrect. 24. Note that if A is a fact in F, β(A) = P,,,(A | θ).