c c 

NASA Contractor Report 1 81 81 0 

* Evidence Flow Graph Methods for Validation 

and Verification of Expert Systems 

Lee A. Becker, Peter G. Green, and Jayant Bhatnagar 

Worcester Polytechnic Institute 

Worcester, MA oisos 

I Contract NAG1 -809 

National Aeronautics and 

Space Administration 

Langley Research Center 

Hampton,Virginia 23665 

(NASA-CR-T81810) EVXDDEEE fLOH GRAPH R 89- 2 83 28 

HETHODS FOR YALIDATIOI AND VERIPICATXCP OF 

EXPERT SYSTEUS [Worcester Polytechnic 

Inst.) 46 p CSCL 09B Unclas 

-- 

63/62 ~ 0220032 
I 

. 

TABLE OF CONTENTS 

1. Introduction .................................................. 1 A 

2. A Framework for Verifying Expert Systems ...................... 5 

3. Knowledge Level Verification for a Rule-based Representation ... 10 

Translator ................................................. 10 

3.a. The Knowledge Representation to Evidence Flow Graph 

3.b. The Simulator .............................................. 14 

3.c. The Post Processor ......................................... 21 

4. Types of Testing .............................................. 21 

5. Results of the Project ........................................ 23 

6. Conclusions ................................................... 28 

Appendices .................................................... 31 

References .................................................... 43 

I: 

c i 
1. INTRODUCTION 

DATABASE 

This final report describes the results of an investigation into 

the use of evidence flow graph techniques for performing validatior! 

and verification of expert systems. The term validation in this 

context is taken to mean demonstrating that the system meets user 

requirements, and the term verification is taken to mear, 

demonstrating that the system meets specifications. Since the 

principal uses cf the techniques described in this report are in 

the context of verification, the term verification will be used 

throughout this document, although many of the techniques may also 

be applicable to validation. 

RULES 

4 

Simple expert systems consist of a set of rules, a data base, and 

an inference engine as shown in figure 1. 

Figure 1: A'Simple Expert System 

An evidence flow graph representation (MIC87) for such a system 

replaces each rule with a process that is triggered by the arrival 

of data into the data base, either from an external source or from 

the execution of another decision process, as shown in figure 2. 

The result is a graph with data flow properties (ACK82) in which 

input data triggers rule executions until outputs are generated. 
The word 'process' here is used in the operating systems sense, as 

meaning a computational object with its own register state, memory 

map, local data and stack, and access to code and fixed In 

an Evidence Flow Graph context, a decision process is a node in the 

graph which has an input queue for receiving messages from its 

input graph arcs. State variables may be contained within decision 

processes and partial solutions are transmitted along the arcs of 

data. 

the graph. 

7a ,b Evi&nce Flow Graph 

Messqes 

Decision pmss (DP) execution is mggered by 

the arrival oi messages travelling along arcs. 

2b: A Simple Rule-based Expert System 

Rule 1: IfXandB thenC 

Rule2: IfD andE thenF 

Rule3: IfCandFthenG 

2: Rules mapped onto evidence flow graph 

A 

C 

G 

B 

D b 

F 

DP Defiaons 

DPI: 

DE? 

DP3: 

When A and B arrive send C to DP3 

When D and E arrive sendF to DP3 

When C and F arrive ourpt G 

FiguPY 2: Transformation of a Rule-Bad Expen System 

into an Evidence Flow Graph 
3 

The potential importance of evidence flow graphs for verification 

is twofold. First, the flow graph representation makes it possible 

to simulate the actions of the rules using discrete event 

simulation tools developed for analyzing complex systems. This 

opens up the possibility of performing monte-carlo performance 

tests under a wide variety of input values and timings. Second, 

the flow graph representation is independent of the inference 

engine and offers the potential for verifying "portable" sets of 

rules which will work under any rule execution sequence imposed by 

an inference engine. When it is determined that correct operation 

is dependent on the inference engine, the rules and inference 

engine must be verified and controlled as a unit. 

The principal purpose of the research reported here was to 

determine whether evidence flow graph techniques would be useful in 

the verification of expert systems. This was approached by 

developing: 

a) A translator to translate simple horn-clause rule bases into the 

evidence flow graph representation developed by Chisvin (CHI88) 

based on the work of Michalson (MIC88). 

b) A simulation program written in SIMSCRIPT (RUS83,LAW84) to 

analyze the performance of the flow graph under a variety of 

conditions. 

c) Methods for analysis which attempted to identify problems with 

rule execution by examining the output of the simulation program. 

These tools were then applied to a simple rule base which contained 
4 

errors. It was found that the method was capable of identifying 

problems, although it was evident th.at a much more sophisticated 

results analysis program will be needed if this technique is to be 

used on a large scale system. 

It was found that the order of presentation of input data can 

affect the output from a set of rules. By corollary, the order in 

which the inference engine executes the rules may affect the 

output. This can cause problems when undesired outputs are 

produced before all the data is available or before all possible 

rules have been executed. It was also found possible to affect the 

resultant output by making small changes to critical parameters. 

AS a result of this investigation we have determined that evidence 

flow graph techniques can be used to find problems in rule-based 

expert systems and that these techniques therefore have a place as 

part of the evaluation regime for the verification of expert 

systems. 

Some of the faults found using evidence flow graph techniques, such 

as circular reasoning and’ unreachable conclusions, could be 

determined by other methods (SW82, NGU85, NGU87, STA87, BEL87, 

JOH88). Some problems, such as critical sensitivity to parameters 

or the timing of data inputs, are uniquely suited to flow graph 

simulation techniques, as is the determination of whether the rules 

are valid for any rule firing order. 

To date experiments have been limited to simple horn-clause rule 

sets with most of the post-simulation analyses being done by hand. 

TO make evidence flow graph techniques practically useful, much 
5 

work remains to be done. First, the work of Michalson (MIC88) 

needs to be extended to cover the translation of commonly used 

expert system shell paradigms into evidence flow graphs. Then some 

work needs to be done to build the software infrastructure to allow 

the automation of monte-carlo sensitivity and data timing 

simulations. Finally it is evident that an intelligent 

post-processing program will be needed to find problems in the mass 

of data produced by the simulations. This program will probably be 

an expert system itself with knowledge about how to find faults 

from the results of the simulations. 

This report presents a framework for verifying expert systems in 

section 2. In section 3 the conversion of rules to evidence flow 

graphs is described followed by a description of the simulation 

program. Section 4 discusses the kinds of testing supported by the 

evidence flow graph approach and section 5 discusses the results, 

given in detail in the appendices, of the tests performed during 

this research. Finally in section 6, the report concludes with a 

summary of the results obtained to date and a favorable prognosis 

for the future use of these 'techniques in the verification of 

expert systems. 

2. A - FRAMEWORK - FOR VERIFYING -- EXPERT SYSTEMS 

Figure 3 depicts our framework for the development of a verified 

expert system. One important feature of our approach is that the 

verification is divided into a set of distinct processes. 

Performance analysis and verification takes place first at the 

knowledge level, then again after information about the execution 
6 

environment has been incorporated. This is followed by a hardware 

failure effects analysis before testing in a simulated real-world 

environment. One cannot just verify a knowledge base. If the rule 

base is not invariant over all control strategies, then this must 

be known, and the rule base and control regime must be verified as 

a pair. In addition, any modification to either the rule base or 

the control regime requires that the pair be reverified. It is 

obvious that if the rule base were invariant over all control 

strategies, the control regime could be changed and reverification 

would not be necessary. This would support portability. 

Evidence Flow Graphs were developed at WPI as a representation for 

rule-based, Hearsay/Blackboard-based, and communication expert 

object-based expert systems (GRE87,MIC87). An evidence flow graph 

is a directed graph which represents decision making in terms of 

the collective behavior of several independent processes. The 

processes are characterized by the ability to make decisions in.a 

limited problem domain and by the ability to communicate the 

results of the'se decisions by passing messages to other decision 

processes. The processes may range in complexity from simple * 
7 

XYCVSiS3GI SOU?.CZS 

(-) 

A 

c 

Figure 3: The Proposed Model for Verification of Expert Systems 

S?z:C::ICd~:ONS .+. 
a 

Evidence flow graphs provide a unified representation that can be 

mapped onto different computer hardware architectures. These 

graphs and their application are being investigated as part of an 

overall research project into how to build intelligent systems that 

are able to function in real-time in uncertain environments. 

In real-time systems uncertainty arises from a number of sources. 

During the processing of the input the environment may change. 

Input data may be erroneous due to noise, imperfect sensors, or 

faulty human data entry. Signal processing algorithms can produce 

false outputs, due to factors such as aliasing, which are used as 

inputs to the expert systems. Finally, the necessarily limited 

knowledge contained in the rule base itself may cause uncertainty. 

Evidence flow graphs are also of value in the verification of 

expert systems. Figure 4 depicts the use of flow graphs for 

performance analysis on different knowledge representatiins. An 

important feature of our approach is transforming the knowledge 

representation used into a graph theoretic form from which it can 

be analyzed and simulated using techniques developed for non-linear 

control systems. 
9 

PERE'ORMAXCE ANALYSIS 

ay SIMULATIONS 

RULES T 

bVEiiIFY -, 

/JLACKBObRDS/ /COMMONICAT!NG[ EXPERT OBjECTS 

COMMUNICATING 

RULES SLACKBOARDS 

I FLOW GUPHS~ 

t MODf:l SIMULATION 

output SPECIFICATION input 

-- 

Figure 4: Evidence Flow Graphs as a Unifying Representation 
10 

, 

3. KNOWLEDGE-LEVEL VERIFICATION -- FOR A RULE-BASED REPRESENTATION 

In the research described in this report we have investigated 

knowledge-level verification and have demonstrated our approach 

using a rule-based knowledge representation. Our system contains 

two modules: a rule-base-to-evidence-flow-graph translator and a 

simulation program. A third logical module, post-processing, 

currently is done by hand. 

3.a. The Knowledge-Representation-to-Evidence-Flow-Graph 

Translator 

A translator takes the knowledge representation and yields an 

evidence flow graph. The knowledge is in the form of Horn-clause 

rules, where the antecedent is a conjunction of predicates and the 

consequent is a conclusion. There are specially designated input 

predicate nodes and output final conclusion nodes, as well as nodes 

for any subconclusions. For each rule there is a directed link 

from each of the predicates of the antecedent (input nodes or 

subconclusions) to the node of the conclusion or subconclusion in 

the consequent, as illustrated in Figure Sa. Weights on the links 

are based on the number of conjuncts. When a parameter is referred 

to in several relational predicates, there is a directed link from 

the parameter to each of the nodes for the relational predicates, 

as illustrated in Figure 5b. 
11 

A and B --> C 

D and E --> F 

F and G --> H 

output 

conclusion 

input 

edicates 

Figure 5a: Evidence Flow Graph Representation for Simple Rules 

W > 200 and A --> B W < 100 and C --> D 

< n 0 

iv > 200 @@ W 

w < 100 

input input relational 

parameter predicates predicates 

Figure 5b: Evidence Flow Graph Representation for Parameter Inputs 
Conversion of a production rule base into an Evidence Flow Graph 

(EFG) is achieved by a translator implemented in LISP on a VAX/VMS 

11/750 system. 

The translator uses a depth-first strategy on the rule base to 

generate the nodes of the graph. Generation begins with the 

selection of an arbitrary rule from the rule base. Next, all rules 

leading One 

conclusion node is created in the graph for each such group. For 

every conjunct of each rule in the group, a new node is created if 

one does not already exist. This node is treated as the conclusion 

node for a new group of rules that have the corresponding conjunct 

as their conclusion. Conjuncts that are specified as inputs to a 

rule are mapped to the input nodes of the graph. Conjuncts which 

are not conclusions of any rule and which are not specified as 

inputs are treated as undefined and are flagged as errors. Graph 

generation continues until all conjuncts that appear in the rule 

base are mapped to the nodes of the graph. 

to the same conclusion are collected to form a group. 

For every conjunct that includes a logical comparison operator in 

its description, two nodes are established. One node is the value 

node that models an input node for the input parameter being 

compared, while the other is the comparison node that contains the 

threshold value against which the parameter value comparison is 

performed. A single arc connects the value node to the comparison 

noc?o. In order for the comparison node to fire, a message must be 

received along this arc. All other conjuncts that perform a 

comparison of the same parameter against a different value have a 

different comparison node with an arc from the same input parameter 
13 

node. 

The translator combines graph generation with static rule base 

checking that preceeds the dynamic testing implemented by the 

simulator (section 3.b.). Static checking enables the 

identification of those rules that contain undefined conjuncts in 

their conditions. In the event of detection of such a rule in the 

rule base, the translator logs an error in the error log file 

indicating the rule in error along with the conjunct that caused 

the error. From then on, the erroneous conjunct is treated as an 

input conjunct and graph generation continues as normal. On 

completion of graph generation, the translator issues a warning on 

the inconsistency of the generated graph arising from the assumed 

treatment of undefined conjuncts. Should no errors occur durin'g 

graph generation/static checking, the translator outputs the graph 

in a canonical form which can then be modified for providing a 

formatted input to the simulator. 

The reformatting of the translator output is provided to describe 

each node completely in the input to the simulator. Each node's 

description includes information on the type of node (e.g. input, 

output, etc.), the arc relations (e.g. conjunctive/disjunctive 

with respect to other arcs), and a description of each arc (e.g 

source node, relative importance of the arc for that node). 
14 

3.b. The Simulator 

A simulator executes the evidence flow graph. All nodes, except 

for the input and relational predicate nodes, are updated with a 

weighted sum of the values of their input arcs. When several rules 

have the same conclusion, the update values are treated as a queue 

which takes the maximum of their input values. For example in 

Figure 6, if both are available E updates with the maximum of the 

weighted sums of A & B and of C & D; if only one sum available 

it becomes the value of E; and if neither is available E will not 

be updated. 

is 

A and B --> E 

C and D --> E 

6 S 

The update values are 

directed arc. The 

For the initial stage 

vera1 Rules with the Same Conclusion 

sent as messages to nodes to which there is a , 

values are real numbers between 0.0 and 1.0. 

of V & V (the knowledge level) it might be -- 

assumed that the work cells (nodes) fire as soon as their inputs 

are available and that there is no contention for computing 
15 

resources. One could then pick processing cell times at random 

from a distribution and test for many possible execution sequences. 

Simulation continues until all activity ceases in the network. 

The motivation for using a 'universal,' idealized environment for 

the basis of knowledge-level verification is portability and 

flexibility; it could also make hardware fault tolerance more 

realizable. The data-flow-like processing allows one to consider 

the knowledge independently of the control strategy and reflects 

inherent parallelism of expression of rules. It is also possible 

to verify a knowledge base under a particular control strategy. 

For example, a rule firing order mechanism for an inference engine, 

like a conflict resolution method, would be converted into a work 

cell scheduling mechanism for computing resources, in this case, 

priorities of node firings. 

The formatted output obtained from the translator provides input to I 

the simulator, which is implemented in SIMSCRIPT 11.5 on a 

VAX/ULTRIX 11/780 system. 

Three major components comprising the simulator are : 

(a) Decision Process Nodes 

(b) Interconnection Arcs 

(c) Communication Messages 

Decislon process nodes are centers of active decision making in the 

evidence flow graph. Broadly they may be classified into four main 

categories : 

(a) Input nodes 

(b) Output nodes 
16 

(c) Intermediate nodes 

(d) Comparison nodes 

Input nodes are entry points for symbolic and numeric information 

flowing into the graph from the external environment. These nodes 

fire collectively in subsets as explained later in this section. 

Information leaving the input nodes appears as input to 

intermediate and/or comparison nodes. 

Intermediate nodes are the centrally located nodes of the graph and 

are isolated from the external environment by the input/output 

nodes. Input to intermediate nodes may appear from input, 

comparison, or other intermediate nodes. On collection of enough 

evidence at the intermediate nodes, decisions regarding the 

subsequent flow of evidence are made. Evidence flowing out from an 

intermediate node is either confirmation or negation of the 

evidence arriving at its input. 

Decisions at the graph nodes are conveyed to other nodes through 

flow of messages in the graph. No feedback information is made 

available at the input pf graph nodes. 

A comparison node is another type of node present in the evidence 

flow graph. Each comparison node has an arc from a parameter input 

node. Comparison nodes handle the flow of numeric evidence into 

the graph. Their functional description is provided later :in this 

section. 

All types of nodes have certain basic attributes, including 

node-id, node-type, node-threshold, node-conclusion, and various 

statistical counters that keep track of node activity in terms of 
17 

the number of input messages received and the number of 

positive/non-positive messages output by the node. Node-id of a 

node is its unique identification in the graph. Behavior of a node 

(i.e. action taken by a node on its activation) depends on the 

type of that node. Input nodes and intermediate nodes send 

messages to other nodes with activation values, while the output 

nodes produce the final conclusions. Node threshold is a static 

comparison value against which total evidence collected at a node 

is measured. If the evidence gathered at a node exceeds the firing 

threshold, the node fires with a boolean true value, otherwise it 

fires with a boolean false value. 

At any time during simulation, the nodes are either in an active 

state or in a state of hibernation. A message arriving from 

another node activates a hibernating node. Input arcs of nodes are I 

checked for message arrivals. Message copies are deposited in 

input queues of the destination node/nodes specified in the I 

message. During its activation, a node checks all relevant arcs 

for messages. If all conjunctive arcs have messages and at least 

one arc in the set of disjunctive arcs has a message, the node 

fires. Messages that initiate firing are removed from input queues 

l 

and the node subsequently enters a hibernation state. Should the 

message requirements at the input arcs be insufficient, the node 

enters the hibernation state without firing. The activation 

sequence for nodes follows a fixed pattern: input nodes fire 

first, followed by the activation of comparison nodes, which in 

turn is followed by activation of intermediate and output nodes. 

Associated with each node are entities called arcs. Incoming 

I 
messages are buffered in the arcs of a node. An arc may bear a 

conjunctive or disjunctive relationship to other incoming arcs of a 

node. As mentioned earlier, messages must be received along all 

conjunctive arcs and along at least one of the disjunctive arcs for 

a node to fire. Each arc entity has attributes such as source 

node, weight, type (conjunctive/ disjunctive), and a count of the 

messages it receives. The weight of an arc is considered for 

determining the importance of messages that are received along that 

arc. In the current system, the arc weight is computed in the 

translator by distributing the certainty factor of a node uniformly 

over the input arcs. The evidence from each arc is the product of 

the message activation level and the weight of the arc. Total 

evidence collected at a node is computed as the sum of evidence 

from all conjunctive arcs plus the maximum of the evidence values 

from all disjunctive arcs. 

Messages form the medium for inter-node communication. Each 

message is characterized by a value (if the evidence it carries is 

a quantifiable numeric quantity), the weight of the corresponding 

arc, and a message number to uniquely identify the message in the 

system. Messages are consumed by a node on its firing. The output 

of a node consists of messages that carry evidence representing a 

combination of evidence brought to the node by other messages plus 

the evidence generated at the node itself. 

The simulatsr operates in two phases: the setup phase and the 

simulation phase. During the setup phase, the description of each 

node of the graph is read from an input file and a corresponding 

node is modelled as follows: if the node is an input node, a 
19 

simulation entity modelling the node is created in the input nodes 

set. If the node is a non-input node, a process is created for 

modelling that node. The process description includes the node's 

attributes (e.g. its type), node entities and their attributes 

(e.g. arcs and the relationships between them, relative weights, 

etc), and a procedure to simulate its action on activation. For 

each such process created, a process notice is placed in the future 

events set of the simulator, which works like a queue. 

For value-comparison nodes, two nodes are modelled in the 

simulator: the parameter value node is placed in the input nodes 

set, while the comparison node is associated with a process notice 

in the future events set. Process notices for all non-input nodes 

are scheduled to execute at the instant they are examined by the 

simulator. This instantaneous execution property of the node 

processes, which are running as co-routines, implemeqts the 

inherent parallel execution model of the Evidence Flow Graph. 

A single simulation is made up of an arbitrary number of simulation 

cycles. The simulation is performed by first generating a value 

for each input. Then, in each simulation cycle, the inputs are 

applied to the graph in random order and in groups of random size. 

All process notices pending in the future events set are examined 

and their associated actions are executed. 

The actions specified for intermediate nodes are as follows: 

verify that at least one message is queued in the buffer of every 

arc of a conjunction of input arcs and at least one message is 

queued in at least one of the arcs of every disjunctive set of 
20 

input arcs. If all appropriate arcs have messages present in their 

buffers, compute the combined measure of evidence collected at this 

node. Check this measure against the node threshold. If there are 

not enough messages received on appropriate arcs, then simply 

suspend execution of the node process. Otherwise fire the node 

with a boolean value and delete all messages that contributed to 

current node firing. Firing of a node is equivalent to generating 

a new message and scheduling a corresponding process notice in the 

future events set with a priority of execution higher than the 

priority of execution of node process notices. Once a node has 

fired its execution is suspended. 

The action sequence specified for output node processes is simpler. 

An output node qualifies for firing in the same way as an 

intermediate node does. If an output node qualifies for firing, 

then the conclusion reached is output and execution is suspended, 

otherwise the node process is suspended and the current simulation 

cycle is continued. During the execution of a message process 

notice mentioned in the action sequence outlined above, the action 

taken is to resume and reschedule all supended node processes, 

followed by storing messages in input buffers of arcs of every 

destination node in the future events set for which the message is 

intended. 

On completion of a simulation cycle, the buffers of all arcs in the 

graph are cleared of any pending messages to prepare for a new 

subsequent simulation cycle. Simulation cycles are repeated until 

the expiration of the user-specified duration of simulation. 
3.c. -- The Post Processor 

Once a simple simulator was built and tested, it became eiiident 

that a post process will need to be developed to aid the user in 

analyzing the simulation results. The pattern of node firings (and 

message passings) is recorded in a logfile by the simulator. A 

post processor could then do various analyses on this file, for 

example to determine nodes that have never fired or nodes that have 

fired very often. The rules corresponding to these nodes warrant 

additional scrutiny. The post processor also could compile results 

from multiple runs with the same input, perhaps available at 

different times. Thus results from different input orderings and 

with different firing orders can be compared to see if the results 

are always the same. In other words, the output of the post 

processor will allow the identification of invariance of results 

with different input orderings, with different firing orders, as 

well as with parameter variation. The development of such a post 

processor is crucial to analysis of large-scale systems. 

4. -- TYPES OF TESTING 

A variety of different types of testing are supported by this 

approach. The most common type of checking done on expert systems 

is for consistency (SUW82,NGY85,NGY87,STA87). Static analysis on 

the evidence flow graph can yield this kind of information. In 

fact, several systems which do consistency checking translatz a 

rule base into a inference net or graph for their analysis 

(STA87,BEL87). Such a graph structure could also be used to derive 

or generate sets of inputs for structural testing, if desired 
22 

(STA87). We concentrate here on the kinds of dynamic testing which 

can be done using simulation. 

If there are available test cases which specify the conclusion to 

be reached for a set of inputs, these can be executed using the 

simulator and wrong conclusions can be detected. This kind of 

testing can also be readily done by executing the expert system 

itself. However, there may be significant difficulty in assembling 

a large, well-distributed set of test cases (OKE86). With the 

proposed method there are a number of types of testing which do NOT 

require the availability of test cases. All these involve running 

multiple simulations with inputs values randomly generated from 

within the operational profile. 

One type of testing which is very significant, which does not 

require knowing the desired conclusion for a set of input values, 

is testing whether the same conclusion will be reached regardless 

of the order that the input values become available. This is 

relevant when the system acts on the basis of the first conclusion 

reached. For a given set of input values, multiple runs are made 

with different orderings of various subsets of the inputs. 

For sensitivity testing the values of parameters are randomly 

varied within their operational profiles to determine whether any 

parameter is critical in its effect on the input, i.e. small 

changes in its value cause significant changes in the output. The 

effects of different degrees of belief of input predicates can also 

be examined. The evidence flow graph can be partitioned to allow 

this testing to be carried out only on the relevant subset of 
23 

nodes. 

For some applications it may be possible or necessary to specify 

critical conclusions that are to be reached only under certain 

conditions or are not to be reached under certain conditions. 

These specifications can be tested using multiple simulations with 

randomly generated inputs. For these applications, it is critical 

to partition the evidence flow graph to allow more exhaustive 

testing. 

5. RESULTS -- OF THE PROJECT 

At present a prototype rule-base-to-evidence-flow-graph translator 

has been completed; this is written in LISP. A simulation program 

to run an evidence flow graph with varying input values and 

orderings has been completed; this is written in SIMSCRIPT. A rule 

base for a small expert system has been translated into an evidence 

flow graph, and the simulation programs have been used to run the 

network. In addition, errors have been inserted into the sample 

rule base to demonstrate the kinds of errors that the proposed 

approach can detect. This is discussed below. 

Appendix 1 contains the sample rule base. Appendix 2 contains the 

evidence flow graph representation that was generated from this 

rule base by the graph generator. Appendix 3 contains the symbolic 

representation of this evidence flow graph. This evidence flow 

graph representation is now described in detail. All the 

INPUT - NODES except for AGE and LENGTH are predicates; their input 

values will be truth values (1 is true and 0 is false, and values 
21 

between 1 and 0 indicate degree of belief). AGE and LENGTH are 

parameter inputs. They are input as real values, and the functions 

in their corresponding COMPARISON - NODES return true values (between 

1.0 and 0.0). 

The OTHER - NODES correspond to conclusions, i.e. right-hand sides 

(RHS's) of rules. The OTHER - NODES which begin with an * are final 

conclusions. In each OTHER - NODE following the node number, 

conclusion, and certainty factor, there is a list of nodes which 

correspond to the conjuncts on the left-hand side (LHS) of the 

rule. 

The nodes for the conjuncts may be either INPUT - NODES, 

COMPARISON - NODES, or other OTHER - NODES. .Following the number of 

the conjunct node, there is a real number between 0.0 and 1.0. 

This stands for the 'weight' on the link from the conjunct node to 

the conclusion node. The OTHER - NODES are updated with a weighted 

sum. The value of each conjunct node is multiplied by its weight 

and these products are added together. 

0 In node 24 for 'mammal,' the second element in the conjunct list 

consists of two nodes; these two nodes correspond to the second 

conjunct in the rule for 'mammal' in EX.l. The second conjunct in 

the rule was 'animal', and there were two rules with 'animal' as a 

conclusion, as there are two OTHER - NODES (4 and 6) with 'animal' as 

a conclusion. These two nodes are connected to node 24 by an 

OR-connection. The value of an OR-connection used for updating is 

the maximum value of the nodes which have so far sent values to the 

updating node. For this rule base there are no ELSE - NODES, which 
are created for if-then-else rules. There are also no NOT - NODES, 

which are used when a negated predicate is a conjunct in the LHS of 

a rule; the same predicate can thus be referred to positively and 

negatively in different rules. 

The errors that can be detected by our techniques can be divided 

into three classes: 

1. sensitivity (over-sensitivity) of the conclusion to 

input parameters, 

2. different conclusions from one set of input values, and 

3. errors which other researchers have detected using static analytic methods but which may also be detected using our techniques. 

Appendix 4 is a sample run with the input values on the right. The 

input values are randomly generated. For this run the conclusion 

'ostrich' was reached. For sensitivity testing of the parameter 

inputs (class 1 above), the values of the other inputs may be held 

constant while just the parameters are varied. Alternatively a 

post-processor could take the results of the randomly generated 

input values, group together those which differ only in a parameter 

input, and perform analysis on the groups. 

For a given set of rules, it is possible that several conclusions 

can be reached from a single set of input values. This may be 

undesirable when an action is to be taken on the basis of the first 

conclusion reached and when the input values become available 

dynamically, i.e. not simultaneously. The simulation program also 

runs in a dynamic mode. This is illustrated in appendices 5, 6, 7. 

Appendices 6, 7, and 8 will be used to present an example of the 

second class of errors. 
26 

As appendix 5 shows, the rule base represented by the graph can be 

run with just a subset of the input values; the additional subsets 

are added until all the values have been input or a conclusion is 

reached. If simulation with a subset of input values reaches a 

conclusion, no additional subsets are run. This is what has 

occurred in appendices 6 and 7. The input values for these two 

runs are both subsets of those in appendix 8. In the runs detailed 

in appendices 6 and 7, different conclusions have been reached 

based on the order in which the input values in appendix 8 have 

become available. This is an example of the second class of 

errors. 

Appendix 9 gives several rules which were added to the original 

rule base. These will be used to illustrate the capabilities of 

the system for identifying the third class of errors, those which 

other researchers have detected using analytic methods but which 

may also be detected using our techniques. 

The last rule wqs identified as problematic during the translation 

process which generates the graph. This is an example of an error 

in which an antecedent conjunct in the LHS of some rule is neither 

an input nor a conclusion of some other rule. The conjunct 

'killshuman' is not parenthesized and therefore indicates an 

intermediate conclusion; however, .there is no rule which has 

'killshuman' as its RHS. Such an error might have many 'sources'. 

For example, the conjunct could havc- been misspelled in either the 

LHS or the RHS of some rule, the rule which concludes this conjunct 

could have been omitted, or it may have been intended that this 

conjunct be an input. 
27 

Appendix 10 illustrates the data on message arrivals which are 

stored for each node. Appendix 11 is a report on the frequency of 

node firings for the graph generated from the rules in appendix 1 

with the rule for 'human' replaced by the one in appendix 9 and the 

rule for 'man' from appendix 9 added. The nodes which never fired 

positively should be examined more fully. This does not 

necessarily indicate a problem, at least for the number of runs 

done, but it points to situations which bear greater scrutiny. For 

example, the conclusions 'shark' and 'ape' were never reached, but 

there is nothing wrong with the rules that lead to them. On the 

other hand, the conclusions 'man' and 'human' from the first two 

additional rules in appendix 5 also never were reached, and closer. 

scrutiny indicates that these rules were circular, each requiring 

the other conclusion to be reached. 

Another possible cause for a conclusion never being reached would 

be if the rules leading to it were directly contradictory. For 

example, conclusion C would be unreachable if the same predicate 

were used positively in the LHS of an intermediate conclusion A, 

' and negatively in the LHS of an intermediate conclusion B, and the 

rule with C in its RHS had A and B in its LHS. Conclusion C would 

also be unreachable if A and B referred to mutually exclusive 

comparison. Running multiple simulations identifies the rules that 

bear greater scrutiny. 

Appendix 12 is a subset of the graph in appendix 3. The original 

graph was partitioned, and appendix 8 contains only the nodes 

corresponding to the rules that can be used to lead to the 

conclusion 'ape'. The smaller graphs created by partitioning allow 
28 

more simulations to be run in a given amount of time. They can be 

used for conclusions of particular interest, perhaps those which 

are only to be reached under certain conditions. 

6. CONCLUSIONS 

It has been shown that Evidence Flow Graph methods can be used to 

detect errors and inconsistencies in expert systems. This has been 

demonstrated experimentally by taking an existing rule base and 

converting it automatically to an evidence flow graph. This flow 

graph was then used as the input to a simulation program which 

predicted the performance of the expert system under a variety of 

conditions. Faults were detected during the translation process 

and as a result of simulation runs. 

The set of techniques developed is general in nature and has a 

number of advantages over other techniques for detecting’problems 

as part of the verification process: 

a) It provides a uniform representation for various 

knowledge representations and control strategies. 

b) The evidence flow graph allows for analysis to 

recognize unused inputs and subconclusions, 

unreachable conclusions, disjoint and hence 

partitionable subgraphs, and relationships between 

inputs and outputs. 

comprehensible representation in which many of these 

can be readily recognized. 

It also provides a visually 
29 

It allows for simulation using techniques developed 

for non-linear stochastic systems. 

It allows the consideration of different orders 

of input availability, and potentially allows for 

multiple data values for a single parameter. 

It allows for sensitivity testing to determine where 

small changes in the values of input parameters 

will result in different conclusions. 

It was concluded that evidence flow graph techniques do have a role 

to play in performing sensitivity analyses as part of the 

verification process for expert systems. More work, however, needs 

to be done to make these techniques practically useful. Some of 

the major future activities needed are: 

1) The development of a program that will automatically develop 

simulation test sequences based on meta-knowledge about such items 

as possible ranges of input data and order of data availability. 

2) The development of a post-processor program to automatically 

analyze the output data from the simulation runs and to detect 

problems. The simulation program generates a large volume of data 

when performing monte-carlo analyses which is not practical to 

examine by hand. This post-processing program will need to embody 

knowledge about faults that could occur and how to detect them. 

3) Further development of techniques to partition flow graphs so as 

to reduce the search space for faults. 
30 

4) Expansion of the translation program to translate more complex 

knowledge forms into evidence flow graphs. 

A successful start has been made on developing techniques which can 

be used for the verification of expert systems. The work described 

in this report has hopefully laid some of the foundation which can 

be used to assure that the expert systems used in our space program 

are reliable and safe. 
LHS* 

Appendix 1: Sample Rule Base 

(((has-skin) (moves - around) (breathes)) 

(((moves - around) (breathes) (eats)) 

((animal (has - fins) (can - swim)) 

(((bites) (length > 5) fish) 

(((edible) fish) 

(((has - wings) animal) 

((bird (can - fly)) 

((bird (long - legs)) 

(((warm - blooded) animal (suckles - young)) 

((mammal (talks) (age < 100)) 

(((lives -- on trees) (age < 100) mammal) 

I 

RHS CF 

animal 

animal 

fish 

shark 

salmon 

bird 

canary 

ostrich 

mammal 

human 

*The conjuncts are enclosed in parentheses, if they are input 

predicates, but not if they are inferred predicates, i.e. those 

on the RHS of some rule. 
32 

Appendix 2: Evidence Flow Graph Representation of the Rule Base 
33 

Appendix 3: Symbolic Representation of the Evidence Flow Graph 

(INPUT - NODES 

(29 (LIVES ON - TREES)) 

(26 (AGE))- 

(25 (TALKS)) 

(23 (SUCKLES YOUNG)) 

(18 (CAN FLY)) 

(22 (LONG LEES)) 

(16 (HAS-WINGS)) 

(14 (EDIBLE)) 

(11 (LENGTH)) 

(10 (BITES)) 

( 8 (CAN SWIM)) 

( 7 (HAS-FINS)) 

( 5 (EATS)) 

( 1 (HAS - SEIN)) 

( 3 (BREATHES)) 

( 2 (MOVES AROUND)) 

) 

(OTHER - NODES 

(* (30 APE 

(* (28 HUMAN 

( (24 MAMMAL 

(* (21 OSTRICH 

( * ( 19 CANARY 

( (17 BIRD 

(* (15 SALMON 

(* (13 SHARK 

( ( 9 FISH 

( ( 6 ANIMAL 

( ( 4 ANIMAL 

) 

0.9 (((29 0.3)) ((27 0.3)) ((24 0.3))))) 

0.9 (((22 0.3)) ((6 0.3)(4 0.3)) ((23 0.3) 

0.9 (((17 0.45)) ((20 0.45))))) 

0.9 (((17 0.45)) ((18 0.45))))) 

0.9 (((16 0.45)) (( 6 0.45)(4 0.45))))) 

0.9 (((14 0.45)) (( 9 0.45))))) 

0.9 (((10 0.3)) ((12 0.3)) (( 9 0.3))))) 

0.9 (((6 0.3)(4 0.3)) ((7 0.3)) ((8 0.3))))) 

0.9 (((2 0.3)) ((3 0.3)) ' ((5 0.3))))) 

0.9 (((1 0.3)) ((2 0.3)) ((3 0.3))))) 

0.9 (((24 0.3)) ((25 0.3)) ((27 0.3))))) 

(COMPARISON - NODES 

(ELSE - NODES) 

(NOT - NODES) 

1 
NODE 

Initial node firings: 

25 

18 

16 

5 

3 

29 

26 

I 

23 

14 

11 

10 

8 

7 

1 

2 

I 

Appendix 4: Sample Run 1 

talks 

warm - blooded 

long - legs 

can - fly 

has - wings 

eats 

breathes 

lives on trees 

age 

suckles - young 

edible 

length 

bites 

can swim 

has - fins. 

has skin 

moves - around 

-- 

- 

- 

VALUE FIRED 

0 

0 

1 

0 

1 

1 

1 

0 

46.38 1 

1 

0 

4.90 1 

0 

1 

1 

0 

1 

34 

Conclusion: 

THERE IS ENOUGH EVIDENCE ( 0.90 ) TO SUGGEST THAT ostrich 
35 

NODE 

Initial node firings: 

25 talks 

20 long - legs 

18 

23 suckles - young 

14 edible 

can - fly 

11 length 

Appendix 5: Sample Run 2 

VALUE FIRED 

can swim 

lives on trees 

- 8 

29 -- 

Additional Node Firings: 

22 warm - blooded 

7 has - fins 

5 eats 

1 has - skin 

Additional Node Firings: 

16 has - wings 

2 moves - around 

Additional Node Firings: 

10 bites 

3 breathes 

Additional Node Firings: 

Input nodes exhaused 

198.56 1 

0 

1 

0 

0 

0 

6.93 1 

1 

1 

1 

1 

0 

1 

>>>>>>>INSUFFICIENT EVIDENCE FOR REACHING ANY CONCLUSION<<<<<<< 
NODE 

Initial node firings: 

1 has - skin 

2 moves - around 

25 talks 

22 warm - blooded 

11 length 

20 long - legs 

16 has - wings 

5 eats 

3 breathes 

~ 

Appendix 6: Sample Run 3 

29 lives -- on trees 

Conclusion: ~ 

VALUE 

4.90 

FIRED 

0 

1 

0 

0 

1 

1 

1 

1 

1 

1 

36 

THERE IS ENOUGH EVIDENCE ( 0.90 ) TO SUGGEST THAT ostrich 
37 

NODE 

Initial node firings: 

Appendix 7: Sample Run 4 

VALUE FIRED 

10 

8 

22 

18 

16 

2 

5 

3 

26 

23 

bites 

can swim 

warm blooded 

- 

- 

can - fly 

has - wings 

moves around - 

eats 

breathes 

age 

suckles - young 

0 

0 

0 

1 

1 

1 

1 

1 

46.38 1 

1 

Conclusion: 

THERE IS ENOUGH EVIDENCE ( 0.90 ) TO SUGGEST THAT canary 
38 

Appendix 8: 

NODE 

Initial node firings: 

25 

22 

20 

18 

16 

5 

3 

29 

26 

23 

14 

11 

10 

8 

7 

1 

2 

talks 

warm - blooded. 

long - legs 

can - fly 

has - wings 

eats 

breathes 

lives on trees 

age 

suckles - young 

edible 

length 

bites 

can - swim 

has - fins 

has - skin 

moves - around 

-- 

Sample Run 5 

VALUE FIRED 

0 

0 

1 

1 

1 

1 

1 

1 

46.38 1 

1 

0 

4.90 1 

0 

0 

0 

0 

1 

Conclusion: 

THERE IS ENOUGH EVIDENCE ( 0.90 ) TO SUGGEST THAT ostrich 

Conclusion: 

THERE IS ENOUGH EVIDENCE ( 0.90 ) TO SUGGEST THAT canary 
39 

Appendix 9: Some Additional Rules 

(((has beard) human) man 

((man (eats) (can-sing)) human 

((ape kills - humans (moves - around)) monster 

- .99 ) 

.99 ) 

-9) 
40 

Appendix 10: DETAILS OF MESSAGE ARRIVALS ON NODE 9 

NODE CONCLUSION : fish 

SOURCE SOURCE 

NODE CONCLUSION 

6 animal 

4 animal 

has fins 

can swim 

7 - 

8 - 

ARC NUMBER 

TYPE MESSAGES 

or 201 

or 201 

and 196 

and 201 
~~ 

_____ ~ 

Appendix 11: Frequency of Node Firings Report 

NODE# NODE CONCLUSION ZERC 

33 lives on trees 46 

31 can sYng29 ha s-be a rd 

26 

25 

23 

22 

20 

18 

16 

14 

11 

10 

8 

7 

5 

3 

2 

1 

27 

12 

30 

28 

24 

17 

9 

6 

4 

34 

21 

19 

15 

13 

agetalks 

suckles young 

warm-blooded 

long legs 

can Tly 

ha s-w i ng s 

edigle 

length 

bites 

can swim 

has-fins 

eats 

breathes 

moves around 

has sEin 

age-< 100 

length > 5 

man 

human 

mammal 

bird 

fish 

animal 

animal 

ape 

ostrich 

canary 

salmon 

shark 

48 

57 

52 

46 

52 

42 

45 

53 

51 

40 

46 

48 

42 

51 

50 

44 

47 

48 

73 

65 

92 

93 

91 

87 

93 

82 

82 

92 

91 

90 

93 

92 

NON-ZERO TOTAL 

50 

48 

36 

43 

50 

42 

54 

51 

43 

45 

55 

47 

48 

54 

45 

47 

53 

50 

46 

22 

28 

0 

0 

2 

9 

2 

15 

12 

0 

5 

5 

2 

0 

96 

96 

93 

95 

96 

94 

96 

96 

96 

96 

95 

93 

96 

96 

96 

97 

97 

97 

94 

95 

93 

92 

92 

93 

96 

95 

97 

94 

92 

96 

95 

95 

92 
Appendix 12: Partitioned Graph for Output 'APE' 

(INPUT - NODES 

(23 (SUCKLES YOUNG)) 

( 1 (HAS SKIR)) 

( 5 (EATS)) 

(22 (LONG ZEGS)) 

(26 AGE)^ 

( 3 (BREATHES)) 

( 2 (MOVES AROUND)) 

(29 (LIVES -- ON TREES)) 

I 

! (OTHER - NODES 

42 

(* (30 APE 0.9 (((29 0.3)) ((27 0.3)) ((24 0.3))))) 

( ( 4 ANIMAL 0.9 (((1 0.3)) ((2 0.3)) ((3 0.3))))) 

( ( 6 ANIMAL 0.9 (((2 0.3)) ((3 0.3)) ((5 0.3))))) 

( (24 MAMMAL 0.9 (((22 0.3)) ((6 0.3)(4 0.3)) ((23 0.3))))) 

(ELSE-NODES) 

(NOT - NODES) 
Ref e rences 

Ackerman, W.B. 1982. Data Flow Languages. IEEE Computer 15.2: 

15-25. 

Chisvin, L. 1988. Using Discrete Event Simulation to Predict the 

Network Communication Performance of Message-Based Data Flow 

Multiprocessor Systems. Master‘s Thesis, Worcester Pdlytechnic 

Institute, Worcester, MA. 

Green, P.G. and W.R. Michalson. 1987. Real-Time Evidential 

Reasoning and Network Based Processing. Proceedin s of the IEEE 

First Annual International Conference - on Neura * Networ s,Vc 2, 

pp. 3-EmZ-5. 

Johnson, S. 1988. Validation of Highly Reliable, Real-Time 

Knowledge-Based Systems. Proceedings of the 2nd Annual Workshop on 

Space Operations Automation and Robotics (SOAR 88). 

Michalson, W.R., Green, P.E., Duckworth, R.J. 1987. Evidence Flow 

Graphs: A Unified Representation for Distributed Artificial 

Intelligence Systems. Worcester Polytechnic Institute Report 

EE87IMP10. 

Michalson, W.R. 1988. A Computing Architecture for Real-Tim.e 

Decision Making. Ph.D. Dissertation, Worcester Polytechnic 

Institute, Worcester, MA. 

Nguyen, T.A., Perkins, W.A., Laffey, T.J. and Pecora, D. 1985. 

Checking .an expert system knowledge base for consistency and 

completeness. IJCAI9, pp. 376-378. 

Nguyen, T.A., Perkins, W.A., Laffey, T.J. and Pecora, D. 1987. 

Knowledge .base verification. - AI Magazine, Vo1.8, NO.^., e 

65-79. 

Law, A.M. and Larme C.S. 1984. An Introduction - to Simulation 

mgmSCmT&- - - 

O’Keefe, R.M., Balci, O., and Smith, E.P. 1987. Validating Expert 

System Performance. IEEE Expert, Vo1.2, NO.^., pp. 81-89. 

Russell, E.C. 1983. Building Models with Simscript 11.5. CACI, 

Inc., Los Angeles, CA. 

Stachowitz, R.A., Chang, C.L., Stock, T.S., and Combs, J.B. 1987. 

Building Validation Tools for Knowledge-Based Systems. - of the First Annual Workshop on S ace 

Robotics (S0-7), pp. 709% 

2491, Houston, TX., August 1987. 

Suwa, M., Scott, A.C. and Shortliffe, E.H. 1982. An approach to 

verifying completeness and consistency in a rule-based expert 

system. AI Magazine, - Vo1.3, No.4, pp. 16-21. 
Report Documentation Page 

I. Report No. 2. Government Accession No. 

NASA CR-181810 

4. Title and Subtitle 

Evidence Flow Graph Methods for Validation and 

Verification of Expert Systems 

17. Key Words (Suggested by Authorls)) 

7. Authorls) 

Lee A. Beckerr Peter G. Greenr and Jayant Bhatnagar 

18. Distribution Statement 

9. Performing Organization Name and Address 

Worcester Polytechnic Institute 

Worcester, MA 01699 

19. Security Classif. (of this report) 20. Security Classif. (of this page) 21. No. of pages 

Unclassified Unclassified 45 

2. Sponsoring Agency Name and Address 

National Aeronautics and Space Administration 

Langley Research Center 

Hamptonr VA 23665-5225 

22. Price 

A0 3 

5. Supplementary Notes 

Langley Technical Monitor: Sally C. Johnson 

Final report 

3. Recipient's Catalog No. 

5. Report Date 

July 1989 

6. Performing Organization Code 

8. Performing Organization Report No. 

10. Work Unit No. 

505-66-21-01 

11. Contract or Grant No. 

NAG1-809 

13. Type of Report and Period Covered 

Contractor Rewrt 

14. Sponsoring Agency Code 

6. Abstract 

This final report'describes the results of an investigation into the use 

This was approached by developing a translator to convert 

of evidence flow graph techniques for.perforrning validation and verification 

of expert systems. 

horn-clause rule bases into evidence flow graphs, a simulation program, and 

methods of analysis. 

which contained errors. 

identifying a variety of problems, for example that the order of presentation 

of input data or small changes in critical parameters could affect the output 

from a set of rules. 

These tools were then applied to a simple rule base 

It was found that the method was capable of 

.Knowledge-Based Systems 

Expert Systems 

Software Validation 

Unclassified - Unlimited