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.
Contents
- Revision and update
- Example
- Contraction expansion revision consolidation and merging
- The AGM postulates
- Conditions equivalent to the AGM postulates
- Contraction
- The Ramsey test
- Non monotonic inference relation
- Foundational revision
- Model based revision and update
- Iterated revision
- Merging
- Social choice theory
- Complexity
- Implementations
- References
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 "
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
This example shows that revising the belief
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 the names of 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
- Closure:
K ∗ P is a belief base (i.e., a deductively closed set of formulae); - Success:
P ∈ K ∗ P - Inclusion:
K ∗ P ⊆ K + P - Vacuity:
If ( ¬ P ) ∉ K , then K ∗ P = K + P -
K ∗ P is inconsistent only ifP is inconsistent orK is inconsistent - Extensionality:
If P and Q are logically equivalent, then K ∗ P = K ∗ Q (see logical equivalence) -
K ∗ ( P ∧ Q ) ⊆ ( K ∗ P ) + Q -
If ( ¬ Q ) ∉ K ∗ P then ( K ∗ P ) + Q ⊆ K ∗ ( P ∧ Q )
A revision operator that satisfies all eight postulates is the full meet revision, in which
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
A preference ordering
Contraction
Contraction is the operation of removing a belief
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
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
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
Non-monotonic inference relation
Given a fixed knowledge base
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 bases should be considered equal when revising. This is called the principle of irrelevance of syntax.
This principle has been and is currently debated: while
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 bases typically select some subsets of
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 worlds, 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 and update
A number of proposals for revision and update based on the set of models of the involved formulae were developed independently of the AGM framework. The principle behind this approach is that a knowledge base is equivalent to a set of possible worlds, that is, to a set of scenarios that are considered possible according to that knowledge base. Revision can therefore be performed on the sets of possible worlds rather than on the corresponding knowledge bases.
The revision and update operators based on models are usually identified by the name of their authors: Winslett, Forbus, Satoh, Dalal, Hegner, and Weber. According to the first four of these proposal, the result of revising/updating a formula
The revision operator defined by Hegner makes
Iterated revision
The AGM postulates are equivalent to a preference ordering (an ordering over models) to be associated to every knowledge base
Establishing a relation between the ordering associated with
Given that a preference ordering allows deriving its associated knowledge base but also allows performing a single step of revision, studies on iterated revision have been concentrated on how a preference ordering should be changed in response of a revision. While single-step revision is about how a knowledge base
Two kinds of preference ordering are usually considered: numerical and non-numerical. In the first case, the level of plausibility of a model is representing by a non-negative integer number; the lower the rank, the more plausible the situation corresponding to the model. Non-numerical preference orderings correspond to the preference relations used in the AGM framework: a possibly total ordering over models. The non-numerical preference relation were initially considered unsuitable for iterated revision because of the impossibility of reverting a revision by a number of other revisions, which is instead possible in the numerical case.
Darwiche and Pearl formulated the following postulates for iterated revision.
- if
α ⊨ μ then( ψ ∗ μ ) ∗ α ≡ ψ ∗ α ; - if
α ⊨ ¬ μ , then( ψ ∗ μ ) ∗ α ≡ ψ ∗ α ; - if
ψ ∗ α ⊨ μ , then( ψ ∗ μ ) ∗ α ⊨ μ ; - if
ψ ∗ α ⊭ ¬ μ , then( ψ ∗ μ ) ∗ α ⊭ ¬ μ .
Specific iterated revision operators have been proposed by Spohn, Boutilier, Williams, Lehmann, and others.
Merging
The assumption implicit in the revision operator is that the new piece of information
While the input to the revision process is a pair of formulae
When merging a number of knowledge bases with the same degree of plausibility, a distinction is made between arbitration and majority. This distinction depends on the assumption that is made about the information and how it has to be put together.
The above is the original definition of arbitration. According to a newer definition, an arbitration operator is a merging operator that is insensitive to the number of equivalent knowledge bases to merge. This definition makes arbitration the exact opposite of majority.
Postulates for both arbitration and merging have been proposed. An example of an arbitration operator satisfying all postulates is the classical disjunction. An example of a majority operator satisfying all postulates is that selecting all models that have a minimal total Hamming distance to models of the knowledge bases to merge.
A merging operator can be expressed as a family of orderings over models, one for each possible multiset of knowledge bases to merge: the models of the result of merging a multiset of knowledge bases are the minimal models of the ordering associated to the multiset. A merging operator defined in this way satisfies the postulates for merging if and only if the family of orderings meets a given set of conditions. For the old definition of arbitration, the orderings are not on models but on pairs (or, in general, tuples) of models.
Social choice theory
Many revision proposals involve orderings over models representing the relative plausibility of the possible alternatives. The problem of merging amounts to combine a set of orderings into a single one expressing the combined plausibility of the alternatives. This is similar with what is done in social choice theory, which is the study of how the preferences of a group of agents can be combined in a rational way. Belief revision and social choice theory are similar in that they combine a set of orderings into one. They differ on how these orderings are interpreted: preferences in social choice theory; plausibility in belief revision. Another difference is that the alternatives are explicitly enumerated in social choice theory, while they are the propositional models over a given alphabet in belief revision.
Complexity
The problem about belief revision that is the most studied from the point of view of computational complexity is that of query answering in the propositional case. This is the problem of establishing whether a formula follows from the result of a revision, that is,
Since a deductively closed knowledge base is infinite, complexity studies on belief revision operators working on deductively closed knowledge bases are done in the assumption that such deductively closed knowledge base are given in the form of an equivalent finite knowledge base.
A distinction is made among belief revision operators and belief revision schemes. While the former are simple mathematical operators mapping a pair of formulae into another formula, the latter depend on further information such as a preference relation. For example, the Dalal revision is an operator because, once two formulae
The complexity of query answering and model checking in the propositional case is in the second level of the polynomial hierarchy for most belief revision operators and schemas. Most revision operators suffer from the problem of representational blow up: the result of revising two formulae is not necessarily representable in space polynomial in that of the two original formulae. In other words, revision may exponentially increase the size of the knowledge base.
Implementations
Systems specifically implementing belief revision are: Immortal, SATEN, and BReLS. Two systems including a belief revision feature are SNePS and Cyc. Truth maintenance systems are used in Artificial Intelligence to implement belief revision.