4 ms·

The problem from the benchmark is automatically learning the function, to check three strings are ordered by length, from examples. What you are doing is categ

The problem from the benchmark is automatically learning the function, to check three strings are ordered by length, from examples. What you are doing is categorically different, because you are manually guiding the search process by telling it which interim lines to generate. This ignores all the interesting parts of the challenge.

deleted 6y ago
[deleted]
YeGoblynQueenne 6y ago
Ah, I see what you mean. 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. For instance, I did not direct Louise to define shorter/2 by means of length/2. In order to do this I would have to specify length/2 as BK for shorter/2, but I didn't. Note the BK declarations in the experiment file I put on pastebin: background_knowledge(llength/2, [tail/2,p/2]). background_knowledge(shorter/2, [s/2]). % ground_peano/1 is added here so it's reported by list_mil_problem/1 background_knowledge(ordered/3, [ground_peano/1]). background_knowledge(ordered_leq/3, [leq/2,ground_peano/1]). Remember how in an erarlier comment I pointed out that the definition of shorter/2 changed to use leq/2, instead of s/2, when the examples of ordered_leq/3 where in the BK? Again, Louise figured that on its own. In fact, this ability of Louise (actually, its learning procedure, Top Program Construction, or TPC) is kind of native, in the sense that TPC was originally conceived as an algorithm to select relevant background knowledge for a different learning system ("Thelma" for "Theory Learning Machine"; hence "Louise"). So it can figure out what BK it needs on its own. Automatic selection of relevant background knowledge in ILP was the original subject of my PhD research. Interestingly, it turns out that once we had a system that could perform this task, it could also learn its own programs.
- Veedrac 6y ago
  > 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

Ah, I see what you mean. 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. For instance, I did not direct Louise to define shorter/2 by means of length/2. In order to do this I would have to specify length/2 as BK for shorter/2, but I didn't. Note the BK declarations in the experiment file I put on pastebin: background_knowledge(llength/2, [tail/2,p/2]). background_knowledge(shorter/2, [s/2]). % ground_peano/1 is added here so it's reported by list_mil_problem/1 background_knowledge(ordered/3, [ground_peano/1]). background_knowledge(ordered_leq/3, [leq/2,ground_peano/1]). Remember how in an erarlier comment I pointed out that the definition of shorter/2 changed to use leq/2, instead of s/2, when the examples of ordered_leq/3 where in the BK? Again, Louise figured that on its own. In fact, this ability of Louise (actually, its learning procedure, Top Program Construction, or TPC) is kind of native, in the sense that TPC was originally conceived as an algorithm to select relevant background knowledge for a different learning system ("Thelma" for "Theory Learning Machine"; hence "Louise"). So it can figure out what BK it needs on its own. Automatic selection of relevant background knowledge in ILP was the original subject of my PhD research. Interestingly, it turns out that once we had a system that could perform this task, it could also learn its own programs.

Veedrac 6y ago
> 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.