Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!mit-eddie!ll-xn!ames!ucbcad!ucbvax!ORSTCS.CS.ORST.EDU!tgd
From: tgd@ORSTCS.CS.ORST.EDU (Tom Dietterich)
Newsgroups: comp.ai.digest
Subject: Lenat's AM program
Message-ID: <8710211650.AA18715@orstcs.CS.ORST.EDU>
Date: Wed, 21-Oct-87 12:50:51 EDT
Article-I.D.: orstcs.8710211650.AA18715
Posted: Wed Oct 21 12:50:51 1987
Date-Received: Sat, 24-Oct-87 15:59:15 EDT
Sender: daemon@ucbvax.BERKELEY.EDU
Organization: The ARPA Internet
Lines: 83
Approved: ailist@kl.sri.com

The exact reasons for the success of AM (and for its eventual failure
to continue making new discoveries) have not been established.  In
Lenat's dissertation, he speculated that the source of power was the
search heuristics, and that the eventual failure was caused by the
inability of the system to generate new heuristics.

Then, in a paper by Lenat and Brown, a different reason is given:
namely that the representation of concepts was the critical factor.
There is a close relationahip between mathematics concepts and lisp,
so that mathematical concepts can be represented very concisely as
lisp functions.  Simple syntactic mutation operations, when applied to
these concise functions, yield other interesting mathematical
concepts.  In new domains, such as those tackled by Eurisko, it was
necessary to engineer the concept representation so that the concepts
were concisely representable.

Finally, in a paper published this year by Lenat and Feigenbaum, yet
another explanation of AM's (and Eurisko's) success and failure is
given: "The ultimate limitation was not what we expected (cpu time),
or hoped for (the need to learn new representations), but rather
something at once surprising and daunting: the need to have a massive
fraction of consensus reality already in the machine."

The problem with all of these explanations is that they have not been
subjected to rigorous experimental and analytical tests, so at the
present time, we still (more than ten years after AM) do not
understand why AM worked!

I have my own pet hypothesis, which I am currently subjecting to an
experimental test.  The hypothesis is this: AM succeeded because its
concept-creation operators generated a space that was dense in
interesting mathematical concepts.  This hypothesis contradicts each
of the preceding ones.  It claims that heuristics are not important
(i.e., a brute force search using the concept-creation operators would
be only polynomially--not exponentially--more expensive).  It claims
that the internal representation of the concepts (as lisp functions)
was also unimportant (i.e., any other representation would work as
well, because mutation operators are very rarely used by AM).
Finally, it claims that additional world knowledge is irrelevant
(because it succeeds without such knowledge).

There is already some evidence in favor of this hypothesis.  At CMU, a
student named Weimin Shen has developed a set of operators that can
rediscover many of AM's concepts.  The operators are applied in brute
force fashion and they discover addition, doubling, halving,
subtraction, multiplication, squaring, square roots, exponentiation,
division, logarithms, and iterated exponentiation.  All of these are
discovered without manipulating the internal representation of the
starting concepts.

AM is a "success" of AI in the sense that interesting and novel
behavior was exhibited.  However, it is a methodological failure of
AI, because follow up studies were not conducted to understand causes
of the successes and failures of AM.  AM is not unique in this regard.
Follow-up experimentation and analysis is critical to consolidating
our successes and extracting lessons for future research.  Let's get
to work!

Tom Dietterich
Department of Computer Science
Oregon State University
Corvallis, OR 97331
tgd@cs.orst.edu
OR tgd%cs.orst.edu@relay.cs.net


References:

\item Lenat, D. B., (1980). AM: An artificial intelligence approach to
discovery in mathematics as heuristic search, In Davis, R., and Lenat,
D. B., {\it Knowledge-based systems in Artificial Intelligence}, 1980.

\item Lenat, D. B., and Brown, J. S. (1984). Why AM and EURISKO appear to work,
{\it Artificial Intelligence}, 23(3) 269--294.

\item Lenat, D. B., and Feigenbaum, E. A. (1987). On the thresholds of
knowledge.  In {\it IJCAI87, The Proceedings of the Tenth
International Joint Conference on Artificial Intelligence}, Milan, Los
Altos, CA: Morgan-Kaufmann.

\item Shen, W. (1987).  Functional transformations in AI discovery
systems.  Technical Report CMU-CS-87-117, Carnegie-Mellon University,
Department of Computer Science.