3
$\begingroup$

This is a machine learning question. Given this series of categorical data, what program will derive the underlying algorithm and predict what comes next in the series?

Here is the series:

B, BA, BB, BAA, BAB, BBA, BBB, BAAA, BAAB, BABA, ...

Anyone with knowledge of computer science may quickly realize that this series is simply counting in binary with "A" substituted for "0" and "B" substituted for "1". This is true, but...

the program that predicts what comes next must do so only by manipulating the symbols given in the series. It must not use hard-coded knowledge of binary counting.

I realize many patter recognition algorithms are available but I haven't seen how any can solve this deceptively hard problem.

-Edit-

Based on the votes that this problem is insolvable, I've done some refactoring and posed the question another way, with more constraints, here: What program will derive the underlying algorithm in these question-answer pairs (updated)?

Improve this question
$\endgroup$
1
  • $\begingroup$ genetic algorithms/genetic programming with string primitives can be used to solve this type of problem in theory but havent seen it done yet... $\endgroup$
    – vzn
    Commented Jan 11, 2014 at 19:29

2 Answers 2

Reset to default
6
$\begingroup$

Without any a priori knowledge, the problem is insoluble. There are infinitely many possible answers and you have no wat at all to say that one of them is preferable to any of the others. How can you possibly tell just by manipulating symbols that the sequence is "Counting in binary using A and B for 0 and 1" rather than "B, BA, BB, BAA, BAB, BBA, BBB, BAAA, BAAB, BABA, BABB, BBAA, widgeon, 27, expunge" followed by a list of the squares of every third prime, number written in base-14 using Hebrew letters instead of the even digits?

Wait – how would you even know that there is a next element?

Improve this answer
$\endgroup$
2
  • $\begingroup$ You have a valid point that the number of patterns potentially represented by the sequence is infinite. Therefore, based on Occam's Razor, the simplest solution is preferred. To your last point, it is given that the data is a series. It might stop, but nothing in the series indicates that. The series does indicate certain rules, for example, all items start with B. $\endgroup$
    – Calvin
    Commented Jan 11, 2014 at 1:29
  • $\begingroup$ @Calvin. Heh. You're still going to have trouble until you define "simplest". Even when you do, you'll still likely have problems, though. $\endgroup$
    – Rick Decker
    Commented Dec 8, 2015 at 2:05
0
$\begingroup$

Here it is not machine learning anymore but some sort of deep/hard artificial intelligence. The problem could be stated as :

« given that infinite sequence (the program can get as many terms as it wants) what is the shortest algorithm (or program, given a programming langage) capable of generating that sequence » ? (because it is an infinite sequence you are never 100% sure, but you can affect a probability of correctness once the first $10^N$ terms have been generated correctly)

You are still able to try all the possible programs (let's say in a small subset of the C language) and wait until you find one which generates correctly the 100000 first terms,

but this is not a fully satisfactory solution (is it a matter of complexity, because trying randomly all the possible programs is exponential in time with respect to the size ? could an AI do better than that ?).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.