Download Method for obtaining information in an expert system

United States Patent [191
[11]
Patent Number:
4,763,277
Ashford et al.
[45]
Date of Patent:
Aug. 9, 1988
[54]
4,675,829
METHOD FOR OBTAINING INFORMATION
6/l987 Clemenson ........................ 1. 364/513
IN AN EXPERT SYSTEM
OTHER PUBLICATIONS
[75] Inventors: Thomas J‘ Ashford’ 83.“ Jose’ Cam‘;
Mitsura Ishizuka, “An Extension of Dempster & Sha
g”: F d
-
'
‘3 e -
fer’s Theory to Fuzzy Set for Constructing Expert Sys
e -
terns", 7/32, pp. 26-29.
Rep' 9f Germany} Chrisune T‘
Iwask‘lw’ Columbla' Md]; Roberta P’
[73] Assignee:
Mitsura Ishizuka, Another Extension of Dempster &
Shafer’s Theory to Fuzzy Set for Constructing Expert
5mm“, Pasadena’ Callf-
Systems, 9/83, pp. 43 and 43.
International Business Machines
priman, Examme,_Gary v_ Harkcom
Comma”, Amonk’ N'Y'
[21] APPL NOJ 319,663
[22] Filed:
[51]
[52]
Jan. 17, 1986
[57]
Int Cl 4
U
"""""""""""""""""""
'
Assistant Examiner-Randy W. Lacasse
Attorney, Agent, or Firm—Richard E. Cummins
ABSTRACT
G06‘; 15/18
364/900‘
A method for use in an expert system which selectively
allows the system to avoid asking the user a question by
’ 364/306
providing the answer to that question based on related
' """"""""""""""""" "
[58] Field of Search .......... .. /APS- MS File; 364/513,
-
311mm?“
‘Th5’e matyhggvfs
be?“ prevml’jiy amine‘: i“
e sys em.
me
1nvo ves provl mg an ac ion
364/550’ 200 MS File’ 900 Ms F116’ 300
References Cited
Us. PATENT DOCUMENTS
attribute that can be attached to any node in the rule
tree. The attribute is assigned to a node in the tree
which provides an answer to a class question based on
processing various other dependent nodes. When the
[56]
4,479,241 10/1984 Buckley .............................. .. 382/15
answer is obtained, the action attribute then causes all
459L983 5/1986 Bennett et a1‘ "
322/403
other nodes in the rule base referencing the same class
21ml‘. 6: :1!‘
4’644’479 2/1987 K225; at a‘:
3
364/550
question to be set to the same answer. The user is there
fore only requested to supply information as a last re
364/513
8°“
4,648,044
3/1987
4,649,515
4,658,370
3/1987 Thompson et al. .
364/900
4/1987 Ennan et a1. ..................... .. 364/513
Hardy et al. . . . . . . . .
. . . ..
9 Claims, 14 Drawing Sheets
m: mm mm
lll‘tt “UNIS
71:
m: CDIPlLEI
(201151111111
{-
l
_
_
l “
NI‘ILIDRULE
FYLES
_
—
om
|
._
_
_
_
---1
'
"m": 5
r 11 |
|
,
III'EIENCE
um:
rtunsulrl
i
H
_ _ _ :_
i
I
'
_ q _ _
1 1'3“ Q
l
j
"elm .TL
w
,
I‘
_
mttnunr
c111 cm
mlum
L5
mtruulr
H m:
-
unrmct
1
1
I
_|
PIMEOIJIE
"NEW" A
um
US. Patent
Aug. 9, 1938
4,763,277
Sheet 1 0f 14
ms mm rm
RULE WRITERS
PIE
47
RULE COHPILER
‘
(cousmum
|_
_
'I
COIPILED RULE
Fl
LES
!
_
__
‘E
_
__ __ _'_ _
:
SUPERVISOR 42
|
INFERENCE
0m *____- Lam
|
(comm
_
_
Wm“ Ls
|_
|
cm 00-
,4
(momma
-
_
__
_
L
PROCEDURE
_
|
mums:
I
_
_
PRMDURE a
PROCEDURE A
I
AND
2_1
EVIDENCE;
'YES' T0 ‘ARE
"28
THEREREAD/
-
WRITE mans?‘
FIG-
_2_g
EXTERNAL
REFERENCE
2.3.
a
|
NUDE
_
PROCEDURE n
cm;
'm msmrs mm‘
21
l
‘3
PROCEDURE
|
_]
I
_ __ _ I.
FIG. 1
_
"a?"
I“
AC E +
m
,
I
_
2
_1
US. Patent
Aug. 9, 1988
Sheet 2 0f 14
4,763,277
CLASSES
PRINTER
TEXT *‘OOES YOUR PROBLEM SEEM TO INVOLVE YOUR PRINTER"
VALUES '4 OF I'YES' 'HO')
PREDEFIHEO WEIGHT - 4
IBH52I5
TEXT-‘ARE YOU USING AH IBH 5245 PRINTER?’
VALUES ' 4 OF
(‘YES' 'NO')
PREDEFIHED WEIGHT - I
SYHPTOH
TEXT - ‘DO YOU NOTICE ANY OF THE FOLLOWING SYIIIPTOHS;
(I)
CHARACTERS IISSIHC
(2) CHARACTERS HISFRIHTIHC
(3) CHARACTER SHUOGED
I4) PAPER FEEDS CROOAED
(5) MORE OF THE ABOVE '
VALUES ' I OF L5
PREDEFINED HEIGHT ' 4
PRIHTERLITE
TEXT I ‘IS THE LIGHT BLIHIIIHC ON THE FRONT OF YOUR PRINTER?‘
VALUES ' 4 OF ('YES' 'HO')
PREDEFINEO WEIGHT '1
FIG.
3A
US. Patent
Aug. 9, 1988
Sheet 3 of 14
PROCEDURES
PR INTERTEST
NAME - PRINTERTU
PASS 32 767
‘A SVC NUMBER
RETURN STATUSB IT HEY (I I
%
END
PARAMETERS
PR INTERNUMBER
TEXT -
‘WHAT IS THE NUMBER OF YOUR PRINTER? '
DEFAULT
-
' IBM '
RULES
5L RULE TREE 4 BC
I
CDAL
TEXT - ‘ INSTALL A NEW ELEMENT DR R I BBDN. ‘
NAME -
2
CDALI
DR
NAME - LEVEL2 DR
3
AND
NAME - RIBBON
4
EVIDENCE
NAME *
PRINTERI
CLASS ' ( ‘YES’ ) DF PR INTER
4
EV IDENCE
NAME - YES 521 5
CLASS - I‘ YES‘ I BE IBMSZI 5
3
EVIDENCE
NAME ' SYM PTOM‘I
CLASS - I BE SYMPTDM
‘A RULE TREE 2 %
I
COAL
TEXT -
lit-MN
' REPORT SERVICE REDUEST NUMBER I51 DIB
FOR THE PRINTERNUMRER PRINTER. ‘
AN 0
NOT
REFERENCE
NAME -
RIBBD N
DR
EXTERNAL
PRDC -
PRINTERTEST
STATU SBI T NE '00‘ NB
EV I DE NCE
CLASS - (‘YES ‘I (If PR INTER L ITE
EVIDENCE
CLASS I
2 OF SYM PTDM
FIG.
3B
4,763,277
US. Patent
Aug. 9, 1988
Sheet 4 of 14
4,763,277
RULE TREE 4
mi
com
INSTALL ELEMENT on mason
NAME‘
LEVELZOR
0R
|
MN‘
~
R'BM
Hm
EVIDENCE:
4T0 snmou
'
m5
srmom
NAME
PRlHTE
EVIDENCE‘
‘YES’ T0 PRINTER
EVIDENCE:
'vzs' T0 M5245
Fl G .
um
TES5245
4
RULE TR£E 2
REPORT SRN 151 048
AND
1
'
uor
W
0R
EVIDENCE:
2 T0 snmou
REFERENCE:
EXTERNAL:
EVIDENCE:
NAHE-
PROCEDURE -
'vEs' T0
meow
PRINTERTEST
PRINTERUTE
smusan <>o
FIG. 5
US. Patent
Aug. 9, 1988
Sheet 5 0f 14
4,763,277
11
_
k_[
\
mx.za@oH3O|mwn?0h5.zxu.Ea1mj:_bh54m<2z
_
\
_
\
I]Nx.zmnOHP:MQ‘oaF5m<0z:umatEH2buka4:“m2
_
\
Tu"x=m3.n0w“5Lxozu*3H‘;m:z
TAmXNg4O.Qom?HZwz3-ajnmu:2hz
m
_
w
<.
IN5.zaQ1H3nH2m05m<oumm»;sz:a‘2Dh54nm2:
TmxIFqorm?Aiuz4asJm:hz
v
M
n
,
|_
70
Fu
7m
mnzm
|—
Tum
US. Patent
Aug. 9, 1988
Sheet 7 0f 14
4,763,277
S ZE
MFW ARNMTUD VRIBPAENDOT.{LI- TANaln- HEVRO
v!I-|
A-.VlLRGRI NEPR
E!|
AVrI.GC
FAR
AGEYTINVERA I“LIlIuRT 0LAID“RUVE SAU‘RTF|.UN0EUNFA
L
STuF.
T..
‘Lrum“
FIG. 7
:0
in
um
5U
P o N T i in
‘RLE
54|20
25-
PAR NEXT! WORD RULE PAR‘
5-7
8
00n0
-
:0 4
W'aOoRD OCIoLAS P.'Danoc
FIG.
\l \
CIlLA‘H.S P.lROiC‘
6N.EXT
Q
a
NIL
O
US. Patent
Aug. 9, 1988
PTR FROM
CLASS-
mew TABLE
mm
Sheet 8 of 14
HASH
JRULE
"W
LE
9_o
CLASSREF
IHDX
E
7
.,
more
sou
gsmscc ASS
"‘
S
L
ms mozx
w
RULEREF 95
mes
::
==
-
MEMBERSHIP usr roman
‘' L F
s2
FIRST
m5 RULE uons-
ME
Fl
4,763,277
;
91
94
9_5_
-
PROPERTY usT POINTER
um cuss POINTER
1
FROM
_
TABLE
-
HASH
m
PROPNAIE
9-6
97
mm mm
PROPNAME
FILEINDEX
PR IOP
NEXTPROP
v11
.
FLAGS
'
MEMBERSHIP
PROPNAHE
‘
PROPERTY
"EXTPROP
I
'
'
um cu ss POINTER
_
l
um PROP
.
l
I
.
e
9B
'
mm
.
99
402
“P, HEXTHEIBER —/————~
.
HASH PTR on
/ NEXTPRQP
401
F IG .
Jig-EL.
l
RULE NUDE
US. Patent
Aug. 9, 1988
PTR FR nu
Sheet 9 of 14
men E AD
4,763,277
RULE NUDE - FIRST RUL E
um TABLE
usmc TH IS PRO CEDURE
_. FILEINDEX
F'Lmw
PM F U "C
1L5“7
HASH TABLE
1T_0 PROC TOCALL
PR T o R
PRUPNAHE
wT
RULEREF m
ms 5
PROPERTYLLG
1- ~-
TL
MEMBERSHIP
m
T
j
f
ARBHEAD
PROPNAHE
mum
:}
IIEITPROP
@
I
1
[H8
mm
_.
g:
NEXTPROC
- - -
,
424
m PROPERTY
:;
“
l
“720/ NEXTNEHBER
NEXTPRDP
NEXTPROP
I
I
VARIABLE
VALUE
CLASSRESP
PROPNAME
:;
i;
NEXTPROP
rnocuux
NEXT ARC
ms
VALUE
NEXTRETURN
1
VAR ‘ABLE
mu
_
CLASSRESP
I
mT m
.
F I s. 10
J
US. Patent
Aug. 9, 1988
Sheet 10 of 14
4,763,277
F l G . 4 ‘I
mums
HASH TABLE ENTRY
431
1
2
PAP-“REF
w
~
~
1
FILEINDEX
omuu
I
um
rues
PROPERTY
NEXT PARA!
f 432
€ 33
.-/
nonz w r TH rm
us I nc nus
PARAH
==
f
4
50
F I L E INDEX
‘
DEFAULT
W5
J:
PROPE RT r
HAGs
PROP, NAME
n man
A
mp Em
um PROPERTY
{as
E
PROP. NAME
um PARAH
’
A
EX FARM
NEXT PROP.
»
A
430
I
~
US. Patent
Aug. 9, 1988
Sheet 11 of 14
TOPRULE
HWQRC)
FILEH‘DEX
RULEREF
“0°57” E
4,763,277
FATHER
MEL
BROTHER
--—-——-o
ASSOC
cuusxu
man
IT
PTS
7 HI L
FLAGS
RULE REF
PROPKRTL um
um
FIRST sou
"W9
T
|
RULEREF
1
FATHER
FILEINDEX
NODETYPE
FILEINDEX
NODETYPE
Assoc
ASSOC
IT
PTS
PIS
FLAGS
NAME
NAME
I
son
RULEREF
IT
FLAGS
I
1‘
FIRST- LAST- FATHER
“0RD
LAST sou
F1R5T~ LAsF- FATHER
50*"
cous m son so:
‘_i_;
nLEnmEx
FILE l NDEX
I
mm PE
* REF *
I
ASSOC
I
W
I
FLAGS
I
um
|
' ASSOC
PTS
L
IT
PROPS
PTS
FLAGS
um —
— T- -—1
El RSTSON F1 "JR LASTSON
g __
__|._. ._
q
FILE INDEX
FILEINDEX
MODE TYPE
NODETYPE
ASSOC
ASSOC
WT
PTS
PTS
mes
mos
NAME
NAME
-F\ as}
50"
T
NIL
1L As} FIRSTI
NIL 50'‘
5°“
NIL
J
._
__
_
_
IT
FIGJZ
lusr
m L so"
US. Patent
Aug. 9, 1988
Sheet 12 0f 14
4,763,277
mauzwfm
3E
.
$2 3 .muzmEzH
_
m
_
0
y
m
OHwm:juaknzmErP<Q=
msozH
US. Patent
Aug. 9, 1988
Sheet 13 of 14
4,763,277
A
Type
Test
Printer
B
PAND
_____l
L____
AND
¢]__J
Liv
External
Test-Cable
E
OR
AND
RC = D
J
l_“\
Evidence
Value I '52‘ of
Test-type
F
G
H
I
External
External
External
External
Test-type
Test type RC=19
Test type RC=8O
Test-type
RC=52
SETC type Ir
SETC type =
RC = 99
SETC TYPE -
IBM 5219
5152
FIG léa
EPSON 2D
External
Test 52
7:
US. Patent
Aug. 9, 1988
4,763,277
Sheet 14 0f 14
A
F
Tyyp
Goal
Test Display
Display
Bad
8
C
AND
OR
C
D
E
H
External
External
External
Evidence_
Display 1
Cable-Test
Read-Display
Hatch I
RC = O
z 0
SetC Match = 1
FIG.
l'
1
4,763,277
2
well. The programs of an expert system are independent
of the problem domain (taxes) and serve to process the
data structures without regard to the nature of the prob
lem area they describe. For example, there are pro
grams to acquire the described data values through user
METHOD FOR OBTAINING INFORMATION IN
AN EXPERT SYSTEM
FIELD OF INVENTION
interaction, programs to represent and process special
organizations of description, and programs to process
lar, to an improved method in which answers to ques
the declarations that represent semantic relationships
tions solicited from the user may be obtained indirectly
within the problem domain and an algorithm to control
from related information previously collected by the 10 the processing sequence and focus.
system.
The general architecture of an expert system involves
two
principal components: a problem dependent set of
RELATED APPLICATIONS
data declarations called the knowledge base or Rule
U.S. application Ser. No. 6/749,076 ?led on June 26,
base, and a problem independent (although highly data
1985, in the name of and entitled “Method for Dynami
structure dependent) program which is called the infer
cally Collecting Current Data for Use in an Expert
ence engine.
System From Speci?ed External Processes and Proce
Individuals Involved with Expert Systems
dures," is directed to an expert system in which the
rulebase is segmented to permit use in computing sys
There
are generally three individuals having an inter
tems having limited memory capacity. U.S. application 20 action with expert systems. Primary among these is the
Ser. No. 6/748,789 entitled “Method for Dynamically
end-user; the individual who uses the system for its
Collecting Current Data for Use in an Expert System
problem solving assistance. In the building and mainte
From Speci?ed External Processes and Procedures,"
nance of the system there are two other roles: the prob
?led on June 26, 1985, and assigned to the assignee of
the present invention is directed to a method of collect~ 25 lem domain expert who builds the knowledge base, and
a knowledge engineer who assists the experts in deter
ing data in which an independent external process or
mining the representation of their knowledge and who
procedure can be initiated under the control of the
de?nes the inference technique required to obtain useful
expert system and results speci?ed and generated by the
This invention relates in general to methods for ab
taining information in an expert system and, in particu
problem solving activity.
process or procedure are returned to the expert system
for use in concluding speci?c Goal nodes.
30
BACKGROUND ART
Expert systems is a term applied to a special kind of
The End User
The end-user usually sees an expert system through
an interactive dialog, an example of which follows:
problem solving computer program. The general func
tion of expert systems is to solve (or assist in the solution 35 Q. Do you know to which restaurant you want to go?
of) problems normally addressed by highly trained and
A. No
experienced human experts. This is not a new goal; in
fact, many successful computer programs have
Q. Is there any kind of food you would particularly
achieved notable success in providing expert levels of
like?
performance in certain problem areas. What is different 40 A. Unknown
about expert system type programs is the approach
taken, and the resulting form of the program itself.
Q. Do you like spicy food?
Expert Systems vs. Problem Solving Systems
As explained in the cross-referenced applications, the
principal distinction between expert systems and tradi
tional problem solving programs is the way in which
the problem related expertise is coded. In traditional
applications, problem expertise is encoded in both pro
gram and data structures.
A. No
45
Q. Do you usually drink wine with meals?
A. Yes
Q. When you drink wine, is it French wine?
A. Why
In the expert system approach all of the problem
As can be seen from this dialog, the system is leading
related expertise is encoded in data structures only.
the user through a set of questions, the purpose of
None is in programs. Several bene?ts immediately fol
which is to determine a suitable set of restaurants to
low from this organization.
An example may help contrast the traditional prob 55 recommend. This dialog begins with the system asking
if the user already knows the restaurant choice (a com
lem solving program with the expert system approach.
mon feature of expert systems) and immediately illus
The example is the problem of tax advice. In the tradi
trates a characteristic of expert systems; users may
tional approach data structures describe the taxpayer
choose not to respond to any question. In expert sys
tems, dialogs are not pre-planned. There is no fixed
control structure. Dialogs are synthesized from the
current information and the contents of the knowledge
the taxpayer to tax table choices. It is this representation
base. Because of this, not being able to supply the an
of the tax expert’s knowledge that is difficult for the tax
swer to a particular questions does not stop the consul
expert to understand or modify.
In the expert system approach, the information about 65 tation.
and tax tables, and a program in which there are state
ments representing an expert tax consultant’s knowl
edge, such as statements which relate information about
taxpayers and tax computations is again found in data
structures, but now the knowledge describing the rela
Another major distinction between expert systems
and traditional systems is illustrated by the following
tionships between them is encoded in data structures as
answer given by the system when the user answers a
3
4,763,277
4
question with the question “why," as occurred in the
above example. The answer is;
Thus, when a conclusion is drawn, it is possible to
understand how this conclusion was reached. Further
more, because the expert system uses knowledge in a
form similar to the expert, it may be easier to retrieve
A. I am trying to determine the type of restaurant to
suggest. So far Chinese is not a likely choice. It is 5 this information from the expert.
possible that French is a likely choice. I know that if
Chaining
the diner is a wine drinker, and the preferred wine is
There are two main methods of reasoning when using
French, then there is strong evidence that the restau
inference Rules: backward chaining and forward chain:
rant choice should include French.
mg.
Forward chaining starts with the data available and
It is very dif?cult to implement a general explanation
system (answering questions like Why and How) in
uses the inference Rules to conclude more data until a
traditional systems. The response of the expert system
to the question WHY is an exposure of the underlying
desired goal is reached. An inference engine using for
ward chaining searches the inference Rules until it ?nds
knowledge structure. It is a rule; a set of antecedent 5 one in which the if-clause is known to be true. It then
concludes the then-clause and adds this information to
conditions which, if true, allow the assertion of a conse
its data. It would continue to do this until a goal is
quent. The rule references values, and tests them against
reached. Because the data available determines which
various constraints or asserts constraints onto them.
inference Rules are used, this method is also called ‘data
This, in fact, is a signi?cant part of the knowledge struc
ture. There are values, which may be associated with 20 driven.’
Backward chaining starts with a list of goals and
some organizing entity. For example, the individual
works backwards to see if there is data which will allow
diner is an entity with various attributes (values) includ
it to conclude any of these goals. An inference engine
using backward chaining would search the inference
ing whether they drink wine and the kind of wine.
There are also rules, which associate the currently
known values of some attributes with assertions that can 25 Rules until it ?nds one which has a then-clause that
matches a desired goal. If the if-clause of that inference
Rule is not known to be true, then it is added to the list
of goals. For example, suppose a Rulebase contains two
Rules:
(1) If Fritz is green then Fritz is a frog.
be made about other attributes. It is the orderly process
ing of these rules that dictates the dialog itself.
The Knowledge Engineer
The knowledge engineer is concerned with the repre
sentation chosen for the expert’s knowledge declara
(2) If Fritz is a frog then Fritz hops.
Suppose a goal is to conclude that Fritz hops. The Rule
base would be searched and Rule (2) would be selected
because its conclusion (the then clause) matches the
goal. It is not known that Fritz is a frog, so this “iF'
statement is added to the goal list. The Rulebase is again
searched and this time Rule (1) is selected because its
then clause matches the new goal just added to the list.
This time, the if-clause (Fritz is green) is known to be
true and the goal that Fritz hops is concluded. Because
the list of goals determines which Rules are selected and
used, this method is called ‘goal driven.’
tions and with the inference engine used to process that
knowledge. There are several characteristics known to
be appropriate to a good inference technique.
1. A good inference technique is independent of the
problem domain.
In order to realize the bene?ts of explanation, knowl
edge transparency, and re-usability of the programs
in a new problem domain, the inference engine
must contain domain speci?c expertise.
2. Inference techniques may be speci?c to a particular
task, such as diagnosis of hardware con?guration.
Other techniques may be committed only to a par
Con?dences
ticular processing technique.
Another advantage of expert systems over traditional
3. Inference techniques are always speci?c to the 45
methods of programming is that they allow the use of
knowledge structures.
Successful examples of Rule processing techniques
Con?dences. When a human reasons he does not always
include:
conclude things with 100% con?dence. He might say,
“If Fritz is green, then he is probably a frog” (after all,
(a) Forward chaining
(b) Backward chaining
he might be a chameleon); or, that Fritz’s leg is broken,
but not much). This type of reasoning can be imitated
The Inference Rule
by using numeric values called Con?dences. For exam
ple, if it is known that Fritz is green, it might be con
An understanding of the “Inference Rule” concept is
cluded with 0.85 Con?dence that he is a frog; or, if it is
important to understand expert systems. An Inference
Rule is a statement that has two parts, an if-clause and a 55 known that he is a frog, it might be concluded with 0.95
Con?dence that he hops. These numbers are similar in
then-clause. An example of an Inference Rule is:
nature to probabilities, but they are not the same. They
If the restaurant choice includes French, and the
50
occasion is romantic,
are meant to imitate the Con?dences humans use in
reasoning rather than to follow the mathematical de?ni
Then the restaurant choice is de?nitely Paul Bocuse.
An expert system’s Rulebase is made up of many such 60 tions used in calculating probabilities.
inference Rules. They are entered as separate Rules and
it is the inference engine that uses them together to
draw conclusions. Because each Rule is a unit, Rules
may be deleted or added without affecting other Rules
(though it should affect which conclusions are reached). 65
One advantage of inference Rules over traditional pro
gramming is that inference Rules use reasoning which
more closely resemble human reasoning.
The following general points about expert systems
and their architecture have been illustrated.
l. The sequence of steps taken to reach a conclusion
is dynamically synthesized with each new case. It is
not explicitly programmed when the system is
built.
2. Expert systems can process multiple values for any
problem parameter. This permits more than one
5
4,763,277
6
line of reasoning to be pursued and the results of
processing system, much of the Rulebase is not required
incomplete (not fully determined) reasoning to be
since many of the components which are optional units
of the system will not be present in the system. Never
presented.
3. Problem solving is accomplished by applying spe
cific knowledge rather than speci?c technique.
theless, prior art expert systems require the entire Rule
base to be stored since all the Rules were, in effect,
This is a key idea in expert systems technology. It
chained or linked together by the structure of the Rule
re?ects the belief that human experts do not pro
base.
cess their knowledge differently from others, but
The invention described in cross-referenced applica
they do possess different knowledge. With this
tion Ser. No. 6/749,076 is directed to an expert system
philosophy, when one ?nds that their expert sys 0 in which the Rulebase is segmented, preferably into
tem does not produce the desired results, work
contextual segments or units. When the Rulebase is
begins to expand the knowledge base, not to re
segmented, it is then possible to eliminate portions of
program the procedures.
the Rulebase containing data or knowledge that is not
The prior art has disclosed various expert systems in
needed in a particular application. The segmenting of
which a “Rulebase” and an “inference engine” cooper
ate to simulate the reasoning process that a human ex
the Rulebase also allows the expert system to be run
with systems or on systems having much smaller mem
pert pursues in analyzing a problem and arriving at a
conclusion. In these prior art systems, in order to simu
ory capacities than was possible with prior art arrange
late the human reasoning process, a vast amount of
ments since each segment of the Rulebase can be paged
into and out of the system as needed. The segmenting of
knowledge needed to be stored in the knowledge base. 20 the Rulebase into contextual segments requires that the
Generally, the knowledge base of a prior art expert
expert system manage various intersegment relation
system consisted of a relatively large number of “if
ships as segments are paged into and out of memory
then” type of statements that were interrelated in a
during execution of the program. Since the system per
manner that, in theory at least, resembled the sequence
mits a Rulebase segment to be called and executed at
of mental steps that were involved in the human reason 25 any time during the processing of the ?rst Rulebase,
ing process.
Because of the need for large storage capacities and
related programs to store the Rulebase, most expert
systems have, in the past, been run only on large infor
mation handling systems. Recently, the storage capacity
of personal computers has increased to a point where it
is becoming possible to consider running some types of
simple expert systems on personal computers. A num
ber of such programs and their applications are dis
cussed in PC Magazine, dated Apr. 16, 1985 beginning
on page 108. Another article entitled “Arti?cial Intelli
gence” appears on page 34 of PC World Magazine, Vol.
2 #1, dated January 1984.
Additional publications of interest that describe Ex
pert Systems of the type represented by the present
invention include;
1. “A User’s Manual for Construct and Consult in the
GPSI Environmen ” authored by Paul Nielsen,
provision must be made to store the data that has been
accumulated up to that point so that at some time later
in the process, when the system returns to the ?rst seg
ment, it can proceed from the last point or RULE node
that was processed. Also, provision must be made so
that data that has been collected by the system up to
that point can be passed to the second segment of the
Rulebase after it has been paged into the system and
data collected during the processing of the second seg
ment can be passed to the ?rst segment when the system
returns to complete processing that segment.
The embodiment of the invention described in that
application employs a segmented Rulebase that has
been established for the primary purpose of diagnosing
the faulty hardware operation of a data processing sys
tem such as a personal computer. The overall objective
of the system is therefore to identify a Field Replaceable
Unit (FRU) that is most probably the cause or source of
currently available from the University of Illinois
the problem.
KBPA Project.
45
In the second referenced application, the embodiment
2. Gordon, Robert K., A Rule Editor for an Expert
was substantially the same except that the system could
System Environment
Towards Automating
perform a self-diagnosis on its own hardware since it
Knowledge Acquisition, M.S. Thesis, University
of Illinois, Urbana, Ill. 1984.
3. Harandi, Mehdi T., A General Purpose System for
Inferencing, Proceedings of the IBM University
Study Conference, Raleigh, NC, October 1983.
had the ability to initiate external procedures or test
units on speci?c components which, when concluded,
would return the results to the expert system. Informa
tion was therefore collected by these systems by asking
questions of the user or running so-called test units or
external processes.
Aid in Program Debugging, M.S. Thesis, Univer
The User interface and the Procedure interface are
55 two important functions in the information collection
sity of Illinois, Urbana, Ill., 1981.
In some applications of expert systems, the nature of
process of the systems described in the cross-referenced
the application and the amount of stored information
applications.
necessary to simulate the human reasoning process for
The User Interface
that application is just too vast to store in the active
memory of a computer. In other applications of expert 60
The function of the user interface is to present ques
systems, the nature of the application is such that not all
tions and information to the operator and supply the
4. Laursen, Andrew L., GPSI : An Expert System to
of the information is always needed in the reasoning
process. An example of this latter type application
operator’s responses to the Inference Engine.
Any values entered by the user must be received and
interpreted by the user interface. Some responses are
processing system comprising many separate compo 65 restricted to a set of possible legal answers, others are
nents, some of which are optional. When that type of
not. The user interface checks all responses to insure
expert system employs a single integrated Rulebase to
that they are of the correct data type. Any responses
would be the use of an expert system to diagnose a data
diagnose the minimum system con?guration of the data
that are restricted to a legal set of answers are compared
7
4,763,277
8
it. As explained in the cross” referenced application,
A leaf that is an EXTERNAL node indicates that
data will be used which was obtained from a Procedure
Call.
A REFERENCE node functions to refer to another
communication between the user interface and the In
tree or subtree.
against these legal answers. Whenever the user enters
an illegal answer, the user interface informs the user
that his answer was invalid and prompts him to correct
ference Engine is performed through the use of a User
Interface Control Block (UICB) which is passed be
A tree may also contain intermediate or minor nodes
Procedure Node Interface
between the Goal node and the Leaf node. An interme
diate node can represent logical operations like And or
Or.
The inference logic has two functions. It selects a tree
The function of the Procedure node interface is to
receive infonnation from the Procedures coordinator
and create the appropriate Procedure Call. The ability
selected, that tree is traced, depth-?rst, left to right.
The word "tracing” refers to the action the system
tween the two.
to call a Procedure and receive information from that
Procedure can be viewed as simply a generalization of
input from the external world. While in some prior art
expert systems external information has been obtained,
that information was obtained only in a predetermined
manner so only certain information could actually be
acquired. This expert system, disclosed in the cross
referenced application, through the knowledge base, is
permitted to invoke any Procedure allowed on its host
system. This makes the expert system useful in a much
wider class of knowledge domains than if it had no
external access or only limited external access.
In the area of machine diagnostics using expert sys
tems, particularly self-diagnostic applications, it is not
possible to conclude the current state of “health” of a
machine without some information. The best source of
information is the machine itself, for it contains much
detailed information that could not reasonably be pro
vided by the operator.
As explained in the prior art, the knowledge that is
represented in the system appears in the Rulebase. In
the Rulebase described in the cross-referenced applica
tions, there are basically four different types of objects,
with associated information present.
1. Classes-these are questions asked to the user.
2. Parameters-a Parameter is a place holder for a char
acter string which may be a variable that can be in
serted into a Class question at the point in the ques
tion where the Parameter is positioned.
to trace and then it traces that tree. Once a tree has been
takes as it traverses the tree. asking Classes (questions),
calling Procedures, and calculating Confidences as it
proceeds.
As explained in the cross-referenced applications, the
selection of a tree depends on the ordering of the trees.
The original ordering of the trees is the order in which
they appear in the Rulebase. This order can be changed,
however, by assigning an EVIDENCE node an attri
bute “initial” which is described in detail in these appli
cations. The ?rst action taken is to obtain values for all
EVIDENCE nodes which have been assigned an “ini
25 tial” attribute. Using only the answers to these initial
Evidences, the Rules are ordered so that the most likely
to succeed is evaluated ?rst. The trees can be further
re-ordered since they are constantly being updated as a
selected tree is being traced.
It has been found that the type of information that is
solicited by the system from the user by means of ques
tions or classes should be tailored to the level of knowl
edge of the user. In many applications, the group of
prospective uses is nicely de?ned and the knowledge
35 level can be estimated so that the questions can be pres
ented at a level which corresponds generally to the
average user. However, in other applications, knowl
edge of the speci?c domain of the expert system might
vary considerably among the group of prospective us
ers.
One application where this is particularly true in
volves the use of an expert system, operating in a self
diagnostic mode on a personal computer to assist the
operator of the personal computer to diagnose the cause
3. Procedures-these are de?nitions of calls to external
of a fault or error in either the hardware or software. In
45
Procedures.
general, asking the operator for information is the most
. Rule Nodes-The inferencing in the system is done
straightforward
way for the expert system to gather
by a tree structure which indicates the Rules or logic
information assuming, of course, that the information is
or should be within the operator’s understanding. For
trees are called RULE nodes. There are several dif
50 example, in diagnosing a personal computer, the expert
ferent types of RULE nodes.
system must know the major functional components of
The Rulebase comprises a forest of many trees. The
the system. It could ask the operator, for instance, if the
top node of the tree is called the Goal node, in that it
display is a monochrome or color display. The operator
contains the conclusion. Each tree in the forest has a
should, in all probability, be able to provide the correct
different Goal node. The leaves of the tree are also 55 answer 100% of the time. The expert system could, on
which mimics human reasoning. The nodes of these
referred to as RULE nodes, or one of the types of
RULE nodes. A leaf may be an EVIDENCE node, an
EXTERNAL node, or a REFERENCE node.
An EVIDENCE node functions to obtain informa
the other hand, cause a test unit to be run to determine
the type of display. The accuracy of the data collected
by either approach in this instance probably would not
be that different so the knowledge engineer could em
tion from the operator by asking a speci?c question. In
responding to a question presented by an EVIDENCE
node, the operator is generally instructed to answer
“yes” or "no" represented by numeric values 1 and 0 or
provide a value of between 0 and 1, represented by a
ploy either approach without affecting the accuracy of
the diagnosis. However, in many instances, because of
handled in a different manner.
invention that in many situations the information is
the nature of the information being solicited, it is better
to obtain the information from the system rather than
asking the operator, because the accuracy of the data
“maybe.“
65 supplied by the operator is so low that the system could
not effectively process it to a meaningful conclusion.
Questions which require a response from the operator
other than yes or no or a value between 0 and l are
It has been found in accordance with the present
9
4,763,277
already in the system, in a form of which permits the
10
FIG. 3A and FIG. 3B in combination, illustrate the
data for a sample Rulebase.
FIG. 4 is a Rule tree constructed from the input data
shown in FIG. 3A and FIG. 38.
FIG. 5 is another tree constructed for the input data
shown in in FIG. 3A and FIG. 33.
FIG. 6A and FIG. 6B in combination, illustrate the
records of the major linked lists.
correct answer to a question to be obtained through a
process of inductive or deductive reasoning. The data
previously collected by the system could be answers
provided by the user to less complex questions that
were asked for a different reason or results returned
from test units that were previously run.
For example, in testing diskette drives there are cer
tain tests which require that a scratch diskette be pres
FIG. 7 illustrates the general format of the variable
ent in diskette drive A. These tests may cause data to be 10 ?eld of the records shown in FIG. 6A and FIG. 6B,
written to the diskette or the diskette to be reformatted.
FIG. 8 illustrates the relationship of the link lists to
Data on the diskette may be destroyed, so it is impera
the Hashtable structure.
tive that the diskette with the diagnostics routines not
FIG. 9 illustrates the relation of the Class linked list,
be inserted in drive A. Rather than relying on the user
the member list, the Hashtable, and RULE nodes that
to be sure that a scratch diskette is present, there are 15 are members of the Class.
certain things that may indicate to the system that such
FIG. 10 illustrates the relation of the Procedure
is the case. If drive A is a low capacity diskette drive
linked list, the Membership list of a Procedure object,
and a diskette is present, then the diskette must be a
the Hashtable and the RULE nodes that are members of
scratch diskette. If the drive is a high capacity diskette
drive, and the procedure, READ__VOLUME_LA~
20
BEL returns a nonzero return code, then the diagnostic
diskette is not in drive A, and a scratch diskette must be.
the Procedure object.
FIG. 11 illustrates the organization of the Parameter
linked list.
FIG. 12 illustrates the organization of the Rulenode
In the case that the drive is high capacity and
linked list
READ_VOLUME_LABEL returns a zero return
code, then the user must be told to insert a scratch 25
diskette in A.
FIG. 13 illustrates the organization of the various
programming modules employed in the Expert System
FIG. 14a and 14b illustrate examples of Rulenodes in
In the Rulebase of the expert system, action attributes
which answers to class questions that are obtained from
can be associated with any node. One of these actions,
the system, and the question is therefore never pres
the SET action, indicates that if this node is evaluated to
be true, then the answer to a speci?ed question can be 30 ented to the user.
set to a speci?ed value. In this way, answers to ques
DESCRIPTION OF THE PREFERRED
tions can be obtained without directly asking the user
EMBODIMENT
the question. If the node with the action attribute is
The
preferred
embodiment
of the present invention
invalidated, then the question speci?ed in the action
to
be
described
employs
a
segmented
Rulebase that has
attribute will not be affected.
35
been established for the primary purpose of diagnosing
These SET actions are equivalent to adding rules to
the faulty hardware operation of a data processing sys
the rulebase which would resemble the IF . . . THEN
tem such as a personal computer. The overall objective
rules as follows:
of the embodiment is therefore to identify a Field Re~
IF drive A is low capacity
placeable Unit (FRU) that is most probably the cause or
AND there is a diskette present
source of the problem. The application of an expert
THEN the answer to “Is there a scratch diskette in A?”
system that employs a segmented Rulebase in accor
is “yes.”
dance with the teachings of the cross referenced and in
IF drive A is high capacity
which procedures are run to collect data for use by the
AND the return code of READ_.VOLUME_LA.
BEL is not 0
45 expert system is but one example of an application for
THEN the answer to “Is there a scratch diskette in A?”
this type of expert system. Other applications employ
ing data collected by running external procedures and
is “yes."
It is therefore an object of the present invention to
not using an segmented Rule base may readily be devel
oped based on the following description. The ability to
provide an improved method of collecting information
50 assign an action attribute to the Rulenode, as described
AND there is a diskette present
in an expert system.
A further object of the present invention is to provide
an expert system in which prior to asking a question of
the user, other available methods of determining the
generally in the cross-referenced application is em
ployed in connection with the present invention, in that
a speci?c action attribute, “SETC” permits the answer
to be set to a class question that would always be pres
answer by the system are considered.
55 ented to the user.
A still further object of the present invention is to
SYSTEM OVERVIEW
provide a method in which answers to questions can be
The main components of the expert system shown
set in accordance with the logical combination of data
diagrammatically in FIG. 1 are an Inference Engine IE
obtained from other Rule nodes in the system.
Objects and advantages other than those mentioned 60 10 and a Rulebase ?le 11. The Inference Engine 10
above will be apparent from the following description
when read in connection with the drawing.
BRIEF DESCRIPTION OF THE DRAWING
includes a supervisor program 12, inference logic 133,
and a procedural call coordinator 14. Procedures A-N
are interfaced to the coordinator 14 through the Proce
dure node interface 15. The operator interfaces with the
FIG. 1 illustrates the overall functional relationships 65 supervisor through the operator or user interface block
of the components of an expert system in which the
16. The knowledge represented by the compiled Rule
present invention is advantageously employed.
base is generated by the ?le compiler 17, based on Rule
FIG. 2 illustrates schematically, a sample Rule tree.
inputs from Rule writers.