Copy Link
Add to Bookmark
Report
AIList Digest Volume 4 Issue 121
AIList Digest Saturday, 10 May 1986 Volume 4 : Issue 121
Today's Topics:
Queries - Inferring Program Structure & Machine Translation & Prolog,
Literature - Object-Oriented Programming,
Expert Systems - Expert Systems and Decision Trees
----------------------------------------------------------------------
Date: 8 May 86 13:51:13 EDT
From: Angela.Hickman@ML.RI.CMU.EDU
Subject: References needed!
[Forwarded from the CMU bboard by Laws@SRI-AI.]
I recently received e-mail from a former professor asking for some
references. Below is part of his mail. If you know of any references in
this area, please send mail to ach@ml.
_____
I have a student who will probably do a piece of work in software
engineering. The idea is to take existing programs and try to infer data
structures and data flow. The trick is that these will be large program
systems (many modules), written and "enhanced" (~= "modified" or
"corrected") by many people over some time. Furthermore, they will not have
been designed or built with any of the modern software development
methodologies. In short, they will be real programs that have been
maintained by many people.
Part of the work may involve expert systems and AI work to develop a rules
base to infer the structure. Do you know of anyone doing work in any of
these areas?
------------------------------
Date: 9 May 86 03:27:00 EDT (Fri)
From: Hideto Tomabechi <tomabechi@YALE.ARPA>
Subject: machine translation
I would like to know what types of machine translation projects are
underway now, especially in universities. I have been working on
English-Japanese translation myself. I hope to share our opinions in
this field. If anyone is currently working on machine translation, I
would appreciate it if I can receive some information about your on-
going project.
Hideto Tomabechi
Yale University
tomabechi@yale.arpa
------------------------------
Date: 8 May 86 02:04:05 GMT
From: decwrl!glacier!oliveb!bene!luke!itkin@ucbvax.berkeley.edu
Subject: looking for Prolog
I'm looking for a version of Prolog. The machines available to me
include an AT&T 7300 (Unix PC), AT&T 3B5, AT&T 3B2, Plexus P/60, Plexus
P/35, IBMPC, and AT&T 6300PC (IBMPC compatible). I've spoken with
someone from AT&T who suggests that Quintus may be porting to the 7300.
I've spoken with someone from Quintus who says there is no port and no
contract at this time. I've heard of something called C-Prolog, but
don't know for sure what it is.
What I'm looking for is a system on which I can begin to learn Prolog
and prototype some applications. Any help will be GREATLY appreciated.
Public domain or commercial is fine, as long as the price is reasonable
or I can convince my employer.
advTHANKSance
--
***
* Steven List @ Benetics Corporation, Mt. View, CA
* Just part of the stock at "Uncle Bene's Farm"
* {cdp,engfocus,idi,oliveb,plx,tolerant}!bene!luke!itkin
***
------------------------------
Date: Wed 7 May 86 23:25:20-PDT
From: Hiroshi G. Okuno <Okuno@SUMEX-AIM.ARPA>
Subject: Re: What's a good book on Object-Oriented Programming
[Forwarded from the Stanford bboard by Laws@SRI-AI.]
If you can read Japanese, I would recommend you the following book:
"Object-Oriented Programming" edited by Norihisa Suzuki, Kyoritsu
Publishing Co., (Dec. 1985), 2,500 yen (about $14.00).
Contents: Introduction to Smalltalk, Actor, TAO, Concurrent Smalltalk,
Prolog environments written in Smalltalk, CAI on Physics written in
object-oriented system, etc.
Why do I recommend you this book? Of course, because I'm one of
co-authors.
P.S. Sayuri (Nishimura@sumex) and Masafumi (Minami@sumex) have a book.
- Gitchang -
------------------------------
Date: Thu 8 May 86 08:40:36-PDT
From: Bob Engelmore <Engelmore@SUMEX-AIM.ARPA>
Subject: Re: What's a good book on Object-Oriented Programming
[Forwarded from the Stanford bboard by Laws@SRI-AI.]
And if you can't read Japanese, I recommend reading the article by
Mark Stefik and Danny Bobrow in the AI Magazine, Vol. 6, No.4,
Winter 1986. However, I'm biased about articles in that rag.
rse
------------------------------
Date: Thu 8 May 86 08:57:37-PDT
From: Mark Richer <RICHER@SUMEX-AIM.ARPA>
Subject: Re: What's a good book on Object-Oriented Programming
[Forwarded from the Stanford bboard by Laws@SRI-AI.]
There's a new introductory book (available now or soon) on SMalltalk
by Kaehler, Ted and (I think) Patterson, Dave that is supposed to be a
very good and relatively inexpensive book on Smalltalk, the
"protypical" object-oriented programming language. Of course, there
is also the Addison-Wesley series on Smalltalk, more expensive,
detailed, and harder to carry around with a bag of groceries.
mark
------------------------------
Date: Thu 8 May 86 10:39:36-PDT
From: Marvin Zauderer <ZAUDERER@su-sushi.ARPA>
Subject: Re: Good book on object-oriented programming
[Forwarded from the Stanford bboard by Laws@SRI-AI.]
Mark Richer's correct; the new Smalltalk book, "A Taste of Smalltalk",
was written by Ted Kaehler and Dave Patterson. I don't believe Addison-
Wesley has published it yet, although I was told it's due "sometime
in 1986." It's a good introduction to Smalltalk; actually, it's more
of an introduction to Smalltalk than a detailed explanation of object-
oriented programming, although any introduction to Smalltalk
necessarily involves a (brief) introduction to obj-or programming.
-- Marvin
------------------------------
Date: Fri, 9 May 86 04:53:30 EDT
From: ihnp4!lzaz!psc@seismo.CSS.GOV
Subject: Non-trivial expert systems and decision trees - THE RESPONSES!
How pleasant! I got several thoughtful replies to my comments
on experts systems and decision trees. I'd like to thank all
the people who sent me mail. I've summarized the responses
below. I never got what I was *really* looking for, namely, a
good benchmark expert system. More on that after the summary.
The general consensus is that rule based expert systems offer no
more power than decision trees, in just exactly the same way
<your favorite programming language> offers no more power than a
Turing machine. Of course, there are advantages. . . .
===== discussing the problem off the net, I wrote:
My "crisis of faith" has two prongs on it. First, it seems you could
write a production compiler to generate the decision tree from the
productions. The compiler would need a lot of resources, but the
resulting "compiled" expert system would run quickly and in very little
memory. (Other, tougher objections: user can't direct search,
uncertainty hard to track, and only works with forward chaining.)
[Note: going over some other mail I'd received, I discoved an
expert system shell named Radian does just this. It translates
a set of rules into a decision tree implemented as a C program!
The resulting program can explain itself. psc]
Second and more disturbing, *every* example "expert system" I've ever
seen uses productions was written by someone who *first* drew a decision
tree! That's clearly missing the point. I'm looking for systems that
are "non-trivial", not in the sense that they have a lot of rules, but
in the sense aren't just solving a problem that's *better* solved by a
straightforward decision tree. Know of any?
===== Dale Skran (ihnp4!mtgzz!dls):
In general all expert systems can be reduced to
tree searches which can be mapped into pattern matching
operations. . . . The real savings of rule based systems
is that you just add rules and skip the tree.
===== dchandra@TRILLIAN.ARPA identified five kinds of rules:
a) rules for strategy (meta rules)
b) rules for inheritance between objects.
c) rules for normal inference (equivalent to decision tree)
d) rules which create new rules (we have built a rule shell
called IMST which provides this feature. ) We have a system
called CDLII which uses this feature to post constraints.
e) rules can exist in packets and can communicate
through global and local blackboards. Decision trees
do not have a notion of private and global databases.
Decision trees emulate only part (c) above. . . .
Consider this statement: All non-lisp machine AI programs get
compiled into assembly language. So what is so great about lisp.
LISP IS A DATA ABSTRACTION ABOVE ASSEMBLY.
RULEBASED SYSTEMS ARE A ABSTRACTION ABOVE DECISION TREES OR
OTHER LOW LEVEL STUFF.
===== Jean-Francois Lamy <ihnp4!utcsri!lamy%utai>
It does seem to turn out that once you have written down all the
rules and got the system to work the way you want you now
understand the problem well enough that you don't need the fancy
and inefficient AI solution anymore.
One has to realize that not all problems are amenable to
formulation using the brain-damaged OPS5-like production rules
systems. In particular, problems which require a HUGE amount of
implicit knowledge about the world don't quite fit. Consider
story understanding or finding causal relationships in data that
requires multiple forms of reasoning (e.g. heart physical
malfunction, electrical malfunction, chemical unbalance).
===== Bruce Morlan (pur-ee!rutabaga) goes out on a limb for trees:
At risk of being burned for heresy, I would claim (in my dissertation
I will claim) that there is no significant difference between the
following three systems:
(0) rule-based expert systems,
(1) production systems,
(2) decision trees.
This is consistent with results documented in many places, and I would
refer first to Vol I of "The Encyclopedia of AI" for my first support.
This claim extends to experts systems with uncertainty, such as of
the MYCIN or PROSPECTOR class. In my research I have concluded that
the collection of rules from an expert must result in an data suitable
for use in a Markovian decision process.
Whether this applies to _all_ expert systems remains to be seen, and
I would be very interested in hearing about a system that didn't fit
this mold (as you alluded to in your posting).
===== Ehud Reiter (ihnp4!seismo!harvard!reiter):
Decision trees are both very useful and non-trivial to program
if you want to do it "right" (backward chaining, truth
maintainance, interactive graphical tree editing, multiple
solutions, explanations, etc. - I know because I've tried to
implement one). Whether marketing calls the program a "decision
tree" (which they should) or an "expert system" (which means
more sales) is irrelevant - it's still a useful but complex piece
of code.
===== Donald R. Tveter (ihnp4!bradley!drt) takes a useful step backwards:
In going thru graduate school and taking some AI courses,
it came to me that what I was seeing in AI courses, I had seen
before. I found the principles in an old Psychology book, I
had once read: Psychology, by William James, first published in
the 1890's. In his chapter on Association, he showed how people
think. A careful comparison between what he said then and what
people do now in their expert systems, shows up no significant
differences.
===== Mark R. Leeper (ihnp4!mtgzz!leeper):
Don't YOU make your diagnostic inferences by a decision tree?
It may not be a binary tree, but then expert systems don't have
to use binary trees either.
=====
Only Dale Skran suggested a benchmark expert system: the
"monkeys and bananas" problem. Usually shown in OPS5, this
system has a hungry monkey, a locked vault on the ceiling with
bananas, another locked vault with the key to the first, and a
ladder. (I may have forgotten a vault or key or two).
I'm not at all sure that the PC-based expert systems I'll be
reviewing can handle that problem! The difficulty is keeping
track of changing values (the monkey and the ladder move a
*lot*!) The one system I'm using now doesn't get past the
monkey's first move (in a very simplified version.) Of course,
if a particular expert system shell can't handle this problem,
that's useful information, too!
As a brute-force synthetic benchmark, I'm going to have the
expert system traverse a network of nodes equivalent to the
Towers of Hanoi puzzle, with some "cuts" (forbidden moves) that
force it to make twice as many moves as necessary. (In fact, it
must do the equivalent of moving the disks to the middle peg
first.) Both the cuts and resulting network are symmetrical,
keeping the comparison fair for forward- and backward-chaining
systems. A picture is worth a few thousand words: see Figure
2-2, page 82, in Nilsson's PROBLEM SOLVING METHODS IN ARTIFICIAL
INTELLIGENCE.
And I'll use the travel advisory system in the latest issue of
PC, if that doesn't require access to a full database system
(which only Guru has.)
I'm still not satisfied; any suggestions for benchmarks?
Thanks again for your comments.
---
-Paul S. R. Chisholm, UUCP {ihnp4,cbosgd,pegasus,mtgzz}!lznv!psc
AT&T Mail !psrchisholm, Internet mtgzz!lznv!psc@topaz.rutgers.edu
The above opinions may not be shared by any telecomm company.
AT&T Transaction Services - the right choice for point-of-sale networking.
------------------------------
End of AIList Digest
********************
