Appendices

1. Symbolic Evaluation of Atomic Formulas2. General Regression Neural Nets

1. Symbolic Evaluation of Atomic Formulas

A common type of atomic formula in a rule-based expert system is of the form:

<VARIABLE> <RELATION> <CONSTANT>   (A.2.1)

where <RELATION> is one of the relations, =, <, >, <=, or >=.

The following table shows when an atomic formula of this form is true or false given conditions on <VARIABLE> of same form, A.2.1.

In this table, "TRUTH CONDITION" specifies conditions under which the atomic formula is true for all numbers in the interval. "FALSE CONDITION" specifies conditions under which the atomic formulas are false for all numbers in the interval. The following restrictions on the variables a, b and c apply:

a is in [-INFINITY,INFINITY)
b is in (-INFINITY,INFINITY]
c is in (-INFINITY,INFINITY)

ATOMIC FORMULATRUTH CONDITIONFALSE CONDITION
(a,b)<cb<=ca>=c
[a,b)<cb<=ca>c
(a,b]<cb<ca>=c
[a,b]<cb<ca>=c
   
(a,b)=<cb<=ca>=c
(a,b)=<cb<=ca>c
(a,b]=<cb<=ca>=c
[a,b]=<cb<=ca>c
   
[a,b]=ca=b=ca != b or a != c or b != c
   
(a,b)>ca>=cb<=c
(a,b]>ca>=cb<c
[a,b)>ca>cb<=c
[a,b]>ca>cb<c
   
(a,b)=>ca>=cb<=c
[a,b)=>ca>=cb<=c
(a,b]=>ca>=cb<c
[a,b]=>ca>=cb<c

2. General Regression Neural Nets

A general regression neural net (GRNN) is a method for estimating a function from a set of its values at particular points in its domain. Although the GRNN algorithm can be put in the form of a neural net, it is best understood as an interpolation. In particular, GRNN interpolates from known data points by computing a weighted average of nearby points. The weights in this average decay exponentially with distance from the point where the function is being estimated.

Notation

The following notation will be used:

Prerequisites for GRNN

To carry out a GRNN computation, it is necessary that a distance function be defined between any two points in the input domain. The Euclidean distance function works well for GRNNs, although any distance function can be used. The Euclidean distance is defined by:

d(P1, P2) = sqrt( SUM( over fields i)(p1i - p2i)**2)))

A weight function from pairs of points to real numbers is defined as follows:

w(P1,P2) = exp(-K*d(P1,P2))

In other words, the weight assigned to P2 for a GRNN estimate at P1 decays exponentially with the distance from P1 to P2. K is parameter that determines how fast the decay occurs.

The GRNN Interpolation

Following is the GRNN interpolation of a function fn:

grnn(P1) = SUM(all points P2 in data set)w(P1,P2)*fn(P2))

This says that the GRNN estimate of fn at a point is the weighted average of the known function values, where the weights decay exponentially with distance from the point where the estimate is being made.

3. Verification and Validation: Past Practices

Significant numbers of articles on verification and validation of knowledge-based systems first appeared in the literature in the early 1980's. Many authors who have written about or attempted the verification and/or validation of knowledge-base systems have their own definition of the concepts. The method that they use or the system that they design to accomplish the task(s) is usually a reflection of that particular definition. A few authors have asserted that verification and validation are the same.

The following tables summarize past work in verification and validation. Complete references appear in the bibliography.

VALIDATION METHODS THAT HAVE BEEN USED:

METHODEXPERT SYSTEMREFERENCE
Turing Test VariationMycin
KBSCD		Yu, et al., 1979
Agarwal, Kannan,Tanniru,1993
Simple Comparison with
Expert		Diabetes Mellitus
Tegument
Hemody. Monitoring		Lehmann, et. al., 1993
Potter & Ronan, 1987
Koski, et. al., 1991/92
Comparison w/Expert Using
Sensitivity Analysis		ESPE (Tool Set)
Prospector		Franklin, et. al., 1988
Gaschnig, 1979
Comparison w/Expert Using
Freq. Analysis &
Distance Analysis		PNEUMON - IAVerdaguer, et. al., 1992

Table A.3-1: Validation Methods

VERIFICATION METHODS THAT HAVE BEEN USED:

METHODTOOL
(If Exists)		REFERENCE
Tables & Pairwise Rule
Comparisons		Rule-Checker
Check		Suwa, Scott, Shortliffe, 1982
Nguyen, et al.,1987
Decision Tables of 'Contexts'ESC
GRAFCET		Cragun & Steudel, 1987
Renard, Sterling, Brosilow, 1993
Meta-KnowledgeEVA
Valid		Stachowitz, Combs, 1987
Laurent (ESPIRIT-II)
Analytical Hierarchy Process Bahill, Jafar, Moller, 1987
Graphs:
Constraint Connection
Flowgraph
Parameter Dependency Network		 Freeman, 1985
Fenton, Kaposi, 1987
Agarwal, Tanniru, 1992
Petri - Nets Agarwal & Tanniru, 1992
Liu & Dillon, 1991
Partitioning:
Graph-Based
Clustering
Clustering Algorithm
Category Partition Method Testing		 Jacob & Froscher, 1986
Cheng & Fu, 1985
Jacob & Froscher, 1990
Amla & Ammann, 1992
Incidence Matrix TechniqueIMVERCoenen, Bench-Capon, Kent, 1994
Ripple-Down Rules Kang, Gambetta, Compton, 1994

Table A.3-2: Verification Methods

DOMAIN - INDEPENDENT SOFTWARE TOOLS USED FOR V. & V.:

USEDVerification
TOOLPURPOSEMETHODREFERENCE
RITCaGValidationTest Case GeneratorGupta, Biegel, 1990
un-namedValidationRuns Test CasesKang & Bahill, 1990
ESPEValidationSensitivity AnalysisFranklin, et al., 1988
CheckVerificationTablesNguyen et al., 1987
ESCVerificationDecision TablesCragun, Steudel, 1987
GRAFCETVerificationGraphical Design
Lang./Dec. Tables		Renard, Sterling, Brosilow, 1993
un-namedVerificationDecision Tablesanthienen,Dries, 1993
EVAVerificationMeta-languageStachowitz,Combs,1987
ValidVerificationMeta-languageJean-Pierre Laurent (ESPIRIT-II project) - Europe
BEACONVerificationGraphsFreeman, 1985
un-named VerificationLayered Support GraphsValiente, 1992
VALIDATORVer. & Valid.Syntax & Semantics ChecksJafar & Bahill
COVERVerificationFirst-Order LogicPreece, et al. 1992
Expert ChoiceVerificationAnalytical-Hierarchy ProcessBahill,Jafar, Moller, 1987
SpotVerificationProlog Rule BaseLane, 1989
KB-ReducerVerificationKB reductionGinsberg, 1988
IMVERVerificationIncidence matricesCoenen, Bench-Capon, Kent, 1994
un-named Clustering AlgorithmJabob & Froscher, 1990
in-progressVer. & Valid.Meta-language, GUI,
Visual Guide to Rule in Flow-Graphs		Traylor, Schwuttke, Quan, 1994
(JPL-NASA)

Table A.3-3: V&V Software
ap1.gif - 8.58 K

Figure 10

For knowledge bases other than binary systems with more than two hypotheses in rules, an alternative illustration is proposed. An incidence matrix, with rule numbers as values, is developed. The rules are clustered using their commonality of hypotheses and conclusions. The clusters are then ordered so that the bandwidth of the incidence matrix is minimum. Within a cluster, the hypotheses are placed before the conclusions. Figure 10 shows the final incidence matrix for KB1. Note that the partitions are evident. There are three sub-matrices which include all variables of a cluster.
ap2.gif - 4.23 K

ap3.gif - 2.08 K

Figure 11

Another method of representing a knowledge base is the petri-net method. Each variable is given a name, and each value, a digit. For example, the variable "Do you buy lottery tickets?" is assigned the letter "L" and the values "no" and "yes", "1" and "2" respectively. For example, the hypotheses "Do you buy lottery tickets?"= "no" is assigned to variable "L1". In Figure 11, a table in the upper lists the correspondence between the hypotheses and the variables for the knowledge base KB1. There are also two graphical representations of KB1. The upper one relates the variables without details of the logical syntax. The lower one provides those details. The dashed line indicates that the hypotheses are subjected to logical operator "or", and a solid line, "and", as shown in the legend.
ap4.gif - 3.92 K

The terms left blank in the matrix are zero. The product of matrix A from figure 3 and matrix B from figure 4 is called matrix C, shown in figure 5. If subjected to a boolean operation, its non-zero terms become unity. It corresponds to all connections in figure 2.

Figure 5
The dependency relation in the union of the immediate dependency relation and composition operation. It is shown in figure 8 and 9.
ap5.gif - 6.82 K

Figure 6Figure 2
ap6.gif - 7.29 K

Figure 8Figure 9


Bibliography
Link to Table of Contents

[Table of Contents]