Ockham versus Darwin

Posted on June 18, 2008 by Peter Turney

Contemplating the comments on my last post, I began thinking about Ockham’s Razor versus Darwinian Evolution. Both of them can be used as heuristics or algorithms for creation, invention, and discovery. In 1964, Ray Solomonoff proposed A Formal Theory of Inductive Inference (Parts I and II). His theory is an Ockhamian algorithm for searching through the space of computer programs. It inspired Gold’s language identification in the limit and Kolmogorov complexity. On the other hand, genetic programming is an evolutionary algorithm for searching through the space of computer programs. It is interesting to compare these two approaches to searching in program space.

In Solomonoff’s 1964 approach, each program is treated as a black box. This is inefficient, because the knowledge that is gained from evaluating one program cannot be applied when evaluating another program. On the other hand, genetic programming combines pieces from programs to create new programs. The knowledge that is gained from past programs is used in the construction of new programs. Thus we should expect this Darwinian algorithm for searching in program space to perform better than an Ockhamian algorithm for searching in program space. In fact, genetic programming has some impressive successes. As far as I know, Ockhamian algorithms for searching in program space have not achieved anything this impressive. (Let me know if I’m wrong.)

I looked in the index of Peter Grünwald’s The Minimum Description Length Principle and in the index of Marcus Hutter‘s Universal Artificial Intelligence, and I found Solomonoff and Kolmogorov, of course, but there was no mention of genetic programming or John Koza. I looked in the index of Koza’s Genetic Programming, and there was no mention of Solomonoff or Kolmogorov, but Chaitin is mentioned. Most interestingly, Ray Solomonoff has a 2006 paper, Machine Learning – Past and Future, in which he talks about his research in Genetic Programming:

Genetic Programming is my second area of recent research. Koza’s Genetic Programming system has been able to solve many difficult problems of very varied kinds.

Solomonoff was born in 1926. There’s a lesson for us young people.