Let me point out how simple parity really is.
All you need is a search space of programs that process inputs
sequentially and allow for loops or jumps.
A very simple finite state automaton with just one bit of internal state
can correctly classify arbitrary bitstrings by sequentially processing
them one bit at a time, and switching the internal state bit on or off
depending on whether the current input is 1 or 0.
How to learn such behavior from training examples? The problem is so
simple, you can solve it by random guessing. For instance, you can
use a recurrent net whose program is its weight matrix. The weights are
randomly initialized and then tested until the training set error is
zero. After a few thousand trials, the net generalizes perfectly to
parity for ARBITRARY n (not just for n<30 where traditional no-loop-GP
already breaks down). Details in:
S. Hochreiter and J. Schmidhuber. LSTM can solve hard long time lag
problems. In M. C. Mozer, M. I. Jordan, T. Petsche, eds.,
NIPS 9, pages 473-479, MIT Press, Cambridge MA, 1997.
On the other hand, almost any GP variant that allows for loops will
solve n-bit parity very quickly, too. To my knowledge, the first GP
implementation with loops was:
D. Dickmanns, J. Schmidhuber, and A. Winklhofer. Der genetische
Algorithmus: Eine Implementierung in Prolog.
Institut fuer Informatik, Lehrstuhl Prof. Radig, Technische Universitaet
Much smarter than guessing is Levin's universal search (LS), of course.
Unlike GP, LS an asymptotically optimal program search method for
non-incremental situations. LS allocates time to program candidates in
an optimal fashion. Appropriate LS variants will solve n-bit parity in
almost no time:
L. A. Levin (1973). Universal sequential search problems. Problems of
Information Transmission, 9(3):265-266.
First applications of LS and incremental LS extensions to the problem of
discovering programs with loops are:
J. Schmidhuber. Discovering neural nets with low Kolmogorov complexity
and high generalization capability. Neural Networks, 10(5):857-873,
(also ICML 1995).
J. Schmidhuber, J. Zhao, and M. Wiering. Shifting inductive bias
with success-story algorithm, adaptive Levin search, and incremental
self-improvement. Machine Learning 28:105-130, 1997 (also ICML 1996).
Most of the above is downloadable from my home page.
Juergen Schmidhuber director
IDSIA, Galleria 2, 6928 Manno-Lugano, Switzerland
Roland Olsson wrote:
> When developing novel GP methods, it is useful to compare new techniques
> with old ones on a suite of benchmark problems that are easily scalable in
> difficulty. The even-parity problem seems to be the most used such
> benchmark, but results obtained only on that problem are not necessarily
> generally valid.
> Even parity seems popular because:
> 1. It is quite easy to compute fitness.
> 2. It is hard for GP without ADFs.
> 3. It is easy to scale by just increasing the number of variables.