"AllenRobert"@LLL-MFE.ARPA (03/07/84)
In response to Rusty's request regarding EURISKO (V2,#22), the following
is a brief excerpt from my thesis qualifying/background paper on knowledge
acquisition in expert systems. I tried to summarize the system and its
history; a lot of detail has been removed. I hope the description is
accurate; please feel free to criticize.
EURISKO is a part of Doug Lenat's investigation of machine learning,
drawing its roots from his Stanford Ph.D. thesis research with
AM [Lenat 76]. AM was somewhat unusual among learning systems in that it
does not have an associated performance element (expert system). Rather,
AM is supplied with an initial knowledge base representing simple set
theoretic concepts, and heuristics which it employs to explore those
concepts. The goal is for AM to search for new concepts, and
relationships between concepts, guided by those heuristics.
AM represents concepts (eg. prime and natural numbers) in frames. A
frame's slots describe attributes of the concept, such as its name,
definition, boundary values, and examples. A definition slot includes one
or more LISP predicate functions; AM applies definition functions to
objects (values, etc.) to determine whether they are examples of the
concept. For instance, the Prime Number frame has several definition
predicates which can each determine (for different circumstances) if an
integer is prime or not; those predicates (and boundary values)
effectively define the concept "prime number" within AM.
Any slot may have zero or more heuristics, expressed as production rules,
expressing strategies for exploring concepts. Heuristics primarily obtain
or verify slot values; the may also postulate new concepts/frames, or
specify tasks to be performed. AM maintains an "agenda of tasks"
expressed as goals, in the form "Find or verify the value of slot S, from
concept/frame C." The basic control structure selects a task from the
agenda, and checks the slot (S) for heuristics. If one or more are found,
a rule interpreter is invoked to execute them. If slot S has no
heuristics, it may point (possibly through several levels) to another
frame whose corresponding (same name) slot does, in which case those
heuristics are executed; thus, heuristics from higher-level concepts may
be employed or inherited in exploring less abstract concepts. This
continues until all the related heuristics are executed; AM then returns
to the agenda for a new goal.
AM is provided with an initial knowledge base of around one hundred
frames/concepts from finite set theory, which include around 250
heuristics. The system is then "set loose" to explore those concepts,
guided by heuristics; AM postulates new concepts and then attempts to
judge their validity and utility. Over a period of time, AM may
conjecture and explore several hundred new concepts; some eventually
become well established and are themselves used as extensions of the
initial knowledge base.
AM never managed to discover concepts that were not already known in
mathematics; however it did discover many well known mathematical
principles (eg. de Morgan's laws, unique factorization), some of which
were originally unknown to Lenat. It was hoped that AM might might also
be applied to the domain of heuristics themselves; i.e. exploring
heuristic concept/frames instead of mathematical concept/frames, but the
system did not make much progress in this area. Lenat explains an
underlying problem : AM's representation of domain knowledge (LISP
functions) is fundamentally similar to the primitives of mathematical
notation, while heuristics lack a similar close relationship. He has
developed new ideas regarding the meaning and representation of
heuristics, which are being explored with the AM's successor,
EURISKO [Lenat 82,83a,83b].
One significant lesson learned from AM, and being applied in EURISKO, is
(roughly) that explicit treatment of heuristics and meta-knowledge (as
well as assertive domain knowledge) is a necessary condition for learning
heuristics (and assertive domain knowledge). The main focus of the
EURISKO project is to investigate representation and reasoning/control
issues related to learning (heuristics, operators, and new domain
objects). Also, where concepts in AM were related to mathematical notions
(like Prime Numbers), flexibility is an important design criteria for
EURISKO, which is being applied to a number of problem domains (see
[Lenat 83b]).
Like AM, EURISKO is a frame based system which represents domain objects
in frames. However, where AM attached heuristics to slots in
concepts/frames, EURISKO represents heuristics themselves as frames. In
general, EURISKO goes much further than AM in explicitly defining and
representing knowledge at many levels; everything possible is explicitly
represented as an object. For example, every kind of slot (eg. ISA,
Examples) has a frame associated with it, which explicates the meanings
and operations of the slot. This allows the system to reason with each
kind of slot (as well as with the slot value), for example to know whether
a particular type of slot represents guaranteed, probable, or assumed
knowledge.
Part of the approach in EURISKO is to emphasize the importance of the
representation language itself in solving a problem. The RLL frame based
language [Greiner 80] was developed for this purpose. In RLL, almost
every object (notably including heuristics) is represented as an explicit,
discrete frame ("unit" as they are called in RLL). Thus heuristics become
objects which a system can use, manipulate, and reason about just like any
other object. Without going into details, RLL has a number of features
which are oriented toward explicit representation and manipulation of
domain knowledge, both factual and heuristic. It has a more sophisticated
"multiple-agendae" control structure which is itself represented as frames
in the knowledge base. Operations with and on frames include a lot of
bookkeeping by RLL, intended to retain explicit knowledge which was lost
in AM. Because heuristics are explicitly represented objects (frames), it
is possible for built-in or domain-specific knowledge to be applied to the
learning of heuristics (i.e. using built-in heuristics which specify how
to postulate and explore new heuristics).
EURISKO has been notably successful as both a learning and a performance
(expert) system in a number of domains. [Lenat 83b] describes the use of
EURISKO in playing the Traveller Trillion Credit Squadron (TCS) game,
where it has won two national tournaments, and discovered some interesting
playing strategies. In [Lenat 82a], EURISKO's application to "high-rise"
VLSI circuit design is described. EURISKO constructed a number of useful
devices and circuits, and has discovered some important heuristics for
circuit design.
----------
Greiner, R., Lenat, D. 1980. "A Representation Language Language." Proc.
AAAI 1, pp. 165-169.
Lenat, D.B. 1976. "AM: An artificial intelligence approach to discovery
in mathematics as heuristic search." Ph.D. Diss. Memo AIM-286,
Artificial Intelligence Laboratory, Stanford University, Stanford, Calif.
(Revised version in R. Davis, D. Lenat (Eds.), Knowledge Based Systems
in Artificial Intelligence. New York: McGraw-Hill. 1982.)
Lenat, D.B. 1982. "The nature of heuristics." AI Journal 19:2.
Lenat, D.B. 1983a. "The nature of heuristics II." AI Journal 20:2.
Lenat, D.B. 1983b. "EURISKO: A program that learns new heuristics and
domain concepts, The nature of heuristics III." AI Journal 21:1-2.
----------
Rob Allen <ALLEN ROBERT@LLL-MFE.ARPA>