Postulates for Conditional Belief Revision

1 Introduction

Belief revision deals with the dynamics of belief- how should currently held beliefs be modified in the light of new information? Results in this area are mainly in­ fluenced by the so-called AGM theory, named after Al­ chourron, Gardenfors and Makinson who set up a frame­ work of postulates for a reasonable change of beliefs ( cf. [Alchourr6n et al., 1985), [Gardenfors, 1988]) . Usually, the belief sets in AGM theory are assumed to be de­ ductively closed sets of propositional formulas, or to be represented by one single propositional formula, respec­ tively, and the revising beliefs are taken to be proposi­ tional formulas. So the AGM postulates constrain re­ visions of the form 1/J *A, the revision operator * con­ necting two propositional formulas 1/J and A, where 1/J represents the initial state of belief and A stands for the new information. A representation theorem ( cf. [Kat­ suno and Mendelzon, 1991]) establishes a relationship between AGM revision operators and total pre-orders ':S_.p on the set of possible worlds, proving the revised belief set 1/J * A to be satisfied precisely by all minimal A-worlds.

Though belief sets representing what is known for cer­ tain are of specific interest they are only poor reflections of the complex attitudes an individual may hold. The limitation to propositional beliefs severely restricts the frame of AGM theory, in particular, when iterated re­ vision has to be performed. So belief revision should not only be concerned with the revision of proposi­ tional beliefs but also with the modification of revision strategies when new information arrives (cf. [Darwiche and Pearl, 1997], [Boutilier, 1993), [Boutilier and Gold­ szmidt , 1993]) . These revision strategies may be taken as conditional beliefs, therefore revision should be con­ cerned with changes in conditional beliefs and, the other way around, with the preservation of conditional beliefs.

Darwiche and Pearl [Darwiche and Pearl, 1997] explic­ itly took conditional beliefs into account by considering epistemic states instead of belief sets, and they advanced four postulates in addition to the AGM axioms to model what may be called conditional preservation under revi­ sion by propositional beliefs.

In the present paper, we broaden the framework for re­ vising epistemic states presented in [Darwiche and Pearl , 1997] so as to include also the revision by conditional be­ liefs. Thus belief revision is considered here in quite a general framework, exceeding the AGM-theory in two respects:

• We revise epistemic states; this makes it necessary to allow for the changes in conditional beliefs caused by new information.
• The new belief A may be of a conditional nature, thus reflecting a changed or newly acquired revision policy that has to be incorporated adequately.

We present a scheme of eight postulates appropriate to guide the revision of epistemic states by conditional be­ liefs. These postulates are supported mainly by follow­ ing the specific, non-classical nature of conditionals, and the aim of preserving conditional beliefs is achieved by studying specific interactions between conditionals, rep­ resented properly by two relations. Because one of the postulates claims propositional belief revision to be a special case of conditional belief revision, our framework also covers the topic of Darwiche and Pearl's work [Dar­ wiche and Pearl, 1997), and we show that all four postulates presented there may be derived from our postulates. We state representation theorems for the principal pos­ tulates, and finally, we present a conditional belief oper­ ator obeying all of the postulates by using ordinal con­ ditional functions as representations of epistemic states.

The organization of this paper is as follows: In sec­ tion 2, we briefly summarize the results of Darwiche and Pearl concerning the revision of epistemic states and lay down some foundations for this paper. In section 3, we describe conditionals as objects of a three-valued nature and introduce the relations l_ and C between condition­ als which play an important part for studying interac­ tions between conditionals. Section 4 presents and ex­ plains the eight postulates for conditional revision and shows correspondences to the axioms of [Darwiche and Pearl, 1997]. Section 5 contains representation theorems and some consequences of the postulates. In section 6, we introduce a conditional revision operator for ordinal condi tiona! functions that realizes the ideas of this paper, and section 7 concludes this paper with a short summary and an outlook.

2 Revising epistemic states

An epistemic state Ill represents the cognitive state of some individual at a given time. In particular, beside the set of beliefs Bel(w) the individual accepts for certain, Ill contains the revision policies the individual entertains at that time. These revision policies reflect the beliefs (B) the individual is inclined to hold if new information (A) becomes obvious, and are adequately represented by conditionals (B I A), i.e. expressions of the form "If A then B" , conjoining two propositional formulas A and B. So the conditional (B I A) is accepted in the epistemic state Ill iff revising Ill by A yields belief in B. This defines a fundamental relationship between conditionals and the process of revision, known as the Ramsey test (cf. e.g. [Boutilier and Goldszmidt, 1993], [Giirdenfors, 1988]):

where* is a revision operator, taking an epistemic state Ill and some new belief A as inputs and yielding a revised epistemic state Ill* A as output.

Each epistemic state Ill is associated with its belief set Bel(w) which is supposed to be a deductively closed set of formulas of a propositional language £. The re­ vision of Ill by A E £ also yields a revised belief set Bel (Ill *A) ~ £, and of course, this revision should obey the standards of the AGM theory. But the revision of epistemic states cannot be reduced to propositional re­ vision because two different epistemic states Ill 1, Ill 2 may have equivalent belief sets Bel(wl) = Bel(w2). Thus an epistemic state is not described uniquely by its belief set, and revising Ill 1 and Ill 2 by new information A may' result in different revised belief sets Bel(w1 *A) -=t. Bel(w2*A).

Example. Two physicians have to make a diagnosis when confronted with a patient showing certain symp­ toms. They both agree that disease A is by far the most adequate diagnosis, so they both hold belief in A. More­ over, as the physicians know, diseases B and C might also cause the symptoms, but here the experts disagree: One physician regards B to be a possible diagnosis, too, but excludes C, whereas the other physician is inclined to take C into consideration, but not B.

Suppose now that a specific blood test definitely proves that the patient is not suffering from disease A. So both experts have to change their beliefs, the first physician now takes B to be the correct diagnosis, the second one takes C for granted. Though initially the physicians' opinions may be described by the same belief set, they end up with different belief sets after revision.

It is important to note that Giirdenfors' famous triv­ iality result [Giirdenfors, 1988] complaining the incom­ patibility of the Ramsey test with some of the AGM­ postulates does not hold if conditional beliefs are consid­ ered essentially different from propositional beliefs, as is emphasized here and elsewhere (cf. e.g. [Darwiche and Pearl, 1997]). Therefore obeying the difference between Bel(wl) = Bel(w2) and 1!11 = 1!12 makes the Ramsey test compatible with the AGM-theory for propositional belief revision: Whereas Bel (Ill 1) = Bel (1!12) only means that both epistemic states have equivalent belief sets, Ill 1 = Ill 2 requires the two epistemic states to be iden­ tical, i.e. to incorporate in particular the same proposi­ tional beliefs as well as the same conditional beliefs.

Darwiche and Pearl [Darwiche and Pearl, 1997] con­ sider the revision of epistemic states with propositional beliefs, mainly concerned with handling iterated revi­ sions. They generalize the AGM-postulates for belief re­ vision to the framework of revising epistemic states ( cf. [Darwiche and Pearl, 1997]):

Suppose Ill, Ill 1, Ill 2 to be epistemic states and A,A1,A2,B E £;

• (R*l) A is believed in Ill* A: Bel (Ill* A) F= A.
• (R*2) If Bel (Ill) 1\ A is satisfiable, then Bel (Ill* A) Bel(w) 1\ A.
• (R*3) If A is satisfiable, then Bel (Ill* A) is also satisfi­ able.
• (R*4) If 1!11 = 1!12 and A1 = A2, then Bel(lll1 *A1) = Bel(lll2 *A2).
• (R*5) Bel (Ill* A) 1\ B implies Bel (Ill* (A 1\ B)).
• (R*6) If Bel (w*A)I\B is satisfiable then Bel (w*(AI\B)) implies Bel (Ill* A) 1\ B.

Considered superficially, these postulates are exact refor­ mulations of the AGM postulates, as stated in [Katsuno and Mendelzon, 1991], with belief sets replaced through­ out by belief sets of epistemic states. So the postulates above ensure that the revision of epistemic states is in line with the AGM theory as long as the revision of the corresponding belief sets is considered. The most im­ portant new aspect by contrast with propositional be­ lief revision is given by postulate (R · 4): Only identical epistemic states are supposed to yield equivalent revised belief sets. This is a clear but adequate weakening of the corresponding AG M-postulate

which amounts to reducing the revision of epistemic states to propositional belief revision. As we explained above, such a reduction is inappropriate.

Darwiche and Pearl [Darwiche and Pearl, 1997] proved a representation theorem for their postulates which par­ allels the corresponding theorem in AG M theory ( cf. [Katsuno and Mendelzon, 1991]), using the notion of faithful assignments:

Definition 1 ([Darwiche and Pearl, 1997]) Let W be the set of all worlds (interpretations) of the propo­ sitional language C and consider epistemic states ii! the belief sets of which belong to C.

A faithful assignment is a function that maps each such epistemic state ii! to a total pre-order < w on the worlds W satisfying the following conditions:-

for worlds w1, w2 E W and epistemic states ii!, <!I.

As usual, w1 <w w2 means w1 :Sw w2 and w2 fw w1; w1 =w w2 iff w1 :Sw w2 and w2 :Sw w1 .

Given the set W of all worlds of the language C and a propositional formula A E C, we denote by Mod(A) the set of all A-worlds, Mod(A) = {w E W I w f= A}. If ii! is an epistemic state, we set Mod(ii!) = Mod(Bel(ii!)).

Theorem 2 ([Darwiche and Pearl, 1997]) A revi­ sion operator* satisfies postulates (R*l)-(R*6) precisely when there exists a faithful assignment that maps each epistemic state ii! to a total pre-order :Sw such that

i.e. the worlds satisfying Bel (ii! *A) are precisely those worlds satisfying A that are minimal with respect to :Sw.

This theorem shows an important connection between the ordering <w associated with an epistemic state ii! and the proc~s of revising ii! by propositional beliefs. Therefore, at least in the context of revision, epis­ temic states are properly represented as pairs ( ii!, :S w) with a total pre-order :Sw satisfying conditions (1)­ (2) of definition 1 and the so-called smoothness con­ dition min(A; ii!) # 0 for any satisfiable A E C (cf. e.g. [Boutilier and Goldszmidt, 1993]), and such that Mod (ii!) = min(W; :Sw). Using the relationship (RT) between revision and conditionals, theorem 2 immedi­ ately yields

Lemma 3 A conditional (B I A) is accepted in an epis­ temic state (ii!, :Sw) iff all minimal A-worlds satisfy B, i.e. ii! f= (B I A) iffmin(A; ii!) ~ Mod(B).

Thus the pre-order <w encodes the conditional beliefs held in ii!. -

For two propositional formulas A, B, we define A <w B iff for all w E min(A; ii!), w' E min(B; ii!), we h;ve w <w w', i.e. iff the minimal A-worlds are at least as plausible as the minimal B-worlds. To simplify nota­ tions, we will replace a conjunction by juxtaposition and indicate the negation of a proposition by barring, i.e. AB =At\ B and B =-,B. Using this, the lemma above may be reformulated as Lemma 4 A conditional (B I A) is accepted in an epis­ temic state ( ii!, :S w) iff AB < w AB.

Boutilier (cf. e.g. [Boutilier, 1994]) also took conditional beliefs into account. He presented in [Boutilier, 1993] his natural revision that preserves as many conditional beliefs as possible, in accordance with the AGM pos­ tulates, and he generalized this approach to deal with the revision by conditional beliefs [Boutilier and Gold­ szmidt, 1993]. As Darwiche and Pearl emphasized, how­ ever, Boutilier's natural revision seems to be too restric­ tive in that it preserves conditional beliefs at the cost of compromising propositional beliefs ( cf. [Darwiche and Pearl, 1997]). Thus the question which conditional be­ liefs should be kept under revision turns out to be a crucial problem when revising epistemic states. In the framework of iterated revision, Darwiche and Pearl [Dar­ wiche and Pearl, 1997] proposed four postulates concern­ ing the preservation of condjtional beliefs under propo­ sitional revision:

For discussion of these postulates, cf. the original paper [Darwiche and Pearl, 1997].

In this paper, we present postulates for the revision of epistemic states by conditional beliefs which generalize the postulates of Darwiche and Pearl and support them with new conditional arguments. The rationale behind these postulates is not to minimize conditional change, as in Boutilier's work, but to preserve the conditional structure of the knowledge, as far as possible, which is made obvious by studying interactions between condi­ tionals.

3 Conditionals

Conditionals may be given a lot of different interpre­ tations, e.g. as counterfactuals, as indicative, subjunc­ tive or normative conditionals etc. (cf. e.g. [Nute, 1980], [Boutilier, 1994]). In the context of revision, a subjunc­ tive meaning fits particularly well , in accordance with the Ramsey test (RT) : If A were true, B would hold, implicitly referring to a revision of the actual epistemic state by A.

Independently of its given meaning, a conditional (B I A) is an object of a three-valued nature, parti­ tioning the set of worlds W in three parts: those worlds satisfying A t\ B and thus confirming the conditional , those worlds satisfying A t\ -,B, thus contradicting the conditional, and those worlds not fulfilling the premise A and so which the conditional may not be applied to at all. Therefore Calabrese represents a conditional as a generalized indicator function (cf. [Calabrese, 1991])

where u means undefined. Two conditionals are con­ sidered to be equivalent iff they are identical as indica­ tor functions, i.e. (B I A) ::: (D I C) iff A ::: C and AB ::: CD (cf. [Calabrese; 1991]). Usually, a propo­ sitional fact A E £ is identified with the conditional (A I T), where T is tautological.

For a conditional (B I A), we define the affirmative set (B I A)+ and the contradictory set (B I A)- of worlds as

Lemma 5 Two conditionals (B I A), (D I C) are equiv­ alent iff their corresponding affirmative and contradic­ tory sets are equal, i.e. (B I A) ::: (D I C) iff (B I A)+ = (D I c)+ and (B I A)- = (D I c)-.

It is difficult to capture interactions between condi­ tionals. In [Calabrese, 1991], logical connectives and im­ plications between conditionals are defined and investi­ gated. Here we will pursue a different idea of interaction. Having the effects of conditionals on worlds in mind, we define two relations ~ and l_ between conditionals by

and

Thus ( D I C) ~ ( B I A) if the effect of the former condi­ tional on worlds is in line with the latter one, but (D I C) applies to fewer worlds. Thus (D I C) may be called a subconditional of (B I A) in this case. In contrast to this, the second relation l_ symbolizes a kind of indepen­ dency between conditionals. We have (D I C) l_ (B I A) if Mod (C), i.e. the range of application of the condi­ tional (D I C), is completely contained in one of the sets (B I A)+, (B I A)- or Mod(A). So for all worlds which (D I C) may be applied to, (B I A) has the same effect and yields no further partitioning. Note, however, that l_ is not a symmetric independence rela­ tion; (D I C) l_ (B I A) rather expresses that (D I C) is not affected by (B I A).

Both relations may be expressed using the standard ordering < between propositional formulas : A < B iff A I= B, i.e. iff Mod(A) ~ Mod(B). -

• Lemma 6 (i) (D I C) ~ (B I A) iff CD ~ AB and CD~ AB; in particular, if (D I C)~ (B I A) then C<A.
• (ii) (D I C) ~ (B I A) and (B I A) ~ (D I C) iff (D I C)= (B I A).
• (iii) (D I C) l_ (B I A) iff C ~ AB or C < AB or C<A.

4 Revision by conditionals

Revising an epistemic state llf by a conditional (B I A) becomes necessary if a new conditional belief resp. a new revision policy should be included in llf, yielding a changed epistemic state llf' = llf * (B I A) such that llf' I= (B I A), i.e.llf'*A I= B. We will use the same oper­ ator *for propositional as well as for conditional revision, thus expressing that conditional revision should extend propositional revision in accordance with the Ramsey test (RT).

Boutilier and Goldszmidt [Boutilier and Goldszmidt, 1993] presented a generalized version of the natural revi­ sion operator of Boutilier to perform such an adaptation to conditional beliefs; their method minimizes changes in conditional beliefs in accordance with the AGM theory.

Below, we propose several postulates a revision of an epistemic state by a conditional should satisfy. The key idea is to follow the conditionals in llf a.S long as there is no conflict between them and the new conditional belief, and we will use ~ and l_ to relate conditionals appropri­ ately.

Postulates for conditional revision:

Suppose (llf, ~>~>) is an epistemic state and (B I A), (D I C) are conditionals. Let llf * (B I A) denote the result of revising llf by ( B I A).

• (CRO) llf * (B I A) is an epistemic state.
• (CRl) llf * (B I A) I= (B I A).
• (CR2) llf * (B I A)= llf iff llf I= (B I A).
• (CR3) llf * B = llf * (B I T) induces a propositional AGM-revision operator.
• (CR4) llf * (B I A) = llf * (D I C) whenever (B I A)::: (D I C).
• (CR5) If (D I C) l_ (B I A) then llf I= (D I C) iff llf*(B I A) I= (D I C).
• (CR6) If (D I C) ~ (B I A) and llf I= (D I C) then llf * ( B I A) I= ( D I C) .

Postulates (CRO) and (CRl) are self-evident. (CR2) postulates that llf should be left unchanged precisely if it already entails the conditional. (CR3) says that the induced propositional revision operator should be in ac­ cordance with the AGM postulates. (CR4) requires the result of the revision process to be independent of the syntactical representation of conditionals.

The next three postulates aim at preserving the con­ ditional structure of knowledge:

(CR5) claims that revising by a conditional should preserve all conditionals that are independent of that conditional, in the sense given by the relation L The rationale behind this postulate is the following: The va­ lidity of a conditional (B I A) in an epistemic state \[f depends on the relation between (some) worlds in Mod(AB) and (some) worlds in Mod(AB) (cf. lemmata 3, 4). So incorporating (B I A) to \[f may require a shift between Mod (AB) on one side and Mod (AB) on the other side, but should leave intact any relations between worlds within Mod(AB), Mod(AB), or Mod(A). These relations may be captured by conditionals not affected by (B I A), i.e. by conditionals (D I C) l_ (B I A) .

(CR6) states that conditional revision should bring about no change for conditionals that are already in line with the revising conditional, and (CR7) guaran­ tees that no conditional change contrary to the revising conditional is caused by conditional revision.

An idea of conditional preservation is also inherent to the postulates (C1)-(C4) of Darwiche and Pearl [Dar­ wiche and Pearl, 1997] which we will show to be gener­ alized by our postulates.

Theorem 7 Suppose * is a conditional revision opera­ tor obeying the postulates (CRO)-(CR7). Then for the induced propositional revision operator, postulates (C1)­ (C4) are satisfied, too.

Proof: Let A, B, C, DE£.

Suppose C ::S B or C ::S B. Then, according to lemma 6, (D I C) l_ (B IT). (CR3) and (CR5) now imply (C1) and (C2).

(C3) and (C4) are direct consequences of (CR6) and (CR7) by using that (B I A) ~ (B I T) and (B I A) ~ (B IT), respectively, due to lemma 6. 0

This theorem provides further justifications for the pos­ tulates of Darwiche and Pearl from within the framework of conditionals.

5 Representation theorems

Postulates (CR5)-(CR7) claim specific connections to hold between \[f and the revised \[f * ( B I A), thus relating :Silt and ::Silt*(BIA). We will elaborate this relationship in order to characterize those postulates by properties of the pre-orders associated with \[f and \[f * ( B I A).

Postulate (CR5) proves to be of particular im­ portance because it guarantees the ordering within Mod (AB), Mod (AB), Mod (A), respectively, to be pre­ served:

Theorem 8 The conditional revision operator * satis­ fies (CR5) iff for each epistemic state (\lf, :Silt) and for each conditional (B I A) it holds that:

for all worlds w,w' E Mod(AB) (Mod(AB), Mod(A), respectively).

As an immediate consequence, (1) yields Lemma 9 Suppose ( 1) holds for all worlds w, w' E Mod (AB) (Mod (AB), Mod (A), respectively). Let propo­ sition E ::S AB (AB, A), respectively). Then

Together with the Ramsey test (RT), (CR5) yields equalities of belief sets as stated in the following propo­ sition:

Proposition 10 If the conditional revision operator * satisfies postulate ( CR5), then

For the representation theorem~ of postulates (C6) and ( C7), we need postulate ( CR5), respectively equation (1) and its consequence, lemma 9, to ensure that the property of being a minimal world in the affirmative or in the contradictory set associated with some conditionals is not touched under revision.

Theorem 11 Suppose * is a conditional revision oper­ ator satisfying (CR5) . Let \[f be an epistemic state, and let (B I A) be a conditional. ·

1. *satisfies (CR6) iff for all w E Mod(AB), w' E Mod(AB), w <llt w' implies w <llt*(BIA) w'.
2. * satisfies (CR7) iff for all w E Mod (AB), w' E Mod(AB), w' <llt*(BIA) w implies w' <llt w.

6 Ordinal conditional functions

Ordinal conditional functions ( rankings), as introduced by Spohn [Spohn, 1988], are functions "' from worlds to ordinals, i.e. to non-negative integers, such that some worlds are mapped to the minimal element 0. They are considered adequate representations of epistemic states (cf. e.g. [Spohn, 1988], [Darwiche and Pearl, 1997]), in­ ducing a total pre-order on the set W of worlds by set­ ting w1 ::S" w2 iff K-(wl) ::S K-(w2). So the smaller K-(w) is, the more plausible appears the world w, and what is believed (for certain) in the epistemic state repre­ sented by "' is described precisely by the set {w E W I K-(w) = 0} =: Mod(Bel(K-)). For a propositional for­ mula A E £, we set K-(A) = min{K-(w) I w F= A}, so that K-(A VB) = min{K-(A), K-(B)}. In particular, 0 = min{K-(A), K-(A)}, so that at least one of A or A is considered mostly plausible. A proposition A is be­ lieved iff K-(A) > 0 (which implies K-(A) = 0), so that A is believed iff Bel(K-) FA. We abbreviate this again by "-f=A.

Let "' * A denote the revision of the ranking "' (of the corresponding epistemic state, respectively) by the proposition A E £ (for examples of such revision opera­ tors, cf. [Spohn, 1988], [Darwiche and Pearl, 1997]). For a conditional (B I A), we set"' F (B I A) iff"'* A F B, that is iff K-(AB) < K-(AB) (cf. lemma 4). Similar as in probability theory, we define K-(B I A) = K-(AB)- "-(A)

(for the connections between ordinal conditional func­ tions and qualitative probabilistic reasoning, cf. e.g. [Spohn, 1988], [Darwiche and Pearl, 1997), [Goldszmidt and Pearl, 1996)).

We are now going to present a conditional revision operator for ordinal conditional functions that satisfy all of the postulates (CRO)-(CR7) and thus realizes the idea of conditional revision developed in this paper:

For an ordinal conditional function"' and a conditional (B I A), we define"'* (B I A) by setting

where a= -1, if K(AB) < K(AB), and= 0, else.

The check of the postulates is straightforward, due to the representation theorems 8 and 11. So we have

Proposition 12 The conditional revision operator de­ fined by {2) satisfies all of the postulates {CRO}- {CR7).

7 Concluding remarks

We presented a scheme of postulates (CRO)-(CR7) are­ vision of an epistemic state by a conditional should sat­ isfy, with propositional revision and conditionals being connected via the Ramsey test (RT). These postulates are supported by arguments using the conditional struc­ ture of knowledge which can be made obvious by consid­ ering the relations l_ and !;;; between conditionals. We showed that our axioms cover the postulates of Darwiche and Pearl in [Darwiche and Pearl, 1997) and hence are of relevance for iterated belief revision, too. For the most crucial postulates (CR5)-(CR7), we formulated represen­ tation theorems, and we proved that our postulates are satisfiable by presenting a suitable conditional revision operator for ordinal conditional functions.

In addition to the postulates (CRO)-(CR7), another postulate may be worthwhile discussion:

(CR8) clearly exceeds the paradigm of conditional preservation, in favor of imposing conditional structure as long as this does not contradict stated knowledge. The revision operator introduced in (2) satisfies (CR8), too.

The notion of conditional preservation is also men­ tioned in the area of quantified uncertain reasoning in [Kern-Isberner, 1998], within the framework of proba­ bilistic reasoning at optimum entropy. Here we intro­ duced so-called c-adaptations which adjust a prior prob­ ability distribution P to new quantified conditional in­ formation in a manner that preserves the conditional structure inherent to P "as far as possible". Though the axiomatization of conditional preservation given in [Kern-Isberner, 1998) is quite complex, it is easy to prove that the c-adaptations satisfy a probabilistic version of postulate (CR5):

where x, y E [0, 1) are probabilities and P f= (D I C)[y) means that the conditional probability of D given C in P is y, i.e. P(D I C) = y.