Using Specialists to Accelerate General Reasoning

Stephanie A. Miller, Lenhart K. SchubertAAAI 1988

Abstract

This paper presents ECoNet, a hybrid reasoning system designed to overcome the combinatorial explosion inherent in general-purpose theorem provers. By integrating specialized modules for domains such as time, arithmetic, and taxonomies, ECoNet leverages efficient data structures to accelerate logical inference while maintaining soundness.

Introduction

In the late 1980s, automated theorem provers faced a significant hurdle: "combinatorial explosions." Proving even basic assertions required exploring vast trees of logical possibilities. For instance, establishing that a "wolf" is a "living thing" might necessitate traversing a long chain of hierarchical axioms (wolf -> mammal -> animal -> living thing). While humans utilize mental shortcuts for specific domains like time or math, early AI systems treated all facts as generic logical clauses. The University of Alberta researchers addressed this by developing a method to integrate domain-specific "specialists" into a general-purpose engine.

Methods: The ECoNet Architecture

The core of the proposed system is ECoNet, a hybrid architecture centered on a resolution-based theorem prover. The system's efficiency stems from a uniform interface that allows the prover to offload specific tasks to specialist modules.

The ECoNet architecture showing the interaction between the central theorem prover and domain-specific specialists.

As shown in the architecture diagram, specialists for Time, Numbers, Sets/Lists, and Colors surround the central prover, with a Hierarchy Specialist integrated more closely. The prover interacts with these modules in three primary ways:

  1. Literal Evaluation: The prover can query a specialist to determine the truth of a literal. For example, a temporal specialist can consult a "timegraph" to instantly verify if one event preceded another.
  2. Function Evaluation: Specialists simplify complex terms. A math specialist might reduce (add 1 1986) to 1987 before the prover begins its formal resolution process.
  3. Generalized Resolution and Factoring: Specialists can resolve disparate predicates. A type specialist, recognizing that [d dog] and not [x animal] are contradictory, can resolve them into a null clause in a single step.

The communication protocol utilizes "sort tags" (e.g., _time, _number) to route queries efficiently. Furthermore, specialists can manage "interested party lists" to handle delayed evaluations, ensuring they are notified when relevant concepts are updated.

Key Insights

  • Soundness over Completeness: A specialist does not need to solve every problem in its domain. As long as it is "sound" (never incorrect), the general prover can fallback to standard, albeit slower, methods for edge cases.
  • Representational Power: The system recognizes that logic is not always the optimal representation. Using graphs for time or trees for hierarchies is significantly faster than processing lists of logical axioms.
  • Residues: When a specialist cannot fully resolve a problem, it returns a "residue"—a simplified logical condition for the general prover to process.

Evaluation and Results

The system was evaluated using a knowledge base derived from the story of Little Red Riding Hood, encompassing character types, event timing, and properties like color.

Key results included:

  • Significant Speedup: By utilizing specialized structures like "timegraphs" and preorder numbering for types, ECoNet bypassed lengthy transitive inference chains.
  • Mixed Reasoning Capabilities: The system successfully handled complex queries requiring cross-domain logic, such as determining if a "creature" killed the wolf while in the cottage by synthesizing temporal and taxonomic reasoning.
  • Implementation: ECoNet was fully realized in Lucid Common Lisp on a Sun 3/75 workstation, demonstrating the practical feasibility of the uniform interface.

Limitations and Future Work

Despite its successes, the 1988 implementation had limitations. It lacked a comprehensive "equality" specialist, relying on specialists for specific cases rather than a general-purpose reasoner like paramodulation. Additionally, the color specialist was relatively simple, treating colors as disjoint; the authors proposed a future 3D geometric color space specialist. Finally, the authors noted that the overhead of deciding which specialist to invoke must remain minimal to preserve the system's performance gains.

Summary updated

BibTeX
@inproceedings{miller1988using,
  author = {Stephanie A. Miller and Lenhart K. Schubert},
  title = {{Using Specialists to Accelerate General Reasoning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}
Figure