# revision_by_comparison_for_ranking_functions__29a5757f.pdf

Revision by Comparison for Ranking Functions

Meliha Sezgin and Gabriele Kern-Isberner TU Dortmund University, Germany {meliha.sezgin, gabriele.kern-isberner}@tu-dortmund.de

Revision by Comparison (Rb C) is a non-prioritized belief revision mechanism on epistemic states that specifies constraints on the plausibility of an input sentence via a designated reference sentence, allowing for kind of relative belief revision. In this paper, we make the strategy underlying Rb C more explicit and transfer the mechanism together with its intuitive strengths to a semi-quantitative framework based on ordinal conditional functions where a more elegant implementation of Rb C is possible. We furthermore show that Rb C can be realized as an iterated revision by so-called weak conditionals. Finally, we point out relations of Rb C to credibilitylimited belief revision, illustrating the versatility of Rb C for advanced belief revision operations.

1 Introduction

The aim of belief change operators [Alchourr on et al., 1985; Katsuno and Mendelzon, 1992] is to incorporate new pieces of information into an agent s belief set, which means they are intrinsically linked to the principle of primacy of update. Non-prioritized belief revision operators break with this goal and allow that new information can be rejected for several reasons (see [Hansson, 2008] for a survey). Revision by Comparison (Rb C) was firstly introduced by Ferm e and Rott in [2004] and represents a belief change mechanism that allows to accept a new input sentence β only to a certain degree, via specifying the strength of the new belief in the posterior belief state via a so-called reference sentence α. This flexible approach to belief revision results in a hybrid belief change operator between revision with an input information and the contraction of a reference sentence. Rb C adapts the kind of belief change to the prior belief state of an agent and thus links the reliability resp. priority of the new information to a reference sentence which is either specified via the input or can be selected freely by an agent. Except for a weaker form of belief change operators recently proposed in [Schwind et al., 2018], this dynamic form of belief change is unique to the methodology of Rb C and it leads to many interesting connections to other

Contact Author

forms of non-prioritized belief change. Among them are credibility-limited revision operators [Hansson et al., 2001; Booth et al., 2012], which perform a revision of the prior belief state solely if the new piece of information is credible enough, whereby credibility is defined via a fixed set of propositions whose determination remains unclear. Here, Rb C offers the chance to a more flexible approach to credibility using a reference sentence for each new piece of information. We give a motivating example:

Example 1. On a sunny afternoon, an agent watches a video on BBC news that states that scientists discovered a rare penguin type that has the ability to fly! The agent is astonished! Even though she knows that penguins are birds and birds normally fly, she is also aware of the fact that penguins are an exception to this rule and do not fly. So the new information is highly unplausible, but on the other hand the BBC is a trustworthy source of information which acts as reference.

For Rb C the reference sentence, e.g. the trustworthiness of the BBC news, can act as a a marker of reliability and allows us to revise with a seemingly unplausible new information only to a certain degree or even the devaluation of the reference. Despite the intuitive strengths of Rb C the implementation remains unclear in [Ferm e and Rott, 2004]. We show that this is not due to the intricateness of the revision mechanism per se but rather because the determination of the affected worlds is highly dependent on the relative positioning of input and reference beliefs. By changing the framework of belief representation and adapting the underlying change mechanism, we make the methodology and the ensuing application of Rb C more explicit and concise and therefore directly usable for revisions tools. Our main contributions are the following:

We clarify the strategy underlying Rb C and present a more elegant implementation for total preorders in a semi-quantitative framework of belief representation.

Using negative information in the form of so-called weak conditionals, we characterize Rb C as a conditional revision.

We discuss the hybrid belief change character of Rb C and compare our results in the context of credibilitylimited revision operators.

We start in Section 2 by stating some formal preliminaries,

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

whereby we discuss the relation between two qualitative approaches to belief representation in more detail. After recapping the belief revision mechanism of Rb C in Section 3.1, we clarify its methodology by expressing it via possible worlds. This provides the grounds for presenting a more elegant implementation of Rb C via ranking functions [Spohn, 1988] in Section 3.3. And in Section 3.4, we characterize Rb C as a revision with a set of so-called weak conditionals using the highly adaptive framework of c-revisions [Kern-Isberner, 2001] and show that these implementations inherit all relevant features of Rb C. Before we conclude in Section 5, we compare Rb C operators to credibility-limited revision operators in Section 4. The proofs in this paper are straightforward, but technical, and therefore omitted due to lack of space.

2 Formal Preliminaries

In this section, we define some basics from propositional resp. conditional logic and fix our notation. Then we deal with two qualitative belief representation frameworks in more detail.

2.1 Propositional and Conditional Logic We denote by L the set of formulas of a propositional language built over a finite signature Σ using logical connectives and , or and not . For conciseness of notation, we will omit the logical and-connector, writing αβ instead of α β, and overlining formulas will indicate negation, i.e., α means α. The material implication α β From α it (always) follows that β is, as usual, equivalent to α β. We denote by logical truths or tautologies and by logical falsehoods or contradictions. The set of all propositional interpretations over Σ is denoted by ΩΣ. As the signature will be fixed throughout the paper, we will usually omit the subscript and simply write Ω. As usual, we write ω |= α when a world satisfies α, i.e. when ω is a model of α. By slight abuse of notation, we will use ω both for the model and the corresponding conjunction of all positive or negated atoms. The set of all models of a formula α is denoted by Mod(α). The set of classical consequences of a set of formulas A L is Cn(A) = {α L | A |= α}. The deductively closed set of formulas which has exactly a subset W Ωas models is called the formal theory of W and defined as Th(W) = {α L | ω |= α for all ω W}. Let (L|L) = {(β|α) | α, β L} be a flat conditional language where α is called the antecedent of (β|α), and β is its consequent. (β|α) expresses If α, then (plausibly) β . We extend the standard conditional language to a weak conditional language (|L|L|). Weak conditionals represent negated conditional information, as used in Rational monotony [Lehmann and Magidor, 1992]. For a weak conditional (|β|α|), we call α the antecedent and β the consequent and (|β|α|) expresses If α, then β might be the case but β is not plausible . Weak conditionals express an agent s insecure attitude towards the consequent β if α is true, the negation of β is not plausible, but on the other hand β (only) might be true. It holds that (|β|α|) implements the negation of the corresponding standard conditional (β|α), the former is accepted iff the latter is not [Lewis, 1973]. The evaluation of a weak conditional corresponds to the evaluation of the standard con-

ditional [De Finetti, 1975], with verification αβ, falsification αβ and neutrality α.

2.2 Belief Representation In most of the formal developments for methods of nonprioritized belief revision epistemic entrenchment relations, noted as E, are used. Epistemic entrenchment relations mirror the attitude of an agent towards her current beliefs, i.e. represent an inner ordering of the belief set. Some sentences in the belief set have a higher degree of epistemic entrenchment than others, i.e., are more easily abandoned when a contraction is carried out. These degrees of entrenchments are measured only qualitatively, i.e., for two sentences α, β L, the notation α E β stands for β is at least as epistemically entrenched as α and α <E β is defined as α E β but not β E α. Following [Nayak, 1994], we define an epistemic entrenchment relation as follows:

Definition 1 ([Nayak, 1994]). A total preorder over L is called a relation of epistemic entrenchment, if it satisfies the following conditions: (E1) If α E β and β E γ, then α E γ (E2) If α |= β, then α E β (E3) α E α β or β E α β (E4) If α E β for all α L, then β

The original definition of entrenchment relations, such as in [G ardenfors and Makinson, 1988], is given relative to a belief set. However, belief sets can be extracted from each epistemic entrenchment as they contain enough information by themselves (as noted in [Nayak, 1994]) via Bel( E) = {α L | <E α} if <E α for some α, otherwise Bel( E) = L. Note that each epistemic entrenchment relation E is uniquely defined via the entrenchment classification of maximal disjunctions over the signature Σ that constitutes L. In contrast to epistemic entrenchment relations, total preorders (TPOs) on possible worlds rank worlds according to their closeness to a belief set, i.e. they take on the perspective of belief revision and define an implausibility ordering on possible worlds ω Ω, s.t. for two worlds ω, ω Ω, ω ω means that ω is at least as plausible as ω , and ω ω holds if ω ω but not ω ω. The belief set of is defined via minimal worlds, s.t. Bel( ) = Th({ω | ω ω for all ω Ω}) and |= α if α Bel( ). We call such TPOs over possible worlds plausibilistic TPOs. Each plausibilistic TPO on possible worlds induces a plausibilistic relation on formulas via: α β iff min(Mod(α), ) min(Mod(β), ). To ease the notation, we define the following subsets of Ωfor each plausibilistic TPO and two arbitrary sentences γ, δ:

Mod γ (δ) = {ω Ω| ω |= δ and ω γ}.

Plausibilistic TPOs and epistemic entrenchment relations are dual approaches to belief representation and both formalisms are fundamental to AGM belief revision, see [Katsuno and Mendelzon, 1992] for TPOs and [G ardenfors and Makinson, 1988] for entrenchment relations. More precisely, the following proposition summarizes the relationship between entrenchment relations and plausibility orderings which was al-

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

ready discussed in [Peppas and Williams, 1995; Grove, 1988] and will prove to be useful in the context of this paper:

Proposition 1. For each epistemic entrenchment E,

α β iff α E β (1)

defines a plausibilistic TPO s.t. Bel( E) = Bel( ) and vice versa.

Applying (1) on the entrenchment classification of maximal disjunctions in E leads us to possible worlds ranked by plausibility according to E. Plausibilistic TPOs are substantiated using ordinal conditional functions (OCFs, also called ranking functions) κ : Ω N { } [Spohn, 1988], with κ 1(0) = , assigning to each world ω an implausibility rank κ(ω) > 0 and κ( ) = , i.e. the higher κ(ω) the less plausible ω is. The normalization constraint calls for worlds having maximal plausibility and the belief set Bel(κ) = Th(κ 1{0}) is defined via worlds with minimal ranks. It is easy to see that each ranking function defines a TPO κ via

ω κ ω iff κ(ω) κ(ω ) for all ω, ω Ω. (2)

It holds that κ(α) := min{κ(ω) | ω |= α} and it holds that κ |= α if κ(α) > 0. A standard conditional (β|α) is accepted, κ |= (β|α), if κ(αβ) < κ(αβ). For weak conditionals (|β|α|) this condition is weakened s.t. κ |= (|β|α|), if κ(αβ) κ(αβ).

3 Revision by Comparison

In this section, we clarify the methodology of Revision by Comparison, i.e., a belief revision mechanism that specifies the strengths of new beliefs according to the credibility of a reference sentence its coming from, and discuss its special hybrid belief change character. Furthermore, we transfer Rb C to the framework of ranking functions where its intuitive strengths become more apparent and implement it as a conditional revision.

3.1 Basics of Revision by Comparison Revision by Comparison αβ revises a prior belief state over a reference sentence α and an input sentence β. The main idea can be expressed as follows: Accept β in the posterior belief state with a degree of entrenchment that at least equals that of α. We allow for arbitrary input sentences β L but exclude reference sentences α to avoid cases where we have to accept input sentences β as far as logical truths and thus would have a conflict with (E4). In [Ferm e and Rott, 2004], Rb C is defined via a function αβ that can be applied to a belief set Bel( E) extracted from an entrenchment relation E, yielding a new belief set Bel( E) α β. Using belief states makes Rb C suitable for iterated belief revision, thus in the following, we will neglect the belief sets and recall Rb C as an operation on belief states represented by epistemic entrenchment relations.

Definition 2 (Revision by Comparison, α,β E ). Let E be an epistemic entrenchment relation and α,β E be the posterior

min(Mod(α), )

Mod(β) Mod(β)

Figure 1: Schematic Revision by Comparison for plausibilistic preorders. The hatched area displays Mod

entrenchment relation after Rb C with α as reference and β as input sentence. Then α,β E is defined by

γ α,β E δ iff α (β γ) E (β δ), if γ E α γ E δ, otherwise (3)

for any arbitrary sentences γ, δ. Exceeding the basic success condition formulated above, Ferm e and Rott formulated desirable properties for Rb C in [Ferm e and Rott, 2004] as follows: Let α,β E be the posterior entrenchment relation after an Rb C αβ. Then the following properties hold for α,β E :

(Success) β is at least as entrenched as α: α α,β E β

(Lifting) It does no extra lifting: α < α,β E β iff α <E β

(α-level) It does no extra lifting: α < α,β E β iff α <E β (Min) The entrenchment relation between two sentences that are at least as entrenched as α in the prior belief state will not be affected by the operation: Let γ, δ L, if α E γ and α E δ then: γ α,β E δ iff γ E δ

3.2 Revision by Comparison for Plausibilistic TPOs We transfer the methodology underlying Rb C in the framework of entrenchment relations to qualitative constraints for plausibilistic TPOs and α,β corresponding to the entrenchment relations E and α,β E :

ω α,β ω iff α (βω) βω , if ω α ω ω , otherwise (4)

These constraints follow immediately from (3) via (1) for γ, δ as maximal disjunctions; their negations are then maximal conjunctions and correspond to possible worlds, yielding (4) for possible worlds ω resp. ω . It is not easy to understand the strategy of Rb C and therefore also its special features are not clear. In order to discuss these in more detail, we clarify the strategy of Rb C expressed in (3). In Figure 1 a schematic Rb C for plausibilistic TPOs is depicted: The relations among worlds in Mod(β) and among worlds in Mod(β) that are less plausible than α are kept when performing Rb C. Because, for worlds ω1 Mod(β) that are less or equally plausible than α, it holds that α (βω1) α ω1 ω1, i.e. the first case in (4) is equivalent to ω1 ω2 for ω2 Mod(β). The second case implies that the relations are preserved for the remaining

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

worlds in Mod(β) and β-worlds that are less plausible than α. But all worlds ω Mod

α (β), marked in the hatched area in Figure 1 are shifted up to the level of plausibility where α resides, thus α α,β β. This follows from the first case in (4), since α (βω) βω is always true if ω is some minimal α-world and conversely, α (βω ) βω holds. This shifting of worlds in Mod

α (β) results in the fact that worlds in Mod

α (β) become the most plausible ones in the posterior TPO. This is illustrated in Figure 1 and in Example 2. We provide semantic constraints that depict the mechanism of Rb C in a more comprehensible way than (4):

Theorem 1. Let be a plausibilistic TPO and αβ = α,β be the posterior TPO according to (4). Then it holds that

ω α,β ω iff

ω ω and α ω ω ω and ω Mod

α (β), ω |= β α ω and ω Mod

α (β), ω |= β ω α, ω |= β

Theorem 1 follows from (4) via equivalent reformulations and strict case distinctions between worlds in Mod

α (β) and Mod

α (β). For the contradictory case α , it holds that α is a logical truth and we fix by convention that α is represented by an arbitrary minimal world in the prior ordering. Then the constraints in (4) and (5) lead to no changes in the prior ordering because the first case in (5) holds for all ω Ω and it holds that Mod

α (β) = . The characterization in (5) makes clear that the change of the prior belief state depends on the relation between the reference and the input sentence, something which was already observed in [Ferm e and Rott, 2004] and thus Rb C displays a hybrid belief change operation. We can further specify this statement: the possible worlds in Mod

α (β) and Mod

α (β) are crucial for the posterior ordering and the kind of change performed by Rb C is solely dependent on whether these sets are empty or not. It follows from (4) and Theorem 1 that the hybrid character of Rb C transfers immediately to our characterization (5). There are three cases of prior orderings which correspond to the cases defined in [Ferm e and Rott, 2004] and have different effects on the posterior state α,β:

β-revision: If Mod

α (β) = , s.t. β, β α, then α,β|= β

Vacuous case: If Mod

α (β)= , s.t. α β, then α,β=

α-contraction: If Mod

α (β)= , s.t. α β, then α,β |= α

The β-revision corresponds to the intended case in [Ferm e and Rott, 2004], in which the negation of the input β is more plausible than the negation of the reference α. Then it holds that β Bel( α,β) and Rb C displays a revision with β. If β is already more or equally plausible as α, then it follows from (1) that (Success) is already satisfied and Rb C does not change anything. We speak of the vacuous case. Yet, if Mod

α (β) = , then α is more plausible than the input β and Rb C performs a contraction of α such that α Bel( α,β). This case is called the unsuccessful case in [Ferm e and Rott,

αβ αβ αβ αβ αβ, αβ αβ αβ, αβ αβ αβ αβ αβ, αβ αβ, αβ αβ αβ, αβ αβ, αβ αβ αβ, αβ 1 1 2 2 3 3

Figure 2: Examples for Revision by Comparison for plausibilistic TPOs 1, 2 and 3. The worlds are ordered in ascending order of plausibility with the most plausible worlds at the bottom.

2004] and it corresponds to the idea that the reference sentence displays the source β is coming from, so that the plausibility of α can be interpreted as the reliability of this source, which decreases in the case of a sufficiently implausible input. Note that if Mod

α (β) = then the vacuous case and α-contraction coincide. In this case Rb C does not change the prior ordering and α Bel( α,β) follows from α Bel( ).

Example 2. In Figure 2 we give three examples of Rb Crevised TPOs s.t. 1= ( α,β)1, 2= ( α,β)2 and 3= ( α,β)3. The first revised TPO 1 corresponds to a βrevision with Mod 1

α (β) = {αβ} and Mod 1

α (β) = {αβ}. As we can see it holds that 1|= β. For 2 it holds that Mod 2

α (β) = and the operation does not change anything s.t. 2= 2, this corresponds to the vacuous case. For the third TPO Rb C performs an α-contraction, since Mod 3

α (β) = and it holds that 3 |= α.

In the following subsection, we will discuss the three above mentioned cases and their effect on the belief change induced by Rb C in the framework of ranking function, but for now we complete the examination of Rb C αβ in the possible-worlds semantic and transfer the properties of Rb C as follows:

(Success)tpo α is at least as plausible as β: α α,β β

(Lifting)tpo It does no extra lifting: α α,β β iff α β

(α-level)tpo For any sentence γ, it holds that α α,β γ iff α γ, and γ α,β β iff γ α or γ β

(Min)tpo If α γ and α δ then: γ α,β δ iff γ δ

The properties (Success), (Lifting), (α-level) and (Min) hold for α,β E [Ferm e and Rott, 2004] and thus, we can conclude for each TPO α,β satisfying (4) that α,β satisfies (Success)tpo, (Lifting)tpo, (α-level)tpo and (Min)tpo. Note that in the contradictory case (α ), (Success)tpo holds trivially, since β is always true. Moreover, the posterior epistemic states of Rb C tend to make relations among worlds much coarser, since we loose plausibility distinctions between worlds in Mod

α (β). Hence Rb C does not satisfy the Darwiche and Pearl postulates [Darwiche and Pearl, 1997].

3.3 Revision by Comparison for Ranking Functions Next, we present a semi-quantitative version of Rb C that implements the semantical recipe of Rb C given in (5) for ranking functions κ in a simple, yet elegant way. Furthermore, the use of ranking functions makes the change on the prior belief

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

state and the dependence on the relation between input and reference information in Rb C more explicit. First, we define the set of βresp. β-worlds that are more plausible than α according to κ analog to Mod

α (β) resp. Mod

α (β) as follows:

α (β, κ) = {ω Ω| ω |= β and κ(ω) < κ(α)},

α (β, κ) = {ω Ω| ω |= β and κ(ω) < κ(α)}.

Definition 3 (Rb C for OCFs). Let κ be a ranking function. We define the Revision by Comparison αβ with input sentence β and reference sentence α for ranking functions as follows

κ α β(ω)=κ α,β(ω)=κ0 + κ(α), ω Mod<

α (β, κ) κ(ω), otherwise (6)

where κ0 = min{κ(α), κ(β)} is a normalization constant. The normalization constant κ0 can be computed as follows: We have κ0 = minω Mod<

α (β,κ){κ(α), κ(ω)}. For

α (β, κ), it must hold that ω |= β or κ(ω) κ(α). Hence, only ω |= β can be relevant for the minimum. Thus, we can conclude κ0 = min{κ(α), κ(β)}. For the contradictory case α , it holds that Mod<

α (β, κ) = and therefore Rb C does not modify the prior ranking function and κ α,β(ω) = κ(ω) for all worlds and κ0 = 0. The methodology of Rb C depicted in Figure 1 and defined via the constraints in (5) can be seen directly from Definition 3. Now, it is easy to see that the worlds in Mod<

α (β, κ) are shifted to the α-level of plausibility, s.t. κ α,β(α) κ α,β(β) and that the plausibility relations among the worlds Ω\ Mod<

α (β, κ) remain the same. Their ranks only change according to the normalization of the posterior ranking function. We get the following theorem: Theorem 2. Let κ be a ranking function and κ α,β = κ α β be the Rb C-revised ranking function from (6). Then the corresponding TPO κ α,β can be defined from κ by (5). Since κ α,β satisfies (5), it follows from Theorem 1 that it also satisfies (4) and therefore the properties of Rb C follow via (2) for κ α,β and we get that: Theorem 3. Let κ be a ranking function and κ α,β = κ α β. The associated TPO κ α,β satisfies (Success)tpo, (Lifting)tpo, (α-level)tpoand (Min)tpo. Theorem 2 and 3 together show that Definition 3 is a suitable definition of Rb C for ranking functions. In the following, we will show that Rb C can also be defined as c-change operation via a designated set of conditionals. This conditional revision also reflects the hybrid character of Rb C which we discussed earlier, since it displays a revision or a contraction depending on the prior belief state.

3.4 Revision by Comparison as a c-Revision C-revisions, introduced by Kern-Isberner [Kern-Isberner, 2001], provide a highly general framework for revising ranking functions by sets of conditionals with respect to conditional interactions, while preserving conditional beliefs in the former belief state as far as possible. In this section, we will

use c-revisions to revise a ranking function κ with a suitable set of weak conditionals to obtain κ α β as given in (6). In general a c-revision with a set of weak conditionals = {(|δi|γi|)}n i=1 is an OCF κc = κ of the form

κc(ω) = κ0 + κ(ω) + X

ω|=γiδi ν i

with a normalization constant κ0 that ensures that κc is a ranking function and non-negative impact factors ν i that satisfy the following inequalities:

ν i min ω|=γiδi

ω|=γjδj ν j min ω|=γiδi

ω|=γjδj ν j (7)

These inequalities ensure that κc |= . Note that, (7) is satisfiable for each , since sets that consist solely of weak conditionals are always consistent [Sezgin and Kern Isberner, 2021]. The c-revision with corresponds to the c-contraction with a set of conditionals that consists of all negated conditionals from , for more details see [Kern Isberner et al., 2017]. Consider

α,β = {(|α|α ω|) | ω Mod<

expressing the constraints that κ α,β(α(α ω)) = κ α,β(α) κ α,β(α(α ω)) should hold in the revised ranking function for ω Mod<

α (β, κ). For contradictory reference sentences α , we get that α,β = since Mod<

α (β, κ) = and therefore the c-revision does not change anything. The minimal c-revision with α,β can be computed as follows: First, it holds that the falsification of conditionals (|α|α ω|) α,β is

(α ω) α ω α ω, (8)

because ω Mod(α) holds for ω Mod<

α (β, κ), since κ(ω) < κ(α) and due to minimality of rank κ(α). Thus, for each ω Mod<

α (β, κ) only a single conditional is falsified and a c-revision with α,β, κ α,β c = κ α,β, is given by:

κ α,β c (ω) = κ0 + κ(ω) + ν ω, ω Mod<

α (β, κ) 0, othw. (9)

with κ0 a normalization constant and ν ω as non-negative impact factors for each weak conditional in α,β satisfying the constraints

ν ω min ω |=α{κ(ω ) + X

ω |= ω Mod<

α (β,κ), ω =ω ν ω }

min ω |=ω α{κ(ω ) + X

ω |= ω Mod<

α (β,κ), ω =ω ν ω } (10)

=κ(α) κ(ω).

Note that, in both minima the sums equal zero and the second minimum in (10) ranges only over ω (see (8)). Thus, to obtain a minimal c-revision, we can choose

ν ω = κ(α) κ(ω). (11)

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

κ α,β c (ω) = κ0 + κ(α), ω Mod<

α (β, κ) κ(ω), otherwise

The normalization constant κ0 can be substantiated as κ0 = min{κ(α), κ(β)}. following the same argumentation as for κ α,β. So, we get the same posterior ranking function as the quantitative Rb C and state the following Theorem: Theorem 4. Let κ be a ranking function. Let κ α,β be the posterior ranking function after quantitative Rb C as defined in Definition 3 and κ α,β c = κ α,β be the posterior ranking function after the minimal c-revision. Then it holds for all ω Ωthat κ α,β(ω) = κ α,β c (ω), i.e., both revision mechanisms yield the same results. The following corollary follows from Theorem 3 and 4 and shows that Rb C defined as a c-revision satisfies all properties of Rb C: Corollary 2. Let κ be a ranking function and κ α,β c = κ α,β a minimal c-revision. Then it holds that the corresponding TPO κ α,β c defined via (2) satisfies (4) resp. (5) and (Success)tpo, (Lifting)tpo and (α-level)and (Min)tpo. The advantage of implementing Rb C for ranking functions by a c-revision using sets of weak conditionals is that the core of the required change process can be made very explicit in α,β, also showing clearly what does not change, namely the relations among worlds in Ω\ Mod<

α (β, κ). Thus, weak conditionals support the hybrid belief change character of Rb C. The dependence on the prior ranking function is made visible and we discuss the three cases that we introduced in Section 3.2 and their impact on the Rb C-revised ranking function κ α,β c : β-revision: Since Mod

α (β) = it holds that α,β = and we can conclude from Mod<

α (β, κ) = that κ(β) < κ(α). Hence, κ(β) = κ α,β c (β) < κ α,β c (α) κ α,β c (β). Thus κ α,β c (β) > 0, s.t. κ α,β c |= β and Rb C for ranking functions performs a revision with β

Vacuous case: Since Mod

α (β) = it holds that α,β = . Thus, κ α,β c (ω) = κ(ω) for all ω Ω α-contraction: Since Mod

α (β) = it holds that κ(α) κ(β), i.e. κ α,β c (α) κ α,β c (β). Since κ α,β c (α) κ α,β c (β) holds for all κ α,β c and due to the minimality of ranks, we get that κ α,β c (α) κ α,β c (ω) for all ω Ω, thus κ α,β c |= α and Rb C for ranking functions results in a contraction of α It is clear from Theorem 4 that these results also hold for κ α,β as defined in Definition 3. We have seen that Rb C can be displayed as a revision with negative information, therefore the Darwiche and Pearl postulates [Darwiche and Pearl, 1997] are not the right framework to capture the dynamic belief change induced by Rb C. We illustrate Rb C with input sentence β and α as reference as a c-revision with α,β in the following example: Example 3. In Figure 3 a ranking function κ is depicted with Mod<

α (β, κ) = {αβγ} = and Mod<

κ κ α,β c αβγ, αβγ αβγ, αβγ 3 αβγ, αβγ αβγ, αβγ 2 αβγ αβγ, αβγ 1 αβγ αβγ 0 αβγ, αβγ αβγ

Figure 3: Example of Revision by Comparion κ α β performed via a c-revision with α,β = {(|α|α (αβγ)|)}

{αβγ, αβγ} = , i.e. Rb C κ α β with input β and reference α performs a β-contraction. It holds that α,β = {(|α|α (αβγ)|)} with impact factor ν αβγ = 2 and the c-

revised ranking function κ α,β c = κ α,β = κ α β can be found in Figure 3 and it holds that κ α,β c |= β.

4 Related Work

The dynamic belief change performed by Rb C moves it in the vicinity of credibility-limited revision operators (CLoperators) [Hansson et al., 2001], where a revision on a general epistemic state Ψ is solely performed if the input information is part of a set of credible formulas Bel(Ψ) C otherwise the prior belief state is kept. In [Booth et al., 2012], these operators are defined for epistemic states. Using Rb C we clarify the methodology of choosing a set of credible worlds. We have seen that Rb C with input β and reference α performs a revision with β in the case that β, β are more plausible than α, i.e. if Mod

α (β) = . Thus Rb C generates a restricted set of credible worlds Cα,β = Mod

α (β) which is dependent from the inputs β and α with Bel( ) Mod(β) Cα,β. The set is restricted since not the whole belief set Bel( ) is part of Cα,β. We define the belief set of an Rb C-based CL-operator Rb C α as follows:

Bel( Rb C α β)= Bel( αβ), if Mod(β) Mod

α (β) = Bel( ), otherwise

Rb C is appealing as basis for a CL-operator since it allows for a flexible and reasonable determination of the set of credible worlds via choosing suitable reference sentences. Exploring extensions of CL-operators and their connection to Rb C more thoroughly is part of our future work.

5 Conclusion

We have clarified the strategy underlying Revision by Comparison and transferred the versatile belief change mechanism to the semi-quantitative framework of ranking functions. The implementation of the Rb C-revised ranking function inherits all characteristics of Revision by Comparison as a hybrid belief change mechanism. Using negated conditional information, we defined Rb C as a conditional revision and therefore paved the way to the implementation of interesting operators capable of dealing with hybrid belief change operators. At last, we discussed the relationship between Rb C and credibility-limited belief revision operators.

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

References [Alchourr on et al., 1985] Carlos Alchourr on, Peter G ardenfors, and David Makinson. On the logic of theory change: Partial meet contraction and revision functions. Journal of Symbolic Logic, 50:510 530, 06 1985. [Booth et al., 2012] Richard Booth, Eduardo Ferm e, S ebastien Konieczny, and Ram on Pino P erez. Credibilitylimited revision operators in propositional logic. 13th International Conference on the Principles of Knowledge Representation and Reasoning, KR 2012, 01 2012. [Darwiche and Pearl, 1997] A. Darwiche and J. Pearl. On the logic of iterated belief revision. Artificial Intelligence, 89:1 29, 1997. [De Finetti, 1975] B. De Finetti. Theory of Probability: A critical introductory treatment. Wiley Series in Probability and Statistics. Wiley, 1975. [Ferm e and Rott, 2004] Eduardo L. Ferm e and Hans Rott. Revision by comparison. Artif. Intell., 157(1-2):5 47, 2004. [G ardenfors and Makinson, 1988] Peter G ardenfors and David Makinson. Revisions of knowledge systems using epistemic entrenchment. In Moshe Y. Vardi, editor, Proceedings of the 2nd Conference on Theoretical Aspects of Reasoning about Knowledge, Pacific Grove, CA, USA, March 1988, pages 83 95. Morgan Kaufmann, 1988. [Grove, 1988] Adam Grove. Two modellings for theory change. Journal of Philosophical Logic, 17(2):157 170, 1988. [Hansson et al., 2001] Sven Ove Hansson, Eduardo Leopoldo Ferm e, John Cantwell, and Marcelo Alejandro Falappa. Credibility limited revision. The Journal of Symbolic Logic, 66(4):1581 1596, 2001. [Hansson, 2008] Sven Ove Hansson. What s new isn t always best. Theoria, 63:1 13, 2008. [Katsuno and Mendelzon, 1992] Hirofumi Katsuno and Alberto O. Mendelzon. Propositional knowledge base revision and minimal change. Artif. Intell., 52(3):263 294, 1992. [Kern-Isberner et al., 2017] Gabriele Kern-Isberner, Tanja Bock, Kai Sauerwald, and Christoph Beierle. Iterated contraction of propositions and conditionals under the principle of conditional preservation. In Christoph Benzm uller, Christine Lisetti, and Martin Theobald, editors, GCAI 2017. 3rd Global Conference on Artificial Intelligence, volume 50 of EPi C Series in Computing, pages 78 92. Easy Chair, 2017. [Kern-Isberner, 2001] Gabriele Kern-Isberner. Conditionals in Nonmonotonic Reasoning and Belief Revision - Considering Conditionals as Agents, volume 2087 of Lecture Notes in Computer Science. Springer, Berlin, 2001. [Lehmann and Magidor, 1992] Daniel Lehmann and Menachem Magidor. What does a conditional knowledge base entail? Artif. Intell., 55(1):1 60, 1992.

[Lewis, 1973] David K. Lewis. Counterfactuals. Blackwell, Oxford, 1973. [Nayak, 1994] Abhaya C. Nayak. Iterated belief change based on epistemic entrenchment. Erkenntnis, 41(3):353 390, 1994. [Peppas and Williams, 1995] Pavlos Peppas and Mary-Anne Williams. Constructive Modelings for Theory Change. Notre Dame Journal of Formal Logic, 36(1):120 133, 1995. [Schwind et al., 2018] Nicolas Schwind, S ebastien Konieczny, and Pierre Marquis. On belief promotion. In Michael Thielscher, Francesca Toni, and Frank Wolter, editors, Principles of Knowledge Representation and Reasoning: Proceedings of the Sixteenth International Conference, KR 2018, Tempe, Arizona, 30 October - 2 November 2018, pages 297 307. AAAI Press, 2018. [Sezgin and Kern-Isberner, 2021] Meliha Sezgin and Gabriele Kern-Isberner. System Z for conditional belief bases with positive and negative information. In Eric Bell and Fazel Keshtkar, editors, Proceedings of the Thirty-Fourth International Florida Artificial Intelligence Research Society Conference, North Miami Beach, Florida, USA, May 17-19, 2021, 2021. [Spohn, 1988] Wolfgang Spohn. Ordinal conditional functions: A dynamic theory of epistemic states. In William L. Harper and Brian Skyrms, editors, Causation in Decision, Belief Change, and Statistics, pages 105 134. Springer, Dordrecht, 1988.

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)