4 ms·
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 c
by 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 agoI 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.
- YeGoblynQueenne 6y ago