Given this set of question-answer pairs, what program will derive the underlying algorithm and provide the correct answer for any question of the same format.
Question-Answer Pairs (training set):
B:BA BA:BB BB:BAA BAA:BAB BAB:BBA BBA:BBB BBB:BAAA BAAA:BAAB BAAB:BABA
Those familiar with binary may notice that the training set is binary numbers with A and B substituted for 0 and 1. The answer to each question is the next binary number (using A and B).
After processing the training set, the program should be able to answer questions such as the following using the algorithm it derived:
BABA:? BABB:? BBBBAAA:? BAABBAAABBABA:?
- The program must derive the counting algorithm only by manipulating the data given in the training set. It must not use hard coded knowledge of binary counting.
- Many algorithms may produce the correct answers. Therefore, the simplest algorithm is preferred.
- The program should assume that each answer is a transformation of the question.
- All questions will be in the binary format seen above, but they may be of arbitrary size.
Can any existing machine learning programs/algorithms solve this? If so, how? If you believe this is unsolvable, please explain why.
This update contains background to the question, explanation of the problem space, a new constraint, a proposed solution, and further questions.
This problem is relevant to general machine learning where the machine must learn by observation and feedback the algorithms that govern the world around it.
Based on Kolmogorov complexity, there is at least one program that can produce the correct mappings:
if B, then BA if BA, then BB (etc. for all pairs in training set)
This will work for every pair in the training set and nothing else. This will be the shortest program if the training set is completely random. The good news is that this is an upper bound. For any training set that is not random, there will be a smaller program that will work. Also, the number of programs smaller than upper bound is finite.
A unfortunate result of Kolmogorov complexity is that it cannot be calculated. This is due to the halting problem. We can't know if any program will stop until it does.
If the question is "Write pi," then the program that produces the correct answer would never halt because pi has infinite digits. An answer infinitely long is never desirable so I think the best way to deal with this is to put an arbitrary limit on the length of the answer.
With that additional constraint, here is an (inefficient) program that will generate a correct solution program shorter than the upper bound if one exists. (sorry of this is confusing, but these steps outline a program that generates programs that implement an algorithm to map questions to answers in a training set):
- Create the "upper bound" program. One that maps each input in the training set directly to its output.
- Generate every possible program that is shorter than the upper bound and list them from shortest to longest.
- Starting with the shortest program, run the first step of every program.
- Stop when a correct program is found.
- Eliminate programs that stop without a correct answer or produce an answer longer than the arbitrary limit.
- Repeat steps 3-5 running the second step, third step, etc. of the programs.
This program has the following benefits:
- It limits the number of programs to those smaller than the "upper bound" program.
- It avoids the halting problem by
- incorporating an arbitrary limit to the length of the answer and
- executing step x in all programs before moving on to step x+1 so that the solution will be found before looping infinity.
The main disadvantage is that it is terribly slow. It takes millions of years to crack a 128 bit password and I think this program could have comparable performance.
Now, the questions:
Do you see any significant flaws in this solution?
Can this program's performance be improved in any significant way without introducing onerous constraints?