6 ms·

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

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).
- Veedrac 6y ago
  > Aren't you shifting the goalposts a bit? No, I don't think so. My original comment was “I have looked at the program synthesis literature before and it really does not seem very advanced to me. The General Program Synthesis Benchmark Suite lists unsolved benchmarks like “Given three strings n1, n2, and n3, return true if length(n1) < length(n2) < length(n3), and false otherwise”, and that's with 100 examples. So, probably less practically useful than GPT-3, which wasn't even trained on the task.” I only asked about ILP to clarify your defense. I maintain, after seeing the ILP you were referring to, that the defence doesn't meaningfully affect my point, that the problem you claim to be solving is not the one I was talking about, and not meaningfully more interesting. > 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. I'm not looking to solve arbitrary programs. I'm looking, at least at this first hurdle, to solve a few largely trivial ones. If you saw 100 examples, you would be able to solve this problem, or at least get very close. Therefore this sort of theoretical argument cannot hold. > 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). I assume you've seen GPT-f? (https://arxiv.org/abs/2009.03393 https://arxiv.org/abs/2009.03393) Section 4.7.1 shows this is entirely feasible for neural networks, though the technique is very different. Though I prefer even more the elegance (and general absurdity) of learning the bias by pretraining on WebMath (GitHub, arXiv Math, Math StackExchange). > The bottom line is that learning arbitrary programs from examples is a hard problem I agree it's hard, but in my mind this sentence completes to “and therefore our only hope is to use most powerful tool we have available, neural networks.”
  - YeGoblynQueenne 6y ago
    >> I only asked about ILP to clarify your defense. I maintain, after seeing the ILP you were referring to, that the defence doesn't meaningfully affect my point, that the problem you claim to be solving is not the one I was talking about, and not meaningfully more interesting. I must admit I'm very confused by this. I really thought you were talking about the problem of ordering three strings by length. What problem where you talking about, if not that?

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).

Veedrac 6y ago
> Aren't you shifting the goalposts a bit? No, I don't think so. My original comment was “I have looked at the program synthesis literature before and it really does not seem very advanced to me. The General Program Synthesis Benchmark Suite lists unsolved benchmarks like “Given three strings n1, n2, and n3, return true if length(n1) < length(n2) < length(n3), and false otherwise”, and that's with 100 examples. So, probably less practically useful than GPT-3, which wasn't even trained on the task.” I only asked about ILP to clarify your defense. I maintain, after seeing the ILP you were referring to, that the defence doesn't meaningfully affect my point, that the problem you claim to be solving is not the one I was talking about, and not meaningfully more interesting. > 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. I'm not looking to solve arbitrary programs. I'm looking, at least at this first hurdle, to solve a few largely trivial ones. If you saw 100 examples, you would be able to solve this problem, or at least get very close. Therefore this sort of theoretical argument cannot hold. > 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). I assume you've seen GPT-f? (https://arxiv.org/abs/2009.03393 https://arxiv.org/abs/2009.03393) Section 4.7.1 shows this is entirely feasible for neural networks, though the technique is very different. Though I prefer even more the elegance (and general absurdity) of learning the bias by pretraining on WebMath (GitHub, arXiv Math, Math StackExchange). > The bottom line is that learning arbitrary programs from examples is a hard problem I agree it's hard, but in my mind this sentence completes to “and therefore our only hope is to use most powerful tool we have available, neural networks.”
- YeGoblynQueenne 6y ago
  >> I only asked about ILP to clarify your defense. I maintain, after seeing the ILP you were referring to, that the defence doesn't meaningfully affect my point, that the problem you claim to be solving is not the one I was talking about, and not meaningfully more interesting. I must admit I'm very confused by this. I really thought you were talking about the problem of ordering three strings by length. What problem where you talking about, if not that?