A vast and interesting family of natural semantics for belief revision is defined. Suppose one is given a distance d between any two models. One may then define the revision of a theory K by a formula α as the theory defined by the set of all those models of α that are closest, by d, to the set of models of K. This family is characterized by a set of rationality postulates that extends the AGM postulates. The new postulates describe properties of iterated revisions. 1 Introduction The aim of this paper is to investigate semantics and logical properties of theory revisions based on an underlying notion of distance between individual models. In many situations it is indeed reasonable to assume that the agent has some natural way to evaluate the distance between any two models of the logical language of interest. The distance between model m and model m ′ is a measure of how far m ′ appears to be from the point of view of m. This distance may measure how different m ′ is from m under some objective measure: e.g., the number of propositional atoms on which m ′ differs from m if the language is propositional and finite, but it may also reflect a subjective assessment of the agent about its own capabilities such as, for example, the probability that, if m is the case, the agent (wrongly) believes that m ′ is the case. Any such distance between models may be used to define a procedure for theory revision: both a theory T and a formula α define a set * This work was partially supported by the Jean and Helene Alfassa fund for research in Artificial Intelligence and by grant 136/94-1 of the Israel Science Foundation on "New Perspectives on Nonmonotonic Reasoning". 1 of models, M(T ) and M(α), respectively, and the result of revising T by α, T * α, is the theory of the set of those models of M(α) that are closest to M(T ). The purpose of this paper is not to suggest specific useful notions of distance. It assumes some abstract notion of a distance is given and studies the properties of the revisions defined by this distance. The distances that will be considered in this paper do not always satisfy the properties generally accepted for distances, they are really pseudo-distances. There is no obvious reason why, in particular, our distance should satisfy the triangular inequality or even be symmetric. It may be the case that, from the perspective of m, m ′ looks very far away, but, from the perspective of m ′ , m looks close by. In the terms of one of our examples above: if m is the case, our agent may give a very low probability to m ′ being the case, but if m ′ is the case, our agent may well be hesitant about whether m or m ′ is the case: assume, for example, that m and m ′ differ by the value of one atomic proposition p that is tested by our agent. The test for p may well be very reliable if p is the case but quite unreliable if p is not the case. In [AGM85], Alchourrón, Gärdenfors and Makinson introduced the study of theory revision. Their account of revision is indirect: they describe contractions in terms of maximal non-implying sub-theories and they go on to characterize revisions, reducing revision to contraction via the Levi identity. In [Gro88], Grove gave a direct, semantic, characterization of revision. The result of revising a theory K by a proposition α is determined by the models of α that are, individually, closest to the set, taken collectively, of all models of K. It thus uses a relation between individual models and sets of models. It is natural to seek to analyze such closeness in terms of a distance function between models. A first attempt was made by Becher in [Bec95], in view of comparing revision and update in a unified setting. Becher worked with not necessarily symmetric distances and showed that the AGM postulates hold in distance based revision, but gave no representation result. Independently, the authors presented, in [SLM96], a preliminary version of the results given in this paper. There, only the finite case of symmetric distances was treated. We deal here with the infinite case of symmetric distances and with the finite case of nonsymmetric distances. We also provide here proofs and counter-examples. We present, first, our results on an abstract level, dealing with abstract sets and, then, specialize our results to the case of sets of models. In recent work (personal communication) Areces and Becher gave a representation result for the arbitrary, i.e. infinite and not necessarily symmetric case. Their conditions are different from ours, based on complete consistent theories, i.e. single models, and partly in an "existential" style, whereas our conditions are "universal" and more in the AGM style. We do not know whether there is an easy direct, i.e. not going via the semantics, proof of the equivalence of the Areces/Becher and our conditions. Thus, their approach is an alternative route, whose relation to our results is a subject of further research. The infinite case for non-symmetric distances with 2 conditions in our style is still open. After a short motivation in Section 1.1, we present and discuss the AGM framework for revision in Section 1.2 and modify it slightly. Section 1.3 introduces pseudo-distances, which are distances weakened to the properties essential in our context. In particular, pseudo-distances are not necessarily symmetric. We formalize revision based on a (pseudo-) distance, and we show that the usual AGM properties hold for such distance-based revisions, at least in the finite case. An additional property (definability preservation) guarantees them to hold in the infinite case, too. Here, we also discuss some properties of distance-based revision going beyond the AGM postulates. Our main results are algebraic in nature, and work for arbitrary sets, not only for sets of models. The translation to logic is then straightforward. Section 2 presents the algebraic representation results, which describe the conditions which guarantee that a binary set operator | is representable by a pseudo-distance In Section 2.2, we treat the case of symmetric pseudo-distances, the result applies to sets of arbitrary cardinality. Note that this infinite case requires a limit condition: For nonempty sets A, B there is some b ∈ B with closest distance (among the elements of B) to A. In Section 2.3, we treat the not necessarily symmetric case, but our result applies only to the finite situation. Section 3 finally translates the results of Section 2 to logic. We there describe the conditions which guarantee that a revision operator * can be represented by a pseudo-distance d between models, i.e. T * is the set of models of the theory T, and T h(X) the set of formulas valid in the set of models X. Analogously to the algebraic characterization, the logical representation results are for possibly infinite languages in the symmetric case (with some caveat about definability preservation) and for finite ones in the not necessarily symmetric case. Intelligent agents must gather information about the world, elaborate theories about it and revise those theories in view of new information that, sometimes, contradicts the beliefs previously held. Belief revision is therefore a central topic in Knowledge Representation. It has been studied in different forms: numeric or symbolic, procedural or declarative, logical or probabilistic. The AGM framework One of the most successful frameworks in which belief revision has been studied has been proposed by Alchourrón, Gärdenfors and Makinson, and is known as the AGM framework. It deals with operations of revision that revise a theory (the set of previous beliefs) by a formula (the new information). It proposes a set of rationality postulates that any reasonable revision should satisfy. A large number of researchers in AI have been attracted by and have developed this approach further: both in the abstract and by devising revision procedures that satisfy the AGM rationality postulates. Two remarks should be made immediately. First, the AGM framework presents rationality postulates for revision. It does not choose anyone specific revision among the many possible revisions that satisfy those postulates. FH96] to the effect that this identification of epistemic states to belief sets is not welcome in many AI applications. When iterated revisions are considered, it is reasonable to assume that the agent's epistemic state includes information related to its history of revisions and that all this history, not only the agent's current belief set, may influence future revisions. This paper keeps the AGM commitment to identifying epistemic states with belief sets, but proposes additional rationality postulates. Those additional postulates characterize exactly the revisions that are defined by pseudo-distances. They constrain revisions in the way they treat their left argument, the theory to be revised (in this respect the AGM postulates are extremely, probably excessively, liberal) and they imply highly non-trivial properties for iterated revisions. This paper therefore treats iterated revisions within the original AGM commitment to the identification of epistemic states and belief sets. Results related to the ideas of this paper may be found in [BGHPSW97] . Similar ideas in a context in which epistemic states are not belief sets may be found in [BLS99] . This work provides a semantics for theory revisionà la AGM, or for a sub-family of such revisions. It is the first such effort to describe semantically the whole revision operation * in a unified way. Previous attempts [Gro88], [GM88] describe the revision of each theory K by a different structure without any glue relating the different structures: sphere systems or epistemic entrenchment relations, corresponding to different K's. In this paper, the revisions of the different K's are obtained from the same pseudo-distance. A tight fit (coherence) between the revisions of different K's seem crucial for a useful treatment of iterated revisions: it must be the same revision operation that executes the successive revisions for any interesting properties to appear. Our revisions are therefore defined by a polynomial (in the number of models considered) number of pseudo-distances instead of an exponential number of sphere systems or epistemic entrenchment relations (one for each theory K). Semantics based on a more or less abstract notion of distance is not a new idea in nonclassical logics. The best known example is perhaps the Stalnaker/Lewis distance semantics for counterfactual conditionals, see e.g. [Lew73] . The AGM framework, defined in [AGM85], studies revision operations, denoted * , that operate on two arguments: a set K of formulas closed under logical deduction on the left and a formula α on the right. Thus K * α is the result of revising theory K by formula α, using revision method * . Our base logic will be classical propositional logic, though our main results are purely algebraic in nature, and therefore carry over to other logics, too. By abuse of language, we call a language finite whose set of propositional variables is finite. A theory will be an arbitrary set of formulas, not necessarily deductively closed. We use the customary notation Cn(T ) for the set of all logical consequences of a theory T. Cn(T, α) will stand for Cn(T ∪ {α}). Con(T ) will stand for: T is (classically) consistent, Con(T, T ′ ) abbreviates Con(T ∪ T ′ ). |= will be classical validity, and |= T ↔ T ′ will abbreviate the obvious: |= T → φ ′ for all φ ′ ∈ T ′ and |= T ′ → φ for all φ ∈ T. Given a propositional language L, M L will be the set of its models. M(T ) will be the models of a theory T (likewise M(φ) for a formula φ), and T h(X) the set of formulas valid in a set of models X. T ∨ T ′ := {φ ∨ φ ′ : φ ∈ T, φ ′ ∈ T ′ }. P will be the power set operator. The logical connectives ∧ and ∨ and the set connectives ∩ and ∪ always have precedence over the revision and set operators * and | . Numbering of conditions: (| i) will number conditions common to the symmetric and the not necessarily symmetric set operators |, (| Si) and (| Ai) conditions for respectively the symmetric and the not necessarily symmetric set operator | . ( * i), ( * Si), ( * Ai) will do the same for the theory revision operator * . The original AGM rationality postulates are the following, for K a deductively closed set of formulas, and α, β formulas. We prefer to modify slightly the original AGM formalism on two accounts. First, it seems to us that the difference required in the types of the two arguments of a revision: the left argument being a theory and the right argument being a formula is not founded. The lack of symmetry is twofold: the left-hand argument, being a theory, may be inherently infinite and not representable by a single formula while the right-hand argument is always a single formula, but also the left-hand argument is not an arbitrary set of formulas, but closed under logical implication, whereas the right-hand argument is not deductively closed, thus requiring Postulate K * 6 to assert invariance under logical equivalence. There is no serious reason for this lack of symmetry. We shall therefore prefer a formalism that is symmetric in both arguments. Our results for symmetric pseudo-distances are valid for infinite sets, our results for not necessarily symmetric pseudo-distances have been proved only for finite sets -where sets are to be understood as sets of models. The latter are thus proved for languages based on a finite set of propositional variables only. We therefore choose a formalism in which both arguments of the revision operator are theories, which, in the not necessarily symmetric case, will be assumed to be equivalent to single formulas. We thus look at T * T ′ , the theory that is the result of revising theory T by the new information represented by theory T ′ . Secondly, in the AGM formalism, each one of the theory K and the formula α may be inconsistent. There is no harm in doing so, but the interesting revisions are always revisions of consistent theories by consistent formulas and the consideration of inconsistent arguments makes the treatment unnecessarily clumsy. Therefore, we shall only revise consistent theories by consistent theories, and assume both arguments are consistent. The AGM postulates may now be rewritten in the following way. We rewrite K * 3 and K * 4 in one single postulate, ( * 3), and similarly for K * 7 and K * 8, in ( * 4). K * 1 and K * 5 are summarized in our general prerequisite and ( * 1). Remember that T, T ′ , T ′′ , S, S ′ are now arbitrary consistent theories. Revision based on pseudo-distances We will base our semantics for revision on pseudo-distances between models. Pseudodistances differ from distances in that their values are not necessarily reals, no addition of values has to be defined, and symmetry need not hold. All we need is a totally ordered set of values. If there is a minimal element 0 such that d(x, y) = 0 iff x = y, we say that d respects identity. Pseudo-distances which do not respect identity have their interest in situations where staying the same requires effort. We first recollect: A binary relation ≤ on X is a preorder, iff ≤ is reflexive and transitive. If ≤ is in addition total, i.e. iff ∀x, y ∈ X x ≤ y or y ≤ x, then ≤ is a total preorder. A binary relation < on X is a total order, iff < is transitive, irreflexive, i.e. x < x for all x ∈ X, and for all x, y ∈ X x < y or y < x or x = y. Note 1.1: If ≤ is a total preorder on X, ≈ the corresponding equivalence relation defined by x ≈ y iff x ≤ y and y ≤ x, [x] the ≈ -equivalence class of x, and we define [x] < [y] iff x ≤ y, but not y ≤ x, then < is a total order on {[x] : x ∈ X}. Definition 1.4 d : U × U → Z is called a pseudo-distance on U iff (d1) holds: (d1) Z is totally ordered by a relation < . If, in addition, Z has a < -smallest element 0, and (d2) holds, we say that d respects identity: 7 Note that we can force the triangle inequality to hold trivially (if we can choose the values in the real numbers): It suffices to choose the values in the set {0} ∪ [0.5, 1], i.e. in the interval from 0.5 to 1, or as 0. Recall that our main representation results are purely algebraic, and apply to arbitrary sets U, which need not necessarily be sets of models. Intuitively however, U is to be understood as the set of models for some language L, and the distance from m to n, d(m, n) represents the "cost" or the "difficulty" of a change from the situation represented by m to the situation represented by n. M. Dalal [Dal88] has considered one such distance: the distance between two propositional worlds is the number of atomic propositions on which they differ, i.e., the Hamming distance between worlds considered as binary kdimensional vectors, where k is the number of atomic propositional variables. A. Borgida [Bor85] considered a similar but different distance, based on set inclusion. His distances are not totally ordered and therefore the framework presented here does not fit his work. Another example of such a distance is the trivial distance: d(m, n) is 0 if m = n and 1 otherwise. Both those distances satisfy the triangular inequality. In applications dealing with reasoning about actions and change, one may want to consider the distance between two models to represent how difficult, or unexpected, the transition is. In such a case, a natural pseudo-distance may well not be symmetric. We give the formal definition of the elements of B d-closest to A: Definition 1.5 may be presented in a slightly different light. be the set of all minimal elements (under <) of the set A × B. Then, A | d B is nothing else than the right projection (on B) of A × B. Thus, A | d B is the subset of B consisting of all b ∈ B that are closest to A. Note that, if A or B is infinite, A | d B may be empty, even if A and B are not empty. A condition assuring non-emptiness will be imposed when necessary. The aim of Section 2 of this article is to characterize those operators |: P(U) × P(U) → P(U), for which there is a pseudo-distance d, such that A | B = A | d B. We call such | representable: unanswered the question of the nature of the dependence of the revision T * T ′ on its left argument, T . Since we, like most researchers in Artificial Intelligence, are mostly interested in iterated revisions, proper understanding, and semantics, for this dependence is crucial. The purpose of this paper is to answer the question by proposing a suitable semantics. We completely characterize the semantics by a set of postulates. We do not claim that the semantics proposed are the most general ones, we present one family of reasonable semantics, based on pseudo-distances between models. The following is the central definition, it describes the way a revision * d is attached to a pseudo-distance d on the set of models. ). * is called representable iff there is a pseudo-distance d on the set of models s.t. The main goal of this work is to characterize the properties, i.e., rationality postulates satisfied by revisions representable by pseudo-distances. Revision based on pseudo-distances and the AGM postulates The AGM postulates hold for revision based on pseudo-distances in the finite case Definition 1.8 An operation | on the sets of models of some logic is called definability preserving iff M(T ) | M(T ′ ) is again the set of models of some theory S for all theories T, T ′ . Abstractly, definability preservation strongly couples proof theory and semantics. To obtain the same kind of results without definability preservation, we would have to allow a "decoupling" on a "small" set of exceptions. This is illustrated e.g. by the results in The same proof shows that the AGM postulates also hold in the infinite case, if the operation | is definability preserving, and if we impose a limit condition for postulate ( * 1). ( * 0) is evident, as we work with models.
Independently, the authors presented, in REF , a preliminary version of the results given in this paper.
Distance Semantics for Belief Revision
Journal of Symbolic Logic, Vol. 66 No.1 (March 2001) pp. 295-317
Computer Science Mathematics