TL;DR
This paper introduces a computational model for iterated theory base change, addressing practical limitations of the standard AGM paradigm. It proposes using "partial entrenchment rankings" to represent an agent's knowledge and its commitment to that knowledge, enabling a more robust and iterative modification of beliefs.
What Problem Does This Paper Address?
The AGM (Alchourron, Gardenfors, Makinson) paradigm provides a formal framework for rational information change (revision and contraction). However, it faces two practical challenges: representing finite information effectively and supporting the iteration of change operations. The standard AGM operators, while theoretically elegant, don't inherently propagate the underlying preference structure of the information, making it difficult to model sequences of belief updates. This paper aims to bridge this gap by providing a computational model that allows for iterated theory base change while maintaining a finite representation of knowledge and its associated preferences.
Methods
The core of the paper's contribution lies in the introduction and utilization of partial entrenchment rankings. These rankings are a formal way to represent an agent's knowledge base and its commitment to that knowledge. They map sentences to ordinals, where higher ordinals signify greater certainty. The paper defines a transmutation schema for these rankings, which allows them to be modified when new information arrives. Specifically, they focus on an adjustment mechanism, which is a policy for change based on an absolute measure of minimal change. This adjustment process computationally modifies the partial entrenchment ranking to incorporate new information with a specified degree of firmness. The paper also establishes theoretical connections between these theory base change operators and the standard AGM revision and contraction operators.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Partial Entrenchment Rankings as a Solution: The paper proposes partial entrenchment rankings as a canonical representation for theory bases. This finite representation captures not only the explicit beliefs but also the agent's commitment to them, addressing the representation problem.
- Iterated Change via Transmutations: The concept of "transmutation" for partial entrenchment rankings is key to enabling iterated theory base change. This allows the preference structure to be propagated through successive updates.
- Minimal Change for Practicality: The focus on "adjustment" as a transmutation policy, based on an absolute measure of minimal change, provides a practical and computationally feasible way to update belief states.
- Bridging Theory and Practice: The paper demonstrates that these theory base change operators, based on adjustments, are closely related to standard AGM operators, suggesting they exhibit desirable behaviors like retaining as much explicit information as possible.
- Computational Model: The development of a computational model for adjustments, which can be realized using any theorem prover, offers a concrete path towards implementing iterated belief revision systems.
Key Results
The paper provides theoretical results establishing the relationship between partial entrenchment rankings and epistemic entrenchment orderings. It defines transmutation schemas for theory base change and proves theorems showing how these transmutations relate to AGM revision and contraction operators. Specifically, Theorems 9 and 10 demonstrate that theory base adjustments maintain explicit beliefs and can be used to formulate theory change operators. The paper also presents a computational model for adjustments and illustrates its use with examples.
Limitations and Future Work
The authors acknowledge that a full complexity analysis of their proposed procedure is yet to be conducted. They also note that their definition of transmutation, while consistent with their interpretation, might not satisfy the recovery postulate in all cases, though modifications to address this are straightforward. Future work could involve exploring more elaborate computational optimizations and further investigating the complexity of the proposed algorithms.
Summary updated