An Approach to Qualitative Belief Change Modulo Ontic Strength

Abstract

Sometimes, strictly choosing between belief revision and belief update is inadequate in a dynamical, uncertain environment. Boutilier combined the two notions to allow updates in response to external changes to inform an agent about its prior beliefs. His approach is based on ranking functions. Rens proposed a new method to trade off probabilistic revision and update, in proportion to the agent's confidence for whether to revise or update. In this paper, we translate Rens's approach from a probabilistic setting to a setting with ranking functions. Given the translation, we are able to compare Boutilier's and Rens's approaches. We found that Rens's approach is an extension of Boutilier's.

-

Traditionally, belief revision is regarded as change of beliefs about the objective static state of the world. And belief update is regarded as change of beliefs due to recording the change which occurred in the underlying state of the world. We shall use the generic term belief change to including belief update and belief revision. An agent may not always be certain whether an observation is a side-effect of an action/event (requiring update), or whether the observation did not have a physical cause and is thus pure information (requiring revision).

Boutilier [ 3 ] proposed a generalized qualitative update procedure, which combines both belief update and revision. He used ranking functions as advocated by Spohn [ 13, 14 ] to capture notions of preference. Rens [ 11 ] proposed a quantitative approach to mix probabilistic belief update and revision, where the trade-off is controlled by the so-called ontic strength of the observation received. To our knowledge, his “mixture” method is novel. In this paper, we propose a translation of Rens’s method back to a qualitative setting using Spohn-rankings. The difference in the present approach to that of Boutilier is that ours trades belief update and revision off in proportion to the agent’s judgement of the ontic strength of the received evidence.

There are several reason why we would like a qualitative version of Rens’s hybrid stochastic belief change (HSBC).

Ordering preferred worlds by ranking them instead of providing exact probabilities may be more intuitive for agent designers. Some domains may not require the agent to work with precise values like probabilities, and computations over ranked preferences are then cheaper, because finding the minimum of a set is generally cheaper than finding its sum (the distinction between minimization and summation will become clear later). We may gain insights about the relationship between belief revision and belief update when analysed in the qualitative belief change setting.

Let L be the classical propositional language, and W the (finite) set of possible worlds (valuations) induced from a finite set of propositional variables. We denote the models of a sentence 2 L by J K and the fact that w satisfied by w . For a set of sentences K L, JKK := fw 2 W j 8 2 K; w g. We refer to a probability function or a ranking function as an epistemic state. In this paper, we denote the result of a belief change operation as , where is an epistemic state and is the operator. If we need to refer to the value of a particular world w in the changed epistemic state, we write (w).

Next, we review the essentials of Rens’s HSBC construction. In Section 3, we provide the qualitative, rank-based translation of HSBC (i.e., HQBC). We analyse our HQBC with respect to two fundamental classical rationality postulates in Section 4. In Section 5, we compare our hybrid qualitative belief change construction to Boutilier’s generalized update construction. Two examples are presented in Section 6, and we end the paper with a summary of what has been achieved here, and a discussion about related and future work. 2

Hybrid Belief Change via Probability Theory Rens [ 11 ] proposed the hybrid stochastic belief change (HSBC) operation to combine notions of probabilistic belief revision and probabilistic belief update. HSBC may be employed in agents who deal with uncertainty by maintaining a probability distribution b over possible worlds w they could be in. That is, b : W ! [0; 1], such that Pw2W b(w) = 1, and b( ) := Pw2W;w b(w) for all 2 L. b will often be represented as a set of pairs f(w; p) j w 2 W; p 2 [0; 1]g. We refer to b as an epistemic state in the context of this work. In the HSBC framework, an agent maintains an epistemic state, which changes as new information is received or observed.

Rens [11] proposes the tuple hW; Evt ; T ; E; O; osi to formalize

the HSBC framework, where

W is a set of possible worlds; Evt is a set of atomic events; T : W Evt W ! [0; 1] is a transition function such that for every e 2 Evt and w 2 W , Pw02W T (w; e; w0) = 1, and T (w; e; w0) models the probability of a transition to world w0, given the occurrence of event e in world w; E is the event function such that E(e; w) = P (e j w), the probability of the occurrence of event e in w; O : L W ! [0; 1] is an observation function such that for every world w, P 2 O( ; w) = 1, and O( ; w) models the probability of observing in w, where L is the set of possible observations, up to equivalence, and where if , then O( ; w) = O( ; w), for all worlds w;3 os : W ! [0; 1] such that os( ; w) is the agent’s ontic strength for perceived in w.

In HSBC, the epistemic state updated with defined as (denoted b ) is b := (w0; p0) j w0 2 W; p0 = where is a normalizing factor.

It is mostly agreed upon that Bayesian conditioning corresponds to classical belief expansion. This is evidenced by Bayesian conditioning (BC) being defined only when b( ) 6= 0 (i.e., when does not contradict the agent’s current beliefs). In other words, one could define revision to be b BC

:= f(w; p) j w 2 W; p = P (w j )g; as long as P ( ) 6= 0, where

P (w j ) := Pw02W O( ; w0)b(w0) :4 O( ; w)b(w) (1)

To accommodate cases where b( ) = 0, that is, where contradicts the agent’s current beliefs and its beliefs need to be revised in the stronger sense, we shall make use of imaging. Imaging was introduced by Lewis [ 9 ] as a means of revising a probability function. Informally, Lewis’s original solution for accommodating contradicting evidence is to move the probability of each world to its closest, -world. Lewis made the strong assumption that every world has a unique closest -world. More general versions of imaging allow worlds to have several, equally proximate closest worlds.

In two papers, Rens [ 11 ] and colleagues [ 12 ] propose generalized imaging: Let Min( ; w; d) be the set of -worlds closest to w measured with d, some acceptable measure of distance between worlds (e.g., Hamming or Dalal distance). Formally, Min( ; w; d) := fw0 2 J K j 8w00 2 J K; d(w; w0) d(w; w00)g: Then generalized imaging (denoted GI) is defined as b GI :=

else p = (w; p) jw 2 W; p = 0 if w 62 J K;

X w02W w2Min( ;w0;d) b(w0)=jMin( ; w0; d)j :

Rens [ 11 ] argues that if observation likelihoods are known, they should be used to weight the probabilities computed by the GI operation; a new imaging operation is thus defined as b OGI := n(w; p) j w 2 W; p = Pw02W O( ; w0)bGI(w0) O( ; w)bGI(w) o; where the denominator is a normalizing factor. At last, with respect to revision, Rens [ 11 ] defines BCI to revise by conditioning when the 3 denotes logical equivalence. 4 Note that b( ) is equivalent to P ( ). evidence does not contradict the agent’s current beliefs, and to revise by imaging otherwise: b BCI := b BC b OGI if b( ) > 0 if b( ) = 0

Finally, Rens [ 11 ] proposes a way of trading off the probabilistic update and probabilistic revision, using the notion of ontic strength. He argues that an agent could reason with a range of degrees for information being ontic (the effect of a physical action or occurrence) or epistemic (purely informative). It is assumed that the higher the information’s degree of being ontic, the lower the epistemic status of that information. “An agent has a certain sense of the degree to which a piece of received information is due to a physical action or event in the world. This sense may come about due to a combination of sensor readings and reasoning. If the agent performs an action and a change in the local environment matches the expected effect of the action, it can be quite certain that the effect is ontic information,” [11, p. 129].

os( ; w) is defined to equal 1 when is certainly ontic in w, and 0 when is certainly epistemic (the epistemic strength of in w is es( ; w) := 1 os( ; w)).

The hybrid stochastic change of epistemic state b due to new information with ontic strength (denoted b ) is defined as b := n(w; p) j w 2 W; p = 1 0

es( ; w)bBCI(w) + os( ; w)b (w) o; where 0 is a normalizing factor so that Pw2W b (w) = 1. 3

Hybrid Belief Change via Ranking Theory Let be a ranking on worlds in W , representing the agent’s current epistemic state, as first proposed by Spohn [ 13 ]. That is, : W ! N [ f1g, where N = f0; 1; 2; : : :g, such that there exists a w 2 W for which (w) = 0 and (wi) (wj ) is interpreted as world wi being at least as plausible or preferred as world wj .

(w ) = 1 is meant to indicate that w is impossible, implausible, least preferred. Worlds w0 for which (w0) = 0 are considered most plausible, most preferred, or believed. In fact, ranking functions are rankings of implausibility. The degree of plausibility of proposition is ( ) :=

min w2W;w f (w)g: (2) We shall denote an agent’s belief set, given epistemic state , as Bel ( ) := f 2 L j 1(0)

J Kg:

Since Spohn’s ranking functions can be considered as the logarithm of probabilities [ 7 ], when translating from probability theory to Spohn ranking theory, multiplication becomes addition, division becomes subtraction, and summation (Pw2W ) becomes minimization (minw2W ).

Conditional plausibility is defined as [ 13 ] ( j ) := ( ^ ) ( ): Let w be a complete theory for w. It will be useful to know that ( ^ ) = ( j ) + ( ). And consequently, that ( ) = minw2W f ( j w) + (w)g. One can also define (w j ) in terms of ( j w) as follows.

(w j ) = = ( w ^

) ( j w) + (w) ( ) ( ): A direct translation of the Bayes Rule would suggest that the above result is analogous to that rule.

Definition 1. The tuple hW; Evt ; TQ; EQ; OQ; osi is a hybrid qualitative belief change (HQBC) model, where

W is a set of possible worlds; Evt is a set of atomic events;

TQ : W Evt W ! N [ f1g is a transition ranking such that

for every w 2 W and e 2 Evt , minw02W fTQ(w; e; w0)g = 0 and TQ(w; e; w0) models the plausibility of a transition to world w0, given the occurrence of event e in world w; EQ : Evt W ! N [ f1g is the event ranking such that for every w 2 W , mine2Evt fEQ(e; w)g = 0 and EQ(e; w) models the plausibility of the occurrence of event e in w;

OQ : L W ! N [ f1g is an observation ranking such that for

every world w, min 2LfO( ; w)g = 0 and OQ( ; w) models the plausibility of observing in w and where if , then 5 6 OQ( ; w) = OQ( ; w), for all worlds w ; os : L W ! N, where os( ; w) is the agent’s ontic strength for perceived in w (note that os is not a -function).

In the qualitative version of the hybrid belief change framework, epistemic strength is defined as the complement of ontic strength. Unfortunately, the notion of complement is not strictly defined for ranking theory. We thus define epistemic strength as the complement of ontic strength with respect to a ‘top’ value.

Definition 2. Let be an even number in N, but do not let Epistemic strength is defined as the -complement of os. = 1. es( ; w) := os( ; w): for all possible observations

and for all worlds w 2 W .

To specify that the agent has no preference for an observation being ontic or epistemic, choose os( ; w) = =2 for all w. Then es( ; w) = =2 for all w.7

Let be regarded as an agent’s epistemic state and a new piece of information to be accommodated. We can define the operation which revises an epistemic state using conditional plausibility: CP

=: f(w; n) j w 2 W; n = Q(w j )g; as long as ( ) 6= 1, where

Q(w j ) := OQ( ; w) + (w) min fOQ( ; w0) + (w0)g w02W is justified by the translation of P (w j ) (Eq. 1) from probability theory to ranking theory. The definition of Q(w j ) can also be derived from first principles, which we leave out here.

As with probabilistic conditionalization, plausibilistic conditionalization is undefined when the evidence/observation is inconsistent with the agent’s current epistemic state. A plausibilistic version of imaging can deal with this problem in the qualitative setting: Translate b GI to

GI := n(w; n) j w 2 W; n = 1 if w 62 J K; else n = min w02W w2Min( ;w0;d)

o f (w0)g : 5 denotes logical equivalence. 6 denotes logical equivalence. 7 Due to being even, =2 is guaranteed to be a whole number. Example 1. Let the vocabulary be fq; r; sg and the current epistemic state 1 = f(qrs; 0), (qrs; 1), (qrs; 2), (qrs; 3), (qrs; 1); (qrs; 1); (qrs; 1); (qrs; 1)g. Let d be defined as Hamming distance. Suppose the observation received is (q ^ r) _ (q ^ :r ^ s). Then

Min( ; qrs; d) = fqrsg Min( ; qrs; d) = fqrsg Min( ; qrs; d) = fqrsg Min( ; qrs; d) = fqrsg

Min( ; qrs; d) = fqrsg Min( ; qrs; d) = fqrs; qrsg Min( ; qrs; d) = fqrsg

Min( ; qrs; d) = fqrs; qrsg and 1GI (qrs) = minf (qrs); (qrs)g = minf1; 1g = 1, 1GI (qrs) = minf (qrs), (qrs), (qrs), (qrs)g = minf3; 2; 1; 0g = 0,

1GI (qrs) = minf (qrs), (qrs), (qrs), (qrs)g = minf1; 2; 1; 0g = 0, 1GI (qrs) = 1GI (qrs) = 1GI (qrs) = 1GI (qrs) = 1GI (qrs) = 1.

1GI (qrs) = 1GI (qrs) = 1.

Notice that (q ^ r) _ (q ^ :r ^ s) does not contradict 1 (i.e.,

1((q ^ r) _ (q ^ :r ^ s)) 6= 1). To show that qualitative imaging can deal with observations contradicting the agent’s epistemic state, consider the following example.

Example 2. We consider the same setting as in Example 1. Suppose the observation received is q ^ s. Note that 1( ) = 1, that is, q ^ s is deemed impossible in 1. Then

1GI (qrs) = minf (qrs); (qrs); (qrs); (qrs)g minf1; 3; 1; 1g = 1,

1GI (qrs) = minf (qrs), (qrs), (qrs), (qrs)g = minf1; 2; 1; 0g = 0, = 1GI (qrs) = 1GI (qrs) = 1GI (qrs) = 1GI (qrs) =

Now, qualitative generalized imaging can be weighted/modulated by the plausibility of the evidence in a particular world: OGI := f(w; n) j w 2 W; n = GI(w) + OQ( ; w) g; where is a normalization factor defined as

:= wm2iWn f GI(w) + OQ( ; w)g: Example 3. Continuing with the previous examples, suppose OQ(q ^ s; qrs) = 1 and for all w 6= qrs, OQ(q ^ s; w) = 0. Then

OGI(qrs) = minf (qrs) + 0; (qrs) + 0; (qrs) + 0; (qrs) + 1 0g = minf1 + 0; 3 + 0; 1 + 0; 1 + 0g = 1 1 = 0, OGI(qrs) = minf (qrs) + 0, (qrs) + 0, (qrs) + 0, (qrs) + 1 1g = minf1 + 0; 2 + 0; 1 + 0; 0 + 1g = 1 1 = 0, OGI(qrs) 1 1OGI(qrs) = =

OGI(qrs) 1 1OGI(qrs) = 1.

= 1OGI(qrs) = 1OGI(qrs) =

In Example 2, qrs is most plausible in 1GI , but in Example 3, due

to q ^ s being slightly less plausibly perceived in qrs than in any other world, qrs becomes slightly less plausible in 1OGI. Thus, in Example 4. We continue, using the vocabulary and epistemic state of the previous examples. For illustrative purposes, we keep the observation, transition and event models very simple, with an arbitrary specification: For all w 2 W , let OQ( ; w) = 0 if w , else, OQ( ; w) = 1. Let there be two events: Evt = fe1; e2g. Let W = fw1; w2; : : : ; wng. EQ(ek; wi) = i k, except for EQ(e1; w1) = 0. TQ(wi; ek; wj ) = i j k, except for TQ(w1; e1; w1) = 0. Then the ranks of the first two worlds are (qrs) =

OQ( ; qrs) +

TQ(w; e; qrs) + EQ(e; w)+ (w) 8 + 0g 0 = 7 (qrs) =

0 = 0+minf0+0+1; 2+2+3; : : : ; 16+ 0 and

OQ( ; qrs) + TQ(w; e; qrs) + EQ(e; w) + (w) 0 = 1 + minf2 + 1 + 1; 4 + 2 + 3; 6 + 3 + 1; : : : ; 32 + 16 + 1g 0 = 10 0. minew22EWvt minew22EWvt We do not work out the ranks of the other worlds.

Given an epistemic state and a new observation , we propose the following HQBC operation.

:=

(w; n) j w 2 W; n = minf CPI (w) + es( ; w); where 00 is a normalizing factor defined as In this section we shall assess two fundamental postulates generally agreed upon as necessary (but not sufficient) for belief change to be rational [6, e.g.]. The categorical matching postulate (CM) states that the representation of an agent’s state of knowledge/belief should have the same formal structure before and after the application of the belief change operation under consideration. The success postulate (S) states that the observation/evidence with which an agent’s state is to be changed should be believed (with certainty) after the belief change operation.8 In the rest of this section, we assume that 2 L is any logically satisfiable piece of information. 8 Here it is assumed that the incoming information is certainly correct. Example 3, qrs and qrs share the status of being most plausible in the agent’s revised epistemic state.

Finally, a qualitative version of BCI can be defined, which revises by conditional plausibility when the evidence does not contradict the agent’s current beliefs, and revises by qualitative imaging otherwise: (3) 0o;

Definition 3. We say event e is possible in iff there exists a world w 2 W such that (w) 6= 1 and EQ(e; w) 6= 1; event e is event-rational when for all w 2 W : there exists a w0 such that TQ(w; e; w0) 6= 1 iff EQ(e; w) 6= 1; evidence is an e-signal when for all w0 2 W : there exists a w such that TQ(w; e; w0) 6= 1 iff OQ( ; w0) 6= 1; evidence is trustworthy iff for all w 2 W , if w 6 , then OQ( ; w) = 1; evidence is clear iff for all w 2 W , if w , then OQ( ; w) = 0; evidence is weakly observable iff there exists a w 2 W such that w and O( ; w) 6= 1; evidence is strongly observable iff for all w 2 W for which w , O( ; w) 6= 1.

Except for possibility, the definitions in the list above are adapted from Rens [ 11 ].

Postulate (CM) If is a ranking function, then so is . is strongly observable, then

CPI is a ranking Lemma 1. If function.

Proof. Omitted to save space; available on request.

Lemma 2. Let the HQBC model be specified such that there exists an event-rational event e 2 Evt possible in , and is an e-signal. Then is a ranking function.

Proof. Note that the normalizing factor will ensure that is a ranking function as long as there exists a world w 2 W for which (w) 6= 1. It must thus be shown that if there exists an event er 2 Evt which is event-rational and is an er-signal, then there must exist a world w 2 W for which (w) 6= 1.

is assumed to be a ranking function. Let w be a world for which (w ) 6= 1. By definition of the transition function, there must exist a world w+ for which T (w ; e; w+) 6= 1, for all e 2 Evt . Choose the er which is event-rational. Then E(er; w ) 6= 1. Furthermore, because w exists such that T (w ; er; w+) 6= 1 and we know that is an er-signal, OQ( ; w+) 6= 1.

By definition of operation (3), (w+) = OQ( ; w+) +

TQ(w; e; w+)+EQ(e; w)+ (w) = OQ( ; w+)+ minew22EWvt min : : : ; TQ(w ; er; w+) + EQ(er; w ) + (w ); : : : 1. 6= Proposition 1. If the HQBC model is specified such that is strongly observable, there exists an event-rational event e 2 Evt possible in , and is an e-signal, then (CM) holds.

Proof. := f(w; n) j w 2 W; n = minf CPI (w) + es( ; w); (w) + os( ; w)g 00g. Recall that neither es( ; w) nor os( ; w) can have a value of 1. And given the antecedents of the proposition, by Lemmata 1 and 2, there must be a w0 for which CPI (w0) = 0 or (w0) = 0. Hence, either CPI (w0) + es( ; w0) 6= 1 or (w0) + os( ; w0) 6= 1. Thus (w0) 6= 1 and due to the normalizing factor 00, there exists a w s.t. (w) = 0.

Postulate (S) If is a ranking function, then ( ) = 0.

Lemma 3. If is strongly observable, then

CPI ( ) = 0.

Lemma 4. Let the HQBC model be specified such that there exists an event-rational event e 2 Evt possible in , and is a trustworthy e-signal. Then ( ) = 0.

Proof. Recall that ( ) = minw2W;w (w). By Lemma 2, is a ranking function and thus there exists a w for which (w) = 0.

Hence, for ( ) not to equal 0, there must exist a w0 2 W s.t.

w0 6 and (w0) 6= 1. But then OQ( ; w0) 6= 1. Therefore, for (S) not to hold, an agent needs to believe that OQ( ; w0) 6= 1 for some world w0 where w0 6 . But then cannot be trustworthy. Arguing by contradiction, (S) must hold.

Note that trustworthiness is required for Lemma 4, in addition to the antecedents required for Lemma 2.

Proposition 2. If the HQBC model is specified such that is strongly observable, there exists an event-rational event e 2 Evt possible in , and is a trustworthy e-signal, then (S) holds.

Proof. Note that neither es( ) nor os( ) can have a value of 1.

Moreover, because is trustworthy, by the definitions of CPI and , CPI (w) = (w) = 1 whenever w 6 . Together with Lemmata 3 and 4, one can thus infer that 00 = wm2iWn fminf CPI (w) + es( ; w); = wm2iWn fminf CPI (w) + es( ; w);

w Then ( ) = wm2iWn f w

(w)g = wm2iWn fminf CPI (w) + es( ; w);

w = wm2iWn fminf CPI (w) + es( ; w);

w = 0: (w) + os( ; w)gg (w) + os( ; w)gg Boutilier [ 3 ] adopts an event-based approach where a set of events E is assumed. These events are allowed to be nondeterministic, and each possible outcome of an event is ranked according to its plausibility via a ranking function. “As in the original event-based semantics, we will assume each world has an event ordering associated with it that describes the plausibility of various event occurrences at that world,” [3, p. 14].

A generalized update model is then defined as hW; ; E; i, where W is a set of possible worlds;

is a ranking over W (the agent’s epistemic state);

E is a mapping from w 2 W and e 2 Evt to rankings w;e

over W , where w;e(w0) describes the plausibility that world w0 results when event e occurs at world w; is a mapping from w 2 W to rankings w over Evt , where w(e) captures the plausibility of the occurrence of event e at world w.

In this model, the set of events Evt is implicit and the (initial) epistemic state explicit.

Lemma 5. TQ corresponds to E, and EQ corresponds to . The correspondence is in the sense that the values of functions are equal for the same arguments, respectively, parameters.

Proof. Omitted to save space; available on request.

In the rest of the paper, due to Lemma 5, we shall assume that TQ(w; e; w0) and w;e(w0) are interchangeable, and that EQ(e; w) and w(e) are interchangeable.

Boutilier calls the evolution of w into w0, under event e, a transition, which he writes w !e w0. He defines (rhs in our notation) (w !e w0) := TQ(w; e; w0) + EQ(e; w) + (w): And he defines the set of possible -transitions:

Tr ( ; ) := fw !e w0 jw; w0 2 W; e 2 Evt ; w0 ; (w !e w0) 6= 1g: Tr ( ; ) is the set of transitions from one world to the next via an event, such that the transition (TQ) is possible, the event in the departure world (EQ) is possible, and the departure world ( ) is possible, and such that the arrival world is an -world.

Then Boutilier defines

result GU ( ; ) := fw j w0 !e w 2 min Tr ( ; )g and defines generalized update as

Bel GU ( ) := f J Kg: (5) Proposition 3. A generalized update model can be realized via an HQBC model.

2 L j result GU ( ; ) Proof. Let G = hW; ; E; i be a generalized update model, where is a (current) epistemic state. Choose an HQBC model H = hW; Evt ; TQ; EQ; OQ; osi with implicit epistemic state and such that, for all w; w0 2 W and e 2 Evt , TQ(w; e; w0) = w;e(w0) and EQ(e; w) = w(e). Then TQ corresponds to E and EQ corresponds to . G is thus realized via H.

Lemma 6. Let H be the class of HQBC models specified such that there exists an event-rational event e 2 Evt possible in and such that evidence is an e-signal, trustworthy and clear. For every generalized update model realizable via an HQBC model in H, Bel GU ( ) = Bel ( ).

Proof. Let H 2 H s.t. H = hW; Evt ; TQ; EQ; OQ; osi with implicit epistemic state . Let G = hW; ; E; i be a generalized update model realized via H. Note that (w !e w0) 6= 1 iff TQ(w; e; w0) 6= 1; EQ(e; w) 6= 1 and (w) 6= 1.

Bel GU ( ) = Bel ( ) iff f 2 L j result GU ( ; ) J Kg = f 2 L j ( ) 1(0) ) 1J(0K)gif(fbryetshuelitrGdUe(fin;itio)n=s: (5) and (2)) iff result GU ( ; ) = ( JBel ( )K.

And result GU ( ; ) = fw j w0 !e w 2 min Tr ( ; )g (by definition of result GU ) =fw j w0 !e w 2 minfw0 !e w j w0; w 2 W; ; (w0 !e w) 6= 1gg (by definition of Tr )

fTQ(w0; e; w) + EQ(e; w0) + (w0)g = e 2 Evt ; w

arg min w;w02W; e2Evt; w w: TQ(w0;e;w)+EQ(e;w0)

+ (w0)6=1 (by definition of (w0 !e w)) = arg min OQ( ; w)

w2W + w02mW;ien2EvtfTQ(w0; e; w) + EQ(e; w0) + (w0)g (by definition of class H, w (w0) 6= 1)

and TQ(w0; e; w) + EQ(e; w0) + = n arg minf w2W (w)go = ( (w)) 1(0) = JBel ( )K: Proposition 4. Let H be the class of HQBC models specified such that there exists an event-rational event e 2 Evt possible in and such that evidence is an e-signal, trustworthy and clear. For every generalized update model realizable via an HQBC model in H, Bel GU ( ) = Bel ( ).

Proof. Let os( ; w) = 0 for all possible and for all w 2 W . Let > (w) OGI (w) for all w 2 W for which (w) 6= 1 and OGI (w) 6= 1. Recall that may not equal 1 and for all w 2 W; os( ; w) 6= 1.

Then, for all w 2 W ,

(w) = minf OGI (w) + es( ; w);

We use Boutilier’s two examples [3, x 3.3]. One can then compare

his generalized update (GU) with our HQBC.

The first example involves a book (B) which might be inside the house or on the patio. There are three events: it rains, in which case the grass (G) and the patio get wet, the sprinkler comes on, in which case only the grass gets wet, or nothing happens. In this example, events are deterministic. If the book is on the patio, it will get wet when it rains, else not. If the book is inside and the book is dry, it will never get wet. Figure 1 illustrates the prior epistemic state of an agent who believes its book is on the patio and that both the grass and the book are dry ( (Patio(B) ^ Dry (B) ^ Dry (G)) = 0), but if the book is not on the patio, the agent believes it has left it inside ( (Inside(B) ^ Dry (B) ^ Dry (G)) = 1). The other less plausible worlds are omitted. Event plausibility is ranked as EQ(null ; w) = 0, EQ(rain; w) = 1, EQ(sprinkler ; w) = 2, for all w (a ‘global’ ordering suitable for all worlds is assumed). This is the only information required for GU.

For HQBC, the observation function (OQ), ontic strength (os) and its top value ( ), and distance measure (d) are required, in addition. We let all observations be trustworthy and clear. For now, let the agent have no opinion as to whether observations are ontic or epistemic, that is, for all possible and for all w 2 W , os( ; w) = es( ; w) = 1.9 d will be defined in accordance with Hamming distance, as before.

Suppose the agent observes that the grass is wet (:Dry (G)). This

contradicts what the agent presently believes, so, with respect to revision, CPI :Dry (G) is interpreted as OGI :Dry (G). We determine that

OGI :Dry(G)(Patio(B) ^ Dry (B) ^ :Dry (G)) = 0 OGI :Dry(G)(:Patio(B) ^ Dry (B) ^ :Dry (G)) = 1 OGI :Dry(G)(w) = 1 for all w 2 W s.t. w 6 Patio(B)^Dry (B)^ :Dry (G) and w 6 :Patio(B) ^ Dry (B) ^ :Dry (G) With respect to update, we determine that :Dry(G)(Patio(B) ^ Dry (B) ^ :Dry (G)) = 1 :Dry(G)(Patio(B) ^ :Dry (B) ^ :Dry (G)) = 0 :Dry(G)(w) = 1 for all w 2 W s.t. w 6 Patio(B)^Dry (B)^ :Dry (G) and w 6 Patio(B) ^ :Dry (B) ^ :Dry (G) Then combining these results gives :Dry(G)(Patio(B) ^ Dry (B) ^ :Dry (G)) = 0 :Dry(G)(Patio(B) ^ :Dry (B) ^ :Dry (G)) = 0 :Dry(G)(:Patio(B) ^ Dry (B) ^ :Dry (G)) = 1 and the other worlds are deemed impossible. If the agent were to reflect on its new beliefs, it might reason as follows.

I believe Patio(B) ^ Dry (B) ^ :Dry (G) because it is the

:Dry (G)-world closest to my prior beliefs (and at least plausible, because it is plausibly explained by the sprinkler coming on). I believe Patio(B) ^ :Dry (B) ^ :Dry (G) because it is a :Dry (G)-world best explained by rain (in my prior beliefs).

I don’t fully believe :Patio(B) ^ Dry (B) ^ :Dry (G), but it

is plausible because it is the :Dry (G)-world second closest to my prior beliefs (although :Patio(B) was previously not fully believed, it was deemed plausible.).

Now suppose the ontic strength of :Dry (G) is defined as os(:Dry (G); w) = 0, for all w 2 W , and = 2. That is, perceiving wet grass is always deemed slightly more ontic than epistemic. Then the resulting epistemic state is determined as in Table 1. In the table, worlds are identified by three letters, such that, for instance, pdd j= Patio(B) ^ Dry (B) ^ Dry (G) and iww j= :Patio(B) ^ :Dry (B) ^ :Dry (G); OGI abbreviates OGI(w), abbreviates (w), es abbreviates es( ; w) and os abbreviated os( ; w), where is the incumbent observation and w is the world of the row. The “min” column indicates the minimum value between the two columns to its left, and is actually the rank assigned to the world w of the incumbent row ( (w)).

Finally, suppose ontic strength of :Dry (G) is defined as

os(:Dry (G); w) = 2 for all w 2 W , with = 2 (which implies that es(:Dry (G); w) = 0, for all w 2 W ). That is, perceiving wet grass is always deemed more epistemic than ontic. Then the resulting epistemic state is determined as in Table 2. We now analyze the results of the two tables/cases a little.

We see that when the agent prefers to interpret or explain :Dry (G) as an ontic observation, the agent considers world pww as most plausible, that is, it fully believes that the book is on the patio, the book is wet and the grass is wet. A reason could be that, given the agent’s most plausible prior belief that the book is on the patio and dry and the grass is dry, it rained. This is the same result produced by generalized update [3, p. 17]; this correspondence makes sense, given that our update ( ) is ‘aligned’ with GU (Bel GU ( ) = Bel ( ) under reasonable conditions; Lem. 6). Notice that the plausibility of pww due to revision is not in contention, because OGI :Dry(G)(pww) = 1.

We see that when the agent prefers to interpret or explain :Dry (G) as an epistemic observation, the agent considers world pdw as most plausible, that is, it fully believes that the book is on the patio, the book is dry and the grass is wet. It can be seen from Table 2 that it is revision which causes the agent to believe pdw. Notice that pdw is the Hamming-closest :Dry (G)-world to the most plausible prior belief (pdd).

The second example is shown in Figure 2. Here only one possible event is assumed, the action of dipping litmus paper in a beaker.

The beaker is believed to contain either an acid or a base ( = 0); little plausibility ( = r) is accorded the possibility that it contains some other substance (say, kryptonite). The expected outcome of the test is a color change of the litmus paper: it changes from yellow to red if the substance is an acid, to blue if it is a base, and to green if it is kryptonite. However, the litmus test can fail some small percentage of the time, in which case the paper also turns green. This outcome is also accorded little plausibility ( = g). If the paper is dipped, and red is observed, the agent will adopt the new belief acid . Unlike KM update [of Katsuno and Mendelzon [ 8 ]], generalized OGI + es 1 + 2 0 + 2

update permits observations to rule out possible transitions, or previously epistemically possible worlds. As such, it is an appropriate model for revision and expansion of beliefs due to information-gathering actions. An observed outcome of green presents two competing explanations: either the test failed (the substance is an acid or a base, and we still dont know which) or the beaker contains kryptonite. The most plausible explanation and the updated epistemic state depend on the relative magnitudes of g and r. The figure suggests that g < r, so the a test failure is most plausible and the belief acid _ base is retained. If test failures are more rare (r < g), then this outcome would cause the agent to believe the beaker held kryptonite. [3, p. 18] Now we investigate how HQBC deals with this scenario for two observations. We let all observations be trustworthy and clear, and Hamming distance is used to define d. The three possible observations are red , blue and green.

Tables 3 and 4 show the agent’s new epistemic state after perceiving the litmus paper turning red, respectively, green. In both tables, the three right-most columns report the new state ( ) when the agent (from left to right) (i) is indifferent about whether the observation is ontic or epistemic, (ii) prefers an ontic interpretation, (iii) prefers an epistemic interpretation. “os = x” (“es = x”) in a column heading means that os( ; w) = x (resp., es( ; w) = x) for all w 2 W . In the tables, worlds are identified by two letters, such that, for instance, ar j= acid ^red , ab j= acid ^blue, bg j= base ^green, ky j= krypt ^ yellow . To save space, rows containing 1 in every row are omitted. Of course, perceiving red, blue or green is inconsistent with the current belief that the litmus paper is yellow; revision operator CPI is thus interpreted as OGI.

We see that when the agent prefers to revise its beliefs (es = 0, os = 2), and when it is indifferent about whether to revise or update (es = 1, os = 1), then its resulting beliefs seem unintuitive to us humans—the agent believes as equally plausible that the substance is acid and that it is base. However, when the agent prefers to update its beliefs (es = 2, os = 0), then it reasonably believes (only) that the substance is acid. A reasonable agent should prefers to update its beliefs because it should consider all its observations in this scenario to be ontic, due to the ontic nature of dipping litmus paper.

Note that for the case when es = 2 and os = 0, the values had to be normalized ( 00 = 2). It is interesting to see that no matter what stance the agent takes on ontic/epistemic strength, when it perceives green, it believes with equal plausibility that the substance is acid and base. Assuming r > 0, the substance is less plausibly kryptonite, but not impossible.

In the cases when the agent has an event-based attitude (i.e., it prefers to interpret observations ontically), all results when HQBC is applied align with the results when GU is applied (w.r.t. the examples in this paper). 7

Concluding Remarks, Related and Future Work A hybrid qualitative belief change (HQBC) construction was presented—based on ranking theory and which trades revision off with update, according to the agent’s confidence for whether the received observation/evidence is ontic (due to a physical event) or epistemic (due to an announcement). We proved that HQBC is, in a particular sense, an extension of Boutilier’s generalized update (GU). In other words, the HQBC model in a class of ‘reasonable’ models can be specified to perform exactly the same belief change as GU would. Moreover, HQBC allows for more sophisticated belief change than GU, in particular, with respect to rankic belief revision (based on conditional plausibility and generalized imaging, for instance) and with respect to employing a notion of ontic strength. The examples in this paper support our propositions concerning the relationship between HQBC and GU.

Determining os( ; w) for every foreseen in every possible world w will be challenging for a designer. Some deep questions are: Should the designer/agent provide the strengths (via stored values or programmed reasoning), or do these strengths come to the agent attached to the new information? What is the reasoning process we go through to determine whether information is epistemic or ontic, if at all? In general, how does an agent know when information is epistemic (requiring revision) or ontic (requiring update)? [ 11 ]

One direction to investigate as a possible answer to the questions above is to condition ontic/epistemic strength on particular propositions. For instance, the more plausible the proposition, the more likely that the received information is ontic. For such an approach to work, the framework would presumably have to accommodate the specification of condition propositions for every observation of interest. Revision and update would then be traded off depending on the plausibility/probability of the condition of the observation under consideration.

Friedman and Halpern [ 5 ] investigate belief revision and update employing a framework based on time-stamps and runs of possible evolutions of a system. They provide some interesting insights regarding the relationship between revision and update, which may also benefit our future work. In their concluding section, they hint that their framework could ‘mix’ revision and update: “In this framework, belief change operations can be determined by choosing a plausibility measure that captures the agent’s preferences among sequences of worlds.... [T]here are prior plausibilities that, when conditioned on a surprising observation, allow the agent to revise some earlier beliefs and to assume that some change has occurred”, [ 5 ]. To our knowledge, they never did investigate the ‘mixture’ approach.

Relationships to the change operations defined by Beierle and Kern-Isberner [ 1, 2 ], which make use of knowledge bases, also need to be investigated.

Although Lang’s work [?] is not directly applicable to ours in terms of ‘mixing’ revision and update, it does unpack and highlight several important characteristics of update. Lang also discusses the relationship between update to revision. His insights might well guide our future efforts in this area. He writes

In complex environments, especially planning under incomplete knowledge, actions are complex and have both ontic and epistemic effects; the belief change process then is very much like the feedback loop in partially observable planning and control theory: perform an action, project its effects on the current epistemic state, then get the feedback, and revise the projected epistemic state by the feedback. Clearly, update allows for projection only. Or, equivalently, if one chooses to separate the ontic and the epistemic effects of actions, by having two disjoint sets of actions (ontic and epistemic), then ontic actions lead to projection only, while epistemic actions lead to revision only. Therefore, if one wants to extend belief update so as to handle feedback, there is no choice but integrating some kind of revision process, as in several recent works [. . . ] [?] This act-update-perceive-revise “feedback loop” is the default approach when complex actions/events are considered; it is fundamentally different to the simultaneous, hybrid belief change approach. Yet, we have not come across a convincing argument against the hybrid approach. It seems that the traditional “feedback loop” approach assumes that there is always certainty about the ontic/epistemic status of every piece of information received. A major question for future research is, Is there a theory or framework to synthesize the two approaches?

Nayak [ 10 ] proves that, given an appropriate function for measuring distance between worlds, classical revision ( ) can be reduced to classical update ( ). Formally, he proves that (x k) x = k x, where k; x 2 L, k is an agent’s knowledge and x is the (new) evidence. Nayak points out that the “nice storyline that cleanly demarcates revision from update appears not to be such a good story after all,” [ 10 ]. Nayak’s surprising result is just one more reason to investigate the hybrid belief change approaches.

“We can regard imaging as a probabilistic version of update, and conditionalization as a probabilistic version of revision,” [ 8 ]. And according to Nayak, KM-update “is known to be the non-probabilistic counterpart of the account of [probabilistic] imaging propounded by David Lewis in order to develop a theory of conditionals [. . . ]” [ 10 ]. Dubois and Prade [ 4 ] give a version of imaging for belief update in the possibilistic framework. Rens [ 11 ] uses imaging (GI) on the revision side; his justification is because imaging can deal with contradictory evidence, whereas conditioning cannot. We are not convinced that imaging is strictly an update process. Where exactly imaging lies on the revision-update spectrum is, to our minds, another deep question still to be answered.

References

[1] C. Beierle and G. Kern-Isberner , ' On the modelling of an agent's epistemic state and its dynamic changes' , Electronic Communications of the European Association of Software Science and Technology , 12 , ( 2008 ).

[2] C. Beierle and G. Kern-Isberner , ' Towards an agent model for belief management' , in Advances in Multiagent Systems, Robotics and Cybernetics: Theory and Practice . (Volume III), eds., G. Lasker and J. Pfalzgraf , IIAS , Tecumseh, Canada, ( 2009 ).

[3] C. Boutilier , ' A unified model of qualitative belief change: A dynamical systems perspective', Artif . Intell., 98 ( 1-2 ), 281 - 316 , ( 1998 ).

[4] D. Dubois and H. Prade , ' Belief revision and updates in numerical formalisms: An overview, with new results for the possibilistic framework' , in Proceedings of the Thirteenth Intl. Joint Conf. on Artif. Intell. (IJCAI-93) , pp. 620 - 625 , San Francisco, CA, USA, ( 1993 ). Morgan Kaufmann Publishers Inc.

[5] N. Friedman and J. Halpern , ' Modeling belief in dynamic systems. Part II: Revision and update' , Journal of Artif. Intell. Research (JAIR) , 10 , 117 - 167 , ( 1999 ).

[6] P. Ga ¨rdenfors, Knowledge in Flux: Modeling the Dynamics of Epistemic States , MIT Press, Massachusetts/England, 1988 .

[7] M. Goldszmidt and J. Pearl , ' Qualitative probabilities for default reasoning, belief revision, and causal modeling' , Artificial Intelligence , 84 , 57 - 112 , ( 1996 ).

[8] H. Katsuno and A. O. Mendelzon , ' On the difference between updating a knowledge base and revising it' , in Belief Revision, ed., P. Ga¨rdenfors, 183 - 203 , Cambridge University Press, ( 1992 ).

[9] D. Lewis , ' Probabilities of conditionals and conditional probabilities' , Philosophical Review , 85 ( 3 ), 297 - 315 , ( 1976 ).

[10] A. C. Nayak , ' Is revision a special kind of update?' , in AI 2011: Advances in Artif . Intell.: Proceedings of the Twenty-fourth Australasian Joint Conf., LNAI , pp. 432 - 441 , Berlin/Heidelberg, ( 2011 ). SpringerVerlag.

[11] G. Rens , ' On stochastic belief revision and update and their combination' , in Proceedings of the Sixteenth Intl. Workshop on Non-Monotonic Reasoning (NMR), eds., G. Kern-Isberner and R. Wassermann , pp. 123 - 132 . Technical University of Dortmund, ( 2016 ).

[12] G. Rens , T. Meyer, and G. Casini, ' Revising incompletely specified convex probabilistic belief bases' , in Proceedings of the Sixteenth Intl. Workshop on Non-Monotonic Reasoning (NMR), eds., G. Kern-Isberner and R. Wassermann , pp. 133 - 142 . Technical University of Dortmund, ( 2016 ).

[13] W. Spohn , ' Ordinal conditional functions: A dynamic theory of epistemic states', in Causation in Decision, Belief Change , and Statistics, eds., W. Harper and B. Skyrms , volume 42 of The University of Western Ontario Series in Philosophy of Science, 105 - 134 , Springer Netherlands, ( 1988 ).

[14] W. Spohn , ' A survey of ranking theory' , in Degrees of Belief, eds., F. Huber and C. Schmidt-Petri , 185 - 228 , Springer Netherlands, Dordrecht, ( 2009 ).