Toward Efficient Default Reasoning

AAAI 1996

TL;DR

This paper tackles the computational intractability of default reasoning, a crucial aspect of artificial intelligence for making quick, common-sense decisions. The authors propose an approach to approximate consistency checking by limiting the scope of reasoning to a "context," trading perfect accuracy for significant speedups, which they argue is a reasonable compromise for default reasoning.

What Problem Does This Paper Address?

Artificial intelligence systems often need to reason with incomplete information and make "best guesses" or defaults. For example, if you see a bird, you'd assume it can fly, even without explicit knowledge of its species. This is known as default reasoning, a form of nonmonotonic reasoning where conclusions can be retracted if new information contradicts them. While intuitively appealing for making quick decisions, formalizing default reasoning has proven computationally very difficult. Specifically, checking if a potential default conclusion is consistent with existing knowledge (i.e., not an exception) is a major bottleneck, often leading to NP-complete or even harder computational complexity. This intractability severely limits the practical application of these powerful reasoning systems.

Methods

The core of the paper's contribution lies in its novel approach to approximate consistency checking. Instead of checking for contradictions across the entire knowledge base (KB), the authors propose focusing on a limited "context." This context is a subset of the KB deemed most relevant to the default being considered.

The key ideas are:

  • Context-Limited Consistency Checking: The reasoning process is confined to a smaller, relevant portion of the KB. This is inspired by the intuition that we don't consider every possible reason for something to be exceptional; we focus on what's readily apparent.
  • Fast Sufficient Tests for Consistency: Within this limited context, the authors leverage fast, albeit potentially incomplete, tests for consistency. These tests can quickly identify if a default is definitely contradicted.
  • Trade-off of Accuracy for Speed: The approach acknowledges that this limited checking might miss some inconsistencies, leading to potentially incorrect conclusions that might need later retraction. However, the authors argue that for default reasoning, this trade-off is acceptable and often mirrors how humans reason.

Datasets

Not discussed in the paper. The authors generated random 3-SAT theories for their experiments.

Key Insights and Ideas

  • The "Top of Your Mind" Intuition: The paper formalizes the idea that we often make defaults based on what's immediately relevant or "at the top of our mind," rather than exhaustively considering all possibilities. This is a powerful justification for context-limited reasoning.
  • Context as a Filter: The context acts as a filter, focusing computational effort on the most likely sources of conflict, thereby improving efficiency.
  • Defaults as a Mitigation Strategy: The authors argue that "good defaults" are those where exceptions are either unlikely or easily detectable. This inherent property of useful defaults makes the proposed trade-off of accuracy for speed more palatable.
  • Asymptotic Correctness: Even with limited contexts, the system can achieve "asymptotic correctness" – if given more time, it can retrieve more information and improve its accuracy, mirroring human deliberation.

Key Results

The paper presents preliminary experimental results on randomly generated propositional theories.

  • Efficiency Gains: Context-limited consistency checking showed significant reductions in run time and search tree size compared to checking the entire KB, especially as problem size (number of variables) increased.
  • Accuracy: Accuracy was generally maintained or only slightly decreased, particularly in underconstrained regions of the problem space. The authors conjecture that accuracy is more dependent on the radius of the context and the density of information (C/V and L/V) than on the absolute problem size.
  • Transition Region Sensitivity: The effectiveness of context limitation decreased as theories approached the "transition region" (where problems become very hard), suggesting that in highly interconnected KBs, global interactions are crucial.
  • Effect of Facts (L): Accuracy tended to dip in the middle range of the number of facts (L) and then increase again, with the authors noting that very high L makes full consistency checking trivial anyway.

Limitations and Future Work

  • Accuracy vs. Speed Trade-off: The primary limitation is the potential for incorrect conclusions due to missed inconsistencies. The authors acknowledge this and argue it's a necessary compromise.
  • Context Selection: Determining the "ideal" context is still an open problem. The current approach uses a rudimentary notion of context based on proximity to a default.
  • Random Theories: Experiments were conducted on randomly generated theories, which may not fully represent the structure of real-world commonsense KBs.
  • Future Work: The authors suggest exploring more sophisticated context-selection mechanisms, investigating the role of sufficient tests for consistency in first-order logic, and applying these ideas to other nonmonotonic formalisms. They also propose further research into how context limitations can help with the other source of complexity in default reasoning: default ordering.

Summary updated

BibTeX
@inproceedings{1996toward,
  title = {{Toward Efficient Default Reasoning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure