Process of changing beliefs to take into account a new piece of information
Belief revision (also called belief change) 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 "formula_1 is true", "formula_2 is true" and "if formula_1 and formula_2 are true then formula_5 is true", the introduction of the new information "formula_5 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:
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 formula_7 and the new piece of information formula_8:
This example shows that revising the belief formula_19 with the new information formula_8 produces two different results formula_21 and formula_18 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:
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 (named after their proponents Alchourrón, Gärdenfors, and Makinson) 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 (addition of a belief without a consistency check), revision (addition of a belief while maintaining consistency), and contraction (removal of a belief).
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 formula_23 called belief set, the new piece of information is a logical formula formula_24, and revision is performed by a binary operator formula_25 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 formula_26 operator denoted expansion: formula_27 is the deductive closure of formula_28. The AGM postulates for revision are:
A revision operator that satisfies all eight postulates is the full meet revision, in which formula_29 is equal to formula_27 if consistent, and to the deductive closure of formula_24 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 formula_25 satisfying the AGM postulates is associated to a set of preference relations formula_42, one for each possible belief set formula_23, such that the models of formula_23 are exactly the minimal of all models according to formula_42. The revision operator and its associated family of orderings are related by the fact that formula_29 is the set of formulae whose set of models contains all the minimal models of formula_24 according to formula_42. This condition is equivalent to the set of models of formula_29 being exactly the set of the minimal models of formula_24 according to the ordering formula_42.
A preference ordering formula_42 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, formula_53 indicates that the situation represented by the model formula_54 is believed to be more plausible than the situation represented by formula_55. As a result, revising by a formula having formula_54 and formula_55 as models should select only formula_54 to be a model of the revised knowledge base, as this model represent the most likely scenario among those supported by formula_24.
Contraction.
Contraction is the operation of removing a belief formula_24 from a knowledge base formula_23; the result of this operation is denoted by formula_62. The operators of revision and contractions are related by the Levi and Harper identities:
 formula_63
 formula_64
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:
 formula_65
According to this postulate, the removal of a belief formula_24 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 formula_19 leads to the removal of more specific conditions such as formula_9 from the belief set; it is then unclear why the reintroduction of formula_19 should also lead to the reintroduction of the more specific condition formula_9. 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.
The Ramsey test.
The evaluation of a counterfactual conditional formula_71 can be done, according to the Ramsey test (named for Frank P. Ramsey), to the hypothetical addition of formula_9 to the set of current beliefs followed by a check for the truth of formula_10. If formula_23 is the set of beliefs currently held, the Ramsey test is formalized by the following correspondence:
 formula_75 if and only if formula_76
If the considered language of the formulae representing beliefs is propositional, the Ramsey test gives a consistent definition for counterfactual conditionals in terms of a belief revision operator. However, if the language of formulae representing beliefs itself includes the counterfactual conditional connective formula_77, the Ramsey test leads to the Gärdenfors triviality result: there is no non-trivial revision operator that satisfies both the AGM postulates for revision and the condition of the Ramsey test. This result holds in the assumption that counterfactual formulae like formula_78 can be present in belief sets and revising formulae. Several solutions to this problem have been proposed.
Non-monotonic inference relation.
Given a fixed knowledge base formula_23 and a revision operator formula_25, one can define a non-monotonic inference relation using the following definition: formula_81 if and only if formula_82. In other words, a formula formula_24 entails another formula formula_84 if the addition of the first formula to the current knowledge base leads to the derivation of formula_84. This inference relation is non-monotonic.
The AGM postulates can be translated into a set of postulates for this inference relation. Each of these postulates is entailed by some previously considered set of postulates for non-monotonic inference relations. Vice versa, conditions that have been considered for non-monotonic inference relations can be translated into postulates for a revision operator. All these postulates are entailed by the AGM postulates.
Foundational revision.
In the AGM framework, a belief set is represented by a deductively closed set of propositional formulae. While such sets are infinite, they can always be finitely representable. However, working with deductively closed sets of formulae leads to the implicit assumption that equivalent belief sets should be considered equal when revising. This is called the "principle of irrelevance of syntax".
This principle has been and is currently debated: while formula_86 and formula_87 are two equivalent sets, revising by formula_8 should produce different results. In the first case, formula_9 and formula_10 are two separate beliefs; therefore, revising by formula_8 should not produce any effect on formula_10, and the result of revision is formula_93. In the second case, formula_94 is taken a single belief. The fact that formula_9 is false contradicts this belief, which should therefore be removed from the belief set. The result of revision is therefore formula_96 in this case.
The problem of using deductively closed knowledge bases is that no distinction is made between pieces of knowledge that are known by themselves and pieces of knowledge that are merely consequences of them. This distinction is instead done by the "foundational" approach to belief revision, which is related to foundationalism in philosophy. According to this approach, retracting a non-derived piece of knowledge should lead to retracting all its consequences that are not otherwise supported (by other non-derived pieces of knowledge). This approach can be realized by using knowledge bases that are not deductively closed and assuming that all formulae in the knowledge base represent self-standing beliefs, that is, they are not derived beliefs. In order to distinguish the foundational approach to belief revision to that based on deductively closed knowledge bases, the latter is called the "coherentist" approach. This name has been chosen because the coherentist approach aims at restoring the coherence
(consistency) among "all" beliefs, both self-standing and derived ones. This approach is related to coherentism in philosophy.
Foundationalist revision operators working on non-deductively closed belief sets typically select some subsets of formula_23 that are consistent with formula_24, combined them in some way, and then conjoined them with formula_24. The following are two non-deductively closed base revision operators.
A different realization of the foundational approach to belief revision is based on explicitly declaring the dependences among beliefs. In the truth maintenance systems, dependence links among beliefs can be specified. In other words, one can explicitly declare that a given fact is believed because of one or more other facts; such a dependency is called a "justification". Beliefs not having any justifications play the role of non-derived beliefs in the non-deductively closed knowledge base approach.
Model-based revision