Eurisko

Speaking of methods, here's a small misquotation from Sherlock Holmes (via Familiar Quotations).

You know my methods, Watson. Apply them!

Anyway, here's the secret. I found the paper, along with others by the same author (Douglas Lenat), by following a reference in some book or other. This was back in college. The papers were interesting enough that I kept copies of them, and I've been keeping an eye on what Lenat's been up to ever since.

I'm pretty sure the original reference was to the fact that Eurisko had won the Traveller Trillion Credit Squadron tournament in 1981 and 1982, but I haven't been able to track that one down. Another possibility is that the original reference was contained in the following passage from the wonderful Gödel, Escher, Bach … or, specifically, from Artificial Intelligence: Retrospects.

Another program, written by Douglas Lenat at Stanford, had as its aim to invent concepts and discover facts in very elementary mathematics. Beginning with the notion of sets, and a collection of notions of what is “interesting” which had been spoon-fed into it, it “invented” the idea of counting, then the idea of addition, then multiplication, then—among other things—the notion of prime numbers, and it went so far as to rediscover Goldbach's conjecture!

The program referred to, by the way, is AM, not Eurisko.

So much for methods. Now I'd like to go through the paper and quote some of the better parts. Let me start with a bit from the abstract that gives a general idea of what the program does.

Our work on the nature of heuristics has enabled the construction of a new language in which the statement of heuristics is more natural and compact.

:

The EURISKO program embodies this language, and it is described in this paper, along with its results in eight task domains: design of naval fleets, elementary set theory and number theory, LISP programming, biological evolution, games in general, the design of three-dimensional VLSI devices, the discovery of heuristics which help the system discover heuristics, and the discovery of appropriate new types of ‘slots’ in each domain.

Here's another bit from the abstract that explains the relationship between AM and Eurisko.

In essence, AM was an automatic programming system, whose primitive actions were modifications to pieces of LISP code, code which represented the characteristic functions of various math concepts. It was only because of the deep relationship between LISP and Mathematics that these operations (loop unwinding, recursion elimination, composition, argument elimination, function substitution, etc.) which were basic LISP mutators also turned out to yield a high ‘hit rate’ of viable, useful new math concepts when applied to previously-known, useful math concepts.

:

By employing this new language, the old property that AM satisfied fortuitously is once again satisfied: the primitive syntactic operators usually now produce meaningful semantic variants of what they operate on.

I've seen the same principle, that mutations need to produce reasonable variants, elsewhere. It might have been applied to a form of assembly language in the article An approach to the synthesis of life, but I can't be sure, since I don't have it handy.

The remaining points are all taken from section 1.2 of the paper, which discusses Eurisko's control structure. This first one was amusing to me because I'd just been thinking about how I divide up my own time … but more on that later.

(1) The control structure of the system is represented as part of the knowledge base. While an AM-like agenda mechanism has been retained, the precise control algorithm is represented within EURISKO as a set of concepts, so the system can modify it itself. Basically, there is a Select-Execute-PostMortem loop represented as a unit. Specializations of this unit form the three nested loops that characterize the EURISKO program: select and work on a topic; given a topic, select and work on a promising task; given a task, select and obey a relevant individual heuristic rule.

The second point fits right in with my program of understanding and exploiting how the mind operates.

(2) Multiple agendae. The human researcher sticks with a topic for an extended period of time. Partly this is due to the difficulty of ‘swapping in’ a whole new set of concepts, heuristics, etc.

At work, I had developed the same idea about swapping—whenever I tried to divide my time between two different projects, I was always much less productive. More recently, I ran across a nice article on the same subject (online).

The second point continues as follows.

Yet part of the reason for this behavior is more rational, and worth duplicating in our mechanical researchers: a developing field will often bog down and appear to stagnate, and this gradual winding down of interestingness is punctuated by occasional bursts of (often serendipitous) discovery, which lead to many promising things to do, which gradually wind down, etc.

It seems to me that the phrase “winding down” is just right. For what it's worth, I think of a discovery that leads to many promising things as a rich lode … a phrase which—correctly—reminds me of the data mining mentioned in Diaspora.

I couldn't find a sufficiently pithy quote for it, but one of the conclusions drawn in the second point is that when you're stagnating, you can often obtain serendipitous discoveries by switching topics, i.e., by juxtaposition.

As someone who makes to-do lists and wonders how best to use them, I naturally found the third point quite appealing.

(3) Dynamic creation and elimination of agendae (topics). On rare occasions, a heuristic rule will advise that an agenda be split into pieces. E.g., here are two rules which make such recommendations:

If agenda A contains more than four times as many tasks as the average agenda, then (try to) split A into about three pieces.

(I've omitted the second rule, which wasn't as interesting.)

Once Eurisko has decided to split an agenda, how does it actually go about splitting it? By applying more heuristic rules, naturally! So, if you buy into my identification of heuristic rules as memes, we can pick out two kinds of idea people might have about to-do lists: ideas that recognize when a list needs to be split, and ideas that suggest how a split should be accomplished.

By the way, I certainly don't mean to suggest that people, like Eurisko, all have little to-do lists built into their heads.

Finally, here's an amusing observation taken from the seventh point.

(7) Each heuristic rule is itself a concept; we do not distinguish metarules from rules.

:

Unfortunately for my philosophy, EURISKO recently chose to define and separate out the set of rules that can operate sometimes on other rules—i.e., the metarules. It did this mainly for aesthetic reasons (co-identification), and decided to keep the distinction around because it noticed a powerful regularity involving metarules: running one on rules usually takes much longer than running it on domain-level concepts.

I like the idea of rules applying to other rules, because it reminds me of how there are memes about memes.