Verification of Multi-Level Rule-Based Expert Systems

Pedro MeseguerAAAI 1991

Abstract

This paper presents a formal framework for the verification of advanced Rule-Based Expert Systems (RBES) that utilize hierarchical control structures and uncertainty management. By extending the concept of labels from Assumption-based Truth Maintenance Systems (ATMS) into "extended labels" (e-labels), the author provides a methodology to detect logical anomalies such as inconsistencies, redundancies, and useless objects in complex, non-boolean environments. Experimental evaluation on real-world systems demonstrates that while the approach is computationally intensive for large-scale rule bases, it remains a practical solution for medium-sized hierarchical expert systems.

Introduction

In the early 1990s, verification tools for Rule-Based Expert Systems (RBES) were primarily designed for "flat" models using simple boolean logic. However, contemporary expert systems had evolved to incorporate Uncertainty Management Systems (UMS) and hierarchical control via metarules. These features introduced new complexities: facts were associated with certainty values (cvs), and metarules dictated the activation of modules or specific rules. Traditional verification methods failed to account for these dynamics, often missing "unreachable" rules caused by higher-level control logic. This paper addresses these limitations by proposing a verification framework that integrates uncertainty and multi-level control structures.

Methodology

The proposed framework builds upon the concepts of labels and environments from ATMS. The core innovation is the Extended Environment (e-environment), defined as a triplet for any given fact $f$:

  1. $SS_i(f)$: The minimal set of external facts required to deduce $f$.
  2. $RCV_i(f)$: The range of certainty values $f$ can assume.
  3. $RS_i(f)$: The specific sequence of rules used to derive $f$, tracking control flow and mutual exclusions.

The author defines algebraic operations—disjunction, conjunction, and modus ponens—to propagate these e-labels through a five-level hierarchy:

  • Level 4 & 3: Metarules acting on the system and specific modules.
  • Level 2: Modules containing goals and rules.
  • Level 1 & 0: Rules and basic facts.

By comparing e-labels, the system mathematically identifies four primary issues: inconsistency (conflicting facts), redundancy (duplicate knowledge), circularity (infinite loops), and useless objects (unfireable rules).

Results and Evaluation

The framework was implemented in Common Lisp and evaluated using three real-world rule bases developed with the MILORD shell. These systems varied in complexity, ranging from a simple configuration with 122 rules to a complex architecture with 344 rules and 59 metarules. Performance was measured on a SUN-4/260 workstation.

Performance metrics for three rule bases of varying complexity.

As shown in the table above, the verification of the smallest system (122 rules) was completed in 1 minute. However, the most complex system (344 rules, 59 metarules) required 1,225 minutes (approximately 20 hours) and significantly more memory (7,424 kb). Interestingly, the computation of e-labels accounted for only about 1% of the total CPU time; the majority of the processing was dedicated to testing the relationships between labels to identify errors.

Discussion

A key insight of this work is that control knowledge is as prone to error as domain knowledge and must be verified with equal rigor. The paper argues against the "flatness fallacy"—the idea that hierarchical systems can be verified by flattening them into a single list—as this loses critical context from metarules. Furthermore, uncertainty fundamentally changes the definition of redundancy; two rules reaching the same conclusion may not be redundant if they provide different certainty values that combine to reach a necessary threshold.

While the framework is effective, its exponential worst-case complexity poses challenges for massive, dense rule bases. Future work should explore incremental verification to reduce the computational burden by only re-checking components affected by specific changes.

Conclusion

This research provides a robust mathematical foundation for verifying modern, hierarchical expert systems. By accounting for uncertainty and multi-level control, the framework offers a more accurate assessment of system integrity than previous boolean-based methods.

Summary updated

BibTeX
@inproceedings{meseguer1991verification,
  author = {Pedro Meseguer},
  title = {{Verification of Multi-Level Rule-Based Expert Systems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1991},
}
Figure