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


2. THEORETICAL FOUNDATION OF EXPERT SYSTEM VERIFICATION AND VALIDATION

In general, V & V of expert systems consists of identifying anomalies such as redundant, contradictory, or deficient knowledge. An anomaly is a difference between what is expected of KB structure and system performance, and what is actually observed. Anomalies are considered as potential errors since not all of them are errors. However, many common KB errors can be identified by identifying anomalies. Anomalies may also result in inefficiency in terms of performance, maintenance, etc.

Before commencing the discussion on the theoretical foundation of expert system V&V, a short note on representations is needed. Most of the work concerning the errors and anomalies that can occur in expert systems has been carried out on rule-based representations. Parallels do exist with frame- and object-based representations. In this section we concentrate on two principal methods of knowledge representation used in expert systems: production rules and object-based representations. Since both rule-based and structured object representational paradigms have their strengths, some efforts have been made to combine the two.

2.1. LOGICAL FOUNDATION OF RULE-BASED ANOMALIES

A variety of methods have been built for detecting the above-mentioned anomalies in rule bases. The early methods looked for anomalies between pairs of rules only, while the most sophisticated methods detect anomalies manifested over chains of inference.

Rule-based expert systems have foundation in formal logic. There is a relation between the production rules of such systems and the implication statements of logical theorems, and also between the facts of the knowledge base and the axioms of logic. This relationship has been the basis for systematic checking methods for rule bases. These methods can be used to determine the internal self-consistency and completeness of rule bases, by interpreting the rules as logical expression followed by syntactic inspection and manipulation. However, terms such as consistency and completeness have slightly different meanings, as shown in Table 1.


TABLE 1
Consistency and Completeness in Logic and Rule Bases
 
Logic Rule bases
Consistency A set of propositions is consistent if and only if there is some interpretation of the symbol in the set such that no contradictions are entailed. A rule set is consistent if and only if there is no way the rules can assert a contradiction from valid input data. (the interpretation of the symbols is defined by the knowledge engineer).
Completeness A set of propositions is complete if and only if all desired inferences can be derived from the set by a sound and complete inference engine. A rule base is complete if and only if it can cope with all possible situations that can arise in its domain.

We choose to focus upon rule-based expert systems that are based on first-order logic because rule-based systems are the most widely used type of expert system and the semantics of rule-based systems based on logic are well known.

The theoretical framework in which anomaly detection systems for rule-based knowledge bases have been be analyzed is based on the first-order logic. The terminology and notation used to express the knowledge base is the following (Preece and Shinghal, 1994):

  • A rule Ri is a formula of the form where each li and m are first-order literals.
  • For each rule Ri, we write antec(R) = {l1, ..., ln} and conseq(R) = m.
  • A rule set R is a set of rules
  • The goal-literals is the set of all ground literals that could be output from the rule set.
  • The input-literals is the set of all ground literals that constitute all possible inputs to the rule set.
  • A semantic constraint is a set of literals {l1, ..., ln} such that their conjunction is regarded as a semantic inconsistency. All semantic constraints for a rule set form the set of semantic constraints.
  • An environment [curly epsilon] is a subset of the input literals that does not contain any semantic constraint. [curly epsilon] is the set of all possible such environments.

The anomalies of rule bases can be informally defined as follows:

  • Unsatisfiable rule: A rule is unsatisfiable iff (iff = if and only if) there is no way of deducing the rule antecedent from any legal input.
  • Unusable rule: A rule is unusable iff the consequent of the rule subsumes neither a goal literal nor any antecedent literal in the rule set.
  • Subsumed rule: A rule is subsumed iff there exists a more general rule.
  • Redundant rule: A rule is redundant in the rule set if the rule is not essential for the computation of any goal literal from any environment.
  • Inconsistent rule pair: Two rules are an inconsistent pair iff both rules are applicable and derive a semantic constraint.
  • Inconsistent rule set: A rule set is inconsistent iff from some legal input it is possible to derive a semantic constraint.
  • Circular rule set: A rule set is circular iff the antecedents cannot be derived from any environment except by adding the rule set consequent.
  • Unused input: An input literal is unused iff any result that can be computed from an environment can also be computed from that environment minus the literal input.
  • Incomplete rule set: A rule set is incomplete iff there exists some output that cannot be computed from any environment.


FIGURE 1 Four types of anomaly.

The use of formal logic will enable us to detect each type of anomaly by considering only the syntactic form of expressions in the knowledge base. For example, consider the two rules l1 [wedge] l2 —> m and l1 —> m. From an understanding of the semantics of the logical operators [wedge] ("and") and —> ("implies"), the first rule is redundant, since it is just a specific version of the second one, which is more general. We can detect this by looking for that particular case of redundancy in which we have two rules with identical consequences, such that the literals in the antecedent of one rule are a subset of the literals in the antecedent of the other.

It is important to realize that such anomalies may not represent actual errors in a rule base, but rather symptoms of possible errors. For example, a redundant rule may occur because there is missing knowledge, the rule l1 —> m should have been l1 [wedge] l3 —> m. It is up to the knowledge engineer together with the human expert to decide what actions to take when such anomalies are detected.

Based on the semantics of first-order logic, four basic types of anomaly have been identified by Preece et al. (1992), some of which have a number of special cases as shown in Figure 1.


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.