3 ms·
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) <
by 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?