Representing Multiple Theories

P. Pandurang NayakAAAI 1994

Introduction

A fundamental challenge in Artificial Intelligence is the lack of generality. Most contemporary AI systems are constructed around a single "domain theory"—a rigid set of rules and facts that rely on a vast array of implicit assumptions. For instance, a robot programmed for terrestrial navigation assumes constant gravity and atmospheric pressure; if relocated to a lunar environment, its internal logic collapses because its foundational assumptions are no longer valid.

To address this brittleness, researchers have proposed the use of contexts. Rather than maintaining one monolithic and fragile theory, an agent should possess a library of specialized theories (e.g., Newtonian vs. Quantum mechanics). This paper formalizes this approach, introducing a propositional logic of context that allows agents to switch between theories, lift facts across boundaries, and reason efficiently without the computational overhead typically associated with complex multi-modal systems.

The Formalism of Context

The paper develops a propositional modal logic of context characterized by several distinct features designed for practical AI application:

Contexts as Modal Operators

Unlike previous frameworks that treated contexts as complex terms—a move that often leads to computationally heavy logics—this system treats contexts as modal operators ($C_i$). If a proposition $\phi$ holds true within context $i$, it is represented as $C_i\phi$. This allows the system to treat "truth" as relative to a specific set of assumptions.

The $F_n$ Axiomatization

The author introduces the $F_n$ system, a specific set of axioms tailored for domain theories. A critical aspect of $F_n$ is its ability to "collapse" nested contexts. In many modal logics, reasoning about what is known about another context creates deep, complex hierarchies. In $F_n$, knowing a fact about another context is treated as a flat property. This prevents the "logical soup" of conflicting information from becoming unmanageable.

Vocabulary Mapping and Lifting

Different contexts often utilize different vocabularies. For example, the term "low temperature" carries different implications in a forest ecosystem context than it does in a planetary atmosphere context. The logic employs interpretation functions to define how facts are "lifted" or translated between contexts, even when the underlying language changes. This allows for the abstraction of general theories into specialized ones for specific times or locations.

Computational Complexity and Efficiency

One of the paper's primary contributions is the formal proof that partitioning a large knowledge base into smaller, contextualized units significantly improves reasoning speed.

NP-Completeness vs. PSPACE-Completeness

Most modal logics with multiple operators fall into the "PSPACE-complete" complexity class, making them extremely difficult to solve in practice. However, by assuming that facts within a context are "context-independent" (via Axioms A3 and A4), the author proves that the $F_n$ logic remains NP-complete. This places it in the same complexity class as standard propositional logic, a significant win for implementability.

The Efficiency of Partitioning

The paper demonstrates that the complexity of finding a solution in this system is dependent on the size of the largest individual context's vocabulary, rather than the total number of propositions across the entire knowledge base. This justifies the modular design of AI knowledge bases from a purely computational standpoint.

Key Results

The theoretical framework is supported by several key theorems:

  • Theorem 1: The satisfiability problem for the proposed $F_n$ logic is NP-complete, providing a formal justification for its use in practical AI systems.
  • Theorem 2: For "Strongly Horn" clauses—a restricted form of logic commonly used in databases—the system can decide satisfiability in polynomial time relative to both the number of contexts and the number of propositions.
  • Logical Equivalence: The paper proves that any formula involving nested contexts is logically equivalent to one without nesting, drastically simplifying the reasoning process.

Discussion and Future Work

While the $F_n$ logic provides the "logical bones" for contextual reasoning, several challenges remain. The logic explicitly allows for mutually incoherent theories; two contexts can contradict each other (e.g., one assuming ideal gas laws and another not) without crashing the system, provided each remains internally consistent.

However, the problem of "transcendence" remains: the logic does not yet explain how an AI can autonomously realize its current context is inadequate or how it should discover a new one. This currently requires human-defined meta-theories. Furthermore, while the paper focuses on propositional logic, extensions to First-Order Logic (FOL) are necessary for broader application. Future work within the SIGMA project aims to evaluate the heuristics required for an agent to choose the most appropriate or simplest context for a given task.

Summary updated

BibTeX
@inproceedings{nayak1994representing,
  author = {P. Pandurang Nayak},
  title = {{Representing Multiple Theories}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure