Prolegomenon to a Theory of Conservative Belief Revision

1 Motivation and Examples

The following example illustrates the traditional account of integrating new information, in accord with minimal change.

Example 1.1 (Exclusive disjunctive update) Leslie and Robin are two students who share an apartment above your's. While they get along, they are independent and have Maurice Pagnucco*

· Also affiliated with National ICT Australia and the ARC Centre of Excellence in Autonomous Systems.

School of CSE The University ofNew South Wales NSW, 2052, AUSTRALIA

morri@cse.unsw.edu.au

their own circles of friends. You initially believe that for the upcoming weekend neither will be in the apartment, say K = ·l A ·r. However, come the weekend you hear muted but unmistakable sounds of domestic activity. You modify your beliefs minimally to account for this new information, and consequently you conclude just that one of them has not gone away for the weekend, i.e. K o (l V r) = (l r; ·r). 1

To be sure, this result is not dictated by the standard postu­ lates but it seems to be the most plausible minimal change, given the information available; as well, this phenomenon recurs in the standard distance-based approaches to update (e.g., [Winslett, 1990]), as well as in the belief revision coun­ terparts. The next example illustrates that these results aren't necessarily desirable all the time.

Example 1.2 (Inclusive disjunctive update) There are two rooms in a warehouse, on the left and on the right. Let l and r denote the fact that the respective rooms are not empty. There are a number of boxes outside the warehouse but the rooms are initially empty, and so K = ·l A ·r. It subsequently be­ gins to rain, and the boxes are moved inside. One concludes just that the rooms are not empty, i.e. K o (l V r) = (l V r).

This example apparently violates the principle of minimal change. As well it conflicts with the aforecited distance-based approaches, which dictate that the result bel r; ·r, that all the boxes are in one room or the other.

The idea here is that for a revision (or update) by a formula ¢>, exactly ¢> is to be incorporated into the knowledge base. Consider K * (p V q). If the idea is that all we know about p and q is that p V q is true, then we would want the possible combinations of truth values {p, q}, { ·p, q}, and {p, ·q} to be considered possible, and so be consistent with K * (p V q) . This sense is reminiscent of Gricean conversational implica­ ture [Grice, 1975] wherein a speaker is required to be max­ imally informative. Thus if a listener is told that p V q is true, then the communicator does not know which of p, q are true; if they did, they would have conveyed the stronger in­ formation to the listener. A similar notion has been studied by Levesque, and Lakemeyer and Levesque (see [Lakemeyer and Levesque, 2000]) dealing with "only-knowing" or "only­ knowing about". These concepts arise in autoepistemic de­ fault reasoning where one may want to assert that all an agent knows is ¢ or all that an agent knows about a is ¢. Techni­ cally in our approach this will amount to the result of a belief change being a conservative extension (Section 2) of the for­ mula to be incorporated in the knowledge base.

1 <--> is material biconditional and = is logical equivalence.

2 Preliminaries

We consider a finitary propositional language £ , over a set of atoms, or propositional letters, P = {a, b, c, ... } , truth-functional connectives ·, 1\, V, ::), and +-+, and truth­ functional constants T and ..l. Interpretations and models are defined in the standard way; M is the set of interpreta­ tions of£. M od.c ( ¢) denotes the set of models of sentence ¢ over language £; the subscript £ may be dropped if the language is clear. For ¢ E £, we will define £( ¢ ), the lan­ guage in which ¢ is expressed, as comprising the minimum set of atoms required to express¢ (see [Parikh, 1999]). Thus £(p 1\ (q V ·q)) = £(p) = {p}. This extends to sets of sen­ tences in the obvious way. It follows that if f= ¢ +-+ 'ljJ then £(¢) = £('1j;), and iff= ¢ then£(¢)= {T}.

We will make use of the notion of a conservative extension of one set of sentences by another.

Definition 2.1 For sets of sentences r 1 ~ f z ~ £we have that f 2 is a conservative extension off1 iff for every¢ E £(f1). ifrz F= ¢ then r1 F= ¢.

Intuitively f 2 is a conservative extension off 1 ifffz extends r 1 but tells us nothing more about sentences that are in the language off1. fz may entail sentences in its extended lan­ guage of course but as far as the language which it shares with r 1 is concerned, it says no more than r 1·

A common approach in addressing belief revision has been to provide a set of rationality postulates for belief change functions. The AGM approach [Giirdenfors, 1988] provides the best-known set of such postulates. The goal is to describe belief change at the knowledge level, that is on an abstract level , independent of how beliefs are represented and manip­ ulated. Belief states are modelled by sets of sentences, called belief sets, closed under logical consequence. K can be seen as a partial theory of the world. For belief set K and formula ¢, K + ¢ is the deductive closure of K U { ¢}, the expan­ sion of K by ¢ . Expansion is intended to be applied when new information is consistent with current beliefs. K 1. is the inconsistent belief set (i.e. K 1. = £).

In belief revision, the new information may be inconsis­ tent with the reasoner's beliefs and needs to be incorporated in a consistent manner where possible. See [Giirdenfors, 1988] for the revision postulates. We will make reference to Grove's use of a system of spheres (SOS) model for charac­ terizing AGM revision [Grove, 1988]. A system of spheres centred on X is a total, well-founded preorder on the set of interpretations, 5:.sos, in £ such that for x E M we have that: x E X iff x 5:. y for all y E M. (That is, X is the least set of worlds in the preorder.) We will often omit the subscript from 5:.sos for readability. Revision is defined for M od.c(K) =X by

where min{} denotes the minimal models under 5:_. Grove shows that for every belief revision operator satisfying the AGM postulates there is a system of spheres characteris­ ing that operator, and vice versa.

3 Conservative Belief Revision

We use * to denote the type of belief revision described in Section 1, called "conservative belief revision" or "C­ revision." The idea we wish to capture is that, for K * ¢, ¢ is exactly what will be believed in the resulting knowledge base, relative to the "subject matter" or "context" implicit in ¢ . So forK* ((p V q) 1\ r) the idea is that (p V q) 1\ r constrains the truth values of the atoms in {p, q, r }, and that exactly (p V q) 1\ r will be known about these atoms in there­ sulting knowledge base. In particular, strengthenings ofpV q, such asp or p +-+ ·q will not be true in the resulting knowl­ edge base. This will be the case even when K implies p or p +-+ ·q; hence a revision may in fact yield a weakening of the knowledge base. This restriction does not necessarily hold for the sentences not in £( ¢).

The semantic intuition behind our proposal is easily visu­ alised. In Figure 1 we consider a revision where the underly­ ing language is generated from atoms x, y and z. The agent believes xl\ ·Y 1\z and encounters evidence ·xV ·y. Accord­ ingly the models are partitioned into four cells corresponding to the interpretations over£( ·x V ·y). The best worlds from each of the three cells satisfying ·X V ·y are chosen to rep­ resent the revised knowledge base. Clearly, the belief content of the new knowledge base modulo £(·x V ·y) will be ex­ actly ·xV·y. Beliefs regarding z will depend on extralogical factors, namely the plausibility of different worlds.

Now, in determining C-revision, we consider the plausibility of different worlds represented in Figure 1 by the concentric "rings". The worlds that are more centrally located are more plausible. Accordingly, from the [x·y] cell, the world x·yz is selected, whereas worlds ·xy·z and · x·y·z are selected from the cells [·xy] and [·x·y] respectively. Since some of these selected worlds satisfy z and some ·z, under this plau­ sibility ordering the belief z is lost. In fact, the new beliefs regarding z can be captured by the beliefs x +-+ z and y V z that are retained from the old knowledge base.

We can formalize this analogously to Grove's system of spheres model for characterizing AGM revision. Given ( 1 ), we have the analogous definition for C-revision:

The overall result is captured by the following theorem:

Theorem 3.1 For any belief set K and input sentence ¢, K * ¢ is a conservative extension of¢, i.e., for 'ljJ E .C( ¢ ), if K * ¢ f= 'ljJ then ¢ f= 'lj;.

We obtain the following elementary results.

Theorem 3.2

2. For ¢ a conjunction of literals, K * ¢ = K * ¢.

This gives rise to the question of whether a specific C-revision function can be captured using the standard definition of re­ vision ( 1) in some suitably-constructed system of spheres. In general the answer is negative; for a counterexample, con­ sider where .C = {p, q} and we are given a C-revision func­ tion such that K = -.pf\·q and in which K * p = K * (pl\q). This entails the following constraints on the ordering:

However, as is easily verified in this case, K * (pV q) = pV q. This however cannot be obtained by standard revision given the above constraints on the ordering, since it would require {p , q} , { -.p, q} and {p, -.q} at the same level.

While a given system of spheres determines a unique C­ revision (as constructed by (2)), the converse in general does not hold. The following example demonstrates this.

Example 3.1 Consider SOS1 : . . . < xyz < x-.y-.z and SOS2 : ... < x-.y-.z < xyz, where the ... in the orderings represent an identical subsequence. The C-revision based on these SOS's (using Definition 2) exhibit identical behaviour since no cell of any partition based on a sub-language of { x, y, z} will pick up exactly the set { xy z, x-.y-.z} .

Thus we notice an asymmetry between the classical AGM account of belief revision and C-revision. An AGM revision operation*, given a fixed belief set K, determines a unique system of spheres. On the other hand, the C-revision oper­ ation, given a fixed belief set K, corresponds to a class of systems of spheres. It is of interest to characterise the class of systems of spheres that a given C-revision operation * deter­ mines. However, we leave this to future work.

We consider next those postulates satisfied by C-revision.

Theorem 3.3 Let K be a belief set, ¢, 'ljJ E .C and let * be defined via (2), then * satisfies the following properties:

( K * 1) K * ¢ is a belief set.

(K*-2) ¢ EK*-¢.

(K*-3) K*-¢ s;; K +¢.

(K*-5) K*-¢=K1-ifff=·¢.

( K * 6) Iff= ¢ ..._.. 'ljJ, then K * ¢ = K * 'ljJ.

(K *- 7) If'lj; E K *-¢then K *- ¢ = K *- (¢ 1\ 'lj;).

(K * 10) If -'-1¢ ~ K *- 'ljJ and ·'1/J ~ K *-¢then K *- ¢ s;; K *- (¢ 1\ 'lj;).

(K * 9) If 'lj; E .C(¢) then K * ¢ f= 'ljJ implies¢ f= '1/J.

The numbering is intended to reflect correspondences with the AGM revision postulates. Postulate (K * 9) is new and states that K * ¢ is a conservative extension of¢. Since C­ revision behaves the same as (standard, AGM-style) revision if the formulas involved in a revision are equivalent to sets of literals, AGM postulates 7 and 8 hold in C-revision if¢ and 'ljJ are equivalent to conjunctions of literals.

There are counterexamples to other AGM postulates.

Observation 1 The following do not hold of K * ¢.

(K * 4) If · ¢ ~ K , then K + ¢ s;; K * ¢ .

( K * 7) K * ( ¢ 1\ 'ljJ) s;; ( K * ¢) + '1jJ .

( K * 8) If -.'lj; ~ K * ¢, then ( K * ¢) + 'ljJ s;; K * ( ¢ 1\ ·l(J) .

4 Conclusion

We have outlined a theory of conservative belief change and presented an analysis of its properties. The main intuitive mo­ tivation for this work stems from an attempt to make the most of the information presented by new evidence that a reasoner acquires. As such, our approach focuses much more on the content of the new evidence. Our current analysis suggests that the operator we introduced based on these intuitions pos­ sesses some interesting and appealing properties.

With respect to semantics, the distinction between standard AGM revision and C-revision is very much analogous to the distinction between revision and update, and in fact the two distinctions may be seen as duals of each other. For an (AGM) revision, K * ¢, we consider the set of all models of K, and revise by selecting the closest models of¢ to that set. For an update, K o ¢, we consider instead each model of K individ­ ually, and for each model of K look for the closest models of ¢; the update is the union of all such models. Analogous to update, for a C-revision, K * ¢, we consider each model of ¢ (over .C( ¢)),and revise K by this model; the C-revision is the union of all such models. In a similar way in which we moti­ vate C-revision from standard revision, we can define a notion of C-update from standard update. This duality between C­ and standard belief change on the one hand, and between re­ vision and update on the other, completes a classification of belief change operators, in terms of whether the models of a knowledge base or formula for change are considered en masse, or individually. It is also relatively straightforward to define syntax-dependent versions of both C-revision and C­ update. Also we can look at C-contraction operations (both syntax-independent and dependent versions). However we leave this to future work.