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.
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.