Knowledge State Reconsideration: Hindsight Belief Revision

Abstract

As a knowledge representation and reasoning (KRR) sys-tem gathers and reasons about information, it has to up-date its belief space to maintain consistency. Some belief change operations it can perform include expansion (ad-dition with no consistency checking), contraction (aka re-moval or retraction), revision (consistent prioritized addi-tion), and consolidation (elimination of any and all incon-sistencies). Whether belief change operations are performed on theories (Alchourrón, Gärdenfors, & Makinson 1985) or bases (Nebel 1989; Hansson 1991; 1993b), with ideal agents or those that are resource-bounded (Wassermann 1999; Williams 1997), there is no doubt that the order of operations typically affects the makeup of the resulting belief base. If a KRR system gains new information that, in hindsight, might have altered the outcome of an earlier belief change decision, the earlier decision should be re-examined. We call this operation reconsideration, and the result is an optimal belief base regardless of the order of previous belief change operations. For this paper, we assume a global decision function is used in the belief change operations, and it will favor retain-ing the most preferred beliefs as determined by a preference ordering () that is irreflexive, anti-symmetric and transi-tive (referred to here as an IAT-preference ordering).1 Any base can be represented as a sequence of beliefs in order of decending preference: B = p1, p2,..., pn, where pi is pre-ferred over pi+1 (pi pi+1). This work proposes maintaining a knowledge state (KS) which is defined as follows: KS = 〈B,B∪,〉, where B is the current belief base2, B ∪ is the set of all beliefs that have ever been in the belief base at any time (effectively, the union of all past and current bases), and is the preference ordering relation for the beliefs in B∪.