   Next: Near-Bias-Optimal Nonincremental Universal Search Up: Survey of Universal Search Previous: Survey of Universal Search

## Bias-Optimality

We will consider a very broad class of problems. A problem is defined by a recursive procedure that takes as an input any potential solution (a finite symbol string , where represents a search space of solution candidates) and outputs 1 if is a solution to , and 0 otherwise. Typically the goal is to find as quickly as possible some that solves .

Define a probability distribution on a finite or infinite set of programs for a given computer. represents the searcher's initial bias (e.g., could be based on program length, or on a probabilistic syntax diagram). A bias-optimal searcher will not spend more time on any solution candidate than it deserves, namely, not more than the candidate's probability times the total search time:

Definition 2.1 (BIAS-OPTIMAL SEARCHERS)   Let be a problem class, a search space of solution candidates (where any problem should have a solution in ), a task-dependent bias in the form of conditional probability distributions on the candidates . Suppose that we also have a predefined procedure that creates and tests any given on any within time (typically unknown in advance). A searcher is -bias-optimal ( ) if for any maximal total search time it is guaranteed to solve any problem if it has a solution satisfying . It is bias-optimal if .

This definition makes intuitive sense: the most probable candidates should get the lion's share of the total search time, in a way that precisely reflects the initial bias. Still, bias-optimality is a particular restricted notion of optimality, and there may be situations where it is not the most appropriate one --compare section 5.4.   Next: Near-Bias-Optimal Nonincremental Universal Search Up: Survey of Universal Search Previous: Survey of Universal Search
Juergen Schmidhuber 2004-04-15

Back to OOPS main page