Belief Revision - Iterated Revision

Iterated Revision

The AGM postulates are equivalent to a preference ordering (an ordering over models) to be associated to every knowledge base . However, they do not relate the orderings corresponding to two non-equivalent knowledge bases. In particular, the orderings associated to a knowledge base and its revised version can be completely different. This is a problem for performing a second revision, as the ordering associated with is necessary to calculate .

Establishing a relation between the ordering associated with and has been however recognized not to be the right solution to this problem. Indeed, the preference relation should depend on the previous history of revisions, rather than on the resulting knowledge base only. More generally, a preference relation gives more information about the state of mind of an agent than a simple knowledge base. Indeed, two states of mind might represent the same piece of knowledge while at the same time being different in the way a new piece of knowledge would be incorporated. For example, two people might have the same idea as to where to go on holiday, but yet they differ on how they would change this idea if they win a million-dollar lottery. Since the basic condition of the preference ordering is that their minimal models are exactly the models of their associated knowledge base, a knowledge base can be considered implicitly represented by a preference ordering (but not vice versa).

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 has to be changed into a new knowledge base, iterated revision is about how a preference ordering (representing both the current knowledge and how much situations believed to be false are considered possible) should be turned into a new preference relation when is learned. A single step of iterated revision produces a new ordering that allows for further revisions.

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.

1. if then ;
2. if, then ;
3. if, then ;
4. if, then .

Specific iterated revision operators have been proposed by Spohn, Boutilier, Williams, Lehmann, and others.

Spohn rejected revision

this non-numerical proposal has been first considered by Spohn, who rejected it based on the fact that revisions can change some orderings in such a way the original ordering cannot be restored with a sequence of other revisions; this operator change a preference ordering in view of new information by making all models of being preferred over all other models; the original preference ordering is maintained when comparing two models that are both models of or both non-models of ;

Natural revision

while revising a preference ordering by a formula, all minimal models (according to the preference ordering) of are made more preferred by all other ones; the original ordering of models is preserved when comparing two models that are not minimal models of ; this operator changes the ordering among models minimally while preserving the property that the models of the knowledge base after revising by are the minimal models of according to the preference ordering;

Transmutations

these are two forms of revision, conditionalization and adjustment, which work on numerical preference orderings; revision requires not only a formula but also a number indicating its degree of plausibility; while the preference ordering is still inverted (the lower a model, the most plausible it is) the degree of plausibility of a revising formula is direct (the higher the degree, the most believed the formula is);

Ranked revision

a ranked model, which is an assignment of non-negative integers to models, has to be specified at the beginning; this rank is similar to a preference ordering, but is not changed by revision; what is changed by a sequence of revisions are a current set of models (representing the current knowledge base) and a number called the rank of the sequence; since this number can only monotonically non-decrease, some sequences of revision lead to situations in which every further revision is performed as a full meet revision.