5 ms·

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 <. I checked by running w

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 <. 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.
- Veedrac 6y ago
  I don't think you've understood my point. At every step of the way you've put in more effort than writing the program and specifying the examples. Clearly this is not trivial. If you're actually inferring programs and not just doing a sort of guided line-by-line generalization of a program you had already written, the only things you would need would be Positive examples ----------------- ordered([a],[b,c],[d,e,f]). Negative examples ----------------- ordered([a],[b],[c]). ordered([a,b,c],[a,b],[c]). I was never in doubt that it was possible to write a different program which would ‘solve’ <=. My criticism was that “it's a different problem”.
  - YeGoblynQueenne 6y ago
    Aren't you shifting the goalposts a bit? First you ask me how I'd solve this problem with ILP: “Given three strings n1, n2, and n3, return true if length(n1) < length(n2) < length(n3), and false otherwise” (a) I say this is a trivial problem to solve with ILP and I show you a, well, trivial solution and you complain that it's - trivial. Then I show you a more elaborate version that learns sub-programs on the way to the full solution and you say that a) it doesn't solve a different problem, with ≤ instead of < and b) that it's not trivial anymore. And now you're saying you want a solution that learns from examples only. You would have saved us both a lot of time had you clarified your expectations up front. No matter. There isn't anything that can do what you ask. Or rather, there are many approaches that could learn (a) just from examples, with a brute-force search. But there is no approach that could learn arbitrary programs only from examples. The reason is that the space of all programs that can be computed by a Universal Turing Machine ("arbitrary") is infinite and any learner trying to find one of them blindly, without some kind of hint to guide it, would be lost for ever inside it. Most machine learning approaches that learn programs from examples adopt some sort of inductive bias to guide a search for a program that satisfies some set of goodness criteria, including neural approaches [1]. In ILP, inductive bias consists primarily of BK and language bias (like the metarules in Louise). ILP has a certain advantage in this, in that the languages of examples, bias and hypotheses are the same (some first order logic language, like Prolog or ASP) and so ILP systems can learn their own bias, like Louise can learn its own BK and metarules. By way of comparison, neural nets, with their hand-crafted architectures, minutely fine-tuned to specific domains or even particular datasets, cannot do that (e.g. a trained model can't be used as a feature to another neural net, in the way that ILP hypotheses can be used as BK). Of course you need to start somewhere, from obvious primitives like head/2, tail/2, s/2 and p/2 that I used above. But I digress. The bottom line is that learning arbitrary programs from examples is a hard problem for any machine learning approach [2]. Classification is a piece of cake, by comparison. And that is why there has been so little progress in this problem even after decades of research [3]. The take home message of course is that neural nets are not the end of the line in AI research and it would be disastrous for the progress of the field to allow research into neural nets to eclipse every other approach. If this happens it will all have to be discovered again, from scratch. And in another 70 years. ____________________ [1] e.g. see Learning explanatory rules from noisy data https://arxiv.org/abs/1711.04574 https://arxiv.org/abs/1711.04574 by DeepMind, which also uses metarules. [2] See for example: Deep Learning for Program Synthesis Synthesizing a program from a specification has been a long-standing challenge. (...) This problem is extremely challenging, and the complexity of the synthesized programs by existing approaches is still limited. https://sunblaze-ucb.github.io/program-synthesis/index.html https://sunblaze-ucb.github.io/program-synthesis/index.html [3] This is where I'd normally say that there have been recent breakthroughs that promise to overturn years of slow progress, but that's a story for another time (and another venue most like).

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.

Veedrac 6y ago
I don't think you've understood my point. At every step of the way you've put in more effort than writing the program and specifying the examples. Clearly this is not trivial. If you're actually inferring programs and not just doing a sort of guided line-by-line generalization of a program you had already written, the only things you would need would be Positive examples ----------------- ordered([a],[b,c],[d,e,f]). Negative examples ----------------- ordered([a],[b],[c]). ordered([a,b,c],[a,b],[c]). I was never in doubt that it was possible to write a different program which would ‘solve’ <=. My criticism was that “it's a different problem”.
- YeGoblynQueenne 6y ago
  Aren't you shifting the goalposts a bit? First you ask me how I'd solve this problem with ILP: “Given three strings n1, n2, and n3, return true if length(n1) < length(n2) < length(n3), and false otherwise” (a) I say this is a trivial problem to solve with ILP and I show you a, well, trivial solution and you complain that it's - trivial. Then I show you a more elaborate version that learns sub-programs on the way to the full solution and you say that a) it doesn't solve a different problem, with ≤ instead of < and b) that it's not trivial anymore. And now you're saying you want a solution that learns from examples only. You would have saved us both a lot of time had you clarified your expectations up front. No matter. There isn't anything that can do what you ask. Or rather, there are many approaches that could learn (a) just from examples, with a brute-force search. But there is no approach that could learn arbitrary programs only from examples. The reason is that the space of all programs that can be computed by a Universal Turing Machine ("arbitrary") is infinite and any learner trying to find one of them blindly, without some kind of hint to guide it, would be lost for ever inside it. Most machine learning approaches that learn programs from examples adopt some sort of inductive bias to guide a search for a program that satisfies some set of goodness criteria, including neural approaches [1]. In ILP, inductive bias consists primarily of BK and language bias (like the metarules in Louise). ILP has a certain advantage in this, in that the languages of examples, bias and hypotheses are the same (some first order logic language, like Prolog or ASP) and so ILP systems can learn their own bias, like Louise can learn its own BK and metarules. By way of comparison, neural nets, with their hand-crafted architectures, minutely fine-tuned to specific domains or even particular datasets, cannot do that (e.g. a trained model can't be used as a feature to another neural net, in the way that ILP hypotheses can be used as BK). Of course you need to start somewhere, from obvious primitives like head/2, tail/2, s/2 and p/2 that I used above. But I digress. The bottom line is that learning arbitrary programs from examples is a hard problem for any machine learning approach [2]. Classification is a piece of cake, by comparison. And that is why there has been so little progress in this problem even after decades of research [3]. The take home message of course is that neural nets are not the end of the line in AI research and it would be disastrous for the progress of the field to allow research into neural nets to eclipse every other approach. If this happens it will all have to be discovered again, from scratch. And in another 70 years. ____________________ [1] e.g. see Learning explanatory rules from noisy data https://arxiv.org/abs/1711.04574 https://arxiv.org/abs/1711.04574 by DeepMind, which also uses metarules. [2] See for example: Deep Learning for Program Synthesis Synthesizing a program from a specification has been a long-standing challenge. (...) This problem is extremely challenging, and the complexity of the synthesized programs by existing approaches is still limited. https://sunblaze-ucb.github.io/program-synthesis/index.html https://sunblaze-ucb.github.io/program-synthesis/index.html [3] This is where I'd normally say that there have been recent breakthroughs that promise to overturn years of slow progress, but that's a story for another time (and another venue most like).