Elaboration Tolerance of Logical Theories

AAAI 1999

TL;DR

This paper introduces the concept of "elaboration tolerance" for logical theories, addressing the challenge of modifying knowledge bases (KBs) without breaking existing reasoning. They propose a theoretical measure of syntactic distance between formal systems and a practical object-oriented logic (OOFOL) to build more adaptable KBs.

What Problem Does This Paper Address?

Building robust knowledge bases (KBs), especially for commonsense reasoning, is a significant challenge. As KBs grow and new information is integrated, existing reasoning mechanisms can break or require extensive rewriting. This lack of "elaboration tolerance" makes KBs brittle and difficult to maintain. The authors highlight that unlike many other development tasks, there's a lack of models for developing logical theories, particularly commonsense ones, that can gracefully accommodate new knowledge. They aim to bridge this gap by providing both theoretical foundations and practical tools for creating more adaptable logical systems.

Methods

The paper proposes a two-pronged approach:

  • Theoretical Front: They define a measure of "syntactic distance" between formal systems. This measure quantifies the minimum number of axiom additions and removals needed to transform one knowledge base into a logically equivalent one. This helps in understanding the impact of different KB reformulations on their maintainability.
  • Pragmatic Front: They introduce two variants of an Object-Oriented First Order Logic (OOFOL): monotonic and nonmonotonic. In OOFOL, an "object" is essentially a theory with an internal language and an interface language. These objects can be linked to form complex theories, with inheritance mechanisms facilitating knowledge engineering. This approach aims for local reasoning within objects and incremental compilation. An application of this is the Logic-based Subsumption Architecture (LSA), which uses logical theories for each layer to enable reasoning.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Elaboration Tolerance is Crucial: The core idea is that logical theories, like software, need to be designed with future modifications in mind. Simply adding new axioms can lead to inconsistencies or break existing reasoning.
  • Syntactic Distance as a Metric: Quantifying the effort to transform one KB to another provides a concrete way to evaluate different design choices and their impact on maintainability.
  • Trade-offs in Reformulation: Some KB reformulations might reduce syntactic distance but at the cost of larger theories or languages. Conversely, changing the entailment relation might have less impact on this distance.
  • Object-Oriented Logic for Modularity: OOFOL offers a way to modularize knowledge, allowing for local reasoning and incremental updates, which is key to achieving elaboration tolerance.
  • LSA as a Practical Implementation: The Logic-based Subsumption Architecture demonstrates how OOFOL principles can be applied to build layered reasoning systems, inspired by Brooks' Subsumption Architecture but with a logical foundation.

Key Results

The paper presents theoretical insights and a framework rather than empirical results with quantitative metrics.

  • Theoretical Findings: They found that some KB reformulations can shorten syntactic distance but may incur costs in theory size or language complexity. Changing the entailment relation appears to have a less drastic impact on syntactic distance.
  • OOFOL Design: They defined monotonic and nonmonotonic variants of OOFOL, including concepts like objects, internal/interface languages, and inheritance, to support knowledge engineering.
  • LSA Architecture: They describe the LSA as an application of nonmonotonic OOFOL, building layered reasoning systems where subsumption is achieved through logical sentence passing between layers.

Limitations and Future Work

  • Theoretical Model Expansion: The authors are currently working on expanding their theoretical model to an "Oracle-based search," which would involve an oracle answering questions about goal nodes and necessary sentences for KB expansion.
  • OOFOL Applications: Future work includes implementing OOFOL for Frame Systems and expanding the LSA's application to synthetic agents.
  • Evaluation: They plan to evaluate the success of these object-oriented structures using their theoretical model.
  • Practical Application of Syntactic Distance: While the syntactic distance measure is defined, its direct application in guiding KB design in practice is still an area for exploration.

Summary updated

BibTeX
@inproceedings{1999elaboration,
  title = {{Elaboration Tolerance of Logical Theories}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
}
Figure