Expert Systems
Volume Number: 2
Issue Number: 3
Column Tag: Lisp Listener
By John Roy
This month, Mactutors' Lisp Listener has a special exclusive. In the first few
installments of the Lisp Listener (nine months ago!) the question of how serious one
can be when it comes to AI on the Mac was raised. This month we can be confident in
saying that Mac can and is being used for developing real AI applications. Last summer
the International Joint Conference on Artificial Intelligence (IJCAI) was the place for
the unveiling of a relatively large number of AI related products for the Mac. These
included ExperLisp version 1.04, ExperOps5, MacProlog, Macscheme and as you will
see in what follows the first serious end user expert system development application.
John Roy has written for us a good description of what Nexpert is, what it does, and how
it does it.
PROGRAMMING IN NEXPERT
by John Roy
What are Expert Systems?
In one sentence, expert systems are programs that imitate human reasoning.
They recognize logical patterns that are similar to those recognized by humans, and
then reason with them to produce expert-like performance. The term "expert system
should not be confused with "rule-based system" nor "production system". These latter
two terms refer to implementation schemes, which are often used to build expert
systems.
The process of capturing expert reasoning is called knowledge engineering.
Previously, the knowledge engineer had to analyze a domain of expertise and socraticly
refine an expert system based upon that expertise until it performed as well as the
human. Eventually, these knowledge engineering pioneers found that declarative
(rather than procedural) programming paradigms are more appropriate when writing
an expert system.
LISP is used as the foundation of many expert systems because of its pattern
matching, language extension, and data typing capabilities. These capabilities allow AI
programmers to design declarative structures (which hold the expert's knowledge) and
inference engines (which imitate the expert's logic). NEXPERT's AI Kernel was
designed in LISP on a Symbolics "LISP Machine" before being ported to the Macintosh.
What is NEXPERT?
NEXPERT is a full blown rule-base development environment for serious
knowledge engineering. It is the first rule-base development tool designed specifically
for writing expert systems on the Macintosh. It uses if...then...do... rules to represent
the domain expert's knowledge. It has many sophisticated aids for rule-base
development such as: automatic, graphical knowledge traces (better than those in
KEE); automatic forward and backward chaining from the same rules (as in ART); an
automatic dialogue system (as in PROLOG); an automatic explanation facility (How,
Why, and Apropos); access to external data bases (those in SYLK form); and execution of
external, compiled programs (such as those developed in C).
It does not have a frame system, nor automatic belief maintenance. Not
incorporating a belief maintenance system was a good idea, since no general theories
are available, and each expert system must tailor uncertainty handling to the specific
application. However, no frame system access means (1) no object oriented data
structures, (2) no message passing, (3) no inheritance of attributes, and (4)
instantiation of flavors. Frame systems concern design, maintenance, and manipulation
of extremely large data bases. For applications where the data base management system
already exists, or for which the data base is small (less than 1000 data values), or for
which there is a simple taxonomy, the external SYLK file access and external program
execution can easily be used to interface and manipulate the applicable data bases.
Enough introduction, let's get down to business.
Basic NEXPERT Programming.
The Rule Editor, shown in Figure 1, is where you view the rules and choose what
operation to perform. By clicking on the dog-ear, the pages can be flipped forward and
backward. The rules are alphabetically indexed by Hypothesis (which is how the
buttons on the right allow rapid movement through the list). It is a bit difficult to
understand the rule-base as a whole from only viewing one rule at a time, but the
Network discussed later gives the rule-base developer a global view. There are similar
windows (called Notebooks) for the Data List and the Hypothesis List. Selection of a
rule-base operation is made by clicking on one of the icons at the bottom of the Rule
Editor. From the left they are; (1) create a new rule, (2) modify the current rule,
(3) create a new rule by copying the current rule, (4) delete the current rule, and
(4) save the knowledge base.
I've found that creating a new rule by copying a similar one, is the best way to
go, particularly since all of the rule conditions are ANDed together, and the only way to
achieve an OR is to create another rule with the ORed condition modified. This is the
same with OPS5, though OPS5 has a MEMBERSHIP operator and NEXPERT does not.
Once an operation has been selected what I call the rule template interface
appears. This is the main development interface. One enters and modifies all of the
rules from this rule template interface. All you need to do is fill in the conditions, the
hypothesis, and the actions via the pop-up menus shown below. Note that currently
only eight (8) conditions and actions can be used in a single rule (i.e. # of conditions +
# of actions < 9). If the rule had more than eight, then two rules must be written such
that they link together and fire in order. One of the nicest, and oddly important,
capabilities available are COPY DATA and COPY HYPOTHESIS. These prevent the
rule-base developer from re-typing, and more importantly, misspelling data and
hypotheses. Note that NEXPERT is case sensitive, and does not allow spaces within the
names given to data.
I've pasted this window together so that all of the pop-up menus are visible at
once. The basic rule template (underneath the three pop-up menus) consists of the IF
slots, the THEN slot, the AND DO slots, and the CONTEXT slots. By clicking on a slot the
appropriate menu will pop-up. Don't worry about the context slots right now, they are
an advanced programming feature that allow the rule-base developer to suggest
knowledge island transitions, (fully explained in a future article, and needed only for
extensive rule-bases). The menu at the left shows all of the tests available to form
rule conditions (see Table 1). The menu at the right shows all of the actions that can be
performed (see Table 2). The menu in the middle (slightly covered by the other
previously mentioned menus) is for entering arguments and equations. The COPY DATA
and COPY HYPOTHESIS are available from this menu.
Table 1 - Condition Tests
CANCEL do nothing
CLEAR clear test slot
YES and NO test boolean
>, <, ≥, ≤, =, ≠ compare numeric equation to constant
NAME declare global synonym
IS and IS ≠ compare multi-valued datum to constant
RESET set datum to "unknown
EQUAL and
UNEQUAL compare two multi-valued data
Table 1 - Action Operations
CANCEL do nothing
CLEAR clear operation slot
DO perform numeric equation and assign to datum
LET assign multi-valued datum a constant
RESET set datum to "unknown
SHOW either type out a text file to the Apropos Window
or pop-up a paint picture to fill the screen
LOADKB append another knowledge base to current one
EXECUTE perform external function
RETRIEVE load data from an external SYLK file
Once the rule has been entered the OK button will only darken if the rule is
structured properly. Clicking on the CHECK button will highlight the offending slot. If
the rule is properly structured, but a datum is misused (eg. using a previously defined
boolean in an equation), a message will appear (after the OK button-click) explaining
the problem. This is very nice most of the time but can be a pain if you decide that you
would like to change the data type of a datum.
NEXPERT has two basic values that any datum may have: NOTKNOWN and
UNKNOWN. NEXPERT uses UNKNOWN as the "reset" value. Whenever a datum's value is
needed and it is currently UNKNOWN, then NEXPERT will switch to backward chaining
to attempt to establish a value from the data already available. If this is unsuccessful
then the user is queried, via the Question Window, for a value. NOTKNOWN on the other
hand, is used to mean that the user has been questioned and does not know the answer.
NOTKNOWN allows default reasoning to be done and pr events NEXPERT from continuing
to ask for a value that the user does not know.
Knowcessing
"Knowcess" is the term for the rule-based inferencing process. This is where
NEXPERT's AI Kernel shows what it is made of. The process can be initiated by
suggesting an hypothesis or volunteering a datum. One may also use a combination of
the two. If any data is volunteered, then the system will drive forward, attempting to
establish as many hypotheses as possible. You can control this forward chaining via
NEXPERT's Strategies (see next NEXPERT article for when, why, and how this should be
done). If one only suggests an hypothesis, NEXPERT will begin by looking backward in
an attempt to find sufficient information that will prove this hypothesis. This
information can lead the system to other hypotheses that need to be established, which
can lead to others, which lead to others, etc.
Once the system reaches a rule that has some UNKNOWN datum in it, the user
will be prompted for a value (see the example in Figure 3 below). At this point the
user can access the multi-level Explanation Facility (via the WHY? and HOW? Buttons
), which is automatically built from the static forward and backward chains already in
the rule-base. Note that the system knows that the example datum BOSS-CALLED is a
boolean and that the user may answer NOTKNOWN. The last button, Apropos, is for
tailoring the system to the application even more. When any Apropos Button is clicked
on, NEXPERT will bring up the file (text or pictures) that the rule-base developer has
made for this datum. This is very useful for instructing the user about the meaning and
use of a specific datum.
There are other windows that allow the rule-base developer to watch the
progress of the Knowcess. The Transcript Window keeps a complete record of the
session, but it slows down the processing by a factor of eight. There is the option to
turn the Transcript Window off, which I always use at run-time. The Hypothesis
Window displays the hypothesis currently under consideration. And the Conclusions
Window reports whether the hypothesis was rejected, established, or underdetermined.
But the best way I have found to debug a rule-base is to get a global view.
As I said before, the way to get a global view is from the Network. This is an
automatic, dynamic, graphical knowledge trace. Figure 4 shows NEXPERT in the middle
of the KNOWCESS process. The dynamics of the system can be followed by noting (a) in
this example, the datum TIME points to the hypotheses DAYTIME, NOON, and WORK, (b)
that DAYTIME and NOON have already been established, (c) that the system is
considering the hypothesis WORK, and (d) that it is currently prompting for the value
of the datum BOSS-CALLED (see arrow and bulls-eye in the lower left corner).
Using the operation icons on the left, the rule-base developer can "navigate
through the knowledge islands." The functions called by these icons allow investigation
of only those areas of the knowledge graphic that are currently of interest. From the
top, the operation icons are: (1) single or multiple knowledge island display, (2)
display data that point to this hypothesis, (3) display hypotheses that this datum points
to, (4) erase this link, (5) focus attention on this datum or hypothesis, and (6)
apropos this datum or hypothesis. These operations only affect the display, not the
actual knowledge graph of the rule-base. From this one window all of the rules can be
viewed, all of the links between rules can be checked, and the dynamics of the Knowcess
process can be monitored; making it an excellent aid in the debugging of a rule-base.
Overall, the programming environment of NEXPERT is very clean and efficient.
In the next article on NEXPERT I'll be addressing the more complex issues of the AI
Kernel, Controlling the Agenda, Customizing the User Interface, Speeding-Up Execution,
Outside Database Access, and of course a Full Bug Report.
