Knowledge-Base Reduction: A New Approach to Checking knowledge Bases for Inconsistency and Redundancy

Allen GinsbergAAAI 1988

Abstract

As expert systems grew in complexity during the 1980s, ensuring the logical integrity of their rule bases became increasingly difficult. This paper introduces KB-Reduction, an algorithm that transforms a propositional rule-based system into a simplified form to reveal every possible logical conflict or redundant rule. By moving beyond limited pairwise checks to a global analysis of input-to-output mappings, KB-Reduction provides a robust framework for auditing and maintaining large-scale knowledge bases.

Introduction

In the era of large-scale expert systems, maintaining a consistent and non-redundant knowledge base (KB) was a significant challenge. Traditional tools for KB validation typically relied on comparing rules in pairs to find direct contradictions. However, Ginsberg (1988) identified a critical gap: logical contradictions often emerge from the complex interaction of three or more rules, which pairwise analysis fails to detect. Furthermore, as systems like AT&T's telecommunications analyzers were deployed across multiple sites, the need for a method that allowed local modifications without compromising global logic became paramount.

Methodology: The KB-Reduction Algorithm

The core innovation of this work is the KB-Reduction process. Instead of treating rules as isolated "if-then" statements, the algorithm views the entire KB as a function mapping raw inputs (findings) to final outputs (hypotheses).

Labeling and ATMS Influence

Drawing inspiration from de Kleer’s Assumption-based Truth Maintenance System (ATMS), the algorithm calculates a "label" $\mathcal{E}(c)$ for every conclusion $c$. This label is a minimal sum-of-products expression representing all combinations of inputs that lead to $c$. These labels are analogous to ATMS "environments"—the minimal sets of assumptions supporting a fact.

Acyclic Processing and Leveling

To manage complexity, the algorithm requires the KB to be acyclic. Rules are organized into "levels" based on their dependencies. Level 0 rules depend only on raw inputs, while higher-level rules depend on conclusions from lower levels. The system processes these levels sequentially, building up "Partial-Labels" that track the state of the KB after each rule is integrated.

Example of the KB-Reduction process showing rule labeling and detection of contradictions and redundancies.

As shown in the figure above, the reduction process explicitly flags potential issues:

  • Inconsistency: If the labels for a fact $B$ and its negation $\neg B$ overlap, the system identifies the specific input conditions leading to a contradiction (e.g., flags * and ** in the table).
  • Redundancy: If a rule's conditions are already covered by existing paths to the same conclusion, or if a rule is found to be unsatisfiable, it is flagged for removal (e.g., flag ***).

Semantic Constraints

The author notes that some logical contradictions are physically impossible (e.g., a patient being both "Male" and "Pregnant"). KB-Reduction allows developers to define "semantic constraints" to filter these cases, preventing the system from flagging "false-positive" inconsistencies.

Empirical Evaluation

The KB-Reducer tool was evaluated on real-world knowledge bases from AT&T projects, including the "GEMS" trunk-trouble analyzer.

  • Small KB: ~50 rules.
  • Medium KB: ~150 rules.
  • Large KB: ~370 rules.

In the 370-rule system, the algorithm generated approximately 35,000 distinct input environments. Despite the theoretical NP-hard nature of the problem, the analysis was completed in 10 CPU hours on a Texas Instruments Explorer II workstation, demonstrating the practical feasibility of the approach for real-world applications.

Key Insights

  1. Global Consistency: Consistency is a global property of the input-to-output mapping, not just a local property of rule pairs.
  2. Minimization as a Diagnostic Tool: Reducing logic to its minimal disjunctive normal form makes redundancies mathematically transparent.
  3. Handling Negation: By using a "closed-world assumption," the system can derive conditions for $\neg S$ by logically negating the label for $S$.

Conclusion and Future Work

KB-Reduction represents a significant step forward in automated KB auditing. While currently limited to acyclic propositional logic, it successfully identified errors in production-level systems that had escaped human review. Future work aims to extend this methodology to handle predicate logic (first-order logic) and to explore its use in supervised learning for automatic rule revision.

Summary updated

BibTeX
@inproceedings{ginsberg1988knowledge,
  author = {Allen Ginsberg},
  title = {{Knowledge-Base Reduction: A New Approach to Checking knowledge Bases for Inconsistency and Redundancy}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}
Figure