next up previous
Next: Introduction


Optimal Ordered Problem Solver
Machine Learning, 54, 211-254, 2004. PDF.

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


We introduce a general and in a certain sense time-optimal way of solving one problem after another, efficiently searching the space of programs that compute solution candidates, including those programs that organize and manage and adapt and reuse earlier acquired knowledge. The Optimal Ordered Problem Solver (OOPS) draws inspiration from Universal Search designed for single problems and universal Turing machines. It spends part of the total search time for a new problem on testing programs that exploit previous solution-computing programs in computable ways. If the new problem can be solved faster by copy-editing/invoking previous code than by solving the new problem from scratch, then OOPS will find this out. If not, then at least the previous solutions will not cause much harm. We introduce an efficient, recursive, backtracking-based way of implementing OOPS on realistic computers with limited storage. Experiments illustrate how OOPS can greatly profit from metalearning or metasearching, that is, searching for faster search procedures.

Keywords: OOPS, bias-optimality, incremental optimal universal search, efficient planning & backtracking in program space, metasearching & metalearning, self-improvement.

next up previous
Next: Introduction
Juergen Schmidhuber 2004-04-15

Back to OOPS main page