Brought to you by EarthWeb
IT Library Logo

Click Here!
Click Here!

Search the site:
 
EXPERT SEARCH -----
Programming Languages
Databases
Security
Web Services
Network Services
Middleware
Components
Operating Systems
User Interfaces
Groupware & Collaboration
Content Management
Productivity Applications
Hardware
Fun & Games

EarthWeb Direct EarthWeb Direct Fatbrain Auctions Support Source Answers

EarthWeb sites
Crossnodes
Datamation
Developer.com
DICE
EarthWeb.com
EarthWeb Direct
ERP Hub
Gamelan
GoCertify.com
HTMLGoodies
Intranet Journal
IT Knowledge
IT Library
JavaGoodies
JARS
JavaScripts.com
open source IT
RoadCoders
Y2K Info

Previous Table of Contents Next


4. CONTRIBUTIONS OF SOFTWARE ENGINEERING TO EXPERT SYSTEM DEVELOPMENT

Software engineering has made a number of significant contributions to expert system development. We review these in this section.

4.1. EVALUATION

There are two ways of ensuring the correctness of a system. One is to prevent errors from occurring during construction; the other is to check for errors after construction is completed. Since error-free construction is generally considered to be infeasible, construction is almost always followed by evaluation. We have referred to the evaluation phase informally above as "testing." In software engineering, evaluation is more formally considered as having two components: verification and validation.

We make a distinction between verification and validation that is widely but not universally accepted. Indeed, some authors use the abbreviation "V&V" as if it was a single noun. Following Boehm (1979), we define verification to denote the process of checking that the system is internally consistent, and we define validation to denote the process of checking that the system performs according to the client's requirements. Informally, we can say that verification answers the question "Have we built the system right?" and validation answers the question "Have we built the right system?"

Evaluation of early expert systems was straightforward: if the expert system gave the same answers as the expert, it was assumed to be correct. As expert systems have increased in complexity, the importance of evaluating them has increased, and evaluation techniques have been borrowed from software engineering (Grogono, Batarekh, Preece, Shinghal, and Suen, 1990).

4.1.1. Verification

Geldof et al. (1996) distinguish two forms of verification: macroverification takes place early in the development cycle and identifies structural and conceptual problems; microverification takes place later in development and provides a detailed analysis of the components of the system.

Software verification is very difficult; even after 20 years or more of research, only a very small proportion of software is formally verified. (Compilers check the syntax and "static semantics" of programs, but this is not usually considered to constitute verification.) The situation for expert systems is somewhat different: since rule bases have a simple and logical structure, verification is straightforward and can even be automated.

An expert system that fails verification is internally inconsistent or has structural defects. The possible defects of a rule base fall into four main categories: ambivalence, circularity, deficiency, and redundancy.

Ambivalence. A rule base is ambivalent if it can derive contradictory or inconsistent results from a single set of input data. A rule base containing the rules

A B —> R

B A —> R

is ambivalent because, given the set {A,B} as input facts, the rule base can use either the first rule to infer that R is true or the second rule to infer that R is false. (The first rule is read "From A and B, infer R." The second rule is read "From B and A, infer not-R.")

Circularity. A rule base is circular if there are infinite chains of rules. For example, a rule base containing the rules

A —> B

B —> C

C —> A

is circular. Even if the inference engine is clever enough to avoid getting stuck in a loop, circularity strongly suggests an error in the formulation of the rules.

Deficiency. A rule base is deficient if it contains incomplete rule chains. For example, if we assume that the set of possible input facts is {A,B} and the set of possible conclusions is {C,D}, then the rule base

A —> X

B —> Y

X —> C

Z —> D

is doubly deficient because input B cannot be used to infer any conclusions and conclusion D can never be derived from the input data.

Redundancy. A rule base is redundant if rules can be deleted from it without changing the set of possible inferences. The rule base

A —> B

B —> C

A —> C

is redundant because the first two rules are sufficient to infer C from A, by transitivity. Redundancy is harmless -- although it may affect the response time of the expert system -- but its presence suggests errors in the formulation of the rules.

Structural errors in a rule base are not necessarily due to mistakes in formalizing the expert's knowledge. They are usually present for more mundane reasons. The deficiency in the example above is due to the rules B —> Y and Z —> D. In an actual rule base, these rules might be

large-flat-base —> box-is-stable

and

box-stable —> can-take-load

In this case, the deficiency is caused by inconsistent naming rather than a logical error.

Verification treats the rule base as a formal system; consequently, verification can be automated, at least in principle. In practice, full verification of a large rule base may be infeasible. Suppose that the rule base contains N rules. Processing each individual rule requires time time proportional to N. Processing all pairs of rules (perhaps for a partial ambivalence check) requires time time proportional to N2. Processing all chains of k rules requires time time proportional to Nk. It follows that full verification of a rule base in which inferences may involve k steps will also require time time proportional to Nk. Since N may be in the thousands, full verification is infeasible even for moderate values of k. The time complexity may be reduced by modularizing the rule base, a possibility discussed further in Section 4.2.

In the above discussion, we have assumed that there are no certainty factors associated with rules and that verification can be based on classical logic. If rules are associated with certainty factors, verification is possible but the results may not be so clear-cut. For example, an apparently redundant rule may not be redundant if its presence increases the certainty of a conclusion.


Previous Table of Contents Next

footer nav
Use of this site is subject certain Terms & Conditions.
Copyright (c) 1996-1999 EarthWeb, Inc.. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Please read our privacy policy for details.