4 ms·

> You mean that I explicitly told Louise how to compose each program from its sub-programs. In truth, I did not. In the incremental learning problems for ordere

> You mean that I explicitly told Louise how to compose each program from its sub-programs. In truth, I did not. In the incremental learning problems for ordered/3 and ordered_leq/3 I gave Louise three learning targets and a few primitives from which to construct them. I specifically and very deliberately did not tell it to use each target to define another. It figured it out on its own. No, I get this, it's just not really more than a surface level pretense of choice. The hard thing about generating programs is that there are many possible programs; something like m^n, where ’m’ is the number of functions you have available to use (say, ~1000) and `n` is the number of steps the program needs to take (say, ~5 in this case), and there's another factor for where to put the parameters which here is low enough to be mostly negligible. It turns out even 1000^5 is really big, so this problem is hard if you don't do it smart. The ‘choice’ you are offering Louise is something like, idk, m=5, n=2. 5^2 is not big. You argue about the terminology, but whatever you call it, it's still exponentially less interesting than the problem first posed. All the interesting work has been done for it, by you. With the way you first laid out the question, there's a good chance (>1%) I could have gotten the answer mostly right (up to parameter order) without looking at the examples, just the background knowledge and the target type.

YeGoblynQueenne 6y ago
Many apologies for the delay in replying - I missed the "more" link at the bottom of the thread. And here I was, refreshing the page disappointed that no more criticism was forthcoming. >> The hard thing about generating programs is that there are many possible programs; something like m^n, where ’m’ is the number of functions you have available to use (say, ~1000) and `n` is the number of steps the program needs to take (say, ~5 in this case), and there's another factor for where to put the parameters which here is low enough to be mostly negligible. It turns out even 1000^5 is really big, so this problem is hard if you don't do it smart. Indeed, the complexity of the raw, combinatorial problem is the greatest hurdle in solving it in the general sense, however this time complexity is calculated somewhat differently than in your comment. Let me show you. First, in terms of ILP, the "number of functions you have available to use" is the number of predicate symbols defined in the BK, which I'll notate as p. "Where to put the parameters" is the number of body literals (similar to function calls) in each metarule, which I'll notate as k. I'll notate the number of metarules as m. "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. What is relevant is the size of the target theory, i.e. its number of clauses (program lines), because of course a larger program means a larger number of combinations of our building blocks. I'll notate the size of the target theory as n. Putting it all together, the time complexity of constructing a program of n clauses from p predicate symbols with m metarules with at most k body literals (of any arity) is O(pmᵏ⁺¹)ⁿ [1]. This is an exponential time complexity that corresponds to the size of the search space for programs that can be constructed from these components, i.e. that's the number of constructible programs. The time complexity of the problem is such that even n = 5 is sufficient to completely bog down a powerful modern computer. Louise can manage it because it doesn't conduct a search of that space, instead it only constructs a unique object in that space, the Top program, that can be constructed in polynomial time O(pmᵏ⁺¹) [2], i.e. the number of constructible clauses. Indeed, Louise is capable of learning large programs, of a few thousand clauses in a few minutes. In other words, the problem is manageable because of the advances encapsulated by Louise's learning procedure, Top Program Construction, not because the problem is trivial, as you portray it - and not because I'm leading Louise by the hand, as you suggest. Even if I was leading Louise by the hand, the combinatorial space of constructible programs would still grow exponentially. 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). To my knowledge, this was first discussed in the following: 1. Introduction This paper addresses a deep difficulty with the generalization problem as defined above: If consistency with the training instances is taken as the sole determiner of appropriate generalizations, then a program can never make the inductive leap necessary to classify instances beyond those it has observed. Only if the program has other sources of information, or biases for choosing one generalization over the other, can it non-arbitrarily classify instances beyond those in the training set. In this paper, we use the term bias to refer to any basis for choosing one generalization over another, other than strict consistency with the observed training instances. (...) 3. The Futility of Removing Biases (...) Although removing all biases from a generalization system may seem to be a desirable goal, in fact the result is nearly useless. An unbiased learning system’s ability to classify new instances is no better than if it simply stored all the training instances and performed a lookup when asked to classify a subsequent instance. Ref: *"The Need for Biases in Learning Generalizations", T.M. Mitchell, Rutgers Computer Science Department Technical Report CBM-TR-117, May, 1980. Reprinted in Readings in Machine Learning, J. Shavlik and T. Dietterich, eds., Morgan Kaufmann, 1990.* http://www.cs.nott.ac.uk/~pszbsl/G52HPA/articles/Mitchell:80a.pdf But this is another reason to read old AI papers: to avoid falling down the same holes people have already thoroughly explored in years gone by. >> With the way you first laid out the question, there's a good chance (>1%) I could have gotten the answer mostly right (up to parameter order) without looking at the examples, just the background knowledge and the target type. Have you tried doing that? I suggest you do- if only to get a feel for the true difficulty of the problem. ________________ [1] https://www.doc.ic.ac.uk/~shm/Papers/ECAI-546.pdf https://www.doc.ic.ac.uk/~shm/Papers/ECAI-546.pdf See section 2.1. Language classes, expressivity and complexity for a sketch proof. [2] Upcoming work, currently in review.
- deleted 6y ago
  [deleted]
- YeGoblynQueenne 6y ago
  I can't edit my post but I forgot to calculate the actual size of the hypothesis space for the multi-predicate problem for ordered/3. That is: p = 5 (tail/2, p/2, s/2 and llength/2 and shorter/2), m = 4, k = 3, n = 3 (the target theory is a clause for each target). The size of the hypothesis search space, i.e. the total number of programs of size n = 3 is (pm^(k+1))^n = 2,097,152,000. As I say above, Louise's TPC procedure avoids searching this space and so effectively ignores the exponential term, reducing the complexity of the problem to that of, in the worst case, enumerating (pm^(k+1)) = 1,280 clauses. In other words, the problem is easy for Louise, not because the problem itself is trivial, but because Louise's learning procedure, TPC, is efficient. For a further example, in the upcoming publication I mention above, Louise is shown to learn a 2,567 clause theory in under 220 seconds with perfect accuracy after training on 20% of all training examples. The hypothesis space for this problem (grid world navigation) is in the order of 2*10^4944 but Louise shrinks it to the problem of enumerating, at worst, a little over 81 million clauses.
- Veedrac 6y ago
  > "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.
  - 6y ago

YeGoblynQueenne 6y ago

Many apologies for the delay in replying - I missed the "more" link at the bottom of the thread. And here I was, refreshing the page disappointed that no more criticism was forthcoming. >> The hard thing about generating programs is that there are many possible programs; something like m^n, where ’m’ is the number of functions you have available to use (say, ~1000) and `n` is the number of steps the program needs to take (say, ~5 in this case), and there's another factor for where to put the parameters which here is low enough to be mostly negligible. It turns out even 1000^5 is really big, so this problem is hard if you don't do it smart. Indeed, the complexity of the raw, combinatorial problem is the greatest hurdle in solving it in the general sense, however this time complexity is calculated somewhat differently than in your comment. Let me show you. First, in terms of ILP, the "number of functions you have available to use" is the number of predicate symbols defined in the BK, which I'll notate as p. "Where to put the parameters" is the number of body literals (similar to function calls) in each metarule, which I'll notate as k. I'll notate the number of metarules as m. "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. What is relevant is the size of the target theory, i.e. its number of clauses (program lines), because of course a larger program means a larger number of combinations of our building blocks. I'll notate the size of the target theory as n. Putting it all together, the time complexity of constructing a program of n clauses from p predicate symbols with m metarules with at most k body literals (of any arity) is O(pmᵏ⁺¹)ⁿ [1]. This is an exponential time complexity that corresponds to the size of the search space for programs that can be constructed from these components, i.e. that's the number of constructible programs. The time complexity of the problem is such that even n = 5 is sufficient to completely bog down a powerful modern computer. Louise can manage it because it doesn't conduct a search of that space, instead it only constructs a unique object in that space, the Top program, that can be constructed in polynomial time O(pmᵏ⁺¹) [2], i.e. the number of constructible clauses. Indeed, Louise is capable of learning large programs, of a few thousand clauses in a few minutes. In other words, the problem is manageable because of the advances encapsulated by Louise's learning procedure, Top Program Construction, not because the problem is trivial, as you portray it - and not because I'm leading Louise by the hand, as you suggest. Even if I was leading Louise by the hand, the combinatorial space of constructible programs would still grow exponentially. 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). To my knowledge, this was first discussed in the following: 1. Introduction This paper addresses a deep difficulty with the generalization problem as defined above: If consistency with the training instances is taken as the sole determiner of appropriate generalizations, then a program can never make the inductive leap necessary to classify instances beyond those it has observed. Only if the program has other sources of information, or biases for choosing one generalization over the other, can it non-arbitrarily classify instances beyond those in the training set. In this paper, we use the term bias to refer to any basis for choosing one generalization over another, other than strict consistency with the observed training instances. (...) 3. The Futility of Removing Biases (...) Although removing all biases from a generalization system may seem to be a desirable goal, in fact the result is nearly useless. An unbiased learning system’s ability to classify new instances is no better than if it simply stored all the training instances and performed a lookup when asked to classify a subsequent instance. Ref: *"The Need for Biases in Learning Generalizations", T.M. Mitchell, Rutgers Computer Science Department Technical Report CBM-TR-117, May, 1980. Reprinted in Readings in Machine Learning, J. Shavlik and T. Dietterich, eds., Morgan Kaufmann, 1990.* http://www.cs.nott.ac.uk/~pszbsl/G52HPA/articles/Mitchell:80a.pdf But this is another reason to read old AI papers: to avoid falling down the same holes people have already thoroughly explored in years gone by. >> With the way you first laid out the question, there's a good chance (>1%) I could have gotten the answer mostly right (up to parameter order) without looking at the examples, just the background knowledge and the target type. Have you tried doing that? I suggest you do- if only to get a feel for the true difficulty of the problem. ________________ [1] https://www.doc.ic.ac.uk/~shm/Papers/ECAI-546.pdf https://www.doc.ic.ac.uk/~shm/Papers/ECAI-546.pdf See section 2.1. Language classes, expressivity and complexity for a sketch proof. [2] Upcoming work, currently in review.

deleted 6y ago
[deleted]
YeGoblynQueenne 6y ago
I can't edit my post but I forgot to calculate the actual size of the hypothesis space for the multi-predicate problem for ordered/3. That is: p = 5 (tail/2, p/2, s/2 and llength/2 and shorter/2), m = 4, k = 3, n = 3 (the target theory is a clause for each target). The size of the hypothesis search space, i.e. the total number of programs of size n = 3 is (pm^(k+1))^n = 2,097,152,000. As I say above, Louise's TPC procedure avoids searching this space and so effectively ignores the exponential term, reducing the complexity of the problem to that of, in the worst case, enumerating (pm^(k+1)) = 1,280 clauses. In other words, the problem is easy for Louise, not because the problem itself is trivial, but because Louise's learning procedure, TPC, is efficient. For a further example, in the upcoming publication I mention above, Louise is shown to learn a 2,567 clause theory in under 220 seconds with perfect accuracy after training on 20% of all training examples. The hypothesis space for this problem (grid world navigation) is in the order of 2*10^4944 but Louise shrinks it to the problem of enumerating, at worst, a little over 81 million clauses.
Veedrac 6y ago
> "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.
- 6y ago