next up previous
Next: Brief Introduction to Optimal

Bias-Optimal Incremental Problem Solving

Jürgen Schmidhuber
IDSIA, Galleria 2, 6928 Manno-Lugano, Switzerland

In S. Becker, S. Thrun, K. Obermayer, eds., Advances in Neural Information Processing Systems 15, NIPS'15, MIT Press, Cambridge MA, p. 1571-1578, 2003. PS. PDF.


Given is a problem sequence and a probability distribution (the bias) on programs computing solution candidates. We present an optimally fast way of incrementally solving each task in the sequence. Bias shifts are computed by program prefixes that modify the distribution on their suffixes by reusing successful code for previous tasks (stored in non-modifiable memory). No tested program gets more runtime than its probability times the total search time. In illustrative experiments, ours becomes the first general system to learn a universal solver for arbitrary $n$ disk Towers of Hanoi tasks (minimal solution size $2^n-1$). It demonstrates the advantages of incremental learning by profiting from previously solved, simpler tasks involving samples of a simple context free language.

Juergen Schmidhuber 2003-02-25

Back to OOPS home page