The Persistence of Derived Information

Karen L. Myers, David E. SmithAAAI 1988

Introduction

In the field of Knowledge Representation and Reasoning, the Frame Problem remains a foundational challenge: how can an artificial intelligence system efficiently represent what remains unchanged when an action occurs? Early solutions relied on "frame axioms," which generally posit that a fact persists unless it is explicitly contradicted by a new state. However, this approach encounters significant hurdles when dealing with derived information—facts that are concluded from other observations rather than being directly observed themselves.

This paper, originally presented at AAAI-88, identifies a critical flaw in how standard frame axioms handle these derivations. The authors argue that traditional logic fails to distinguish between a fact that depends on its proof to remain true and a fact that was merely discovered via that proof. To resolve this, they introduce the concept of inessentiality and a new formal framework for justification-based persistence.

The Paradoxes of Persistence

The authors highlight two primary failures in classical AI reasoning regarding change:

  1. The Green Cheese Problem (Over-persistence): If a system knows $A$ is true, it can logically derive $A \lor B$ (A or B). If an action subsequently makes $A$ false, a naive frame axiom might maintain $A \lor B$ because the disjunction itself isn't directly contradicted. This allows the system to conclude $B$ is true, regardless of what $B$ represents—even absurdities like "the moon is made of green cheese."
  2. The Displaced Cup Problem (Under-persistence): Consider a robot that knows "all objects on the table are liftable." Upon seeing a cup on the table, it derives that the cup is liftable. If the robot moves the cup to the floor, the original justification (being on the table) is removed. A conservative system might "forget" the cup is liftable, despite the fact that the cup's physical weight and structural integrity—the actual reasons for its liftability—have not changed.

Methodology: Inessentiality and Justification

To bridge the gap between logical derivation and physical reality, the authors propose a solution rooted in Default Logic and Justification Tracking. The core of their approach is the introduction of a new predicate: INESSENTIAL(p, q). This predicate specifies that while $q$ may be used to derive $p$, the persistence of $p$ does not depend on the continued truth of $q$.

A New Frame Axiom

The authors develop a formal default rule that evaluates not just the consistency of a fact in a new state, but the underlying reason why it was true. By tracking the "minimal set of fluents" (facts) that justify a conclusion, the system allows a conclusion to persist if all its essential components remain true, even if the inessential ones change.

Handling Overlapping Derivations

The framework is further refined to handle "overlapping derivations," where a single fact might have multiple justifications. For instance, a cup might be known to be liftable because it is on the table and because it is empty. The system is designed to be conservative: if one justification fails due to an inessential component, the system verifies if alternative justifications remain valid before allowing the fact to persist.

Taxonomy of Inessentiality

The paper categorizes inessentiality into three distinct classes, providing a roadmap for how AI systems should categorize knowledge:

  • Incidental: A coincidence of circumstance, such as the location of an object (e.g., the cup on the table).
  • Causal: A common cause where the proof is a symptom rather than a requirement. For example, a person holding a cup proves it is liftable, but the person putting the cup down does not make the cup heavy.
  • Definitional: Parts of a logical equivalence, often seen in hardware troubleshooting (e.g., in a half-adder circuit, a fault in one gate should not imply the failure of an unrelated but logically connected gate).

Results and Implications

The primary contribution of the paper is a formal, nonmonotonic frame axiom that successfully navigates both the "Green Cheese" and "Displaced Cup" paradoxes. By explicitly modeling which parts of a proof are "load-bearing" (essential) and which are "scaffolding" (inessential), the authors demonstrate that an AI can maintain a more stable and realistic model of a changing world.

While the paper uses theoretical "toy domains"—such as robot/cup scenarios and digital logic circuits—to prove its points, the implications are broad. It provides a necessary bridge between pure logical inference and the intuitive human understanding that moving an object does not alter its intrinsic properties.

Limitations and Future Work

The authors acknowledge several areas for further development:

  • The Qualification Problem: Unexpected events (e.g., moving a cup onto a floor covered in glue) can still override inessentiality axioms.
  • Conditional Inessentiality: The current model uses simple binary relations, but the authors suggest that $q$ might be inessential to $p$ only under specific circumstances.
  • Computational Complexity: While the overhead for tracking justifications is suggested to be manageable, the paper does not provide a formal complexity analysis for large-scale knowledge bases.

Summary updated

BibTeX
@inproceedings{myers1988persistence,
  author = {Karen L. Myers and David E. Smith},
  title = {{The Persistence of Derived Information}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}
Figure