7 ms·
Apologies for splitting the thread, but I thought it'd be easier to read this way. This comment addresses your concerns about me writing the program I wanted L
by YeGoblynQueenne 6y ago
Apologies for splitting the thread, but I thought it'd be easier to read this
way.
This comment addresses your concerns about me writing the program I wanted
Louise to generate. I like to see background knowledge ("BK", e.g. shorter/2)
as a library of sub-programs from which the learner can select the ones
necessary to compose a target program. The example above is trivial because
I've defined a BK predicate that is necessary and sufficient to learn, so the
learner was indeed served the solution "on a plate".
However, as I said in my previous comment, Louise can learn its own background
knowledge. This can be done by predicate invention, or more simply, by
incrementally learning necessary sub-programs.
Below is a problem definition and learning session that first learns length/2
(renamed llength/2 to avoid name clashes with the built-in) and shorter/2 from
list and numeric function primitives, before using the learned predicates as
BK for ordered/2. Like I say in my previous comment, it's a little larger
than the previous one:
?- list_mil_problem([llength/2,shorter/2,ordered/3]).
Positive examples
-----------------
llength([],0).
llength([a],s(0)).
shorter([a],[b,c]).
shorter([1,2],[3,4,5]).
ordered([a],[b,c],[d,e,f]).
Negative examples
-----------------
:-ordered([a],[b],[c]).
:-ordered([a,b,c],[a,b],[c]).
Background knowledge
--------------------
tail/2:
tail([A|B],B).
p/2:
p(s(A),A).
s/2:
s(A,s(A)).
Metarules
---------
abduce metarule 'P(X,Y)'.
list_rec_func metarule 'P(x,y):- Q(x,z),R(y,u),P(z,u)'.
list_comp metarule 'P(x,y):- Q(x,z), R(y,u), S(z,u)'.
triadic_chain metarule 'P(x,z,y):- Q(x,z), R(z,y)'.
true.
?- time(learn_dynamic([llength/2,shorter/2,ordered/3])).
llength([],0).
llength(A,B):-tail(A,C),p(B,D),llength(C,D).
shorter(A,B):-llength(A,C),llength(B,D),s(C,D).
ordered(A,B,C):-shorter(A,B),shorter(B,C).
% 20,928 inferences, 0.000 CPU in 0.007 seconds (0% CPU, Infinite Lips)
true.
The BK for this problem consists of tail/2, similar to "car" in Lisp (i.e.
matches the head of a list) and the pair of p/2 and s/2, that act as
"dereferencers" to Peano number functions. These are bog-standard Prolog
programs and useful whenever a target program must manipulate a list, or
perform numerical reasoning. In other words, they're pretty much generic, like
a standard library of sorts.
I've added the full source of the experiment file for the learning task on
pastebin. It includes a few more detailed comments and a set of constraints to
clean up the learned hypothesis, mostly for aesthetic reasons:
https://pastebin.com/nPYFKKpx https://pastebin.com/nPYFKKpx
Of course this is still a toy problem and we know the solution. But I hope it
demonstrates the principle. On the other hand, you'd still not be able to
solve this with alternative approaches, e.g. I see that the benchmark suite
you pointed to is used for genetic programming. I'm also not aware of neural
approaches that build programs incrementally, from a couple of examples of
each sub-program.
That is to say, this is a toy problem for ILP. For other approaches it's
unsolvable.
- Veedrac 6y agoYou've just kicked the can down the road; what you've given there cannot solve, for instance, the same problem but with <= instead of <. I checked by running with positive_example(ordered/3,ordered(S1,S2,S3)):- member([S1,S2,S3],[[[a],[b,c],[d,e,f]] ,[[a,b],[c,d],[e,f,g]] ,[[a],[c],[e,f,g,h,i]] ] ). negative_example(ordered/3,ordered(S1,S2,S3)):- member([S1,S2,S3],[[[a],[],[c]] ,[[a,b,c],[a,b],[c]] ] ). and just got ordered([a,b],[c,d],[e,f,g]). ordered([a],[c],[e,f,g,h,i]). ordered(A,B,C):-shorter(A,B),shorter(B,C). Heck, I don't think it even got `shorter` right; it gave shorter(A,B):-llength(A,C),llength(B,D),s(C,D). which means len(A) + 1 == len(B), not len(A) < len(B), and AFAICT it can't learn len(A) < len(B), not because the program isn't expressible with the primitives you gave, but because it just doesn't reason that far. So again, it's only trivial because it isn't learning the program, it's learning to put fit the puzzle pieces of the program together, after you wrote the program and then chopped it up.
- YeGoblynQueenne 6y ago>> Heck, I don't think it even got `shorter` right; it gave shorter(A,B):-llength(A,C),llength(B,D),s(C,D). >> which means len(A) + 1 == len(B), not len(A) < len(B), and AFAICT it can't learn len(A) < len(B), not because the program isn't expressible with the primitives you gave, but because it just doesn't reason that far. Oops. Haha well spotted @^_^ This is correct for </2: ?- list_mil_problem([llength/2,shorter/2,ordered/3]). Positive examples ----------------- llength([],0). llength([a],s(0)). shorter([a],[b,c]). shorter([1,2],[3,4,5]). ordered([a],[b,c],[d,e,f]). Negative examples ----------------- :-ordered([a],[b],[c]). :-ordered([a,b,c],[a,b],[c]). Background knowledge -------------------- tail/2: tail([A|B],B). p/2: p(s(A),0):-ground_peano(A). p(s(A),A). p(s(A),s(B)):-ground_peano(A),p(A,B). s/2: s(0,s(A)):-ground_peano(A). s(A,s(A)). s(s(A),s(B)):-ground_peano(B),s(A,B). ground_peano/1: ground_peano(A):-ground(A),\+is_list(A). Metarules --------- abduce metarule 'P(X,Y)'. list_rec_func metarule 'P(x,y):- Q(x,z),R(y,u),P(z,u)'. list_comp metarule 'P(x,y):- Q(x,z), R(y,u), S(z,u)'. triadic_chain metarule 'P(x,z,y):- Q(x,z), R(z,y)'. true. ?- time(learn_dynamic([llength/2,shorter/2,ordered/3])). llength([],0). llength(A,B):-tail(A,C),p(B,D),llength(C,D). shorter(A,B):-llength(A,C),llength(B,D),s(C,D). ordered(A,B,C):-shorter(A,B),shorter(B,C). % 29,554 inferences, 0.000 CPU in 0.011 seconds (0% CPU, Infinite Lips) true. Paste that in a file and consult it to test it: ?- ordered:ordered([1],[1,2,3],[1,2,3,4,5,6,7,8]). true . Regarding reasoning "that far" Louise can learn the complete successor / predecessor relation (</2 and >/2) on its own and only from the primitives s(N,s(N)) and p(s(N), N): ?- list_mil_problem([s/2,p/2]). Positive examples ----------------- s(0,s(A)). s(0,s(0)). s(s(0),s(s(s(s(0))))). p(s(A),0). p(s(0),0). p(s(s(s(s(0)))),s(0)). Negative examples ----------------- [] Background knowledge -------------------- s_/2: s_(A,s(A)). p_/2: p_(s(A),A). Metarules --------- identity metarule 'P(x,y):- Q(x,y)'. chain metarule 'P(x,y):- Q(x,z), R(z,y)'. true. ?- learn(s/2). s(0,s(A)). s(A,B):-s_(A,B). s(A,B):-s_(A,C),s(C,B). true. ?- learn(p/2). p(s(A),0). p(A,B):-p_(A,B). p(A,B):-p_(A,C),p(C,B). true. However, in the ordered/3 problem I define p/2 and s/2 by hand so that I can put in ground_peano/1 to avoid infinite recursion when Louise tries to pass two lists to s/2 or p/2 (at that point, their termination conditions never obtain, so they keep recursing). You can chalk the potential for infinite recursion up as a limitation, you're very welcome- but there are techniques to avoid this and guarantee termination (Knuth-Bendix ordering of the Herbrand base, see ref [1]) which I haven't come round to implementing yet (because they are not necessary given a bit of common sense in defining BK, as above). On the other hand that's actually a feature, in the sense that earlier systems required more specific language bias than the metarules, that would avoid this kind of type-unsafety, but also demanded more expert knowledge from the user. In any case, there's outs. >> You've just kicked the can down the road; what you've given there cannot solve, for instance, the same problem but with <= instead of <. That's a different problem. Off we go: ?- list_mil_problem([llength/2,shorter/2,ordered_leq/3]). Positive examples ----------------- llength([],0). llength([a],s(0)). shorter([a],[b,c]). shorter([1,2],[3,4,5]). ordered_leq([a],[b],[d]). ordered_leq([a],[b,c],[d,e,f]). ordered_leq([a],[c],[e,f,g,h,i]). Negative examples ----------------- :-ordered([a,b,c],[a,b],[c]). Background knowledge -------------------- tail/2: tail([A|B],B). p/2: p(s(A),0):-ground_peano(A). p(s(A),A). p(s(A),s(B)):-ground_peano(A),p(A,B). s/2: s(0,s(A)):-ground_peano(A). s(A,s(A)). s(s(A),s(B)):-ground_peano(B),s(A,B). leq/2: leq(A,A):-ground_peano(A). leq(A,B):-s(A,B). ground_peano/1: ground_peano(A):-ground(A),\+is_list(A). Metarules --------- abduce metarule 'P(X,Y)'. list_rec_func metarule 'P(x,y):- Q(x,z),R(y,u),P(z,u)'. list_comp metarule 'P(x,y):- Q(x,z), R(y,u), S(z,u)'. triadic_chain metarule 'P(x,z,y):- Q(x,z), R(z,y)'. true. ?- learn_dynamic([llength/2,shorter/2,ordered_leq/3]). llength([],0). llength(A,B):-tail(A,C),p(B,D),llength(C,D). shorter(A,B):-llength(A,C),llength(B,D),leq(C,D). ordered_leq(A,B,C):-shorter(A,B),shorter(B,C). true. Or I could have added an eq(X,X) predicate instead of leq/2. Note that I didn't declare leq/2 as BK for shorter/2 this time around: ?- background_knowledge(shorter/2, BK). BK = [s/2]. I didn't even change its examples: ?- positive_example(shorter/2, E). E = shorter([a], [b, c]) ; E = shorter([1, 2], [3, 4, 5]). It picked it up on its own, because it's the best way to define shorter/2 as a sub-program for ordered_leq/3. Aaaw. Isn't it smart? Pastebins for the source files: ordered/3 and ordered_leq/3: https://pastebin.com/6NH0VTKK https://pastebin.com/6NH0VTKK s/2 and p/2: https://pastebin.com/0d0YWMfV https://pastebin.com/0d0YWMfV You'll let me know if I've done something else dumb, yes? :) ________________________ [1] https://www.doc.ic.ac.uk/~atn/papers/metagol_mlj.pdf https://www.doc.ic.ac.uk/~atn/papers/metagol_mlj.pdf See section 4.1 "Ordering the Herbrand Base". Edit: You know, it just struck me but when you say that only ML has ever worked out of all AI, that probably means you don't recognise Louise as a machine learning system... because it's not deep learning. That's just another instance of the strange synechdoche I was talking about in my first comment in this thread, where to some peoples' knowledge only deep learning is machine learning because that's all some people know of machine learning. A bit like thinking that chicken is the only thing one can eat because all one has ever had is chicken.