Reconstructing an Agent's Epistemic State from Observations

1 Introduction

The problem of belief revision, i.e., of how an agent should modify its beliefs about the world given some new information which possibly contradicts its current beliefs, is by now a well-established research area in AI [G¨ardenfors, 1988]. Traditionally, the work in this area is done from the agent's perspective, being usually pre-occupied with constructing actual revision operators which the agent might use and with rationality postulates which constrain how these operators should behave. In this paper we change viewpoint and instead cast ourselves in the role of an observer of the agent. Imagine the following scenario. Suppose we are given some sequence (φ1, . . . , φn) of revision inputs which a particular agent, hereafter A, has received over a certain length of time and suppose we are also given a sequence (θ1, . . . , θn) with the interpretation that following the ith input φi, A believed (at least) θi. Throughout the paper, we make the assumptions that A received no input between φ1 and φn other than those listed, and that the θi are correct (but possibly partial) descriptions of A's beliefs after each input. A couple of questions now suggest themselves:

• What will A believe following a further revision input φn+1?
• What did A believe immediately before it received the first input φ1? What, apart from θi did A believe after the ith input φi?

Alexander Nittka

University of Leipzig Dept. of Computer Science Leipzig 04109 Germany nittka@informatik.uni-leipzig.de

One area in which such questions might arise is in humanmachine dialogues [del Cerro et al., 1998], where the φi correspond to inputs given to A - the user - by a machine, and the θi are the user's responses. Here, it can be useful for the machine to keep a model of the evolution of a user's beliefs during a dialogue. Another setting where reconstruction of a prior belief set is needed is in law cases, where guilt and innocence often depend on who knew what, when. Inquiry is a possible method of approaching this type of problem. The above mentioned sequences can be seen as the information the inquiry yields and which is now used for drawing conclusions. Our aim in this paper is to answer these questions.

Our strategy for dealing with these questions will be to adopt a "reverse engineering" approach - constructing a model of the agent. (Similar approaches have already been tried in the context of trying to infer an agent's goals from observable actions, e.g., [Brafman and Tennenholtz, 1997; Lang, 2004].) Having no access to the agent's internals, we assume a belief revision framework A uses for determining its beliefs and for incorporating new information, and construct a model of A that explains the observation about it. By considering this model, we will then be able to make extra inferences or predictions about A's epistemic behaviour. Of course this raises the problem of which belief revision framework to choose. Such a framework will obviously need to support iterated revision [Darwiche and Pearl, 1997; Lehmann, 1995b; Nayak et al., 2003], and preferably also non-prioritised revision [Hansson et al., 2001; Makinson, 1997], i.e., revision in which new inputs are allowed to be rejected. In this paper, we restrict the investigation to one such framework that has been studied in [Booth, 2005]. The idea behind it is that an agent's epistemic state is made up of two components: (i) a sequence ρ of sentences representing the sequence of revision inputs the agent has received thus far, and (ii) a single sentence ▲ standing for the agent's set of core beliefs, which intuitively are those beliefs of the agent it considers "untouchable". The agent's full set of beliefs in the state [ρ,▲] is then determined by a particular calculation on ρ and ▲, while new revision inputs are incorporated by simply appending them to the end of ρ. Note that our choice of this framework does not imply that others are less worthy of investigation. The challenge now becomes to find that particular model of this form which best explains the observation o = 〈(φ1, . . . , φn), (θ1, . . . , θn)〉 we have made of A.

The plan of the paper is as follows. In Sect. 2 we describe in more detail the model of epistemic state we will be assuming. This will enable us to pose more precisely the problem we want to solve. We will see that the problem essentially reduces to trying to guess what A's initial epistemic state [ρ, ▲] (i.e., before it received φ1) was. In Sect. 3, inspired by work done on reasoning with conditional beliefs, we propose a way of finding the best initial sequence - or prefix - ρ(▲) for any given fixed ▲. Then, in Sect. 4 we focus on finding the best ▲. This will amount to equating best with logically weakest. The epistemic state [ρ(▲), ▲] obtained by combining our answers will be our proposed best explanation for o, which we will call the rational explanation. In Sect. 5 we present an algorithm which constructs the rational explanation for any given o, before giving some examples to show the type of inferences this explanation leads to in Sect. 6. In Sect. 7 we briefly mention a related piece of work by Dupin de SaintCyr and Lang, before concluding and giving some pointers for future research.

2 Modelling the Agent

We assume sentences φi, θi,▲, etc. are elements of some finitely-generated propositional language L. In our examples, p, q, r denote distinct propositional variables. The classical logical entailment relation between sentences is denoted by ⊢, while ≡ denotes classical logical equivalence. Wherever we use a sentence to describe a belief set the intention is that it represents all its logical consequences. The set of all possible observations o = 〈ι, τ 〉 which can be made of A, where ι = (φ1, . . . , φn) and τ = (θ1, . . . , θn) are two finite sequences of sentences of the same length, is denoted by O. The operation · on sequences denotes sequence concatenation.

As indicated in the introduction, we follow [Booth, 2005] by assuming that, at any given moment in time, an agent's epistemic state is represented by a pair [ρ,▲]. ([Konieczny and P´erez, 2000; Lehmann, 1995b] also use sequences to represent epistemic states, but without core beliefs). In order to fully specify the agent's epistemic processes, we also need to formally specify (i) how the agent determines its set of beliefs Bel([ρ,▲]) in any given state [ρ,▲], and (ii) how it incorporates new revision inputs into its epistemic state. Turning first to (i), we can describe Bel([ρ,▲]) neatly with the help of a function f, which takes as argument a non-empty sequence σ = (αm, . . . , α1) of sentences, and returns a sentence. f is defined by induction on the length m of σ: if m = 1 then f(σ) = α1. If m> 1 then

In other words f(σ) is determined by first taking α1 and then going backwards through σ, adding each sentence as we go, provided that sentence is consistent with what has been collected so far (cf. the "linear base-revision operation" of [Nebel, 1994] and the "basic memory operator" of [Konieczny and P´erez, 2000].) The belief set associated to the state [ρ,▲] is then given by Bel([ρ,▲]) = f(ρ · ▲). Hence when calculating its beliefs from the sentences appearing in its epistemic state, an agent gives highest priority to ▲. After that, it prioritises more recent information received. Note that ▲ is always believed, and that Bel([ρ, ▲]) is inconsistent if and only if ▲ is inconsistent.

Example 2.1. Consider ▲ = ¬p and ρ = (q, q → p). Bel([ρ,▲]) = f(q, q → p, ¬p). In order to determine f(q, q → p, ¬p) we need to know if q is consistent with f(q → p, ¬p). As f(¬p) = ¬p and q → p is consistent with ¬p, f(q → p, ¬p) = (q → p) ∧¬p ≡ ¬q ∧¬p. So q is inconsistent with f(q → p, ¬p). Consequently we get f(q, q → p, ¬p) = f(q → p, ¬p) and Bel([ρ,▲]) = f (q → p, ¬p) ≡ ¬q ∧ ¬p.

An agent incorporates a new revision input λ into its epistemic state [ρ, ▲] by simply appending λ to ρ, i.e., the agent's revision function ∗ is specified by setting, for every λ ∈ L,

Given this, we see that a new input λ will not always be believed in the new state. Indeed (when ▲ is consistent) it will be so only if it is consistent with ▲. If it contradicts ▲ then it will not be accepted, and in fact in this case the agent's belief set will remain unchanged (c.f. screened revision [Makinson, 1997]). Note also that ▲ remains unaffected by a revision input, i.e., ∗ is a core-invariant revision operator [Booth, 2005]. 1 Core beliefs are needed to ensure that revision inputs can be rejected. If they were not allowed, which corresponds to demanding ▲ = ⊤ in the above definitions, any consistent revision input would belong to the agent's beliefs.

As is shown in [Booth, 2005], the above revision method satisfies several natural properties. In particular, it stays largely faithful to the AGM postulates [G¨ardenfors, 1988] (leaving aside the "success" postulate, which forces all new inputs to be accepted), and satisfies slight,"non-prioritised" variants of several postulates for iterated revision which have been proposed, including those of [Darwiche and Pearl, 1997]. One characteristic property of this method is the following variant of the rule "Recalcitrance" from [Nayak et al., 2003]:

If ▲ ̸⊢ (λ2 → ¬λ1) then Bel([ρ, ▲] ∗ λ1 ∗ λ2) ⊢ λ1 This entails if the agent accepts an input λ1, then it does so wholeheartedly, in that the only way it can be dislodged from the belief set by a succeeding input λ2 is if that input contradicts it given the core beliefs ▲.

Returning to our agent A from the introduction, from now on we assume A's epistemic state is always of the form [ρ,▲], and that A determines its belief set and incorporates new inputs into its epistemic state as described above. Then, suppose we make the observation o = 〈(φ1, . . . , φn), (θ1, . . . , θn)〉 about A. Then after receiving the ith input φi, A's epistemic state must be [ρ · (φ1, . . . , φi), ▲] and its belief set f(ρ · (φ1, . . . , φi) · ▲), where [ρ, ▲] is A's unknown initial (i.e., before φ1) epistemic state. Observation o now amounts to the following:

Definition 2.2. Let o = 〈(φ1, . . . , φn), (θ1, . . . , θn)〉 ∈ O. Then [ρ, ▲] explains o (or is an explanation for o) iff (1) above holds. We say ▲ is an o-acceptable core iff [ρ,▲] explains o for some ρ.

1 In fact the model of [Booth, 2005] allows the core itself to be revisable. We do not explore this possibility here.

Example 2.3. (i) [ρ,▲] = [(p → q), r] explains 〈(p, q), (q, r)〉 because f(p → q, p, r) ≡ p ∧ q ∧ r ⊢ q and f (p → q, p, q, r) ≡ p ∧ q ∧ r ⊢ r. (ii) [(p → q),⊤] does not explain 〈(p, q), (q, r)〉 because f (p → q, p, q, ⊤) ≡ p ∧ q ̸⊢ r.

If we had some explanation [ρ, ▲] for o then we would be able to answer the questions in the introduction: following a new input φn+1 A will believe f (ρ · (φ1, . . . , φn, φn+1) · ▲), before receiving the first input A believes f(ρ · ▲), and the beliefs after the ith input are f(ρ · (φ1, . . . , φi) · ▲).

Note for any o ∈ O there always exists some explanation [ρ, ▲] for o, since the contradiction ⊥ is an o-acceptable core using any ρ. But this would be a most unsatisfactory explanation, since it means we just infer A believes everything at every step.

Our job now is to choose, from the space of possible explanations for o, the best one. As a guideline, we consider an explanation good if it only makes necessary (or minimal) assumptions about what A believes. But how do we find this best one? Our strategy is to split the problem into two parts, handling ρ and ▲ separately. First, (i) given a fixed o-acceptable core ▲, find a best sequence ρ(o,▲) such that [ρ, ▲] explains o, then, (ii) find a best o-acceptable core ▲(o). Our best explanation for o will then be [ρ(o, ▲(o)), ▲(o)].

3 Finding ρ

Given o = 〈(φ1, . . . , φn), (θ1, . . . , θn)〉, let us assume a fixed core ▲. To find that sequence ρ(o,▲) such that [ρ(o,▲),▲] is the best explanation for o, given ▲, we will take inspiration from work done in the area of non-monotonic reasoning on reasoning with conditional information.

Let's say a pair (λ, χ) of sentences is a conditional belief in the state [ρ,▲] iff χ would be believed after revising [ρ,▲] by λ, i.e., Bel([ρ,▲] ∗ λ) ⊢ χ. In this case we will write λ ⇒[ρ,▲] χ. 2 This relation plays an important role, because it turns out A's beliefs following any sequence of revision inputs starting from [ρ,▲] is determined entirely by the set ⇒[ρ,▲] of conditional beliefs in [ρ, ▲]. This is because, for any sequence of revision inputs φ1, . . . , φm, our revision method satisfies

Thus, as far as their effects on the belief set go, a sequence of revision inputs starting from [ρ, ▲] can always be reduced to a single input. (But note the set of conditional beliefs ⇒[ρ,▲]∗λ in the state [ρ,▲] ∗ λ following revision by λ will generally not be the same as ⇒[ρ,▲].)

All this means observation o may be translated into a partial description of the set of conditional beliefs that A has in its initial epistemic state:

Clearly, if we had access to the complete set of A's conditional beliefs in its initial state, this would give another way to answer the questions of the introduction. Now, the problem of determining which conditional beliefs follow from a given set C of such beliefs has been well-studied and several solutions have been proposed, e.g., [Geffner and Pearl, 1992; Lehmann, 1995a]. One particularly elegant and well-motivated solution is to take the rational closure of C [Lehmann and Magidor, 1992]. Furthermore, as is shown in, e.g., [Freund, 2004], this construction is amenable to a relatively simple representation as a sequence of sentences! Our idea is essentially to take ρ(o, ▲) to be this sequence corresponding to the rational closure of C▲(o). First let us describe the general construction.

2 The relation⇒[ρ,▲] almost satisfies all the rules of a rational inference relation [Lehmann and Magidor, 1992]. More precisely the modified version does, viz., λ ⇒′[ρ,▲] χ iff [▲ ⊢ ¬λ or λ ⇒[ρ,▲] χ].

3.1 The rational closure of a set of conditionals

Given a set of conditionals C = {λi ⇒ χi | i = 1, . . . , l} we denote by ˜ C the set of material counterparts of all the conditionals in C, i.e., ˜ C = {λi → χi | i = 1, . . . , l}. Then a sentence ν is exceptional for C iff ˜ C ⊢ ¬ν, and a conditional ν ⇒ µ is exceptional for C iff its antecedent ν is. To find the (sequence corresponding to the) rational closure ρR(C) of C, we first define a decreasing sequence of sets of conditionals C0 ⊇ C1 ⊇ · · · ⊇ Cm by setting (i) C0 = C, (ii) Ci+1 equals the set of conditionals in Ci which are exceptional for Ci, and (iii) m is minimal such that Cm = Cm+1. Then we set

Writing αi for ∧ ˜ Ci, the rational closure of C is then the relation ⇒R given by λ ⇒R χ iff either αm ⊢ ¬λ or [αj ∧λ ⊢ χ where j is minimal such that αj ̸⊢ ¬λ]. Since αm ⊣ · · · ⊣ α0 it easy to check that in fact this second disjunct is equivalent to f (αm, . . . , α0, λ) ⊢ χ.

We now make the following definition:

Definition 3.1. Let o ∈ O and ▲ ∈ L. We call ρR(C▲(o)) the rational prefix of o with respect to ▲, and will denote it by ρR(o, ▲).

Since neither of the individual conditionals are exceptional for C▲(o) we get C0 = C▲(o) and C1 = ∅. Clearly then also C2 = ∅ = C1 so we obtain ρR(o, ▲) = (∧ ∅, ∧ ˜ C▲(o)). Rewriting the sequence using logically equivalent sentences we get ρR(o, ▲) = (⊤, ¬p → r).

Now, an interesting thing to note about the rational prefix construction is that it actually goes through independently of whether ▲ is o-acceptable. In fact a useful sideeffect of the construction is that it actually reveals whether ▲ is o-acceptable. Given we have constructed ρR(o,▲) = (αm, . . . , α0), all we have to do is to look at sentence αm and check if it is a tautology:

Proposition 3.3. Let o ∈ O and ▲ ∈ L, and let ρR(o, ▲) = (αm, . . . , α0) be the rational prefix of o w.r.t. ▲. Then (i) if αm ≡ ⊤ then [ρR(o, ▲), ▲] is an explanation for o. (ii) if αm ̸≡ ⊤ then ▲ is not an o-acceptable core.

Thus this proposition gives us a necessary and sufficient condition for ▲ to be an o-acceptable core. This will be used in the algorithm of Sect. 5.

In Example 3.2 ρR(o,▲) = (⊤, ¬p → r) was calculated. The above proposition implies [(⊤, ¬p → r), ¬p]

is an explanation for o = 〈 ( p , q) , ( r , ¬p ) 〉. This is verified by f(⊤, ¬p → r, p, ¬p) ≡ ¬p ∧ r ⊢ r and f (⊤, ¬p → r, p, q, ¬p) ≡ ¬p ∧ q ∧ r ⊢ ¬p.

3.2 Justification for using the rational prefix

In the rest of this section we assume ▲ to be some fixed oacceptable core. As we just saw, [ρR(o,▲),▲] then provides an explanation for o given this ▲. In this section we want to show in precisely what sense it could be regarded as a best explanation given ▲. Let Σ = {σ | [σ, ▲] explains o}.

One way to compare sequences in Σ is by focusing on the trace of belief sets they (in combination with ▲) induce through o, i.e., for each σ ∈ Σ we can consider the sequence (Belσ 0 , Belσ 1 , . . . , Belσn ), where Belσ i is defined to be the beliefs after the ith input in o (under the explanation [σ,▲]). In other words Belσ i = f(σ · (φ1, . . . , φi) · ▲). (So Belσ 0 gives the initial belief set.)

Example 3.4. Let o, ▲ and ρR(o,▲) be as in Example 3.2. Then the belief trace is (¬p ∧ r, ¬p ∧ r, ¬p ∧ q ∧ r).

The idea would then be to define a preference relation ⪯1 over the sequences in Σ (with more preferred sequences corresponding to those "lower" in the ordering) via some preference relation over their set of associated belief traces. Given any two possible belief traces (β0, . . . , βn) and (γ0, . . . , γn), let us write (β0, . . . , βn) ≤lex (γ0, . . . , γn) iff, for all i = 0, . . . , n, [βj ≡ γj for all j < i implies γi ⊢ βi ]. Then we define, for any ρ, σ ∈ Σ:

(⪯1 is a pre-order (i.e., reflexive and transitive) on Σ.) Thus, given two sequences in Σ, we prefer that one which leads to A having fewer (i.e., weaker) beliefs before any of the inputs φi were received. If the two sequences lead to equivalent beliefs at this initial stage, then we prefer that which leads to A having fewer beliefs after φ1 was received. If they lead to equivalent beliefs also after this stage, then we prefer that which leads to A having fewer beliefs after φ2 was received, and so on. Thus, under this ordering, we prefer sequences which induce A to have fewer beliefs, earlier in o. The next result shows ρR(o, ▲) is a best element in Σ under this ordering.

Another way to compare sequences is to look at their consequences for predicting what will happen at the next step after o.

Thus, according to this preference criterion we prefer ρ to σ if it always leads to fewer beliefs being predicted after the next revision input. It turns out ρR(o,▲) is a most preferred element under ⪯2 amongst all minimal elements under ⪯1.

Proposition 3.6. For all σ ∈ Σ, if σ ⪯1 ρR(o,▲) then ρR(o, ▲) ⪯2 σ.

Thus if we take a lexicographic combination of ⪯1 and ⪯2 (with ⪯1 being considered as more important), ρR(o,▲) emerges overall as a best, most preferred, member of Σ. Having provided a method for finding the best explanation [ρ, ▲] given ▲, we now turn our attention to finding the best ▲ itself.

4 Minimising ▲

As argued earlier, core beliefs are needed, but at the same time we try to minimise the assumptions about the agent's beliefs. This includes minimising ▲. The first idea would be to simply take the disjunction of all possible o-acceptable cores, i.e., to take ▲∨(o), defined by

But is ▲∨(o) itself o-acceptable? Thankfully the answer is yes, a result which follows (in our finite setting) from the following proposition which says that the family of o-acceptable cores is closed under disjunctions.

Proposition 4.1. If ▲1 and ▲2 are o-acceptable then so is ▲1 ∨ ▲2.

So as a corollary ▲∨(o) does indeed satisfy:

What other properties does ▲∨(o) satisfy? Clearly, ▲∨(o) will always be consistent provided at least one consistent oacceptable core exists:

Acceptability and Consistency would appear to be absolute rock-bottom properties which we would expect of any method for finding a good o-acceptable core. However for ▲∨ we can say more. Given two observations o = 〈ι, τ〉 and o′ = 〈ι′ , τ ′ 〉, let us denote by o · o′ the concatenation of o and o′ , i.e., o · o′ = 〈ι · ι′ , τ · τ ′ 〉. We shall use o ⊑right o′ to denote that o′ right extends o, i.e., o′ = o·o′′ for some (possibly empty) o′′ ∈ O, and o ⊑left o′ to denote o′ left extends o, i.e., o′ = o′′ · o for some (possibly empty) o′′ ∈ O.

Proposition 4.2. Suppose o ⊑right o′ or o ⊑left o′ . Then every o′ -acceptable core is an o-acceptable core.

As a result of this we see ▲∨ satisfies the following 2 properties, which say extending the observation into the future or past leads only to a logically stronger core being returned.

Right- and Left Monotony provide ways of expressing that ▲(o) leads only to safe conclusions that something is a core belief of A - conclusions that cannot be "defeated" by additional information about A that might come along in the form of observations prior to, or after o.

We should point out, though, that it is not the case that by inserting any observation anywhere in o, ▲∨ will always lead to a logically stronger core. Consider o1 = 〈(p, q), (p, ¬p)〉 and o2 = 〈(p, ¬p, q), (p, ¬p, ¬p)〉, i.e., 〈(¬p), (¬p)〉 was inserted in the middle of o1. ▲∨(o1) ≡ q → ¬p whereas ▲∨(o2) ≡ ⊤. So although o2 extends o1 in a sense, the corresponding ▲∨ is actually weaker. Looking at o1, assuming as we do that A received no inputs between p and q, the only way to explain the end belief in ¬p is to ascribe core belief q → ¬p to A (cf. the "Recalcitrance" rule in Sect. 2). However, looking at o2, the information that A received (and accepted) intermediate input ¬p is enough to "explain away" this end belief without recourse to core beliefs. Our assumption that A received no other inputs between φ1 and φn during an observation o = 〈(φ1, . . . , φn), (θ1, . . . , θn)〉 is rather strong. It amounts to saying that, during o, we kept our eye on A the whole time. The above example shows that relaxing this assumption gives us an extra degree of freedom with which to explain o, via the inference of intermediate inputs. This will be a topic for future work.

It turns out the above four properties are enough to actually characterise ▲∨. In fact, given the first two, just one of Rightand Left Monotony is sufficient for this task:

Proposition 4.3. Let ▲ : O → L be any function which returns a sentence given any o ∈ O. Then the following are equivalent:

(i) ▲ satisfies Acceptability, Consistency and Right Monotony. (ii) ▲ satisfies Acceptability, Consistency and Left Monotony. (iii) ▲(o) ≡ ▲∨(o) for all o ∈ O.

Note that as a corollary to this proposition we get the surprising result that, in the presence of Acceptability and Consistency, Right- and Left Monotony are in fact equivalent.

Combining the findings of the last two sections, we are now ready to announce our candidate for the best explanation for o. By analogy with "rational closure", we make the following definition:

Definition 4.4. Let o ∈ O be an observation. Then we call [ρR(o,▲∨(o)),▲∨(o)] the rational explanation for o.

In Sect. 6 we will give some examples of what we can infer about A under the rational explanation. But how might we find it in practice? The next section gives an algorithm for just that.

5 Constructing the Rational Explanation

The idea behind the algorithm is as follows. Given an observation o, we start with the weakest possible core ▲0 = ⊤ and construct the rational prefix (αm, . . . , α0)=ρ0 of o w.r.t. ▲0. We then check whether αm is a tautology. If it is then we know by Prop. 3.3 that [ρ0, ▲0] is an explanation for o and so we stop and return this as output. If it isn't then Prop. 3.3 tells us ▲0 cannot be o-acceptable. In this case, we modify ▲0 by conjoining αm to it, i.e., by setting ▲1 = ▲0 ∧ αm. Constructing the rational prefix of o w.r.t. the new core then leads to a different prefix, which can be dealt with the same way.

Algorithm 1 Calculation of the rational explanation

Input: observation o Output: the rational explanation for o

Before showing that the output of this algorithm matches the rational explanation, we need to be sure it always terminates. This is a consequence of the following:

Lemma 5.1. Let ▲ and αm be as after the calculation of ρR(o, ▲). If αm ̸≡ ⊤ then ▲ ̸≡ ▲ ∧ αm.

This result assures us that if the termination condition of the algorithm does not hold, the new core will be strictly logically stronger than the previous one. Thus the cores generated by the algorithm become progressively strictly stronger.

In our setting, in which we assumed a finite propositional language, this means, in the worst case, the process will continue until ▲ ≡ ⊥. However in this case it can be shown the rational prefix of o w.r.t. ⊥ is just (⊤), and so the termination condition will be satisfied at the very next step.

Now, to show the output matches the rational explanation, consider the sequence [ρ0,▲0], . . . , [ρk,▲k] of epistemic states generated by the algorithm. We need to show ▲k ≡ ▲∨(o). The direction ▲k ⊢ ▲∨(o) follows from the fact that [ρk,▲k] is an explanation for o and so ▲k is an oacceptable core. The converse ▲∨(o) ⊢ ▲k is proved by showing inductively that ▲∨(o) ⊢ ▲i for each i = 0, . . . , k: the case i = 0 clearly holds since ▲0 ≡ ⊤. The inductive step uses the following property:

Lemma 5.2. Let 0 < i ≤ k and suppose ρi-1 = (αm, . . . , α0). Then, for any o-acceptable core ▲′ , if ▲′ ⊢ ▲i-1 then ▲′ ⊢ αm.

This enables us to prove that, given ▲∨(o) ⊢ ▲i-1, we must also have ▲∨(o) ⊢ ▲i. Thus ▲∨(o) ⊢ ▲k as required. Since obviously ρk is the rational prefix of o w.r.t. ▲k by construction, we have:

Proposition 5.3. Given input observation o, the algorithm outputs the rational explanation for o.

Example 5.4. Let o = 〈(p, q), (r, ¬p)〉. Starting with ▲=⊤, in the first run ˜ C0 = {f(p,⊤) → r, f(p, q,⊤) → ¬p} = {p → r, p ∧ q → ¬p}. Only the second conditional is exceptional, so ˜ C1 = {p ∧ q → ¬p}. Now the remaining conditional is exceptional for itself, so ˜ C2 = ˜ C1. ▲ is updated to ▲ ≡ p → ¬q because ρ = (p → ¬q, p → (r ∧ ¬q)).

The next calculation yields ˜ C0 = {f(p, p →¬q) → r, f (p, q, p → ¬q) → ¬p} = {p ∧ ¬q → r, q ∧ ¬p → ¬p}. This time none of the conditionals are exceptional, so ˜ C1 = ∅. As this means α1 = ⊤, no further run is necessary and the result is ρ = (⊤, (p ∧ ¬q) → r), ▲ = p → ¬q. [(⊤, (p∧¬q) → r), p → ¬q] is the rational explanation for o.

6 Some Examples

In this section we want to give a few simple examples to illustrate the rational explanation.

For o = 〈(p), (q)〉, the rational explanation is [(⊤, p → q), ⊤]. So we infer A's initial belief set is p → q. Indeed to explain A's belief in q following receipt of p it is clear A must initially believe at least p → q since p itself does not entail q. It seems fair to say we are not justified in ascribing to A any initial beliefs beyond this. After A receives p we assume A accepts this input - we have no reason to expect otherwise - and so has belief set p∧q. If A is given a further input ¬(p∧q) we predict A will also accept this input, but will hold on to its belief in p. The reason being we assume A, having only just been told p, now has stronger reasons to believe p than q. If, instead, A is given further input ¬p we predict its belief set will be just ¬p, i.e., we do not assume A's belief in q persists. Essentially the rational explanation assumes the prior input p must have been responsible for A's prior belief in q. And with this input now being "overruled" by the succeeding input, A can no longer draw any conclusions about the truth of q.

Another illustrative example is o = 〈(p), (¬p)〉, for which the rational explanation is [(⊤), ¬p]. Indeed ¬p must be a core belief, as that is the only possibility for p to be rejected. And if p was not rejected, the agent could not consistently believe ¬p.

In some cases the rational explanation gives only the trivial explanation, i.e., ▲∨(o) ≡ ⊥. One of the simplest examples extends the prior one: o = 〈(p, ¬p), (¬p, p)〉. The first part of the observation tells us that ¬p must be a core belief, but when confirmed of that belief A changes its opinion. This behaviour of always believing the opposite of what one is told can be called rational only in very specific circumstances that are not in the scope of this investigation. Hence, failing to provide a satisfactory explanation for this example is not to be seen as a failure of the method.

7 Conclusion

Before concluding, one paper which deserves special mention as having similarities with the present one is [de SaintCyr and Lang, 2002] on belief extrapolation (itself an instance of the general framework of [Friedman and Halpern, 1999]). A belief extrapolation operator takes as input a sequence of sentences representing a sequence of partial observations of a possibly changing world, and outputs another sequence which "completes" the input. These operators proceed by trying to determine some history of the world which "best fits" (according to various criteria) the observations. A fundamental difference between that work and ours is that belief extrapolation is, like traditional operators of revision and update, an "agent's perspective" operator - it is concerned with how an agent should form a picture of how the external world is evolving, whereas we are interested in forming a picture of how an observed agent's beliefs are evolving. Nevertheless the precise connections between these two works seems worthy of further study.

To conclude, in this paper we made an attempt at reconstructing an agent's initial epistemic state in order to explain a given observation of the agent and make predictions about its future beliefs. We did so by assuming a simple yet powerful model for epistemic states allowing for iterated nonprioritised revision. The algorithm we provided constructs a best explanation based on the rational closure of conditional beliefs. This answer should be applicable to problems requiring the modelling of agents' beliefs, for example in the area of user modelling.

Generalisations of this approach which are object of future work include (i) relaxing the assumption that we are given an unbroken sequence of revision inputs, i.e., allowing also for intermediate inputs as an explanation for what the core accounts for now, (ii) allowing our observations to incorporate information about what the agent did not believe after a given revision step, and (iii) allowing the core beliefs to be revised. Further, it is of interest to compare our results with what other models of epistemic states would yield as explanation.

Acknowledgements

Thanks are due to the reviewers for helpful comments. A.N. acknowledges support by the EC (IST-2001-37004, WASP).