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


3.4.1. KRUST

KRUST (Knowledge Refinement Using Semantic Trees) refines rule bases considering rule priority, taking into consideration the role of control. It is argued that refinement can enhance the functionality of validation systems. The goal is not only to simply identify possible faults, but to explore them further so that anomalies can be rectified.

In common with many other refinement tools, KRUST refines a rule-based expert system on evidence provided by examples that the KBS fails to solve correctly. In contrast with other systems, KRUST considers many possible refinements to cure a single failure. The architecture of KRUST is the following (Figure 12):

  • A set of training examples that the expert system fails to solve is given to the input. Possible causes of failure are detected and rules are classified into different categories of interest.
  • A set of possible refinements is generated, each consisting of a set of rule changes: rules can be strengthened (made more difficult to satisfy), weakened (made easier to satisfy), given an increased chance of firing, etc.
  • The first filter discards those refinements that are poor (based on meta-knowledge). Those that remain are incorporated into the KB, creating a set of refined KBs.
  • The KBs are run against the training examples and those that fail again are rejected.
  • The remaining KBs are suggested to the expert or ranked by a detailed judgment process. As a result, the most suitable KB is selected. Note that this last step requires an appeal to the implicit model in the mind of the expert.


FIGURE 12 KRUST.

KRUST reacts to the most common inconsistencies as follows:

  • Subsumed rule: prevents the more general rule from firing by strengthening its condition in all possible ways to remove the redundancy with a more specialized rule
  • Unreachable rule: weakens the rule's conditions so that it can be reached
  • Cycling rule: breaks the cycle in all possible places by strengthening that rule
  • Attribute with wrong arity: removes extra arguments, or adds suitable arguments, in all possible ways

The blame assignment algorithm allocates a measure of likelihood of error to individual rules, on the evidence of past cases. The statistics highlight those rules that commonly fail during routine testing. For each rule, the following occurrences are counted:

  • True positive: cases where the rule fires correctly
  • False positive: cases where the rule fired when it should not have fired
  • True negative: cases where the rule did not fire and this was correct
  • False negative: cases where the rule did not fire when it should have fired

False positive and false negative are the errors. A false positive indicates that the KB is too general and it should be specialized. Conversely, a false negative indicates that the KB is too specific, and it should be generalized.

3.4.2. COVADIS

The COVADIS system is an inconsistency checking system based on constraint propagation techniques designed to operate on expert systems developed using the MORSE shell. The shell uses forward chaining with attribute-value rules. It generates, from a rule base, the specifications of all fact bases from which absurdity can be deduced. These are then presented to a domain expert to determine whether they are meaningful or not. If a fact base is not considered meaningful, the expert is interactively asked to express why it is not meaningful, in the form of some integrity constraint. Again, this method requires a direct appeal to the expert's implicit model of the domain.

3.4.3. IMPROVER

Another approach to supporting the refinement of the knowledge base in expert system validation is IMPROVER, a knowledge-base refinement tool, guided by error importance. A classification of error importance is needed, based on the error type and on the elements involved in the error. In the medical diagnosis domain, a false negative (a diagnosis that does not appear in the ES output although it should) is a more serious error than a false positive (a diagnosis that appears in the ES but should not), since the consequences of this sort of error for the patient will be more serious.

The refinement is performed on the following expert system model: the KB consists of facts, rules, modules, and metarules. Rules may be concluding rules or up-down rules. Concerning uncertainty management, a Certainty Factor (CF) is assigned to each fact representing positive evidence. Uncertainty is propagated through rule firing. Two types of control are included. Implicit control is embedded into the conflict resolution strategy based on three criteria: most specific rule, highest CF, and the first rule. Explicit control is coded in metarules acting on modules or on the whole ES. The metarules can add or remove modules to/from a list of active modules. The expert system functions as follows: when it starts, a metarule builds a list of active modules. Then, the first module is selected as the current module. Its goals are pursued using the rules contained in it. As soon as new facts are deduced, metarules are tested for firing, and the list of active modules is eventually updated. When every goal in the current module has been tried, a new current module is selected. The same cycle restarts. The expert system stops when there are no modules in the list of active modules.

The task of the expert system is medical diagnosis, in particular to obtain the subset of microorganisms that have caused an infection. IMPROVER is based on the following assumptions:

  • KB refinement is guided by importance of error, which is as follows:

    false negative > false positive > ordering mismatch.

  • Any type of knowledge can be subject to refinement. Both domain and control knowledge may be responsible for the first two types of error, while only domain knowledge is responsible for the ordering mismatch error.
  • The number of generated refinements is controlled by the following two choices: minimal changes are preferred and refinement cannot delete KB objects.

Based on these assumptions, the following refinement operators are legal:

  • Generalize/specialize conditions in the left-hand side of rules and metarules
  • Modify the CF of rules and metarules,
  • Modify the CF in conclusions of up-down rules
  • Modify the right hand side of metarules
  • Add conditions to the left-hand side of rules and metarules
  • Add new rules and metarules to the KB

IMPROVER goes through the following three stages in order: solving false negatives, solving false positives, and solving ordering mismatches. Each stage tries to solve the specific errors. IMPROVER has limited the generated refinements to one elementary change on a single KB object.


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.