Copy Link
Add to Bookmark
Report
AIList Digest Volume 2 Issue 027
AIList Digest Thursday, 8 Mar 1984 Volume 2 : Issue 27
Today's Topics:
Automatic Programming - Request for Bibliography,
Pattern Recognition - Request for Character Recognition Algorithms,
Expert Systems - Request for MYCIN Source Code, Tutorial,
AI Tools - IQLISP Source,
Mathematics - The Four-Color Theorem,
AI Literature - The Artificial Intelligence Report,
Expert Systems - EURISKO/AM Overview
----------------------------------------------------------------------
Date: 6 Mar 1984 1612-EST
From: CASHMAN at DEC-MARLBORO
Subject: For AI digest: request for program synthesis bibliography
Does anyone have (a pointer to) a bibliography (preferably annotated) of
papers on program synthesis? Is there a good survey paper or article on
the field (other than what's in the Handbook of AI)?
-- Paul Cashman (Cashman@DEC-Marlboro)
[Richard Waldinger (@SRI-AI) suggests a survey and bibliography on
program synthesis in "Synthesis: Dreams -> Programs" which appeared in
the IEEE Transactions on Software Engineering about 1975. -- KIL]
------------------------------
Date: 7 Mar 1984 0643 PST
From: Richard B. August <AUGUST@JPL-VLSI>
Reply-to: AUGUST@JPL-VLSI
Subject: SEARCH FOR PATTERN/CHARACTER RECOGNITION ALGORITHMS,
ARTICLES ETC.
BEGINNING RESEARCH ON CHARACTER RECOGINITION TECHNIQUES.
OBJECTIVE: DEVELOP CHARACTER INPUT DEVICE (WAND) TO ACCEPT THE MAJORITY
OF FONTS FOUND IN PUBLICATIONS.
POINTER TO PUBLICATIONS ARE HELPFUL.
THANKS
REGARDS RAUGUST
[The international joint conferences on pattern recognition would
be a good place to start. Proceedings are available from the IEEE
Computer Society. A 1962 book I've found interesting is "Optical
Character Recognition" by Fischer, et al. Good luck (you'll need
it). -- KIL]
------------------------------
Date: Wed, 7 Mar 84 14:14:35 PST
From: William Jerkovsky <wj@AEROSPACE>
Subject: MYCIN
I would like to execute a simple problem on MYCIN. I have recently gotten
interested in expert systems; since my wife is bacteriologist I think both
of us would enjoy the interaction with the program via our home computer
(terminal).
Can anyone point out the way to get a (free) copy of MYCIN (even if it is
only a simple early version)? Is there a way I can execute a version
interactively from home without actually getting a copy? Does anybody know
of an on-line tutorial on MYCIN? Is there a simple version of MYCIN (or a
reasonable facsimile) which runs on an
Apple //e or on an IBM PC?
I'll appreciate whatever help I can get.
Thanks
Bill Jerkovsky
------------------------------
Date: Tue 6 Mar 84 15:48:55-PST
From: Sam Hahn <SHahn@SUMEX-AIM.ARPA>
Subject: IQLISP Source
The source for IQLisp is:
Integral Quality, Inc.
P.O. Box 31970
Seattle, WA 98103
(206) 527-2918
Claims to be similar to UCI Lisp, except function def's are stored in cells
within identifiers, not on property lists; arg. handling is specified in the
syntax of the expression defining the function, I/O functions take an explicit
file argument, which defaults to the console; doesn't support FUNARGS.
IQLisp does provide:
32kb character strings,
77000 digit long integers,
IEEE format floating point,
point and line graphics,
ifc to assembly coded functions,
31 dimensions to arrays,
Costs $175 for program and manual, PCDOS only.
I've taken the liberty to include some of their sales info for those who may
not have heard of IQLisp. It's fairly new, and they claim to soon make a
generic MSDOS version (though probably without graphics support).
------------------------------
Date: Wed, 7 Mar 84 09:16 EST
From: MJackson.Wbst@PARC-MAXC.ARPA
Subject: Re: The Four-Color Theorem
By "planar map" in my previous message I meant to connote a structure on
a two-dimensional surface, not strictly a flat plane. In fact, the
plane and the sphere are topologically equivalent (the plane is a sphere
if infinite radius) so four colors suffice for both; for the torus,
which has a different "connectivity," it has long been known that seven
colors are both necessary and sufficient.
I'm not a mathematician but at one time (right after reading an article)
I felt as if I understood the proof. As I recall it is based on the
fact that if there are any maps that require five colors there is a
minimal (smallest) map that requires five colors. It is possible to
construct sets of graphs (representing map regions) of varying
complexity for which any map must include at least one member of the
set. It is also possible to determine for some particular graph whether
it can be "reduced" (so that it represents fewer regions) without
altering its four-colorability or its interactions with its neighbors.
Clearly the minimal five-color map cannot contain a "reducible" graph
(else it is not minimal).
Evidently, if one can construct a set of graphs of which ANY map must
contain at least one member, and show that EVERY member of that set is
reducible, then the minimal five-color map cannot exist; hence no
five-color map can exist. Now if it were possible to construct such a
set with, say, 20 graphs one could show explicitly BY HAND that each
member was reducible. No one would call such a proof "ugly" or "not a
true proof;" it might not be considered particularly elegant but it
wouldn't be outside the mainstream of mathematical reasoning either (and
it doubtless would have been found years ago). The problem with the
actual case is that the smallest candidate set of graphs had thousands
of members. What was done in practice was to devise algorithms which
would succeed at reducing "most" (>95%?) reducible graphs. So most of
the graph reduction was done by computer, the remaining cases being done
by hand. (I understand that to referee the paper another program had to
be written to check the performance of the first.)
I would like to hear any criticism of the Illinois proof that is more
specific than "ugly" or "many feel that this does not constitute a true
proof." A pointer to the mathematical literature will suffice; my
impression is that the four-color theorem is widely accepted as having
been proved. (We may be getting a bit far afield of AI here; I would
say that my impression of the techniques used in the automatic reduction
program was that they were not "artificial intelligence," but since they
were manifestly "artificial" I hesitate to do so for fear of rekindling
the controversy over what constitutes "intelligence!")
Mark
------------------------------
Date: Tue 6 Mar 84 10:58:51-PST
From: C.S./Math Library <LIBRARY@SU-SCORE.ARPA>
Subject: The Artificial Intelligence Report
[Forwarded from the Stanford bboard by Laws@SRI-AI.]
I have received a sample copy of the Artificial Intelligence Report, vol. 1
number 1, January 1984. It is being published locally and will have ten
issues per year. It is more of a newsletter type publication with the
latest information on research (academic and industrial) and applied AI
within industry. The cost is $250 per year. The first issue has 15 pages.
I will place on the new journal shelf. [...]
[I may try to start charging for AIList ... -- KIL]
------------------------------
Date: Tue, 6 Mar 84 16:50 PST
From: "Allen Robert"@LLL-MFE.ARPA
Subject: EURISKO/AM review (415) 422-4881
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>
------------------------------
End of AIList Digest
********************
