psc@lzaz.UUCP (Paul S. R. Chisholm) (05/09/86)
<submitted to mod.ai (aka AIList) and net.ai>
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.