Bias-Optimality

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

Define a probability distribution $P$ on a finite or infinite set of programs for a given computer. $P$ represents the searcher's initial bias (e.g., $P$ 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 $\cal R$ be a problem class, $\cal C$ a search space of solution candidates (where any problem $r \in \cal R$ should have a solution in $\cal C$), $P(q \mid r)$ a task-dependent bias in the form of conditional probability distributions on the candidates $q \in \cal C$. Suppose that we also have a predefined procedure that creates and tests any given $q$ on any $r \in \cal R$ within time $t(q,r)$ (typically unknown in advance). A searcher is $n$-bias-optimal ($n \geq 1$) if for any maximal total search time $T_{max} > 0$ it is guaranteed to solve any problem $r \in \cal R$ if it has a solution $p \in \cal C$ satisfying $t(p,r) \leq P(p \mid r)~T_{max}/n$. It is bias-optimal if $n=1$.

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 [59]--compare section 5.4.

Back to OOPS main page