Self-Improving Systems

Roland Olsson writes "A relatively easy way to construct "intelligent" systems that improve themselves practically ad infinitum is described at http://www-ia.hiof.no/~rolando/SIG/ Maybe Steven Spielberg's AI film is closer to reality than the general public knows *smile*?"

Comments

if only it were that simple

[rossjudson]

Please. Two notes on a page? Breakthrough? Hah. It's a hell of a lot tougher than it looks.
Read Koza's three tomes for extensive research on genetic programming (the art of developing programs through genetic-evolutionary techniques).
Read about particle swarms if you want to learn about an evolutionary technique that is quietly kicking the ass of most others wherever it is used.
From a theoretical point of view, this feels like it won't solve or do anything that can't be found within the solution space anyway, by another technique.

Re:if only it were that simple

[xmedar]

The main problem is what is not shown, i.e. the fitness function, for those that don't agree I challenge you to derive a fitness function for human beings, when you start finding that the fitness function is partially given by the humans themselves and the technologies and social organisations they adopt (i.e. humans are part of the problem space too) you suddenly find that what looked easy is actually not. The system described on the webpage is a "solution" in the same way that economics has a "solution" by specifying that supply/demand curves are given and not derivable and therefore misses the point. Certainly genetic algorithms are useful for well defined fitness criteria, unfortunately much of life is so intertwined that actually defining it is not possible.

Great..

[VFVTHUNTER]

Someone took a GP algorithm and superimposed it on the architecture of an RS Flip-Flop. On the plus side, with all of /.'s traffic, they probably won't have a hard time finding someone to fill that open position at the bottom of the page.

A framework for self-improving systems

[Black Acid]

ResearchIndex lists Theo: A framework for self-improving systems. Although The NECI Scientific Literature Digital Library: ResearchIndex itself does not carry the document, it lists several related ones. Heavy stuff. An excerpt from ResearchIndex summarizes Theo quite well:

For instance, the THEO system (Mitchell et al. 1989) uses a single knowledge base and a single set of axioms.

I'd suggest anyone seriously interested in self-improving systems check out Mitchell, T. M., J. Allen, P. Chalasani, J. Cheng, O. Etzioni, M. Ringuette, and J. C. Schlimmer's 1989 book, Theo: A Framework for Self-Improving Systems: National Science Foundation, published by DEC.

Genetic Programming

[nyjx]

... has been around since the mid 80's and although it works for toy problems it's very hard to get systems of a significant scale out of it. You're basically swapping sub branches of your program around to see what works - tranversing the space of all possible programs - it takes *a lot* of random attempts to do better than a human doing it analytically. Most AI researchers believe that you need at least a little bit of knowledge to guide your program's adaptation rather than blind mutation.

The Father of GP (John Koza) may disagree with me - he runs genetic-programming.org and more or less invented the field. He's also known for his vigorous defences of GP: anybody know of real applications?

A somewhat more complete description of GP can be found at Genetic-programming.com.

Re:Genetic Programming

[Some Dumbass...]

Which is why efforts at AI programming will continue to require human interaction for the foreseeable future.

No kidding. And in related news, educating humans will require human intervention in the forseeable future.

Obvious, eh? Almost as obvious as the idea that the random mutations used in genetic programming are about as efficient as real random mutations. They get the job done eventually, but require a lot of screw-ups to make one improvement.

Re:Genetic Programming

[call -151]

There are some "real applications" where genetic algorithms are used to solve some difficult questions in abstract mathematics.

There are a number of difficult questions in the field of research in combinatorial group theory for which no reasonable-time (non-exponential or worse) algorithms are known. Genetic algorithms have proven to be surprisingly effective for some questions in this area; I am part of an open-source project (the Magnus project, an endeavor of the New York Group Theory Cooperative) which has implemented a number of genetic algorithms in our software for computations in combinatorial group theory. See this page for a descripition of some of the genetic algorithms implemented in our software. In particular, some difficult theoretical questions that had been studied for more than 20 years turned out to be answered quickly (less than 30 seconds on a 300 Mhz PII) via a genetic algorithm approach. (The most remarkable of them was the dismissal of a potential counterexample to the Andrews-Curtis conjecture which had been very resistant to theoretical and traditional computational approaches.)

I know of other successes of genetic algorithms in research mathematics in areas like control theory and modelling, but I am most familiar with algebraic applications. In the situations described above, there are good measures of `fitness' and a good notion of two reasonably-fit individuals combining and possibly mutating to make even-more-fit offspring. It is much more difficult to apply the techniques where there is not a good measure of fitness or of combination.

GA Archive

[metlin]

Check out the GA Archive. Great collection of the more famous GA's and proceedings.

For those wishing to get an intro to GA, try The Hitchhiker's Guide to Evolutionary Computation.

My own experiments with evolved code

[melquiades]

In college, I did a project in which I attempted to evolve programs for Core Wars, in which two programs running in a virtual machine language basically attempt to overwrite each other's memory space.

My algorithm started with random programs and pitted them against each other in the Core Wars arena. The fitness function was simple: programs that beat other programs got higher ratings. Top-rated programs would "breed", and all programs would mutate. The hope was that after time, successful warriors would evolve.

And, lo and behold, they did! My algorithm "evolved" some simple bombers -- not nearly as good as what a human would write, but amazing considering I put no knowledge about strategy into the algorithm, and started with random core wars code.

Ah, but (there's always a but) I found that there was no significant correlation between how successful a warrior was and how many generations of crossover went into it. In other words, the genetic algorithm did no better than an algorithm which simply selected lots of random programs and kept the ones that work. So actually, my result was not very impressive at all -- I was basically doing a brute force random search for programs, and happened to find a few.

Others might get much better results with different languages, because Core Wars machine code does not lend itself to crossover (i.e. it's had to merge two Core Wars programs into a better program). Functional languages do a bit better with this. But I really doubt that Genetic Algorithms will prove useful in the near future for generating any sort of code that wouldn't be trivially easy for a human to write.

Re:My own experiments with evolved code

[Animats]

In other words, the genetic algorithm did no better than an algorithm which simply selected lots of random programs and kept the ones that work.

That's not unusual. Any broad-front search (which includes genetic algorithms, simulated annealing, and neural nets) should be tested in this way. Both ends of the search spectrum - pure hill-climbing using a greedy algorithm, and random search, should be tried. Unless a more elaborate algorithm beats both of them, it's not accomplishing anything.

This is an embarassing truth which GA researchers hate to hear. But GA people need to do this validation or they waste time on problems for which GAs are unsuitable.

I was recently contemplating the same thing

[I Am The Owl]

I was talking to a friend of mine the other day about how he had taken one of those programs in which you "make" your own battle robot out of assembly code, and had written a program that wrote a bunch of them and then matched them up, combining the instructions of the winning bots to form the next generation.

This got me intrigued, so I hopped on to Google, and, lo and behold, this is what I found. Probably one of the more interesting works that I have read online in quite some time, although there were parts that I didn't understand since I haven't yet taken enough coursees in high math to properly comprehend them.