TL;DR
This paper introduces a novel algorithm that transforms prioritized default reasoning into a simpler, unprioritized (parallel) form. This breakthrough allows for the implementation of more complex and expressive non-monotonic reasoning systems, particularly those involving default inheritance and logic programming, which were previously difficult to handle.
What Problem Does This Paper Address?
Non-monotonic reasoning systems, which allow for beliefs to be revised in light of new information, often rely on "defaults" – assumptions that hold unless contradicted. However, real-world reasoning often involves multiple, conflicting defaults, requiring a way to prioritize them. Prioritized default reasoning handles this by assigning precedence to certain defaults over others. While powerful, existing formalisms like prioritized circumscription struggled with implementing arbitrary prioritization orders, especially non-layered ones crucial for applications like default inheritance. This paper addresses the challenge of efficiently and expressively representing and reasoning with these complex prioritization schemes.
Methods
The core contribution is a general-case transform algorithm that converts any set of prioritized propositional defaults into an equivalent set of parallel (unprioritized) defaults. This transform operates by creating new, more complex defaults that encode the original prioritization logic. The algorithm is described as a multi-functional, meaning it can produce multiple equivalent outputs, offering flexibility. The paper also discusses special-case transforms, particularly for default inheritance based on specificity, which are more computationally efficient.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Prioritization as Reducibility: The transform demonstrates that complex, multi-degree belief confidence (prioritization) can be reduced to just two degrees: "for-sure" and "unprioritized default." This offers a new perspective on the expressive power of prioritization.
- Bridging Formalisms: The work provides a mechanism to extend formalisms like Default Logic and Poole's Theorist with prioritization capabilities equivalent to those in circumscription, offering a unified approach to non-monotonic reasoning.
- Enabling Practical Applications: By making non-layered prioritization tractable, the paper unlocks the implementation of sophisticated default inheritance and logic programming systems, which are vital for many AI applications.
- Expressive Conciseness: The transform suggests that prioritization, while computationally complex to implement directly, offers significant expressive conciseness and naturalness for users specifying knowledge.
Key Results
The paper presents theorems that formally establish the equivalence between prioritized default pre-orders/circumscriptions and their transformed parallel counterparts. While the worst-case complexity of the transform can be exponential in the number of defaults, the paper highlights scenarios where it remains computationally feasible:
- When the number of defaults is small.
- In expressive special cases, such as non-top-heavy prioritization partial orders or columnar structures.
- Special-case transforms, like the one for specificity in inheritance, show significantly better (e.g., quadratic) complexity.
Limitations and Future Work
The authors acknowledge that the transform's worst-case exponential complexity can compound inferencing challenges. Future work includes:
- Experimenting with and evaluating the efficiency of the approach and algorithms.
- Developing more efficient special-case transforms, particularly for specificity in inheritance.
- Applying the results to other non-monotonic formalisms beyond circumscription.
- Addressing the outstanding challenges of achieving sufficient computational efficiency and demonstrating practical applications.
Summary updated