Wrong pruning during the search?
Closed this issue · 9 comments
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
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.
Also, delete/3 is deprecated:
https://www.swi-prolog.org/pldoc/doc_for?object=delete/3
select/3 is the standard relation:
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.)
@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?
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.
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?
%% 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
Thanks, I have understood the issue.