Abstract
Traditional theories of abstraction in Artificial Intelligence often rely on syntactic mappings between formal languages, which can lead to "false proofs" and a lack of intuitive grounding. This paper proposes a semantic framework based on model-mapping. By introducing Model Increasing (MI) abstractions, the authors provide a formal methodology for constructing abstract theories that remain consistent with their original domains. This approach unifies several classic AI techniques and offers a compositional framework for complex system simplification.
Introduction
In Artificial Intelligence, abstraction is the process of simplifying complex problems to make them computationally tractable. Whether applied to robot planning or diagnostic systems, abstraction involves removing irrelevant details. Historically, the study of abstraction has been dominated by syntactic approaches, where formulas in a base language are mapped to formulas in an abstract language. However, this "search and replace" logic often fails to capture why certain abstractions are natural or useful.
Nayak and Levy argue that this perspective is backwards. They propose a semantic theory where abstraction is a two-step process: first, simplifying the "world" (the model), and second, finding the set of formulas (the theory) that best describes that simplified world.
The Semantic Framework: Model Increasing Abstractions
The core of this new theory is the concept of Model Increasing (MI) Abstractions. An abstract theory is considered Model Increasing if every model of the original base theory can be mapped to a model of the abstract theory. This ensures that the abstraction is "truth-preserving" in a specific sense: it never introduces falsehoods relative to the base theory, though it may become less specific or "quieter."
For cases where abstractions do allow "false proofs" (conclusions in the abstract theory that do not hold in the base theory), the authors model these as MI abstractions combined with "simplifying assumptions." For instance, a planner might assume a door is always unlocked to simplify a pathfinding task.
Methods: Constructing the Abstract Theory
To bridge the gap between model-level changes and formal logic, the authors present the Construct-abstraction algorithm. This procedure uses a resolution-based strategy to automatically generate the strongest possible abstract theory for a given model mapping.
The algorithm works by "resolving away" predicates that are intended to be dropped while ensuring that the logical implications between the remaining predicates are preserved. This ensures the resulting theory $T_{abs}$ is the most informative description of the abstracted model.
Key Insights
- Compositionality: Unlike syntactic mappings, MI abstractions are compositional. Abstractions developed for different components of a system can be safely combined without losing consistency.
- The Axiom Trap: The authors disprove the conjecture that a finite base theory always leads to a finite abstract theory. In some cases, the "perfect" abstract version may require an infinite number of rules to maintain full accuracy.
- Unification of AI Techniques: This semantic framework successfully re-interprets and unifies diverse techniques such as Tenenberg’s predicate abstractions and Sacerdoti’s ABSTRIPS planner.
Results
The paper demonstrates that if a base theory is axiomatizable (can be written as a set of rules), its strongest MI abstraction is also axiomatizable. Furthermore, for any intended model-level simplification, there exists a "strongest" abstract theory that exactly implements it. This provides a rigorous mathematical foundation for evaluating the utility and reliability of abstractions in AI.
Limitations and Future Work
While the theory provides a clear definition of the "strongest" abstraction, constructing it can be computationally intensive. The Construct-abstraction algorithm may not terminate if the strongest theory is not finitely axiomatizable. Future research is needed to identify restricted settings where these abstractions are guaranteed to be easily computable and to develop probabilistic methods for evaluating the validity of simplifying assumptions.
Summary updated