Revision by Comparison for Ranking Functions

Meliha Sezgin, Gabriele Kern-IsbernerIJCAI 2022 · DOI

TL;DR

This paper introduces a more elegant and explicit implementation of "Revision by Comparison" (RbC), a belief revision mechanism that allows for nuanced incorporation of new information by considering its source's credibility. By transferring RbC to the framework of ranking functions, the authors provide a more accessible and versatile tool for agents to update their beliefs, especially when dealing with potentially counterintuitive new information.

What Problem Does This Paper Address?

In artificial intelligence, agents often need to update their beliefs when presented with new information. Traditional belief revision mechanisms typically assume that new information, if accepted, completely replaces older, conflicting beliefs. However, in real-world scenarios, agents might want to incorporate new information only partially, especially if it seems implausible but comes from a trusted source. "Revision by Comparison" (RbC) was proposed to address this by allowing the degree of belief revision to be influenced by a "reference sentence" that signifies the source's credibility.

The challenge with the original RbC formulation was its lack of clarity in implementation. This paper aims to make the underlying strategy of RbC more explicit and to provide a more elegant and directly usable implementation, particularly within the framework of ranking functions, which offer a semi-quantitative way to represent an agent's beliefs.

Methods

The authors build upon the original concept of RbC, which was defined using epistemic entrenchment relations (a qualitative way to order beliefs by their importance). They achieve their goals through several key steps:

  • Transfer to Ranking Functions: They translate the RbC mechanism from qualitative epistemic entrenchment relations to ordinal conditional functions (OCFs), also known as ranking functions. Ranking functions assign an "implausibility" score to each possible world, providing a more granular representation of beliefs. This allows for a more elegant and quantitative implementation of RbC.
  • Formalizing the Mechanism: They provide a precise definition of RbC for ranking functions (Definition 3) and demonstrate that it aligns with the semantic constraints derived from the original possible-worlds formulation of RbC.
  • Conditional Revision: They show that RbC can be realized as a "c-revision" using weak conditionals. Weak conditionals represent uncertain or negative information (e.g., "if A, then B might be the case, but B is not plausible"). This approach highlights the hybrid nature of RbC, where it can act as a revision or a contraction depending on the prior belief state and the relationship between the input and reference sentences.

Datasets

Not discussed in the paper. The paper focuses on theoretical formalisms and does not involve empirical evaluation on specific datasets.

Key Insights and Ideas

  • RbC as a Hybrid Belief Change Operator: The paper strongly emphasizes that RbC is not a simple revision or contraction. It's a hybrid mechanism where the outcome depends on the relative plausibility of the input and reference sentences. This makes it particularly useful for scenarios where an agent needs to balance the plausibility of new information with the trustworthiness of its source.
  • Ranking Functions Offer Elegance: The shift to ranking functions provides a more mathematically tractable and intuitive way to implement RbC. It makes the impact of the reference sentence on the belief update much clearer.
  • Weak Conditionals Capture Nuance: Using weak conditionals to define RbC as a conditional revision elegantly captures the mechanism's ability to handle uncertain or partially accepted information. This is a powerful way to represent the "degree" of belief change.
  • Connection to Credibility-Limited Revision: The paper draws a clear link between RbC and credibility-limited revision operators. RbC offers a more flexible way to define the "credible worlds" that trigger a revision, by using a reference sentence rather than a fixed set of propositions.

Key Results

The paper presents several key theoretical results:

  • Equivalent Implementations: They demonstrate that their new definition of RbC for ranking functions (Definition 3) is semantically equivalent to the original possible-worlds formulation and also satisfies the desired properties of RbC (Success, Lifting, a-level, Min).
  • Conditional Revision Equivalence: They show that RbC, when implemented as a c-revision using weak conditionals, yields the same results as the direct ranking function implementation.
  • Characterization of Cases: The paper clearly delineates three cases for RbC:
  • β-revision: When the input sentence (β) is more plausible than its negation (β) and the reference sentence (α) is more plausible than its negation (α). This is the standard revision case.
  • Vacuous Case: When the operation doesn't change the belief state, often when the input is already consistent with the prior beliefs.
  • α-contraction: When the reference sentence (α) is more plausible than the input sentence (β), leading to a contraction of α.

Limitations and Future Work

  • Darwiche and Pearl Postulates: The authors note that RbC does not satisfy the Darwiche and Pearl postulates for belief revision. This is because RbC can make belief relations coarser by reducing plausibility distinctions among certain worlds.
  • Future Work: The paper suggests exploring extensions of credibility-limited operators and their connection to RbC more thoroughly. This indicates a promising avenue for developing more sophisticated belief change mechanisms.

Summary updated

BibTeX
@inproceedings{sezgin2022revision,
  author = {Meliha Sezgin and Gabriele Kern-Isberner},
  title = {{Revision by Comparison for Ranking Functions}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/379},
}
Figure