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
See section 2.1. Language classes, expressivity and complexity for a sketch
proof.
[2] Upcoming work, currently in review.