6 ms·

> "The number of steps the program needs to take" is not relevant to the calculation: we are trying to calculate the complexity of constructing the program by b

> "The number of steps the program needs to take" is not relevant to the calculation: we are trying to calculate the complexity of constructing the program by blindly combining a set of building blocks (BK predicates and metarules)- not the complexity of executing the program. I meant in the sense of denotational semantics, so looping (or rather, finding a fixed point of a loop) is one ‘step’. > Have you tried doing that? I suggest you do- if only to get a feel for the true difficulty of the problem. How exactly would you suggest? By the nature of my criticism, I can't construct the Louise BK blind. If anything you agree here; you say there are only 1,280 clauses it could construct, so I only need discriminatory power of 1-in-13 to have a >1% chance of getting the answer right. > Regarding learning "only from examples" as I understand you to mean it, there is some literature on that, of the kind you say is not "AI" (i.e. it predates 2012's deep learning boom). Yes, and as usual for GOFAI it doesn't solve the problem.

YeGoblynQueenne 6y ago
>> I meant in the sense of denotational semantics, so looping (or rather, finding a fixed point of a loop) is one ‘step’. I understand, but we don't need to take that term into account. We're only interested in the cost of a blind combinatorial search. Even if we added that term in, we'd just get a higher complexity. >> How exactly would you suggest? By the nature of my criticism, I can't construct the Louise BK blind. I mean, try to define some BK and generate combinations of it until you solve the problem. You say that I made the problem easy because I defined some BK by hand. I suggested you try doing that to see whether the problem is as easy as you think. >> If anything you agree here; you say there are only 1,280 clauses it could construct, so I only need discriminatory power of 1-in-13 to have a >1% chance of getting the answer right. There are only 1280 clauses, but there are about 2 billion programs of size n = 3 that can be constructed with those clauses, one of which is the target program. The challenge is to find the target program in that 2 billion. The advantage of Louise is that it only needs to look at the 1280 clauses, not the 2 billion programs. The trick is to find how to do that. It's like the difference between sorting a list with bubblesort and quicksort. Quicksort has to do a lot less work, but the trick is figuring out quicksort. >> Yes, and as usual for GOFAI it doesn't solve the problem. Deep learning doesn't "solve" that problem either- the point is that you can't learn only from examples.
- Veedrac 6y ago
  > I mean, try to define some BK and generate combinations of it until you solve the problem. You say that I made the problem easy because I defined some BK by hand. I suggested you try doing that to see whether the problem is as easy as you think. I genuinely don't understand what you expect me to do here. How can I possibly define BK for a problem I have zero information about beyond the type signature? > There are only 1280 clauses, but there are about 2 billion programs Doesn't matter, since the programmer gives that information. As you admit, Louise cannot check for arbitrary programs. > Deep learning doesn't "solve" that problem either- the point is that you can't learn only from examples. That's literally what DL is. You can also learn programs from examples. People do it all the time. What else would you call the Abstraction and Reasoning Challenge, https://www.kaggle.com/boliu0/visualizing-all-task-pairs-with-gridlines https://www.kaggle.com/boliu0/visualizing-all-task-pairs-wit...?
  - YeGoblynQueenne 6y ago
    Deep neural nets do not learn only from examples! They encode strong inductive biases in their carefully hand-engineered and hand-tuned architectures, hence for example CNNs are used for image recognition and LSTMs for sequence learning etc. Without these biases deep neural nets would not be able to generalise as well as they do (in the sense of local generalisation but not global generalisation as meant by François Chollet [1]). The biggest advances in deep neural nets have come from the discovery and use of good inductive biases: training with gradient descent, backpropagation, more hidden layers, the "constant error carousel", convolutional layers, ReLu over sigmoid, attention, etc, etc. One could say that deep neural nets are all about good inductive bias. It's interesting that you bring up the ARC dataset. The paper that introduced it (also from Chollet) [2] makes a strong claim about the necessity of "knowledge priors" for a system to be considered intelligent. These are described at length in section III.1.2 "Core knowledge priors" and are exactly a set of strong inductive biases that the author of the paper considers necessary for a machine learning system to solve the ARC tasks and that consist of such problem-specific biases as object cohesion, object persistence, object influence via contact, etc. It is exactly such "knowledge priors" that are encoded as background knowledge in ILP systems. Indeed, in the ARC challenge on Kaggle, the best-performing systems (i.e. the ones that solved the most tasks) were crude approximations of the ILP approach: a library of hand-crafted functions and a brute-force search procedure to combine them. I note also that attempts to use deep learning to solve the challenge didn't go anywhere. Humans also have strong inductive biases that help us solve such problems. But I'm not the best placed to discuss all this - I'm not a cognitive scientist. In the end, what you are asking for is magick: a learner that learns only from examples, without any preconceived notions about how to learn from those examples, or what to learn from them. There is no such machine learning system. >> Doesn't matter, since the programmer gives that information. As you admit, Louise cannot check for arbitrary programs. I don't understand what you mean "check for arbitrary programs". I can give Louise zero BK and metarules and ask it to generate all Prolog programs, say. Prolog is a Turing complete language so that would give me the set of all programs computable by a Universal Turing Machine (it would take a while). But what would that achieve? At this point I'm not sure I understand what your remaining objections are against the approach I showed you. For the purpose of learning arbitrary programs it works better than anything else. Of course it's not magick. Perhaps you should take my suggestion to think about the problem a bit more carefully, if you're really intersted in it. Or are you? I mean, if you consider AI solved, e.g. by GPT-3, then I can see how you wouldn't be interested in thinking any further about the issue. _________________ [1] https://blog.keras.io/the-limitations-of-deep-learning.html https://blog.keras.io/the-limitations-of-deep-learning.html [2] https://arxiv.org/abs/1911.01547 https://arxiv.org/abs/1911.01547 P.S. To clarify, I'm keeping this discussion up for your sake, albeit eagerly. You have expressed some strongly held, but incorrect opinions that it seems to me you have acquired by consulting inexpert sources, probably because you have a day job that has nothing to do with AI and doesn't leave you enough time to study the matter properly. My day job is to study AI and I feel that such a privilege is only justified if I spend time and effort to help others improve their knowledge on the subject. I'm guessing that on your part, you're more interested in "winning" the conversation, but please try to gain something from our interaction, otherwise all the time we both spent at it would be to waste. When this is over, try to dig out and read some authoritative sources. I would advise you on which ones - but you'd probably resist my recommendation anyway, so you're on your own there.

YeGoblynQueenne 6y ago

>> I meant in the sense of denotational semantics, so looping (or rather, finding a fixed point of a loop) is one ‘step’. I understand, but we don't need to take that term into account. We're only interested in the cost of a blind combinatorial search. Even if we added that term in, we'd just get a higher complexity. >> How exactly would you suggest? By the nature of my criticism, I can't construct the Louise BK blind. I mean, try to define some BK and generate combinations of it until you solve the problem. You say that I made the problem easy because I defined some BK by hand. I suggested you try doing that to see whether the problem is as easy as you think. >> If anything you agree here; you say there are only 1,280 clauses it could construct, so I only need discriminatory power of 1-in-13 to have a >1% chance of getting the answer right. There are only 1280 clauses, but there are about 2 billion programs of size n = 3 that can be constructed with those clauses, one of which is the target program. The challenge is to find the target program in that 2 billion. The advantage of Louise is that it only needs to look at the 1280 clauses, not the 2 billion programs. The trick is to find how to do that. It's like the difference between sorting a list with bubblesort and quicksort. Quicksort has to do a lot less work, but the trick is figuring out quicksort. >> Yes, and as usual for GOFAI it doesn't solve the problem. Deep learning doesn't "solve" that problem either- the point is that you can't learn only from examples.

Veedrac 6y ago
> I mean, try to define some BK and generate combinations of it until you solve the problem. You say that I made the problem easy because I defined some BK by hand. I suggested you try doing that to see whether the problem is as easy as you think. I genuinely don't understand what you expect me to do here. How can I possibly define BK for a problem I have zero information about beyond the type signature? > There are only 1280 clauses, but there are about 2 billion programs Doesn't matter, since the programmer gives that information. As you admit, Louise cannot check for arbitrary programs. > Deep learning doesn't "solve" that problem either- the point is that you can't learn only from examples. That's literally what DL is. You can also learn programs from examples. People do it all the time. What else would you call the Abstraction and Reasoning Challenge, https://www.kaggle.com/boliu0/visualizing-all-task-pairs-with-gridlines https://www.kaggle.com/boliu0/visualizing-all-task-pairs-wit...?
- YeGoblynQueenne 6y ago
  Deep neural nets do not learn only from examples! They encode strong inductive biases in their carefully hand-engineered and hand-tuned architectures, hence for example CNNs are used for image recognition and LSTMs for sequence learning etc. Without these biases deep neural nets would not be able to generalise as well as they do (in the sense of local generalisation but not global generalisation as meant by François Chollet [1]). The biggest advances in deep neural nets have come from the discovery and use of good inductive biases: training with gradient descent, backpropagation, more hidden layers, the "constant error carousel", convolutional layers, ReLu over sigmoid, attention, etc, etc. One could say that deep neural nets are all about good inductive bias. It's interesting that you bring up the ARC dataset. The paper that introduced it (also from Chollet) [2] makes a strong claim about the necessity of "knowledge priors" for a system to be considered intelligent. These are described at length in section III.1.2 "Core knowledge priors" and are exactly a set of strong inductive biases that the author of the paper considers necessary for a machine learning system to solve the ARC tasks and that consist of such problem-specific biases as object cohesion, object persistence, object influence via contact, etc. It is exactly such "knowledge priors" that are encoded as background knowledge in ILP systems. Indeed, in the ARC challenge on Kaggle, the best-performing systems (i.e. the ones that solved the most tasks) were crude approximations of the ILP approach: a library of hand-crafted functions and a brute-force search procedure to combine them. I note also that attempts to use deep learning to solve the challenge didn't go anywhere. Humans also have strong inductive biases that help us solve such problems. But I'm not the best placed to discuss all this - I'm not a cognitive scientist. In the end, what you are asking for is magick: a learner that learns only from examples, without any preconceived notions about how to learn from those examples, or what to learn from them. There is no such machine learning system. >> Doesn't matter, since the programmer gives that information. As you admit, Louise cannot check for arbitrary programs. I don't understand what you mean "check for arbitrary programs". I can give Louise zero BK and metarules and ask it to generate all Prolog programs, say. Prolog is a Turing complete language so that would give me the set of all programs computable by a Universal Turing Machine (it would take a while). But what would that achieve? At this point I'm not sure I understand what your remaining objections are against the approach I showed you. For the purpose of learning arbitrary programs it works better than anything else. Of course it's not magick. Perhaps you should take my suggestion to think about the problem a bit more carefully, if you're really intersted in it. Or are you? I mean, if you consider AI solved, e.g. by GPT-3, then I can see how you wouldn't be interested in thinking any further about the issue. _________________ [1] https://blog.keras.io/the-limitations-of-deep-learning.html https://blog.keras.io/the-limitations-of-deep-learning.html [2] https://arxiv.org/abs/1911.01547 https://arxiv.org/abs/1911.01547 P.S. To clarify, I'm keeping this discussion up for your sake, albeit eagerly. You have expressed some strongly held, but incorrect opinions that it seems to me you have acquired by consulting inexpert sources, probably because you have a day job that has nothing to do with AI and doesn't leave you enough time to study the matter properly. My day job is to study AI and I feel that such a privilege is only justified if I spend time and effort to help others improve their knowledge on the subject. I'm guessing that on your part, you're more interested in "winning" the conversation, but please try to gain something from our interaction, otherwise all the time we both spent at it would be to waste. When this is over, try to dig out and read some authoritative sources. I would advise you on which ones - but you'd probably resist my recommendation anyway, so you're on your own there.