Vivid Knowledge and Tractable Reasoning

David W. Etherington, Alexander Borgida, Ronald J. Brachman, Henry A. KautzIJCAI 1989

Introduction

In the late 1980s, Artificial Intelligence faced a significant "tractability gap." While first-order logic provided a powerful means to represent complex information, reasoning within such systems was computationally expensive—often NP-hard or worse. In contrast, human commonsense reasoning is nearly instantaneous. This paper addresses the challenge of building Knowledge Representation (KR) systems that achieve human-like speed by trading absolute logical precision for computational efficiency.

Methodology: The Vivification Process

The authors propose a process called Vivification, which transforms an expressive, complex Knowledge Base (KB) into a Vivid Knowledge Base (VKB). A VKB functions similarly to a relational database, storing ground, atomic facts and operating under a "closed-world assumption" (where any fact not explicitly present is assumed false).

The hybrid architecture where a standard Knowledge Base (KB) is transformed into a Vivid Knowledge Base (VKB) for efficient querying.

The system employs a hybrid architecture: the original KB is retained for "ideal competence," while the VKB handles the majority of queries to ensure high performance. Key techniques in this transformation include:

  • Subsumption Hierarchies: Instead of processing slow disjunctions (e.g., "Joe is either a Teacher or a Professor"), the system identifies a more general, "vague" category (e.g., "Joe is an Instructor") and stores it as a single atomic fact.
  • Functional Defaults: The system uses default values (e.g., assuming a car has a spare tire) to avoid the overhead of generating complex conditional plans for every possible edge case.

Key Insights: Vagueness and Mental Models

A core insight of the paper is the distinction between ambiguity and vagueness. Processing ambiguity (e.g., "A or B") requires case analysis, which is computationally slow. In contrast, processing vagueness (e.g., a general category C that includes both A and B) involves a simple identity check, which is significantly faster.

Illustrating how disjunctions are mapped to more general categories in a subsumption hierarchy to replace ambiguity with vagueness.

The authors suggest that this approach mirrors human "mental models," as proposed by psychologists like Johnson-Laird. Rather than manipulating sentential logic, humans maintain a "vivid" internal representation of the world that can be queried like a database. This allows for "graceful degradation": as the subsumption hierarchy becomes richer, the VKB becomes more accurate, but it remains fast regardless of the hierarchy's density.

Results and Performance

The transition to a VKB yields several critical computational advantages:

  • Sublinear Querying: Query answering becomes sublinear relative to the total size of the knowledge base, representing a massive improvement over the exponential time required for standard theorem proving.
  • Polynomial Vivification: While converting inputs to certain logical forms can be NP-complete, the authors demonstrate that the vivification process can be approximated in polynomial time without significant loss of information.
  • Soundness: For "definite" databases consisting of simple facts and rules, the VKB produces results identical to the original KB under the closed-world assumption.

Limitations and Future Directions

Despite its advantages, the vivid approach has limitations. The reliance on the Closed-World Assumption makes handling explicit negation difficult. Furthermore, the system's utility depends on the availability of a "natural" subsumption hierarchy, a concept that remains difficult to define formally. Future work is also needed to better handle existential quantifiers and mutually exclusive classes (e.g., ensuring an entity cannot be both a "Doctor" and a "Patient" simultaneously).

Summary updated

BibTeX
@inproceedings{etherington1989vivid,
  author = {David W. Etherington and Alexander Borgida and Ronald J. Brachman and Henry A. Kautz},
  title = {{Vivid Knowledge and Tractable Reasoning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1989},
}
Figure