Popper (Inductive Logic Programming, ILP) and my Popper page

General
1

Popper (GitHub - logic-and-learning-lab/Popper: Popper is an inductive logic programming (ILP) system.) is a really interesting Inductive Logic Programming (ILP) system, using SWI-Prolog and ASP (Clingo) to find Prolog programs (as definition of a predicate) given some positive and negative examples. It’s still a work-in-progress but it evolves quite fast now and can solve some interesting/fun instances.

My Popper page (My Popper page) contains some examples that Popper now can solve. Also see Popper’s example directory (Popper/examples at main · logic-and-learning-lab/Popper · GitHub ) for some other examples.

For example, Popper solve this puzzle (which was at Facebook the other day) in some second:

  1 + 4 = 5
  2 + 5 = 12
  3 + 6 = 21
  5 + 8 = ??

Here’s Popper’s solution:

f(A,B,C):- mult(A,B,D),plus(A,D,C).

I.e. ?? = 45, which is one of the (many) possible answers to the puzzle.

Popper also supports predicate invention so it can find solutions as the following for a graph problem (relatedness ):

target(A,B) :- inv1(B,C),
inv1(A,C). inv1(A,B) :- parent(A,B). 
inv1(A,B) :- parent(C,A),inv1(C,B).

where inv1 is the invented predicate.

Note that some of the solutions that Popper finds might not be the best solution, for example the predicate might not be reversible as one would expect if a Prolog programmer wrote it.

Compared to other ILP systems that I have played with (e.g. Metagol, Progol, Aleph), Popper is - IMHO - a little easier to use since one don’t have to state the type or directions of the background knowledge (BK) predicates; but given this information might boost the performance. However, the other systems - especially Aleph - have features that Popper don’t support (yet?), such as noise. Also it don’t support constants (but one can use “names constants”, see constants1_b for an example). And it don’t handle floats very well.

One approach that I probably will delve into further is to use clpfd together with Popper to try to find the valid constraints given some examples. Here’s a first tests of this: clpfd_test with quite a few different small tests. Note that it use my SWI Prolog utils file: My SWI-Prolog page /hakank_utils.pl .

For example, given the following positive (pos/1) and negative (neg/1) examples:

pos(target([2,3,4,5,1])).
pos(target([2,3,5,1,4])).
pos(target([2,4,5,3,1])).
pos(target([2,4,1,5,3])).
pos(target([2,5,4,1,3])).
neg(target([1,2,3,4,5])).

Popper find the constraint circuit/1. The negative example ([1,2,3,4,5]) makes it skip other constraints such as all_different.

9 Likes
2

I was playing around with your cyclic example because i found it interesting :slight_smile:

I was curious if it could use predicate invention to find the path/3 predicate but this seemed to take a long time / not work (I interrupted execution after a couple of minutes). Not sure if this is beyond Popper’s capabilities or if my example was inappropriate…

What i got was:

10:38:10 Num. pos examples: 3
10:38:10 Num. neg examples: 4
10:38:22 Searching programs of size: 3
10:38:22 ********************
10:38:22 New best hypothesis:
10:38:22 tp:1 fn:2 size:3
10:38:22 cyclic(A):- arc(A,C,B),arc(A,B,C).
10:38:22 ********************

My bias.pl

enable_pi.
enable_recursion.
head_pred(cyclic, 1).
body_pred(arc, 3).

My bk.pl

arc(x, a, b).
arc(x, b, c).
arc(x, c, d).
arc(x, d, a).

arc(y, a, b).
arc(y, b, c).
arc(y, c, a).

arc(z, a, b).
arc(z, b, a).

% non cyclic

arc(p, a, b).
arc(p, b, c).
arc(p, a, c).

arc(q, a, b).
arc(q, a, c).

arc(r, a, b).
arc(r, b, c).
arc(r, c, d).
arc(r, b, d).

arc(s, a, b).
arc(s, b, c).
arc(s, a, c).

My exs.pl

pos(cyclic(x)).
pos(cyclic(y)).
pos(cyclic(z)).

neg(cyclic(p)).
neg(cyclic(q)).
neg(cyclic(r)).
neg(cyclic(s)).
1 Like
3

Great that you testing Popper, JCR!

I tested your model but didn’t found any solution with PI or recursion. However, Popper finds a “plain” solution after 0.9s using this bias file. Note the addition of type and direction to help Popper a little.

enable_pi.
enable_recursion.
head_pred(cyclic, 1).
body_pred(arc, 3).

type(cyclic,(item1,)).
direction(cyclic,(in,)).

type(arc,(item1,item2,item2)).
direction(arc,(in,out,out)).

Here the solution (both precision and recall are 1 and no FN or FP):

********** SOLUTION **********
Precision:1.00 Recall:1.00 TP:3 FN:0 TN:4 FP:0 Size:9
cyclic(A):- arc(A,D,C),arc(A,B,D),arc(A,C,B).
cyclic(A):- arc(A,E,C),arc(A,C,B),arc(A,B,D),arc(A,D,E).
******************************

Note: Without enable_pi and enable_recursion the solution is found slightly faster: after 0.55s.

So, let’s test this in SWI-Prolog. First the content of bk.pl and then the found solution:

?- [user].
% bk.pl
arc(x, a, b).
arc(x, b, c).
arc(x, c, d).
arc(x, d, a).

arc(y, a, b).
arc(y, b, c).
arc(y, c, a).

arc(z, a, b).
arc(z, b, a).

% non cyclic

arc(p, a, b).
arc(p, b, c).
arc(p, a, c).

arc(q, a, b).
arc(q, a, c).

arc(r, a, b).
arc(r, b, c).
arc(r, c, d).
arc(r, b, d).

arc(s, a, b).
arc(s, b, c).
arc(s, a, c).

% The found program
cyclic(A):- arc(A,D,C),arc(A,C,B),arc(A,B,D).
cyclic(A):- arc(A,C,E),arc(A,D,B),arc(A,E,D),arc(A,B,C).
^D

% Test it!
?- findall(A,cyclic(A),L).
L = [y, y, y, x, x, x, x, z, z].

?- setof(A,cyclic(A),L).
L = [x, y, z].


% Test the negative examples
?- cyclic(p).
false.

?- cyclic(q).
false.

?- cyclic(r).
false.

?- cyclic(s).
false.

I would say that the found program is “fairly correct”, though checking cyclic(x) it yields too many solutions to be really good.

?- cyclic(x).
true ;
true ;
true ;
true ;
false.

I also played with different settings of max_vars/1, max_body/1, and max_clauses/1 but that didn’t help getting a solution with PI or recursion.

Perhaps Popper would find a PI / recursive version with some ASP trickery, but I’m not sure what would the proper way to force this. See the Popper example examples/robots-pi/bias.pl or examples/filter/bias.pl for such ASP trickery.

4

Thats interesting, thanks.

I guess a problem with my example is that the path/3 predicate i was expecting Popper to invent does not terminate in a cyclic graph, e.g.

arc(x, a, b).
arc(x, b, c).
arc(x, c, d).
arc(x, d, a).

path(G, A, B):- arc(G, A, B).
path(G, A, B):- arc(G, A, C), path(G, C, B).

test:- path(G, A, B), writeln(path(G, A, B)).

which yields

?- test.
path(x,a,b)
true ;
path(x,b,c)
true ;
path(x,c,d)
true ;
path(x,d,a)
true ;
path(x,a,c)
true ;
path(x,a,d)
true ;
path(x,a,a)
true ;
path(x,a,b)
true

and on and on…

So this test might have been a bit unfair. Maybe i’ll try another example to se if predicate invention and recursion can be combined…