Default-Reasoning with Models

Roni Khardon, Dan RothIJCAI 1995 · OpenReview

Abstract

Reasoning with model-based representations is an intuitive paradigm, which has been shown to be theoretically sound and to possess some computational advantages over reasoning with formula-based representations of knowledge. In this paper we present more evidence to the utility of such representations. In real life situations, one normally completes a lot of missing "context" information when answering queries. We model this situation by augmenting the available knowledge about the world with context-specific information; we show that reasoning with model-based representations can be done efficiently in the presence of varying context information. We then consider the task of default reasoning. We show that default reasoning is a generalization of reasoning within context, in which the reasoner has many "context" rules, which may be conflicting. We characterize the cases in which model-based reasoning supports efficient default reasoning and develop algorithms that handle efficiently fragments of Reiter's default logic. In particular, this includes cases in which performing the default reasoning task with the traditional, formula-based, representation is intractable. Further, we argue that these results support an incremental view of reasoning in a natural way.

Introduction

In classical artificial intelligence, knowledge is traditionally stored as a collection of logical formulas within a Knowledge Base (KB). To answer a query, a system performs deduction to determine if the answer logically follows from these formulas. However, this formula-based approach is often computationally expensive. The challenge intensifies when dealing with default reasoning—the non-monotonic logic humans use to make assumptions based on what is "usually true" (e.g., assuming a bird flies unless it is known to be a penguin).

Even when the underlying rules are relatively simple, such as Horn clauses, determining what follows by default is frequently NP-Hard. This paper addresses this "complexity gap" by advocating for a model-based representation, demonstrating that how we represent knowledge fundamentally dictates the efficiency of the reasoning process.

The Model-Based Paradigm

Instead of storing abstract rules like "All humans are mortal," a model-based system stores a set of characteristic models. These are specific, representative assignments of truth values that describe what a valid state of the world looks like. This approach is often described as "vivid" because it deals with concrete assignments rather than symbolic manipulation, mirroring cognitive theories of human "mental models."

Core Algorithms

The authors introduce three primary algorithms to leverage this representation:

  1. MBR (Model-Based Reasoning): The foundational algorithm that checks if a query holds true across the set of characteristic models.
  2. C-MBR (Contextual MBR): An extension designed for "reasoning within context." In real-world scenarios, we often have situational information (e.g., "I am at the airport"). C-MBR filters the model set to only those consistent with the current context before answering queries.
  3. D-MBR (Default MBR): The core contribution of the work. D-MBR manages multiple, potentially conflicting default rules by iterating through models to find a maximal set of consistent assumptions that support a conclusion.

Theoretical Insights and Complexity

The mathematical foundation of this work relies on the Monotone Theory of Boolean Functions. This theory identifies which specific models are "characteristic" enough to guarantee correct reasoning for certain classes of queries.

A striking insight of this research is that the complexity of reasoning is representation-dependent. The authors prove that for several classes of knowledge—including cases where the Knowledge Base has a polynomial-size Disjunctive Normal Form (DNF)—default reasoning can be solved in polynomial time. This effectively bypasses the NP-Hardness encountered when using traditional formula-based representations for the same logic.

Key Results

  • Efficiency Gains: The paper demonstrates that model-based reasoning supports efficient default reasoning even in fragments of Reiter’s default logic, a standard framework that is typically computationally intractable.
  • Handling Context: By treating context as a filter for the model set, the approach remains efficient while formula-based methods often become bogged down by the addition of situational constraints.
  • Incremental Intelligence: The authors argue that this framework supports an incremental view of learning. An agent can "paste together" different narrow views of the world (contexts) into a coherent model-based representation over time, rather than needing to re-calculate a massive set of logical formulas.

Limitations and Future Directions

While promising, the model-based approach has constraints:

  • Representation Size: Although often small, there are cases where the number of characteristic models could grow exponentially relative to a formula-based representation.
  • Basis Dependency: Some efficiency results require knowing a "basis" for the function class, which may not be available in all domains.
  • Expressivity: The current work is focused on propositional logic. Extending these efficiency gains to first-order logic, which involves complex objects and relations, remains a significant challenge for future research.

Conclusion

By shifting the focus from formula manipulation to model-based evaluation, Khardon and Roth provide a pathway to more efficient AI reasoning. Their work suggests that the difficulty of "thinking" may not be inherent to the logic itself, but rather a byproduct of how that logic is represented and stored.

Summary updated

Abstract

Reasoning with model-based representations is an intuitive paradigm, which has been shown to be theoretically sound and to possess some computational advantages over reasoning with formula-based representations of knowledge. In this paper we present more evidence to the utility of such representations. In real life situations, one normally completes a lot of missing "context" information when answering queries. We model this situation by augmenting the available knowledge about the world with context-specific information; we show that reasoning with model-based representations can be done efficiently in the presence of varying context information. We then consider the task of default reasoning. We show that default reasoning is a generalization of reasoning within context, in which the reasoner has many "context" rules, which may be conflicting. We characterize the cases in which model-based reasoning supports efficient default reasoning and develop algorithms that handle efficiently fragments of Reiter's default logic. In particular, this includes cases in which performing the default reasoning task with the traditional, formula-based, representation is intractable. Further, we argue that these results support an incremental view of reasoning in a natural way.
BibTeX
@inproceedings{khardon1995default,
  author = {Roni Khardon and Dan Roth},
  title = {{Default-Reasoning with Models}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1995},
  url = {https://openreview.net/forum?id=SkVdcrf_WB},
}
Figure