A Parallel Self-Modifying Default Reasoning System

Jack Minker, Donald Perlis, Krishnan SubramanianAAAI 1986

Introduction

In the mid-1980s, automated reasoning systems typically operated under a "wait-until-finished" paradigm. A system would exhaustively search its knowledge base before providing any response. If the search was computationally expensive, the user was left without feedback, a stark contrast to human cognition. When humans are asked a question, we often provide a quick "tentative" answer—sometimes a default "I don't know"—while our subconscious continues to retrieve the information. If the memory surfaces shortly after, we correct ourselves.

This paper introduces a reasoning system designed to mimic this behavior. By monitoring its own internal deductive processes in real-time and employing a self-modifying learning rule, the system provides rapid default responses and learns to optimize its "thinking time" based on past experiences with specific types of queries.

System Architecture and Methods

The researchers implemented their approach using PRISM (Parallel Inference System), a logic programming environment designed for parallel execution. The core of the system is a meta-interpreter that serves as the interface between the user and the underlying deductive engine.

Detailed architecture of the parallel reasoning system and meta-interpreter.

The architecture distinguishes between two primary data structures:

  1. Extensional Database (EDB): Contains ground facts, analogous to short-term memory, which can be accessed quickly.
  2. Intensional Database (IDB): Contains complex rules requiring multi-step inference, analogous to long-term memory.

The meta-interpreter monitors the "depth" of the inference—the number of steps taken to resolve a goal. Instead of a fixed wall-clock timeout, the system uses this inference depth as a hardware-independent proxy for reasoning intensity. Each predicate in the knowledge base is assigned a "depth tag." If the engine does not find a "True" result within the depth specified by the tag, the system issues a default "False" response while continuing to search in the background.

The Self-Modifying Learning Rule

To ensure the system becomes more efficient over time, it employs a simple moving average formula to update its depth tags ($D$): $$D_{new} = \frac{(D_{old} \times N) + D_{latest}}{N + 1}$$ where $N$ is the number of times the query has been posed and $D_{latest}$ is the actual inference depth (AID) required to find the answer in the most recent session. This allows the system to asymptotically converge on an ideal "wait time" for specific predicates, balancing responsiveness with accuracy.

Experimental Results

The system was evaluated using a custom "Waterproof/Shelter" toy domain to test its ability to handle tentative failures and subsequent corrections. For example, determining if a "Pup" tent qualifies as a "waterproof shelter" might require a deep inference that initially exceeds the default depth tag.

Convergence of inference depth tags over repeated queries for different predicate types.

As shown in the experimental plots, the system demonstrates three key learning behaviors:

  • Asymptotic Convergence: In cases where the initial depth tag is low, the system gradually increases its "patience" as it encounters successful deep inferences, eventually stabilizing at the average required depth (Plots a and b).
  • Increased Cautiousness: By learning to wait longer for "deep" predicates, the system reduces the frequency of "Wait! I know it" corrections, providing more reliable initial answers.
  • Efficiency in EDB Queries: For queries that are purely factual (EDB), the system learns to lower its depth tag toward 1 (Plot c). It recognizes that if a fact isn't found almost immediately in the EDB, it likely does not exist, allowing for faster negative defaults.

Conclusion and Future Work

This 1986 work laid early groundwork for non-monotonic reasoning and real-time AI responsiveness. By treating inference depth as a learnable parameter, the system effectively "gets to know" its own knowledge base.

Future refinements suggested by the authors include improving background mode execution to handle multiple concurrent queries and developing more sophisticated methods for managing conflicting defaults. The ultimate goal is a system that can automatically switch between "default mode" and "normal mode" based on the urgency of the user's needs and the context of the query.

Summary updated

BibTeX
@inproceedings{minker1986parallel,
  author = {Jack Minker and Donald Perlis and Krishnan Subramanian},
  title = {{A Parallel Self-Modifying Default Reasoning System}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}
Figure