Optimal Ordered Problem Solver

By J. Urgen Schmidhuber. 2002

190 citations recorded by the source corpus.

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 Levin's 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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Algorithms & Complexity

Citations in the corpus

Learning to Optimize Neural Nets (2017, background): “Other meth-ods (Brazdil et al., 2003; Schmidhuber, 2004) aim to learn how to choose a base-level learner that would perform the best on a given task.”
Neural Symbolic Machines: Learning Semantic Parsers on Freebase with Weak Supervision (2016, background): “Earlier works such as OOPS (Schmidhuber, 2004) has desirable characteristics, for example, the ability to define new functions.”
Deep learning in neural networks: An overview (2014, background): “Numerous alternative HRL techniques have been proposed (e.g., Bakker & Schmidhuber, 2004; Barto & Mahadevan, 2003; Dietterich, 2000b; Doya, Samejima, Katagiri, & Kawato, 2002; Ghavamzadeh & Mahadevan, 2003; Jameson, 1991; Menache, Mannor, & Shimkin, 2002; Moore & Atkeson, 1995; Precup, Sutton, &…”
AutoML-Zero: Evolving Machine Learning Algorithms From Scratch (2020, neutral): “The synthesized programs—or algorithms—solve problems like sorting, addition, counting [74, 27, 70, 85], string manipulations [64, 61, 19], character recognition [38], competitionstyle programming [5], structured data QA [56, 45, 46],”
World Models (2018, background): “…et al., 2017; Bansal et al., 2017; Al-Shedivat et al., 2017) and PowerPlay (Schmidhuber, 2013; Srivastava et al., 2012) also explores methods that lead to a natural curriculum learning (Schmidhuber, 2002), and we feel this is one of the more exciting research areas of reinforcement learning.”
Learning to Learn without Forgetting By Maximizing Transfer and Minimizing Interference (2018, methodology): “Another relevant work is the POWERPLAY framework (Schmidhuber, 2004; 2013) which is a method for asymptotically optimal curriculum learning that by definition cannot forget previously learned skills.”
Hindsight Experience Replay (2017, background): “oximating multiple value functions. Learning simultaneously to perform multiple tasks has been also investigated for a long time in the context of Hierarchical Reinforcement Learning, e.g. Bakker and Schmidhuber (2004); Vezhnevets et al. (2017). Our approach may be seen as a form of implicit curricu”
PowerPlay: Training an Increasingly General Problem Solver by Continually Searching for the Simplest Still Unsolvable Problem (2011, neutral): “, P (p) = 2, or on a probabilistic syntax diagram [32, 31].”
Learning Simple Algorithms from Examples (2015, background): “Consequently, the unexpectedly long test sequence makes it unsure of what the correct action is.”
A Roadmap Towards Machine Intelligence (2015, neutral): “The idea of incremental learning, motivated by the same considerations as in the papers we just mentioned, also appears in Solomonoff (2002), a work which has much earlier roots in research on program induction (Solomonoff, 1964, 1997; Schmidhuber, 2004).”
Online Meta-Learning (2019, neutral): “Meta-learning: Prior works have proposed learning update rules, selective copying of weights, or optimizers for fast adaptation (Hochreiter et al., 2001; Bengio et al., 1992; Andrychowicz et al., 2016; Li & Malik, 2017; Ravi & Larochelle, 2017; Schmidhuber, 2002; Ha et al., 2017), as well as recurre”
First Experiments with PowerPlay (2012, methodology): “SLIM RNN is a general computer, and its weights are its program, subsets of the weights can be viewed as sub-programs, and new sub-programs can be formed from old ones in essentially arbitrary computable ways, like in general incremental program search [21].”
On Learning to Think: Algorithmic Information Theory for Novel Combinations of Reinforcement Learning Controllers and Recurrent Neural World Models (2015, methodology): “General methods for incremental multitask RL and algorithmic transfer learning that are not NN-specific include the evolutionary ADATE system [182], the Success-Story Algorithm for SelfModifying Policies running on general-purpose computers [233, 252, 251], and the Optimal Ordered Problem Solver [23”
One Big Net For Everything (2018, methodology): “…trained in a series of trials through a black box optimization method in Step 3 of Algorithm 1, e.g., through incremental neuroevolution [17], hierarchical neuroevolution [100, 93], hierarchical policy gradient algorithms [13], or asymptotically optimal ways of algorithmic transfer learning [69].”
Formal Theory of Creativity, Fun, and Intrinsic Motivation (1990–2010) (2010, methodology): “A runtime-dependent performance measure inspired by concepts of optimal universal search [43], [81], [82], [85], [96], [99] is”
Maximizing Fun by Creating Data with Easily Reducible Subjective Complexity (2013, methodology): “Many ingredients of this system may be just what one needs to build practical yet sound curious and creative systems that never stop expanding their knowledge about what can be done in a given world, although future reimplementations should probably use alternative reward optimizers that are more ge”