9.5 Epistemic States and Iterated Revision


9.5 Epistemic States and Iterated Revision

Agents do not change their beliefs just once. They do so repeatedly, each time they get new information. The BCS framework models this naturally, showing how the agent's local state changes as a result of each new observation. It would seem at first that revision operators make sense for iterated revision as well. Given a revision operator and an initial belief set K, it seems reasonable, for example, to take (K φ1) φ2 to be the result of revising first by φ1 and then by φ2. However, Example 9.3.6 indicates that there is a problem with this approach. Even if (K φ1) = K, it may not be desirable to have (K φ1) φ2 = K φ2. In Example 9.3.6, revising by φ1 and then φ2 is not the same as revising by φ2, even though the agent has the same belief set before and after revising by φ1.

The culprit here is the assumption that revision depends only on the agent's belief set. In a BCS, there is a clear distinction between the agent's epistemic state at a point (r, m) in , as characterized by her local state sa = ra(m), and the agent's belief set at (r, m), Bel (, sa). As Example 9.3.6 shows, in a system in , the agent's belief set does not in general determine how the agent's beliefs will be revised; her epistemic state does.

It is not hard to modify the AGM postulates to deal with revision operators that take as their first argument epistemic states rather than belief sets. Suppose that there is a set of epistemic states (the exact form of the epistemic state is irrelevant for the following discussion) and a function BS( ) that maps epistemic states to belief sets. There is an analogue to each of the AGM postulates, obtained by replacing each belief set by the beliefs in the corresponding epistemic state. Letting E stand for a generic epistemic state, here are the first three modified postulates:

  • R1. E φ is an epistemic state.

  • R2. φ BS(E φ).

  • R3.BS(E φ) Cl(BS(E) {φ}).

The remaining postulates can be obtained in the obvious way. The only problematic postulate is R6. The question is whether R6 should be "if e φ ψ, then BS(E φ) = BS(E ψ)" or "if e φ ψ, then E φ = E ψ." Dealing with either version is straightforward. For definiteness, I adopt the first alternative here.

There is an analogue of Theorem 9.3.5 that works at the level of epistemic states. Indeed, working at the level of epistemic states gives a more elegant result. Given a BCS , there is a single revision operator that characterizes belief revision in ; it is not necessary to use a different revision operator for each local state sa in .

To make this precise, given a language e, let *e consist of all sequences of formulas in e. In a BCS, the local states are elements of *e (although some elements in *e, such as p, p, cannot arise as local states in a reliable BCS). There is an obvious way of defining a revision function on *e: if E *e, then E φ = E φ.

Theorem 9.5.1

start example

Let be a system in . There is a function BS that maps epistemic states to belief sets such that

  • if sa is a local state of the agent in , then Bel (, sa) = BS(sa), and

  • (, BS) satisfies R1–8.

end example

Proof Note that BS must be defined on all sequences in *e, including ones that are not local states in . Define BS(sa) = Bel(, sa) if sa is a local state in . If sa is not in , then BS(sa) = Bel(, s), where s is the longest suffix of sa that is a local state in . The argument that this works is left to the reader (Exercise 9.18).

At first blush, the relationship between Theorem 9.5.1 and Theorem 9.3.5 may not be so clear. However, note that, by definition,

so, at the level of epistemic states, Theorem 9.5.1 is a generalization of Theorem 9.3.5.

Theorem 9.5.1 shows that any system in corresponds to a revision operator over epistemic states that satisfies the modified AGM postulates. Is there a converse, analogous to Theorem 9.3.7? Not quite. It turns out that R7 and R8 are not quite strong enough to capture the behavior of conditioning given a consistent observation. It is not hard to show that R7 and R8 (together with R3 and R4) imply that

(Exercise 9.17(a)). The following postulate strengthens this:

R9 says that revising E by φ and then by ψ is the same as revising by φ ψ if φ ψ is consistent. This indeed strengthens (9.9), since (given R2)if ψ BS(E φ), then e (φ ψ) (Exercise 9.17(b)). It is not hard to show that it is a nontrivial strengthening; there are systems that satisfy (9.9) and do not satisfy R9 (Exercise 9.17(c)).

The following generalization of Theorem 9.5.1 shows that R9 is sound in :

Theorem 9.5.2

start example

Let be a system in . There is a function BS that maps epistemic states to belief sets such that

  • if sa is a local state of the agent in , then (, sa) = BS(sa), and

  • (, BS) satisfies R1–9.

end example

Proof See Exercise 9.18.

The converse to Theorem 9.5.2 also holds: a revision system on epistemic states that satisfies the generalized AGM postulates and R9 corresponds to a system in . Let e consist of all the sequences 〈φ1, , φk in *e that are consistent, in that e (φ1∧…∧ φk).

Theorem 9.5.3

start example

Given a function BSe mapping epistemic states in *e to belief sets over e such that BSe(〈〉) is consistent and (, BSe) satisfies R1–9, there is a system whose local states consist of all the states in e such that BSe(sa) = Bel), sa) for sa e.

end example

Proof Let = (, , π) be defined as follows. A run in is defined by a truth assignment α to the primitive propositions in e and an infinite sequence o1, o2, …〉 of observations, each of which is true under truth assignment α. The pair (α, o1, o2, …〉) defines a run r in the obvious way: re(m) = α for all m and ra(m) = o1, o2, , om. consists of all runs that can be defined in this way. The interpretation is determined by α: π(r, m) = re(m). All that remains is to define a prior that ensures that BSe (sa) = Bel (, sa) for all sa e. This is left to the reader (Exercise 9.19).

To summarize, this discussion shows that, at the level of epistemic states, the AGM postulates are very reasonable (with the possible exception of R5, which perhaps should be modified to R5*) provided that (a) all propositions of interest are static (i.e., their truth values do not change over time), (b) observations are reliable (in that what is observed is true), (c) nothing is learned from observing φ beyond the fact that φ is true, and (d) there is a totally ordered plausibility on truth assignments (which by (a) and (c) determines the plausibility on runs). The generality of plausibility measures is not required for (d); using conditional probability measures, ranking functions, possibility measures, or total preference orders will do as well.

Clearly these assumptions are not always appropriate. Nor are they necessary in the BCS framework; it makes perfect sense to consider BCSs that violate any or all of them. For example, it is easy enough to allow partial orders instead of total orders on runs. The effect of this is just that R4 and R8 (or R4 and R8) no longer hold. In the next section, I consider a natural collection of BCSs that do not necessarily satisfy these assumptions, based on the Markov assumption discussed in Section 6.5.




Reasoning About Uncertainty
Reasoning about Uncertainty
ISBN: 0262582597
EAN: 2147483647
Year: 2005
Pages: 140

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net