Wrong pruning during the search?

[yangdinglou]

Hello,

I have not read the codes, but according to the description in the paper, the learner should give the best solution. During my test, the learned predicate is not stable for the same setting. The test case and the results are as follows.

%%bias.pl
max_vars(5).
max_body(5).
max_clauses(2).
enable_recursion.

head_pred(f,2).
body_pred(nullptr,1).
body_pred(delete,3).
body_pred(my_min_list,2).
body_pred(empty,1).
body_pred(value,2).
body_pred(pointer,2).

type(f,(element,list)).
type(nullptr,(element,)).
type(delete,(list,integer,list)).
type(my_min_list,(list,integer)).
type(empty,(list,)).
type(value,(element,integer)).
type(pointer,(element,element)).

%%bk.pl
use_module(library(lists)).

empty([]).
zero(0).
one(1).

value(n1,1).
value(n2,2).
value(n3,3).
value(n4,4).

pointer(n1, n2).
pointer(n2, n3).
pointer(n3, n4).
pointer(n4, null).
nullptr(null).

my_min_list(List, Num):-
    ground(List), min_list(List, Num).

%%exs.pl
pos(f(n1,[4,3,1,2])).
pos(f(n2,[4,3,2])).
pos(f(n3,[3,4])).
pos(f(n4,[4])).
pos(f(null,[])).

neg(f(n1,[4,1,2])).
neg(f(n1,[4,3,5,2])).
neg(f(n1,[4,3,2])).
neg(f(n2,[4,3,2,7])).
neg(f(n3,[3,4,5])).
neg(f(n4,[])).

The program won't run for long when it returns the correct result. (with --info flag)

Thread 1 (main): foreign predicate system:is/2 did not clear exception: 
        time_limit_exceeded
% NEW BEST PROG 1:
f(A,B):-my_min_list(B,C),value(A,C).
% Precision:0.57, Recall:0.80, TP:4, FN:1, TN:3, FP:3

% NEW BEST PROG 309:
f(A,B):-empty(B),nullptr(A).
f(A,B):-pointer(A,C),my_min_list(B,E),delete(B,E,D),f(C,D).
% Precision:0.83, Recall:1.00, TP:5, FN:0, TN:5, FP:1


% BEST PROG 891:
f(A,B):-empty(B),nullptr(A).
f(A,B):-pointer(A,C),my_min_list(B,D),delete(B,D,E),value(A,D),f(C,E).
% Precision:1.00, Recall:1.00, TP:5, FN:0, TN:6, FP:0

Wrong result

Thread 1 (main): foreign predicate system:is/2 did not clear exception: 
        time_limit_exceeded
% NEW BEST PROG 1:
f(A,B):-value(A,C),my_min_list(B,C).
% Precision:0.57, Recall:0.80, TP:4, FN:1, TN:3, FP:3

% NEW BEST PROG 261:
f(A,B):-nullptr(A),empty(B).
f(A,B):-nullptr(C),value(A,D),my_min_list(B,D),pointer(A,C).
% Precision:1.00, Recall:0.40, TP:2, FN:3, TN:6, FP:0


% BEST PROG 16022:
f(A,B):-nullptr(A),empty(B).
f(A,B):-nullptr(C),value(A,D),my_min_list(B,D),pointer(A,C).
% Precision:1.00, Recall:0.40, TP:2, FN:3, TN:6, FP:0

[andrewcropper]

This issue is caused by non-terminating programs.

Prolog programs are not guaranteed to terminate. Therefore, we enforce a maximum evaluation time per example. In this case, Popper is generating programs that timeout, so it considers them failures.

I tried this change and Popper seems to reliably solve your problem:

% add to bk.pl
my_delete(List1, Elem, List2):-
ground(List1),
ground(Elem),
delete(List1, Elem, List2).

% add to bias.pl
direction(f,(in,in)).
direction(nullptr, (out,)).
direction(empty, (out,)).
direction(value,(in,out)).
direction(pointer,(in,out)).
direction(my_delete, (in, in, out)).
direction(my_min_list, (in, in)).

The directions help Prolog as some arguments must be ground.

With these changes, I see the following output.

% BEST PROG 187:
f(A,B):-empty(B),nullptr(A).
f(A,B):-value(A,C),pointer(A,E),my_delete(B,C,D),my_min_list(B,C),f(E,D).
% Precision:1.00, Recall:1.00, TP:5, FN:0, TN:6, FP:0

Total programs: 187
Generate:
Called: 195 times Total: 0.28 Mean: 0.001 Max: 0.019
Test:
Called: 187 times Total: 0.26 Mean: 0.001 Max: 0.027
Build:
Called: 186 times Total: 0.05 Mean: 0.000 Max: 0.001
Ground:
Called: 186 times Total: 0.03 Mean: 0.000 Max: 0.003
Add:
Called: 186 times Total: 0.06 Mean: 0.000 Max: 0.001
Total operation time: 0.68s
Total execution time: 0.73s

You will likely run into more non-termination issues. It is something I am looking into, but it is a fundamental problem when dealing with Turing-complete languages.

[andrewcropper]

Also, delete/3 is deprecated:

https://www.swi-prolog.org/pldoc/doc_for?object=delete/3

select/3 is the standard relation:

https://www.swi-prolog.org/pldoc/doc_for?object=select/3

[yangdinglou]

Thank you. I will try to think about the optimization. Please close the issue if you want to. (I am not sure whether it should be.)

[yangdinglou]

@andrewcropper Hi Andrew, sorry to interrupt again. I found some examples which implied that the reason seemed to not be non termination, if I didn't wrongly understand. The evidence was that, I set the eval_timeout to 10s by --eval-timeout=10, and the system didn't always (but sometimes) learn the optimal solution within less than 6s. Do I wrongly understand some setting?

[yangdinglou]

Maybe there is a little ambiguity. When learned the optimal solution, the overall time is less than 2s. If not optimal solution is learned, the overall time is less than 6s.

[andrewcropper]

HI, no problem about the questions. Thank you for asking them!

Is the example that fails one of the scenarios above? If so, might you be able to attach the code for me to check what is going on?

[yangdinglou]

%% expected predicate:
%% f(A,B):-nullptr(A),empty(B).
%% f(A,B):-my_min_list(B,D),value(A,D),q(E,C),pointer(A,E),my_delete(B,D,C).
%% bias
max_vars(5).
max_body(5).
max_clauses(2).

head_pred(f,2).
body_pred(nullptr,1).
body_pred(my_delete,3).
body_pred(my_min_list,2).
body_pred(zero,1).
body_pred(empty,1).
body_pred(value,2).
body_pred(pointer,2).
body_pred(q,2).

type(f,(element,list)).
type(nullptr,(element,)).
type(my_delete,(list,integer,list)).
type(my_min_list,(list,integer)).
type(empty,(list,)).
type(zero,(integer,)).
type(one,(integer,)).
type(value,(element,integer)).
type(pointer,(element,element)).
type(q,(element,list)).

:-
	body_literal(0,q,_,_).
:-
    not clause(1).
:-
	#count{A,Vars : body_literal(1,pointer,A,Vars)} = 0.

%% exs.pl
pos(f(p1,[4,3,1,2])).
pos(f(p2,[4,3,2])).
pos(f(p3,[4,3])).
pos(f(p4,[4])).
pos(f(null,[])).
pos(f(n2,[4,3,1])).
pos(f(n3,[4,3])).
pos(f(n4,[4])).

neg(f(p1,[4,1,2])).
neg(f(p1,[4,3,5,2])).
neg(f(p1,[4,3,2])).
neg(f(p2,[4,3,2,7])).
neg(f(p3,[3,4,5])).
neg(f(p4,[])).
neg(f(n1,[4,3,1,2])).
neg(f(n2,[4,3,2])).

%% bk
use_module(library(lists)).
empty([]).
zero(0).
one(1).

value(p1,1).
value(p2,2).
value(p3,3).
value(p4,4).
value(n1,2).
value(n2,1).
value(n3,3).
value(n4,4).

pointer(p1, p2).
pointer(p2, p3).
pointer(p3, p4).
pointer(p4, null).
pointer(n1, n2).
pointer(n2, n3).
pointer(n3, n4).
pointer(n4, null).
nullptr(null).

q(p2,[4,3,2]).
q(p3,[4,3]).
q(p4,[4]).
q(null,[]).
q(n2,[4,3,1]).
q(n3,[4,3]).
q(n4,[4]).

my_min_list(List, Num):-
    ground(List), min_list(List, Num).
my_delete(List1, Elem, List2):-
    ground(List1),
    ground(Elem),
    select(Elem, List1, List2).

The non optimal solution is (with --eval-timeout=10 flag)

...
NO MORE SOLUTIONS

% BEST PROG 929:
f(A,B):-nullptr(A),empty(B).
f(A,B):-pointer(C,D),q(D,B),pointer(C,A).
% Precision:1.00, Recall:0.88, TP:7, FN:1, TN:8, FP:0

[andrewcropper]

This issue was tricky to identify. The problem is caused by Prolog needing ground arguments for certain relations. Popper was generating two versions of the solution: %% Program A: f(A,B):-nullptr(A),empty(B). f(A,B):-my_delete(B,D,C),pointer(A,E),q(E,C),my_min_list(B,D),value(A,D). % Precision:1.00, Recall:0.12, TP:1, FN:7, TN:8, FP:0 %% Program B: f(A,B):-nullptr(A),empty(B). f(A,B):-value(A,D),my_min_list(B,D),q(E,C),pointer(A,E),my_delete(B,D,C). % Precision:1.00, Recall:1.00, TP:8, FN:0, TN:8, FP:0 Although they both look correct, program A fails on some positive examples. The reason that program A fails is that Prolog evaluates rules from left to right. When Prolog calls my_delete(B,D,C), the D argument has no value and so that relation fails. You can overcome this issue by giving Popper directions, which allows it to deduce the correct order of literals in a rule: direction(f,(in,in)). direction(nullptr,(out,)). direction(my_delete,(in,in,out)). direction(my_min_list,(in,out)). direction(empty,(out,)). direction(zero,(out,)). direction(one,(out,)). direction(value,(out,out)). direction(pointer,(out,out)). direction(q,(out,out)). An `out` argument means it need not be ground (i.e. you can get the value out of a relation). By contrast, an `in` argument must be ground and must be `given` to the relation. With these directions, Popper learns the correct solution for this problem in ~2s. Can you check whether that helps?

…

On 19 Feb 2022, at 15:08, yangdinglou ***@***.***> wrote: %% expected predicate: %% f(A,B):-nullptr(A),empty(B). %% f(A,B):-my_min_list(B,D),value(A,D),q(E,C),pointer(A,E),my_delete(B,D,C). %% bias max_vars(5). max_body(5). max_clauses(2). head_pred(f,2). body_pred(nullptr,1). body_pred(my_delete,3). body_pred(my_min_list,2). body_pred(zero,1). body_pred(empty,1). body_pred(value,2). body_pred(pointer,2). body_pred(q,2). type(f,(element,list)). type(nullptr,(element,)). type(my_delete,(list,integer,list)). type(my_min_list,(list,integer)). type(empty,(list,)). type(zero,(integer,)). type(one,(integer,)). type(value,(element,integer)). type(pointer,(element,element)). type(q,(element,list)). :- body_literal(0,q,_,_). :- not clause(1). :- #count{A,Vars : body_literal(1,pointer,A,Vars)} = 0. %% exs.pl pos(f(p1,[4,3,1,2])). pos(f(p2,[4,3,2])). pos(f(p3,[4,3])). pos(f(p4,[4])). pos(f(null,[])). pos(f(n2,[4,3,1])). pos(f(n3,[4,3])). pos(f(n4,[4])). neg(f(p1,[4,1,2])). neg(f(p1,[4,3,5,2])). neg(f(p1,[4,3,2])). neg(f(p2,[4,3,2,7])). neg(f(p3,[3,4,5])). neg(f(p4,[])). neg(f(n1,[4,3,1,2])). neg(f(n2,[4,3,2])). %% bk use_module(library(lists)). empty([]). zero(0). one(1). value(p1,1). value(p2,2). value(p3,3). value(p4,4). value(n1,2). value(n2,1). value(n3,3). value(n4,4). pointer(p1, p2). pointer(p2, p3). pointer(p3, p4). pointer(p4, null). pointer(n1, n2). pointer(n2, n3). pointer(n3, n4). pointer(n4, null). nullptr(null). q(p2,[4,3,2]). q(p3,[4,3]). q(p4,[4]). q(null,[]). q(n2,[4,3,1]). q(n3,[4,3]). q(n4,[4]). my_min_list(List, Num):- ground(List), min_list(List, Num). my_delete(List1, Elem, List2):- ground(List1), ground(Elem), select(Elem, List1, List2). The non optimal solution is (with --eval-timeout=10 flag) ... NO MORE SOLUTIONS % BEST PROG 929: f(A,B):-nullptr(A),empty(B). f(A,B):-pointer(C,D),q(D,B),pointer(C,A). % Precision:1.00, Recall:0.88, TP:7, FN:1, TN:8, FP:0 — Reply to this email directly, view it on GitHub, or unsubscribe. Triage notifications on the go with GitHub Mobile for iOS or Android. You are receiving this because you modified the open/close state.

[yangdinglou]

Thanks, I have understood the issue.