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.
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
- Global Consistency: Consistency is a global property of the input-to-output mapping, not just a local property of rule pairs.
- Minimization as a Diagnostic Tool: Reducing logic to its minimal disjunctive normal form makes redundancies mathematically transparent.
- 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