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:
- incQ(i)
increases the current probability of by
incrementing and .
Analogously for decQ(i) (decrement).
It is illegal to set all probabilities
(or all but one) to zero;
to keep at least two search options.
incQ(i) and decQ(i)
do not delete argument from ds, by not decreasing dp.
- boostq(n) sequentially goes through all instructions of
the -th self-discovered frozen program;
each time an instruction is recognized as some ,
it gets boosted:
its numerator and the denominator are increased
by . (This is less specific than incQ(i), but can be useful,
as seen in the experiments, Section 6.)
- pushpat()
stores the current search pattern
by incrementing and copying the sequence
;
poppat() decrements , returning its old value.
setpat(x) sets , 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: Initial User-Defined Programs: Examples
Up: Primitive Instructions
Previous: Control-Related Instructions
Juergen Schmidhuber
2004-04-15
Back to OOPS main page