Rule-Based Inference in Large Knowledge Bases

William MarkAAAI 1980

Abstract

In this seminal 1980 paper, William Mark addresses the "scaling wall" encountered by early expert systems. As rule bases grew, they suffered from computational inefficiency and a loss of perspicuity. Mark proposes a shift from flat rule lists to a philosophy of inference as redescription. By integrating rules into a structured taxonomic knowledge base, inference becomes a process of classification, ensuring efficiency and modularity regardless of system size.

Introduction

By the late 1970s, rule-based AI systems like MYCIN demonstrated success in specialized domains. However, scaling these systems revealed two critical roadblocks. First, computational inefficiency: searching through thousands of rules for an applicable one becomes a massive search problem. Second, loss of perspicuity: in a flat rule base, predicting interactions between rules is nearly impossible, obscuring the system's overall logic. Mark argues these issues stem from treating rules as external "pattern/action pairs" rather than integral parts of the knowledge representation.

Methodology: Inference as Redescription

The proposed methodology treats inference as a process of redescription. The system iteratively transforms a problem specification (e.g., a natural language request) until it aligns with a known solution pattern (e.g., a database command). This occurs in two modes:

  1. Narrowing-down: A forward-moving process using rules to transform input into an "expert-friendly" format.
  2. Homing-in: If the system stalls, it identifies the "closest" known solution and uses specific consequent rules to resolve differences between the current state and the goal.
Rule-based mapping from user actions to system operations

Implementation Technologies

The methodology was evaluated through two prototype systems:

  • Askit: A natural language database query system for project scheduling. It organizes rules into "packets" based on case frames, drastically reducing the search space by only considering rules relevant to the current data structure.
  • Consul: An interactive system for online tools using KL-ONE (a precursor to Description Logics). In Consul, rules are nodes in a taxonomic hierarchy. Finding an applicable rule is a matter of "classifying" the current description into this hierarchy.

Key Insights and Ideas

A central insight is that structure equals efficiency. By anchoring rules to specific structures, the inference engine avoids exhaustive searches. Furthermore, inference as classification unifies knowledge representation and reasoning; determining rule applicability is identical to classifying a data object.

Inference as redescription between complex operation invocations

The "homing-in" mode enhances robustness. If a user's request doesn't perfectly match a system function, the system identifies the specific gap and attempts to bridge it through targeted redescription.

Results and Discussion

The paper provides a qualitative proof-of-concept for a scalable AI architecture. Key results include:

  • Rule Independence: Rule selection time becomes independent of the total rule count, provided the knowledge base is well-structured.
  • Improved Modularity: Tying rules to specific classes allows developers to clearly see a rule's scope, facilitating debugging and extension.

However, challenges remain. The knowledge acquisition bottleneck is significant, as building detailed KL-ONE hierarchies is complex. Additionally, while rule search is faster, the computational overhead of classification in complex networks introduces its own costs. Finally, the system's success depends on user requests being reasonably close to the system's domain of expertise.

Summary updated

BibTeX
@inproceedings{mark1980rule,
  author = {William Mark},
  title = {{Rule-Based Inference in Large Knowledge Bases}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1980},
}
Figure