Download pdf - arXiv
Transcript
26
CHAPTER 2. BACKGROUND
are invalid combinations of the signature (r(2,0),r(2,1),...). On
the other hand, the first bound variable of the predicate r/2 makes
that only r(0,1) and r(0,2) are valid subtrees.
– So, we need to check the rule after each solving step, checking if
there are new variables after the substitutions. If there are, we
will need to obtain the probability of the whole predicate that has
free variables, in the same way we are calculating a new example.
For instance, if we have:
0.7 :: r (A , B ) : - B is A , p ( C ) .
0.3 :: r (A ,0) .
... % we do not include the rules for p /1.
To calculate r(X1 , X2 ), we will need first p(X) because in the rule
r/2 this predicate appears with a free variable. If we suppose that
p/1 has an estimated probability of 0.25, then we will multiply by
this factor the result for the rule r/2 to obtain the real probability
of that evidence.
Although, a limitation in the depth of SSLD-derivations must be considered, since they could be infinite. If we look again at program P5 (Listings
2.5), the function symbol s/1 makes infinite the growth of the SSLD-tree for
predicate sum/3, as we show in Figure 2.3.
sum(X1,X2,X3)
{X1/s(X1),X3/s(X3)}
0.5
{X1/0,X2/X3}
0.5
sum(0,X2,X2)
sum(s(X1),X2,s(X3))
0.5
{X1/s(X1),X3/s(X3)}
{X2/s(X2)}
{X2/0}
0.5
0.5
sum(0,s(X2),s(X2))
sum(s(s(X1)),X2,s(s(X3)))
sum(0,0,0)
{X1/s(X1),X3/s(X3)}
0.5
sum(s(s(s(X1))),X2,s(s(s(X3))))
Figure 2.3: An example of SLD-tree with infinite derivations
In this SSLD-tree, if we use a low value for the maximum depth inside
the tree, the sum of the probabilities for the predicate is going to be nearby
1, but not all the stochastic logic programs are going to have a so simple
structure in which the prune of the SSLD-tree is not going to trim important
facts that need more depth in the derivation.
2.6
Previous approaches for coding logical theories
Measuring the length or “cost” of a theory expressed as a logic program is
not a new area of research. As we have pointed out at the beginning of this
chapter, there are other previous works for coding logic programs. However,