Hi everyone,
I have an ILP algorithm that’s giving me some trouble with infinite recursion
and I wanted to use tabling for it. My first attempts failed so I thought I’d
ask for help.
It’s probably best if I avoid any descriptions of the algorithm, before
they’re really needed so let’s be lazy instead. At some point in the execution
of the algorithm, (a portion of) the dynamic database look like this:
,- m(ancestor, stathis, kostas).
| m(ancestor, stefanos, dora).
| m(ancestor, kostas, stassa).
| m(ancestor, alexandra, kostas).
E+ | m(ancestor, paraskevi, dora).
| m(ancestor, dora, stassa).
| m(ancestor, stathis, stassa).
| m(ancestor, stefanos, stassa).
| m(ancestor, alexandra, stassa).
'- m(ancestor, paraskevi, stassa).
,- m(parent, A, B) :-
| p(father, A, B).
| m(parent, A, B) :-
| p(mother, A, B).
BK |
| p(father, kostas, stassa).
| p(father, stathis, kostas).
| p(father, stefanos, dora).
| p(mother, alexandra, kostas).
| p(mother, dora, stassa).
'- p(mother, paraskevi, dora).
,- m(ancestor, A, C) :-
H | m(ancestor, A, B),
'- m(ancestor, B, C).
In short, the clauses marked with E+ are positive examples, the clauses marked
BK are background knowledge and the clauses marked with H are the clauses of
the hypothesis that we have learned so far. The target predicate is
ancestor/2. The clauses of m/3 are “encapsulating” the E+, BK and H (for reasons
omitted for now).
You’ll notice that H is left-recursive. What’s really causing me the trouble is that the
procedure that calls H is nondeterministic, so even though there’s the “base case”
of the positive examples, H eventually causes the whole procedure to “go infinite”.
The procedure needs to be nondeterministic to be complete.
I was hoping to use tabling on m/3 to avoid infinite recursion. Clauses of m/3
are added to the dynamic database as they are induced, so I’ve tried this:
:-table m/3 as dynamic.
But my program is still going infinite. Tracing it a bit, I can see that it’s
really m/3 that’s going infinite.
You can try it yourself. Write the E+, BK and H to a file and load it, then
try a query like m(ancestor,X,Y). After a few solutions (all the pairs of X-Y
ancestor-descendant), it will enter an infinite recursion (that’s where I abort,
below):
?- m(ancestor,A,B).
A = stathis,
B = kostas ;
A = stefanos,
B = dora ;
A = kostas,
B = stassa ;
A = alexandra,
B = kostas ;
A = paraskevi,
B = dora ;
A = dora,
B = stassa ;
A = stathis,
B = stassa ;
A = stefanos,
B = stassa ;
A = alexandra,
B = stassa ;
A = paraskevi,
B = stassa ;
A = stathis,
B = stassa ;
Action (h for help) ? abort
% Execution Aborted
Is there something special I need to do or is tabling just no help in this
situation? If the latter- why?
Cheers,
Stassa
