next up previous
Next: Initial User-Defined Programs: Examples Up: Primitive Instructions Previous: Control-Related Instructions

Bias-Shifting Instructions to Modify Suffix Probabilities

The concept of online-generated probabilistic programs with ``self-referential'' instructions that modify the probabilities of instructions to be executed later was already implemented earlier by [65]. Here we use the following primitives:

  1. incQ(i) increases the current probability of $Q_i$ by incrementing $p[curp][i]$ and $sum[curp]$. Analogously for decQ(i) (decrement). It is illegal to set all $Q$ probabilities (or all but one) to zero; to keep at least two search options. incQ(i) and decQ(i) do not delete argument $i$ from ds, by not decreasing dp.

  2. boostq(n) sequentially goes through all instructions of the $n$-th self-discovered frozen program; each time an instruction is recognized as some $Q_i$, it gets boosted: its numerator $p[curp][i]$ and the denominator $sum[curp]$ are increased by $n_Q$. (This is less specific than incQ(i), but can be useful, as seen in the experiments, Section 6.)

  3. pushpat() stores the current search pattern $pat[curp]$ by incrementing $patp$ and copying the sequence $pat[patp] := pat[curp]$; poppat() decrements $patp$, returning its old value. setpat(x) sets $curp := x$, thus defining the distribution for the next search, given the current task.

    The idea is to give the system the opportunity to define several fairly arbitrary distributions on the possible search options, and switch on useful ones when needed in a given computational context, to implement conditional probabilities of tokens, given a computational history.

Of course, we could also explicitly implement tape-represented conditional probabilities of tokens, given previous tokens or token sequences, using a tape-encoded, modifiable probabilistic syntax diagram for defining modifiable n-grams. This may facilitate the act of ignoring certain meaningless program prefixes during search. In the present implementation, however, the system has to create / represent such conditional dependencies by invoking appropriate subprograms including sequences of instructions such as incQ(), pushpat() and setpat().

Instead of or in addition to boostq() we could also use other probability-modifying primitives, of course. For instance, we could plug in a time-consuming algorithm such as Probabilistic Incremental Program Evolution [44,45,46]. Likewise we could use variants of Evolutionary Computation [40,67] or Genetic Algorithms [17] or Genetic Programming (GP) [8,2] as primitives. Generally speaking, whenever there is prior knowledge about promising directions in the search space, such as gradients, and about certain potentially useful incremental learning techniques, then this knowledge should be implemented in form of primitives. We just need to make sure that any time-consuming primitive is written such that OOPS can interrupt it at any time, and can undo the effects of (partially) executing it.

next up previous
Next: Initial User-Defined Programs: Examples Up: Primitive Instructions Previous: Control-Related Instructions
Juergen Schmidhuber 2004-04-15

Back to OOPS main page