Belief Revision and Updates in Numerical Formalisms: An Overview, with new Results for the Possibilistic Framework

1 Introduction

Numerical formalisms for the representation of uncertainty usually describe states of knowledge in terms of possible states of the world roE n. These states ro are supposed to be mutually exclusive and usually Q is assumed to gather all the possible states of the world. Both in probability theory and in possibility theory, to each state ro is attached a degree d(ro)E [0,1] which estimates the extent to which ro may represent the real state of the world. These states can be put in correspondence with the models used in logical formalisms. By convention, d(ro)=O means that we are completely certain that ro cannot be the real state of the world. But the meaning of d(ro)= 1 is completely different in probability theory where it means that ro is the real state (complete knowledge), and in possibility theory where it only expresses that nothing prevents ro from being the real state of the world.

In these two formalisms, the change of the current state of knowledge (called 'epistemic state' in the following), upon the arrival of a new information stating that the real world is in A~Q corresponds to a modification of the assignment function d into a new assignment d'. This change should obey general principles which guarantee that i) d' is of the same nature as d (preservation of the representation principles); ii) A, which denotes 'not A', is excluded by d', i.e., \iroe: A, d'(ro)=O (what is observed is held as certain after the revision or the updating); iii) some informational distance between d' and d is minimized (principle of minimal change). Counterparts to these principles are also at the basis of revision and updating in logical formalisms [12].

The probabilistic framework offers at least two ways of modifying a probability distribution upon the arrival of a new and certain information: the Bayesian conditioning, but also D. Lewis [21]'s 'imaging' which consists in translating the weights originally on models outside A to models which are their closest neighbours in A. This paper shows that the existence of these two modes, which can be also defined in the possibilistic framework, is analogous to the distinction between belief revision based on Alchourr6n, Gfu"denfors and Makinson (AGM) postulates [12] and updating based on Katsuno and Mendelzon [18]' postulates.

The paper is organized in three main parts. The next section surveys basic results on probabilistic conditioning and imaging. Section 3 introduces these two operations in the possibilistic framework and provides new results and justifications for them. Section 4 briefly considers belief and plausibility functions and then emphasizes the existence of a third operation, called 'focusing', in this setting.

2 The Probabilistic Framework

In this setting, an epistemic state is represented by a probability measure P on the set Q of possible worlds, (assumed finite for simplicity), such that

\i A,B!;;Q, AnB:t0::::) P(AuB)=P(A)+P(B). Complete knowledge is represented by P((00()})=1 for some roo. An epistemic state is characterized by the distribution {p(ro),(t)E Q} from which P(A)=I.<OE A p(ro) can be computed.

2.1 Probabilistic Conditioning

Upon learning that event A has occurred, i.e. we are certain that A is true, the a priori epistemic state P is revised by Bayes theorem into the conditional probability

P(BIA)=P(BnA)/p(A)=P(AIB)·P(B)/p(A) (1) where P(B) is changed into P(BIA). It is not defined if A is a priori judged to be impossible. Minimal requirements are satisfied by (1); namely i) P(AIA)=1, when P(A)>O (priority to the input information); ii) P(A)=1::::)P(·IA)=P (an already known input information does not modify the epistemic state). This form of revision via a scaling factor is not so natural (except if one considers that P(BIA) should be a relative frequency) and needs some justification. Several exist.

- Numerical justifications: (1) is the only possibility if for any B,C~A. P(BIA)/P(CIA) should be equal to P(B)/P(C), i.e. there is no relative change. Another justification is given in [12] where conditioning is proved to be the only rule such that:

AnA'=0::::) P(BIAuA )=AP(BIA)+(l-A.)P(BIA') (2) where A.=P(A)/P(AuA')=P(A)/(P(A)+P(A')). This result assumes that P(AIA)=1, and P(·l!l)=P.

- Al11;ebraic justification: Cox [1] and his followers (e.g. [14]) have proved that Bayes rule, as well as probability theory itself can be justified through consistency between the Boolean structure of the subsets of Q and three simple axioms for the measure of uncertainty g, and the conditioned one g(·IA), i.e. (A is the complement of A)

1. g(BnA) = f(g(BIA),g(A)); b) g(A)=s(g(A)), VAdl;
2. f is a continuous strictly monotonic function in both places; s is a continuous, strictly decreasing function.

Then g should be a probability measure and f the product. This is more a justification of conditional probability than of revision itself. See [14) for a Coxian-like justification of conditional probability as actually performing a revision.

- Information-theoretic justification: the information content of a probabilistic epistemic state is Shannon entropy S(P)=-Lroe 0 p(ro)Logp(ro). The less ambiguous P, the smaller S(P); particularly S(P)=O if Pis a complete episte­ mic state and S(P) is maximal iff p(ro)=p(ro'), Vro, ro'e 0.. Kulback & Leibler' informational distance is then defined by

The conditional probability P'=P(·IA) minimizes I(P,P') under the constraint P'(A)=1, see [29).

Note that the understanding of Bayesian conditioning as a revision process (as above) is challenged by many Bayesians who view conditioning as a mere change of reference class reflecting the available evidence, i.e. a "focusing process". However because of the existence of a single conditioning rule, there is no way to distinguish between both views.

2. 2 Probabilistic Imaging

Another path in the problem of updating probabilities is the one followed by Lewis [21]. Assume that 0. is such that for any world roe 0., and for any set A~n. 3ro A such that ro A is the closest world from ro, that belongs to A. Then the principle of minimal change can be expressed as an advice to move probability weights as little as possible away from the worlds that become impossible upon learning that some event Ad} has occurred. This is formally expressed as

This rule is called 'imaging' because p A is the image of p on A obtained by moving the masses p( ro) for roE A to ro A e A, with the natural convention that ro A =ro if roe A. This rule comes from the study of conditional logics. It has been generalized by Gardenfors [12) to the case when the set of worlds in A closest to a given world ro contains more than one element. If A(ro)~A is the subset of closest worlds from ro, p(ro) can be shared among the various worlds ro'e A(ro) instead of being allocated to a unique world. Gllrdenfors has proved that general imaging is the only updating rule that is homomorphic, i.e. (P A is the measure based on p A)

It expresses invariance under convex combination. Imaging can turn imwssible worlds into possible ones, e.g. one may have p A ( ro A)>O while p( ro A)=O. As a consequence a sure fact B a priori, i.e. such that P(B)=1 may become uncertain, i.e. P A(B)<l. This is not the case with Bayesian conditio­ ning. However as with the Bayesian rule, P(A)=1=>P A=P.

2. 3 Illustrative Example (inspired by Morreau)

A box contains either an apple (a) or a banana (b). Let ro1, ffi2,ro3,ro4 denote the states where aAb is true, aA-,b is true, -,aAb is true, -,aA-,b is true respectively. Our epistemic state is represented by p(ro1)=p(ro4)=0, p(ro2)>0, p(ro3)>0. For instance p(ffi2)=0.7, p(ro3)=0.3, i.e. an apple is more probably present than a banana in the box. Upon the occurrence of A={ro3,ro4} (no apple) Bayes rule yields p(ro3IA)= 1; i.e. there is a banana in the box (Gardenfors' revision leads to the same result in the logical setting). Let us now apply Lewis' imaging. The closest "neighbour" of ro2 (E A) in A is w4 (both agree that b is false). Then moving p(w2) to W2A =ro4 (and ro 3 A= ro 3 since ro 3 is in A) gives the update PA(ro4)=0.7; PA(ro3)=0.3; i.e. the most probable situation is that the box is empty. This is in agreement with a reasoning by case: either the box was containing an apple or a banana; if the apple (if any) has been taken out of the box, either the box is now empty or there is still the banana. This agrees with Katsuno and Mendelzon [ 18]' approach to updating. In Bayes rule, A is understood as "there is no apple" (static world), while with imaging, A rather means "there is no longer any apple" (world change).

2.4 Uncertain Inputs

The Bayesian setting has been extended to the case of uncertain inputs. An uncertain piece of evidence corresponds to an event Ac;;;;O. along with a probability a that this event did happen. The updated probability measure P(BI(A,a)) can be computed using Jeffrey [17]'s rule as

where P(BIA) and P(BI A) are obtained by regular conditioning. In the case of a set of possible observations, one of which is the true one, which forms a partition {AJ, ... ,Anl ofO., (6) is extended into

where the probability that Ai is the actual observation is ai, with :Eai=l. In a strict Bayesian view of (6) and (7), ai is interpreted as a conditional probability P(AiiE) where E denotes the (sure) event underlying the uncertain information. Then (7) assumes that P(BIAi)=P(BIAinE), i.e. that for all Ai, E is independent of B in the context Ai (e.g. [23)). (6) and (7) have been justified by Williams [29] on the basis of the distance I(P ,P') under the constraints P'(Ai)=ai.

(7) can be also justified at the formal level by the fact that the only way of combining the conditional probabilities P(B IAi) in an eventwise manner (i.e. using the same combination law for all events B) is to use a linear weighted combination such as (7) [19]. Lastly, pushing (7) to the limit by assuming 0.= { ro 1·· .. ,Wn} and choosing the finest partition Ai={roi}, and then letting ai=P2({wj}), Jeffrey's rule (7) comes down to a simple substitution of P1 by P2. The new piece of evidence totally destroys the epistemic state. Priority is given to the new information.

3 The Possibilistic Framework

A possibility distribution 1t is a mapping from 0. to a totally ordered set V containing a greatest element (denoted 1) and a least element (denoted 0), e.g. V=[0,1]. However any finite, or infinite and bounded, chain will do as well. A consistent epistemic state 1t is such that 1t(ro)=1 for some ro, i.e. at least one of the worlds is considered as completely possible in n. Let 1t and 1t' be two possibility distributions on n describing epistemic states. If ~1t', 1t is said to be more specific than 1t' [30], i.e. the epistemic state described by 1t is more complete, contains more information than the one described by 1t'. If 3rooe n, 1t(roo)=1, and 1t(ro)=0 for W*WO, 7t corresponds to a complete epistemic state.

Interpreted in this framework, the three basic forms of belief dynamics described in [I2], namely expansion, contraction and revision can easily be depicted. The result of an expansion, that stems from receiving new information consistent with a previously available epistemic state described by 1t, is another possibility distribution 7t' that is more specific than 7t. Note that 7t', by definition, is also such that 7t'(w)= I. Hence if we let C(7t)= { wl7t(W)=I} be the core of 1t (i.e. the set of preferred worlds in a given epistemic state), we have C(7t')*0 and C(7t')~C(7t). A contraction, i.e. the result of forgetting some piece of information among those that form an epistemic state, will be expressed by going from 1t to a less specific possibility distribution 7t'~. The term revision will be interpreted as any other belief change which is neither a contraction nor an expansion. Namely, it is when from 7t, we reach 7t' where neither 1t~' nor 1t'~1t hold. More specifically we may speak of "strict" revision when C(7t)nC(7t')=0.

Similarly to the probabilistic case, a possibility distribution generates a set function n called a possibility measure [3I] defined by (for simplicity V=[O,I])

and satisfying Il(AuB) = max(Il(A),Il(B)) as a basic axiom. Il(A) evaluates to what extent the subset A of possible worlds is consistent with the epistemic state 7t. Il(A)=O indicates that A is impossible. Il(A)=I only means that A is consistent with 1t, and it may happen that Il(A)=O(A)=I (A is the complement of A), in which case, it expresses ignorance about A. The degree of certainty of A is measured by means of the necessity function N(A)=I-Il(A), whose characteristic axiom is N(AnB)=min(N(A),N(B)). A is considered as a sure fact in an epistemic state 1t whenever N(A)=l. If S(7t) is the support {wl7t(W)>O} of 1t, then N(A)=I(:=>S(7t}kA, while N(A)>O(:=>C(7t)t;;;;;A (!l finite) means that A is credible.

3.1 Possibilistic Conditioning

If the new information A is such that Il(A)= I, i.e. A is consistent with the epistemic state 1t, 1t is expanded into 1t'

where llA is the characteristic function of the subset A. When Il(A)*I, 1t is revised into 1t' defined through conditionalization. Revision in possibility theory is performed by means of a conditioning device similar to the probabilistic one, obeying an equation of the form [15]

VB, O(AnB)=O(BIA)*Il(A), ifil(A)>O. (10) Possible choices for* are min and the product [4]. In case of *=min, choosing the least specific solution (i.e. the solution with the greatest possibility degrees in agreement with the constraint (10)) yields,

In particular Il(BIA)=O if AnB=0. The conditional necessity function is defined by N(BIA)=I-Il(BIA), by duality. The possibility distribution underlying the conditional possibility measure Il(-IA) is defined by

7t(WIA) = 0 if w~ A; 7t(WIA) = I if 7t(W)=Il(A), WE A ;

provided that Il(A)*0. This is Dempster rule of conditioning, specialized to possibility measures, i.e. consonant plausibility measures of Shafer [25]. The corresponding revised possibility distribution is

7t(wlA)=7t(w)/Jl(A), VWE A ; 7t(WIA)=O otherwise. (I3) This rule is much closer to Bayesian conditioning than the ordinal rule (II) which is purely based on comparing numbers; (12) requires more of the structure of the unit interval (a product operation). In both cases the set function itself remains ordering-based. (I2) makes sense if n is a continuous universe, if 7t is continuous and revision is required to preserve continuity. Both (II) and (13) satisfy

• N(A)=I=>7t(·IA)=7t (no revision if A was already certain)
• Il(A)=I=>7t(·IA)=min(llA,7t)=7t+ A (revision=expansion in case of consistency)
• N(AIA)=I (priority to the new information).

Counterparts of the other AGM [I2] postulates for revision hold as well with the two definitions; see [9] for a detailed study of the possibilistic counterparts of expansion, revision, and contraction. Especially (II) embodies a principle of minimal change. If 1t and 1t' define two real­ valued possibility distributions on a finite n then the Hamming distance between 7t and 1t' is defined by H(7t,7t')= LO>E n 17t( w )-7t'( w )I. Then we have the following result [9]: 7t(·IA) is the possibility distribution the closest to 7t that complies with counterparts of Gardenfors' postulates, as long as there is a single world WA where 7t(WA)=Il(A). H(7t;7t(·IA)) is thus minimal under the constraint N(AIA)=l.

It is worth noticing that the revision rule (II) satisfies the counterpart of (2) for probabilistic conditioning with respect to the disjunction. It can be checked that

Il(BIAuA ')=max(min(a,Il(BIA)),min(a',Il(BIA')) (I4) with a=Il(A')~Il(A) and a'=Il(A)~Il(A') where~ is the multiple-valued implication a~b=I if~ and b otherwise. The function from [0,I]2 to [O,I] defined by Ma,a·(x,y)= max(min(a,x),min(a',y)), where max(a,a')=I is the possibilistic counterpart of the weighted arithmetic mean (or convex mixture) in probability theory. Condition max(a,a')=I is indeed verified in (I4). The behavior of the product-based definitions of Il(BIA) with respect to a disjunction of input is similar to the min-based definition: (I4) remains true when AnA'=0 provided that we define a= Il(A')~Il(A) and a'=Il(A)~Il(A') with the implication a~b=min( I ,bla) and min is changed into product.

While (13) looks as a more natural counterpart of probabilistic conditioning, N(BIA) stemming from (II) is more closely akin to the concept of "would counterfactual" following Lewis [20], and denoted Ao~B. which is intended to mean "if it were the case that A, then it would be the case that B". Lewis proposes to consider Ao~B as true in world w if and only if some accessible world in A n B is closer to w than any world in An B, if there are worlds in A. Let us interpret "closer to world w" as "preferred" in the sense of possibility degrees (w thus denote the "ideal world"). Let us notice that we do have when Il(A)>O,

VB,BnA~,N(BIA)>O (:=> Il(BnA)>Il(DnA) (15) where N(-IA) is the necessity measure based on 7t(·IA). The latter inequality means that there is a world in B n A which is more possible than any world in IJnA. Hence N(BIA)>O agrees with the truth of Ao~B. The counterpart of Lewis'

"might conditional" AO~B is of course O(BIA) in the sense of (10) with *=min.

3. 2 Possibilistic Imaging

It is easy to envisage the possibilistic counterpart to Lewis' imaging since this type of belief change is based on mapping each possible world to the closest one that accomodates the input information. As in Sec. 2, define for any roe n, and non-empty set A~n the closest world ro A E A to ro. Then the image of an epistemic state 1t in A is 7t 0 A (ro')=maxro'=roA x(ro) if ro'e A; 7t 0 A (ro')=O if ro'!i!: A.(16) If there is more than one world ro A closest to ro, then the weight x(ro) can be allocated to each of the closest worlds, forming the set A(ro), and the above updating rule becomes 7t 0 A (ro') = maxro x(ro) if ro'e A; 7t 0 A (ro')=O if ro'!i!: A. (17) ro'e A(ro)

If we define R A as the relation that to each ro assigns its closest neighbours in A, the above update formula is nothing but Zadeh [31]'s extension principle that characterizes the fuzzy image of the fuzzy set whose membership function is 1t, via relation RA.

It is easy to check that the updating rule (16) satisfies all postulates of Katsuno and Mendelson [18]'s updates namely:

• U3) if A~ and 1t is normalized then 7t 0 A is normalized ;
• U4) A=B=>7toA=1toB ; US) min(xoA,JlB):S1toAnB;
• U6) 1to A:SJ!B, 1t 0 B$A=>1to A=1t 0 B;
• U7) 1t maximally specific=> min(7t 0 A,1t 0 B):S7t 0 AuB ;
• US) [max(x,x'W A= max(1t 0 A·1t' 0 A)·

Defining A(ro) precisely as (ro'lx(ro')=O(A)=max(x(ro), roe A}} then 7t 0 A=7t(·IA), i.e. we recover the revision based on conditioning. Clearly in this setting, we see that Katsuno and Mendelzon's approach subsumes the AGM framework. In the setting of possibility theory, the difference between Katsuno and Mendelson framework and the AGM approach are patent. While the AGM approach tries to use the input information so as to reduce incompleteness, the update view tries to carry the incompleteness of the epistemic state to a new epistemic state that agrees with the input information, assuming that the shift of the "real world" is minimal.

When A( ro) is a fuzzy subset of A, (17) reads

7t 0 A (ro')=maxro x(ro)*llA( ro)(ro') if ro'e A; 7t 0 A (ro')=O if ro'E A where ·=min or product; we have to assume JlRA (ro,ro')=l if ro=ro'e Supp(A)= (roe A,JlA (ro)>O}, and 0 if ro'E Supp(A). It can be easily checked that this updating is invariant under weighted max-combination, i.e., the counterpart of (5) reads:

[maxi (Aj*1ti)] 0 A=maxi A;*(1ti) 0 A with maxi Ai=l. Clearly U8 is a particular case of this invariance under max­

weighted combination.

The possibilistic framework would enable us to deal with the apple and banana example in a way similar to the probabilistic solution, although in a more qualitative way. The example is really too elementary to exhibit significant differences between the two approaches.

3. 3 Uncertain Inputs

Belief change can be extended to uncertain inputs of the form N(A)=ex. The main question here is how to interpret such an uncertain input. Two interpretations make sense [9]:

1. N(A)=ex is taken as a constraint that the new epistemic state must satisfy; it means that if x' is obtained by revising 1t with information (A,ex), the resulting necessity measure N' must be such that N'(A)=ex;
2. ii) N(A)=ex is interpreted as an extra piece of information that may be useful or not useful to refine the current epistemic state; in that case ex is viewed as a degree of reliability or priority of information A.

Interpretation i) is in the spirit of Jeffrey's rule. Clearly N(A)= 1 will lead to an expansion of 1t into x+ A or a revision x(·IA), while N(A)=O will force a contraction. In contrast, ii) corresponds to either a revision or an expansion but is never a contraction, since if ex is too low, the input information will be discarded.

The input information is not modelled in the same way whether it is a constraint or an additional information. In the first case (i), N(A)=ex is interpreted as O(A)=l and 0(A)= l-ex, and the belief change rule is of the form [9]

where *=min or product according to whether x(roiA) is the ordinal or Bayesian-like revised possibility distribution. Note that when ex=l, x(roi(A,ex))=x(roiA), but when ex=O, we obtain a possibility distribution less specific than 1t such that the associated necessity of A is zero.

In the second case (ii), the additional information N(A)=a is represented by a fuzzy set F with membership function llF

Letting FA.= { roiJlF( ro )~A.}, each FA. is viewed as the (non­ fuzzy) regular input information underlying F, with guaranteed possibility A. and the revised epistemic state x(-IF) is defined by analogy with Jeffrey's rule as [6]

where the convex mixing is changed into the weighted maximum and * is min or product again. In our particular case, it gives, for a>O

x(roiF)=x(roiA) if roe A; x(roiF)=x(ro)·(l-ex) if roe A.(l9) Note that x( roiF):SJlF=max(Jl A, l-ex); moreover x( rolF)= 1t( ro) if ex=O since then F=il, i.e. the operation is never a contraction. This behavior is very different from the case when N(A) = a is taken as a constraint.

The first revision rule (18) under uncertain inputs can be extended to a set of constraints O(Ai)=A.i, i=l,n, where {Ai,i=l,n} forms a partition of Q, and it gives

where *=minimum or product whether x(roiAi) is ordinal or Bayesian-like. In the limit case when Ai={roi}, Vi, the input is equivalent to a fuzzy input F with JlF(roi)=Ai· The above belief change rule reduces to a simple substitution of 1t by JlF, just as for Jeffrey's rule for probabilities.

To conclude, while the belief change rule (19) is formally analogous to Jeffrey's rule, its behavior is very much akin to a revision a Ia Gardenfors. See Section 3.4. On the contrary the other rule (18)-(20) is very close to the spirit of Jeffrey's rule, and has been proposed in another setting by Spohn [27] who uses the integers as a scale rather than ·[0, 1] with the convention that 0 corresponds to the minimum impossibility (i.e. the maximal possibility), see [6].

3. 4 Epistemic States as Weighted Propositions The set of possible worlds in which a possibilistic logic for­ mula (<p a) is true is the fuzzy set [<p a] on n given by [7]

ll[<p a](W) = 1 if WE [<p] ; ll[<p aJ(W) = 1-a otherwise ; ([ <p] is the set of possible worlds where <p is true); ll[ <p a] is the least specific possibility distribution 1t such that N([<p])= inf roe: [ q>] 1-1t( w )~a. The fuzzy set of worlds which satisfy a possibilistic knowledge base K={(<pi,ai),i=1,m} is defined by the possibility distribution 1tK

VroEO, 1tK(W)=mini=l,m max(ll[<piJ(w),1-ai) (21) which extends [K]=[<p!ln[<p2]n ... n[<pnl from a set of sentences to a set of weighted sentences. Semantic entailment is defined in terms of specificity ordering (1ts;1t'). Namely Kl=(<p a) if and only if 1tKs;max(ll[<p]· 1-a). This notion of semantic entailment is exactly the one of Zadeh [31] . Note that here each possibilistic formula is viewed as an additional piece of information. Indeed min(1t, max(ll[<p]·1-a))<1t only if (<p,a) brings information not de­ ducible from 1t. These definitions make sense for consistent possibilistic knowledge bases, i.e. such that 1tK(W)=1 for some WEn. Consistency of K is equivalent to the consis­ tency of the classical knowledge base K* obtained by remo­ ving the weights. When maxcoe n 1t(W)=l<l, K is said to be partially inconsistent, l being the degree of consistency of K, i.e. inc(K)=1-l. It l=O, K is completely inconsistent.

Let us consider the case when K is consistent but K'=Ku{(<p 1)} is not, and let a=inc(Ku{(<p 1)})>0. The following identity is proved in [7]:

Ku{ (<p 1) }f--('1' P> with P>a if and only if N('lfl<p)>O where N('lfl<p) is the necessity measure induced from 1t(·l[<p]) the possibility distribution expressing the content of K, revised with respect to the set of models of <p. Indeed let 1t' be the possibility distribution on n induced by K' then

1t'=min(1tK,Il[<p]) and O<maxcoen 1t'(w)=1-a<l. The possibility distribution 1t' induced from the consistent part of K' made of sentences whose weights is higher than a, is defined as 1t'(w) = 1t(W) if (J)E [<p) and 1t'(ro)<1-a = 1 if roE [ <p] and 1t( w )= 1-a = 1t'(ro)=O otherwise.

Hence n'=1t( ·I [ <p ]), the result of revising 1t by [<p ]. The corresponding revision is rather drastic since all sentences ( <i'i ai) with weights ais;a are thrown away, and replaced by (<p 1). Note that when TI(<p)>O, N('lfl<p)>O is equivalent to N(-.<pv'lf)>N(-.<pv-.'lf), or equivalently in terms of the associate epistemic entrenchment >c: -.<pv'lf >c -.<pv-,'1' [5], and corresponds to a characteristic condition for having 'I' in the (ordered) belief set obtained by revising the deductive closure of K by <p, in the sense of Gardenfors [12].

4 Revision, Updating and Focusing

Let us now consider Shafer's evidence theory [25][26]. The set of possible worlds is called frame of discernment. In this framework the available knowledge is represented in terms of a basic probability assignment m, which is a set function from the set of subsets 2n to [0,1] with the constraints m(0)=0 and LA m(A)= 1. The subsets A~::n such that m(A)>O are called focal elements. Note that there is no cons­ traint on the structure of the set fF of focal elements (here supposed to be finite and which does not make a partition in general). Each focal element Ai represents the most accurate description, with certainty m(Ai), of the available evidence pertaining to the location of the actual world in n. The sub­ sets Ai are the possible realizations of an imprecise observa­ tion pervaded with uncertainty. Due to the incompleteness of the available information, Ai is not necessarily a singleton. A plausibility function PI and a belief function Bel are bijectively associated with m [25] and are defined by

Dempster rule of conditioning is expressed by

PI(BIA) = Pl(AnB)h>J.(A); Bel(BIA) = 1-Pl(BIA) (24) This rule of conditioning can be justified on the basis of Cox's axiom that defines a conditional function associated to any uncertainty measure g defined on n as in Sec. 2 [4]. Cox's axiom justifies Dempster's conditioning rule as well as the geometric rule of conditioning [28]

Belg(BIA)=Bel(A n B)IBel(A); Plg(BIA)=1-Belg(BIA) (25) In terms of basic probability assignments, PI(-lA) defined by (25) is obtained by transferring all masses m(B) over to AnB, followed by a normalization step, while Belg(·IA) is obtained by letting mg(BIA)=m(B) if B~:;A and 0 otherwise, followed by normalization, i.e. a more drastic way of conditioning. Dempster's role of conditioning looks more attractive from the point of view of updating since Pl(BIA) is undefined only if Pl(A)=O (i.e. A is impossible) while Belg(BIA) is undefined as soon as Bel(A)=O (i.e. A is unknown). This unability to revise with a vacuous prior is counterintuitive, with the geometric rule.

Dempster rule of conditioning is a mixture of AGM-type expansion (when m(B) carries over to AnB if A becomes true) and Bayesian updating. On the contrary, the geometric rule has nothing to do with an expansion on n and is more in the spirit of imaging since all masses outside A are moved inside. Dempster rule of conditioning subsumes conditional possibility based on product, i.e. (12).

Another approach to conditioning has been proposed by De Campos et al. [3] and Fagin and Halpern [11] under the form

P·(BIA) = Bel{AnB)/Bel(AnB)+Pl(AnB) (27) These definitions can be justified by interpreting belief and plausibility functions as lower and upper probabilities, since it has been proved that

where g>(Bel)={PIBel(B)~B)s;Pl(B),VB}. These conditional functions are actually upper and lower conditional probabilities and have been considered by Dempster [2] himself and Ruspini [24]. P·(·IA) has been proved to be still a belief function [11][16). Although very satisfying from a probabilistic point of view, these definitions lead to a rather uninformative conditioning process since P*(·IA)~l(·IA)~ Bel(·IA)~P.(·IA) as noticed by Dempster [2). Especially, complete ignorance is obtained (P*(BIA)=1,P·(BIA)=0) as soon as Bel( An B)=O and Bel(AnB)=O, i.e. as soon as the conditioning set A intersects each focal element without including any one of them, thus making all focal elements smaller. In that case the revising process would correspond to oblivion rather than learning. It has been shown elsewere that (28)-(29) is not a rule for revision but a "focusing rule", by which one only changes the reference class, without forcing P( A)=O [8]. Especially (28)-(29) does not modify the constraints specified by the belief function. Dempster rule of conditioning comes down to add the constraint P(A)= 1 to the set g>(Bel), in the case when Pl(A)=l, i.e. A is viewed as a new piece of information to be integrated in the current knowledge, and leads to a revision, and not only a change of reference class. When Pl(A)~l. the constraint P(A)=Pl(A) can be added to the set of constraints in (28)-(29), and the upper conditional probability thus obtained corresponds to Dempster rule in the general case, as proved by Gilboa and Schmeidler [13], who call it maximum likelihood revision. A more refined proposal can be found in [22] where the distributions which do not maximize P(A) are also somewhat taken into account.

5 Conclusion

This paper has emphasized that belief revision in the sense of Gardenfors, as well as updating in the sense of Katsuno and Mendelzon can be defined through conditioning and imaging respectively both in the probabilistic and in the possibilistic settings. The possibilistic framework leads to a more complete agreement with the two sets of postulates (first stated for propositional logic) than the probabilistic setting. The paper also has tried to relate the revision of a possibility distribution on a set of possible worlds to the revision of a knowledge base made of uncertain logical formulas. More work is needed to relate probabilistic rules to the axiomatic approaches to belief change in the logical framework, despite the existing bridges between probability and possibility theories. Namely we might consider devising revision and updating rules in logics of uncertainty different from possibilistic logic, and especially probabilistic logic. Indeed while the problem of change has been thoroughly studied for probabilistic representations of epistemic states on a set of possible worlds, nothing has been done at the syntactic level. Besides the justification of the different rules in evidence theory is in its infancy. The idea of focusing, i.e. changing the reference class as opposed to revising a body of knowledge might be · worth introducing in the logical setting also.

The coherence between numerical versus symbolic approa­ ches to knowledge representation is still present in the revi­ sing and updating problems. Pushing further the conse­ quences of such a coherence looks like a challenging task.

The reader is referred to a more complete version of this paper for further discussions and proofs [10].

Acknowledgements: This work has been partially supported by the European ESPRIT Basic Research Action n° 6156 entitled "Defeasible Reasoning and Uncertainty Management Systems (DRUMS-2)".