Creating Abstractions Using Relevance Reasoning

Alon Y. LevyAAAI 1994

Introduction

In Artificial Intelligence, reasoning within complex, real-world domains is often computationally prohibitive due to the high level of detail in knowledge bases (KBs). While a declarative representation of a domain—such as a database of global flight routes—is designed to be general-purpose, most specific queries only require a fraction of that information. The presence of irrelevant details acts as "noise," significantly slowing down the search for a solution.

This paper addresses the challenge of automatically simplifying KBs by stripping away details irrelevant to a specific query. The primary goal is to generate efficient, query-tailored models that are guaranteed to produce correct results without requiring expensive backtracking between levels of abstraction.

Formal Framework for Abstraction

The paper defines abstraction as a mapping between a base representation and a simplified one. The core idea is that a "good" abstraction is essentially the removal of irrelevant knowledge. The framework categorizes different types of abstractions based on their mapping functions and intended semantics.

Table 1: Common types of abstraction mappings and their intended semantics.

While the general theory supports various mappings (as shown in the table above), the paper focuses specifically on Argument Projection, where specific arguments (columns) of predicates are removed if they are deemed irrelevant to the query.

Relevance Reasoning and the Query-Tree

The proposed method relies on Relevance Reasoning to identify "irrelevance subjects." A subject is considered irrelevant if its removal does not alter the system's ability to answer a query correctly. To achieve this, the author introduces the Query-Tree, a symbolic tool used to trace potential derivations of a query.

Figure 1: A Query-Tree for a flight route domain, illustrating how rules (r1-r5) and predicates (Flight, Route) are linked to derive a query.

The Query-Tree helps identify which rules in the KB contribute to an answer. By analyzing the tree, the Argument Projection Algorithm can find the maximal set of predicate arguments that can be "projected out." For instance, in a flight query, the "cost" argument might be irrelevant if the user only cares about airline carrier and destination, allowing the system to ignore cost-related constraints during reasoning.

Key Theoretical Insights

The framework is built upon several critical logical foundations:

  • Independence: A rule is "independent" of an abstraction if the abstracted version does not introduce incorrect conclusions.
  • Guaranteed Correctness: By utilizing independent clauses, the framework ensures the abstracted KB is a TD-abstraction (Truth-Decreasing, meaning it won't introduce false positives) and a TI-abstraction (Truth-Increasing relative to the query, meaning it won't lose valid answers).
  • Efficiency: The Query-Tree can be constructed in time linear to the number of rules in the KB. This ensures that the overhead of generating the abstraction is minimal compared to the computational savings during the actual reasoning process.

Conclusion and Future Directions

The paper demonstrates that formal relevance reasoning can effectively automate the creation of query-specific abstractions. While the current algorithm focuses on argument projection, the underlying theory is extensible to more complex mappings like object grouping or function simplification.

Future work aims to address "approximate" irrelevance, where details are removed based on probabilistic unimportance rather than absolute logical irrelevance. This approach serves as a foundation for Compositional Modeling, where AI systems can dynamically assemble "just right" models for specific tasks from a library of detailed components.

Summary updated

BibTeX
@inproceedings{levy1994creating,
  author = {Alon Y. Levy},
  title = {{Creating Abstractions Using Relevance Reasoning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}

Loading related content...

Figure