Belief revision


Belief revision is the process of changing beliefs to take into account a new piece of information. The logical formalization of belief revision is researched in philosophy, in databases, and in artificial intelligence for the design of rational agents.
What makes belief revision non-trivial is that several different ways for performing this operation may be possible. For example, if the current knowledge includes the three facts " is true", " is true" and "if and are true then is true", the introduction of the new information " is false" can be done preserving consistency only by removing at least one of the three facts. In this case, there are at least three different ways for performing revision. In general, there may be several different ways for changing knowledge.

Revision and update

Two kinds of changes are usually distinguished:
; update : the new information is about the situation at present, while the old beliefs refer to the past; update is the operation of changing the old beliefs to take into account the change;
; revision : both the old beliefs and the new information refer to the same situation; an inconsistency between the new and old information is explained by the possibility of old information being less reliable than the new one; revision is the process of inserting the new information into the set of old beliefs without generating an inconsistency.
The main assumption of belief revision is that of minimal change: the knowledge before and after the change should be as similar as possible. In the case of update, this principle formalizes the assumption of inertia. In the case of revision, this principle enforces as much information as possible to be preserved by the change.

Example

The following classical example shows that the operations to perform in the two settings of update and revision are not the same. The example is based on two different interpretations of the set of beliefs and the new piece of information :
; update : in this scenario, two satellites, Unit A and Unit B, orbit around Mars; the satellites are programmed to land while transmitting their status to Earth; and Earth has received a transmission from one of the satellites, communicating that it is still in orbit. However, due to interference, it is not known which satellite sent the signal; subsequently, Earth receives the communication that Unit A has landed. This scenario can be modeled in the following way: two propositional variables and indicate that Unit A and Unit B, respectively, are still in orbit; the initial set of beliefs is and the new piece of information is . The only rational result of the update is ; since the initial information that one of the two satellites had not landed yet was possibly coming from the Unit A, the position of the Unit B is not known.
; revision : the play "Six Characters in Search of an Author" will be performed in one of the two local theatres. This information can be denoted by, where and indicates that the play will be performed at the first or at the second theatre, respectively; a further information that "Jesus Christ Superstar" will be performed at the first theatre indicates that holds. In this case, the obvious conclusion is that "Six Characters in Search of an Author" will be performed at the second but not the first theatre, which is represented in logic by.
This example shows that revising the belief with the new information produces two different results and depending on whether the setting is that of update or revision.

Contraction, expansion, revision, consolidation, and merging

In the setting in which all beliefs refer to the same situation, a distinction between various operations that can be performed is made:
; contraction : removal of a belief;
; expansion : addition of a belief without checking consistency;
; revision : addition of a belief while maintaining consistency;
; extraction : extracting a consistent set of beliefs and/or epistemic entrenchment ordering;
; consolidation : restoring consistency of a set of beliefs;
; merging : fusion of two or more sets of beliefs while maintaining consistency.
Revision and merging differ in that the first operation is done when the new belief to incorporate is considered more reliable than the old ones; therefore, consistency is maintained by removing some of the old beliefs. Merging is a more general operation, in that the priority among the belief sets may or may not be the same.
Revision can be performed by first incorporating the new fact and then restoring consistency via consolidation. This is actually a form of merging rather than revision, as the new information is not always treated as more reliable than the old knowledge.

The AGM postulates

The AGM postulates are properties that an operator that performs revision should satisfy in order for that operator to be considered rational. The considered setting is that of revision, that is, different pieces of information referring to the same situation. Three operations are considered: expansion, revision, and contraction.
The first six postulates are called "the basic AGM postulates". In the settings considered by Alchourrón, Gärdenfors, and Makinson, the current set of beliefs is represented by a deductively closed set of logical formulae called belief set, the new piece of information is a logical formula, and revision is performed by a binary operator that takes as its operands the current beliefs and the new information and produces as a result a belief set representing the result of the revision. The operator denoted expansion: is the deductive closure of. The AGM postulates for revision are:
  1. Closure: is a belief set ;
  2. Success:
  3. Inclusion:
  4. Vacuity:
  5. Consistency: is inconsistent only if is inconsistent
  6. Extensionality:
  7. Superexpansion:
  8. Subexpansion:
A revision operator that satisfies all eight postulates is the full meet revision, in which is equal to if consistent, and to the deductive closure of otherwise. While satisfying all AGM postulates, this revision operator has been considered to be too conservative, in that no information from the old knowledge base is maintained if the revising formula is inconsistent with it.

Conditions equivalent to the AGM postulates

The AGM postulates are equivalent to several different conditions on the revision operator; in particular, they are equivalent to the revision operator being definable in terms of structures known as selection functions, epistemic entrenchments, systems of spheres, and preference relations. The latter are reflexive, transitive, and total relations over the set of models.
Each revision operator satisfying the AGM postulates is associated to a set of preference relations, one for each possible belief set, such that the models of are exactly the minimal of all models according to. The revision operator and its associated family of orderings are related by the fact that is the set of formulae whose set of models contains all the minimal models of according to. This condition is equivalent to the set of models of being exactly the set of the minimal models of according to the ordering.
A preference ordering represents an order of implausibility among all situations, including those that are conceivable but yet currently considered false. The minimal models according to such an ordering are exactly the models of the knowledge base, which are the models that are currently considered the most likely. All other models are greater than these ones and are indeed considered less plausible. In general, indicates that the situation represented by the model is believed to be more plausible than the situation represented by. As a result, revising by a formula having and as models should select only to be a model of the revised knowledge base, as this model represent the most likely scenario among those supported by.

Contraction

Contraction is the operation of removing a belief from a knowledge base ; the result of this operation is denoted by. The operators of revision and contractions are related by the Levi and Harper identities:
Eight postulates have been defined for contraction. Whenever a revision operator satisfies the eight postulates for revision, its corresponding contraction operator satisfies the eight postulates for contraction and vice versa. If a contraction operator satisfies at least the first six postulates for contraction, translating it into a revision operator and then back into a contraction operator using the two identities above leads to the original contraction operator. The same holds starting from a revision operator.
One of the postulates for contraction has been longly discussed: the recovery postulate:
According to this postulate, the removal of a belief followed by the reintroduction of the same belief in the belief set should lead to the original belief set. There are some examples showing that such behavior is not always reasonable: in particular, the contraction by a general condition such as leads to the removal of more specific conditions such as from the belief set; it is then unclear why the reintroduction of should also lead to the reintroduction of the more specific condition. For example, if George was previously believed to have German citizenship, he was also believed to be European. Contracting this latter belief amounts to ceasing to believe that George is European; therefore, that George has German citizenship is also retracted from the belief set. If George is later discovered to have Austrian citizenship, then the fact that he is European is also reintroduced. According to the recovery postulate, however, the belief that he also has German citizenship should also be reintroduced.
The correspondence between revision and contraction induced by the Levi and Harper identities is such that a contraction not satisfying the recovery postulate is translated into a revision satisfying all eight postulates, and that a revision satisfying all eight postulates is translated into a contraction satisfying all eight postulates, including recovery. As a result, if recovery is excluded from consideration, a number of contraction operators are translated into a single revision operator, which can be then translated back into exactly one contraction operator. This operator is the only one of the initial group of contraction operators that satisfies recovery; among this group, it is the operator that preserves as much information as possible.