images/824_1.pdf -- Eurisko by DB Lenat, the program that made the fleet which won the 1981 and 1982 Traveller's challenge, as I discovered in this New Yorker article by Malcolm Gladwell.
- Notable observations of the author: EURISKO'S progress in this domain was entertaining, and a fundamental feature of this domain became clear: large programs are carefully engineered artifacts, complex constructs with thousands of pieces in a kind of unstable equilibrium. Any sort of random perturbation is likely to produce an error rather than a novel mutant. The analogy to biological evolution is strong.
- EURISKO had successes in automatic programming only when it modified functions which had been coded as units. Why was this?
- He also tried simulating biological evolution, and found that progress was slow when the mutations were random, but were quite rapid when they were organized by a set of heuristics. Heuristics, in this case, refer to rules like 'fewer defenses require faster legs and better ears and noses' - which can be generalized by simple observations of nature - or 'large cranium requires large female cervical opening' which is a heuristic that has only weakly been encoded in our DNA in the form of mate preference (maybe).
- Quote: The net effect of having these heuristics for guiding plausible mutations was that, in a single generation, an offspring would emerge with a whole constellation of related mutations that worked together. For example, one had thicker fur, a thicker fat layer, whiter fur, smaller ears, etc. It is not known whether there is any biological validity to this radical hypothesis, but there is no doubt that the simulated evolution progressed almost not at all when mutation was random, and quite rapidly when mutation was under control of a body of heuristic rules. See [10].
- This is consistent with homeobox genes, which were discovered in 1983. ref
- The introductory and explicit description of the program was more difficult to parse than the later examples illustrating exactly what Eurisko did/does; the introduction of weakly-weighted contrapositive heuristics to a defeated heuristics on page 90 (page 30 in the pdf), for example, is revealing.
- Eurisko has a sensible trigger for invoking heuristic / generalizing rules: when a particular node has too many entries (slots, in his terminology), a set of heuristics are called in to segregate the set of entries by common features, e.g. clustering.
- The conclusion - a list of ideas (heuristics!) regarding the development of his program - is well articulated and useful, even 29 years later! In particular: "In other words, even though the discovery of new heuristics is important, the presence (and maintenance) of an appropriate representation for knowledge is even more necessary." (my emphasis)
- Again: "Brevity is a key attribute in any kind of asemantic exploration. If useful concepts are short expressions in your language, then you have some chance of coming across them often, even if you don't know much about the terrain."
|