Friday, September 7, 2007

The optimal IQ test

The hardest part for me when thinking about seed AI and optimal optimization, is coming up with a good fitness (IQ) test. Since you need the test to run fast, you end up testing that the algorithm can get somewhere fast, i.e checking only the extreme beginning of a performance curve that ultimately must continue to be good many thousand times longer. What we want to measure is something like the Big O performance of the algorithm in the limit and not what it looks like the first second of it's life. Another problem is that we want the intelligence to be as general as possible and not over-specialized on solving a few test cases.

A fitness test of a fitness test

Recently I got a new idea of what constitutes a good IQ test. Our current approach to seed AI is about developing a really good programmer that can program better versions of itself. A good fitness test is a test that has a high correlation between a program testing good on it and the same program being able to generate new programs that gets even better scores. Not only is this a necessary criterion. It might be sufficient. Any test of a program which means that this program is likely to produce new programs that perform well (strictly - reach a new global optimum) on the test, might be a good fitness test of what we are after. The test that produces new Masters (see this post) most frequently might be the best test. Getting the most new Masters over time, also ensures that the test does not take unnecessarily long to run. I am not completely sure, but we might need to force all tests to start with a kernel of an intelligence test (compress this string, predict this numeric sequence, something like that), just to set it of in the right direction and eliminate trivial solutions, like giving all programs a random IQ from some distribution. The trivial solution of giving all programs the perfect IQ, would not be a candidate, because no new globally optimal solutions would be found, so no new Masters would come, and thus that fitness test would not test well on the fitness test test (am I making sense?).

Having a fitness test of our fitness test suggests that we can start by evolving a good test, or even more beautifully, co-evolve solution and test.

Perhaps I am just dreaming, but it sure would be a beautiful algorithm if it worked...

Thursday, September 6, 2007

Coincidence?

I once read a short story about the creation of the world's most powerful computer. In essence, each time they tried to turn it on, they had some minor misfortune, a power outage, the maid accidentaly tripped on, and unplugged, the power cord, etc. The highly technical twist in the end was that since we live in a Multiverse, all things that can happen happens in a separate universe. It turns out that the computer was so advanced (or something) that it turned in to a black hole when switched on, destroying all life. Since the observers could only exist in the universes where the computer remained switched off, they experienced these "coincidences", that protected them.

A database of all human knowledge

When I read up a bit on Cyc, the other day, I came upon a competing project that I, myself, once added some mindpixels to.
Mindpixel was a web-based collaborative artificial intelligence project which aimed to create a database of millions of human validated true/false statements, or probabilistic propositions.
Unfortunately the project is now defunct, since the founder Chris McKinstry committed suicide on 23rd January, 2006.

Well, never fear, because from the Mindpixel page on Wikipedia, we learn that Open Mind Common Sense is a similar project, run by MIT, whose goal is to build a large common sense knowledge base from the contributions of many thousands of people across the Web.

Unfortunately that project is also stalling, since Push Singh who was slated to become a professor at the MIT Media Lab to lead the Commonsense Computing group in 2007, commited suicide on Tuesday, February 28, 2006. Just a month after the other visionary of web knowledge, Chris McKinstry.

Let the unreasonable conspiracy theories commence.

Wednesday, September 5, 2007

12:50, press Return

The deed is done.

I and my friend Nils made a "sprint" last night, where we finished the first version of our seed AI.

First we made a simple IQ-function that tests how well a program (a Program Generator or PG) can generate new programs (leaves) from feedback of how close a leaf is to what we want.

A PG that receives the best IQ so far gets a chance to generate new PG's, in effect it becomes a Program Generator Generator. We call this state a Challenger. When a Challenger generates a new PG with the best IQ so far, it has verified that not only does it have good IQ, but it can produce other programs with good IQ, and is thus promoted to the status of Master (and the smart PG gets to be Challenger).

The programs are generated and run in a circular buffer under a virtual machine, where all sequences of integers are valid programs and no operators can throw exceptions. Such a VM is much slower than machine code, but the process gets faster than if it were running on bare bones x86, because on an x86 (or other architecture) most bytes are meaningless and will throw exceptions, which are slow to process. A PG that is good enough (for example a human) to understand how to write code without generating (many) exceptions, would theoretically run faster on x86, but our current primitive PGs will benefit from a virtual environment.

Anyway, we wrote the code, pressed Enter (the title is a reference to the nice movie Pi), and voĆ­la, our random generating seed started finding more intelligent programs than itself - Challengers. After a while, Nils calls it 15 seconds, a Challenger managed to become Master and after a longer while the Master produced a Challenger that later became the third generation Master. Spectacular!

Now we just need a better IQ test and a way to inspect the generated programs! Well, we also need tons and tons of hardware. This is the sort of task that could happily use up Google's entire computer armada for a year and still benefit from more. Hmm.. perhaps if I ask them nicely..