Belief Change in Branching Time: AGM-consistency and Iterated Revision

We study belief change in the branching-time structures introduced in Bonanno (Artif Intell 171:144–160, 2007). First, we identify a property of branching-time frames that is equivalent (when the set of states is finite) to AGM-consistency, which is defined as follows. A frame is AGM-consistent if the partial belief revision function associated with an arbitrary state-instant pair and an arbitrary model based on that frame can be extended to a full belief revision function that satisfies the AGM postulates. Second, we provide a set of modal axioms that characterize the class of AGM-consistent frames within the modal logic introduced in Bonanno (Artif Intell 171:144–160, 2007). Third, we introduce a generalization of AGM belief revision functions that allows a clear statement of principles of iterated belief revision and discuss iterated revision both semantically and syntactically.     

Iterated Belief Revision and Conditional Logic

In this paper we propose a conditional logic called IBC to represent iterated belief revision systems. We propose a set of postulates for iterated revision which are a small variant of Darwiche and Pearl's ones. The conditional logic IBC has a standard semantics in terms of selection function models and provides a natural representation of epistemic states. We establish a correspondence between iterated belief revision systems and IBC-models. Our representation theorem does not entail Gärdenfors' Triviality Result.     

Some Logics of Iterated Belief Change

The problems that surround iterated contractions and expansions of beliefs are approached by studying hypertheories, a generalisation of Adam Grove's notion of systems of spheres. By using a language with dynamic and doxastic operators different ideas about the basic nature of belief change are axiomatised. It is shown that by imposing quite natural constraints on how hypertheories may change, the basic logics for belief change can be strengthened considerably to bring one closer to a theory of iterated belief change. It is then argued that the logic of expansion, in particular, cannot without loss of generality be strengthened any further to allow for a full logic of iterated belief change. To remedy this situation a notion of directed expansion is introduced that allows for a full logic of iterated belief change. The new operation is given an axiomatisation that is complete for linear hypertheories.     

The Relevance of Logic to Reasoning and Beleif Revision: Harman on 'Change in View'

In Change of View: Principles of Reasoning , Gilbert Harman argues that (i) all genuine reasoning is a matter of belief revision, and that, since (ii) logic is not "specially relevant" to belief revision, (iii) logic is not specially relevant to reasoning, either. Thus, Harman suggests, what is needed is a "theory of reasoning"–which, incidentally, will be psychologistic, telling us both how we do and how we should reason. I argue that Harman fails to establish the need for such a theory, because (a) reasoning is not always a matter of belief revision, and (b) logic is, in fact, of the utmost relevance to both reasoning and belief revision.     

Revision algebra semantics for conditional logic

The properties of belief revision operators are known to have an informal semantics which relates them to the axioms of conditional logic. The purpose of this paper is to make this connection precise via the model theory of conditional logic. A semantics for conditional logic is presented, which is expressed in terms of algebraic models constructed ultimately out of revision operators. In addition, it is shown that each algebraic model determines both a revision operator and a logic, that are related by virtue of the stable Ramsey test.The author is grateful for a correction and several other valuable suggestions of two anonymous referees. This work was supported by the McDonnell Douglas Independent Research and Development program.     

Coherence and Conservatism in the Dynamics of Belief

In this paper I discuss the foundations of a formal theory of coherent and conservative belief change that is (a) suitable to be used as a method for constructing iterated changes of belief, (b) sensitive to the history of earlier belief changes, and (c) independent of any form of dispositional coherence. I review various ways to conceive the relationship between the beliefs actually held by an agent and her belief change strategies (that also deal with potential belief sets), show the problems they suffer from, and suggest that belief states should be represented by unary revision functions that take sequences of inputs. Three concepts of coherence implicit in current theories of belief change are distinguished: synchronic, diachronic and dispositional coherence. Diachronic coherence is essentially identified with what is known as conservatism in epistemology. The present paper elaborates on the philosophical motivation of the general framework; formal details and results are provided in a companion paper.     

Towards a “Sophisticated” Model of Belief Dynamics. Part II: Belief Revision.

In the companion paper (Towards a “sophisticated” model of belief dynamics. Part I), a general framework for realistic modelling of instantaneous states of belief and of the operations involving them was presented and motivated. In this paper, the framework is applied to the case of belief revision. A model of belief revision shall be obtained which, firstly, recovers the Gärdenfors postulates in a well-specified, natural yet simple class of particular circumstances; secondly, can accommodate iterated revisions, recovering several proposed revision operators for iterated revision as special cases; and finally, offers an analysis of Rott’s recent counterexample to several Gärdenfors postulates [32], elucidating in what sense it fails to be one of the special cases to which these postulates apply.     

Iterated revision and minimal change of conditional beliefs

We describe a model of iterated belief revision that extends the AGM theory of revision to account for the effect of a revision on the conditional beliefs of an agent. In particular, this model ensures that an agent makes as few changes as possible to the conditional component of its belief set. Adopting the Ramsey test, minimal conditional revision provides acceptance conditions for arbitrary right-nested conditionals. We show that problem of determining acceptance of any such nested conditional can be reduced to acceptance tests for unnested conditionals. Thus, iterated revision can be accomplished in a virtual manner, using uniterated revision.     

Interrogative Belief Revision Based on Epistemic Strategies

I develop a dynamic logic for reasoning about ??interrogative belief revision??, a new branch of belief revision theory that has been developed in a small number of papers, beginning with E. J. Olsson and D. Westlund??s paper ??On the role of the research agenda in epistemic change?? [12]. In interrogative belief revision, epistemic states are taken to include a research agenda, consisting of questions the agent seeks to answer. I present a logic for revision of such epistemic states based on the notion of an epistemic strategy, a stable plan of action that determines changes in the agent??s research agenda. This idea is a further development of an idea put forward in [6], that changes in the research agenda of an agent should be determined by stable, ??long term?? research interests. I provide complete axioms and a decidability result for the logic.     

Iterated Belief Revision

This is a discussion of the problem of extending the basic AGM belief revision theory to iterated belief revision: the problem of formulating rules, not only for revising a basic belief state in response to potential new information, but also for revising one’s revision rules in response to potential new information. The emphasis in the paper is on foundational questions about the nature of and motivation for various constraints, and about the methodology of the evaluation of putative counterexamples to proposed constraints. Some specific constraints that have been proposed are criticized. The paper emphasizes the importance of meta-information—information about one’s sources of information—and argues that little of substance can be said about constraints on iterated belief revision at a level of abstraction that lacks the resources for explicit representation of meta-information.

---

Global and Iterated Contraction and Revision: An Exploration of Uniform and Semi-Uniform Approaches

In order to clarify the problems of iterated (global) belief change it is useful to study simple cases, in particular consecutive contractions by sentences that are both logically and epistemically independent. Models in which the selection mechanism is kept constant are much more plausible in this case than what they are in general. One such model, namely uniform specified meet contraction, has the advantage of being closely connected with the AGM model. Its properties seem fairly adequate for the intended type of contraction. However, the revision operator based on it via the Levi identity collapses into an implausible operation that loses all old information when revising by new information. A weaker version, semi-uniform specified meet contraction, avoids the collapse but has the disadvantage of a remarkably weak logic. It is left as an open issue whether there is an intermediate class of contraction operators that yields a more satisfactory logic.     

A NEW REVISABILITY PARADOX

Abstract:  In a recent article, Mark Colyvan has criticized Jerrold Katz's attempt to show that Quinean holism is self-refuting. Katz argued that a Quinean epistemology incorporating a principle of the universal revisability of beliefs would have to hold that that and other principles of the system were both revisable and unrevisable. Colyvan rejects Katz's argument for failing to take into account the logic of belief revision. But granting the terms of debate laid down by Colyvan, the universal revisability principle still commits Quineans to holding that one belief is both revisable and unrevisable: the belief that some beliefs are revisable.     

Preference-based belief revision for rule-based agents

Agents which perform inferences on the basis of unreliable information need an ability to revise their beliefs if they discover an inconsistency. Such a belief revision algorithm ideally should be rational, should respect any preference ordering over the agent’s beliefs (removing less preferred beliefs where possible) and should be fast. However, while standard approaches to rational belief revision for classical reasoners allow preferences to be taken into account, they typically have quite high complexity. In this paper, we consider belief revision for agents which reason in a simpler logic than full first-order logic, namely rule-based reasoners. We show that it is possible to define a contraction operation for rule-based reasoners, which we call McAllester contraction, which satisfies all the basic Alchourrón, Gärdenfors and Makinson (AGM) postulates for contraction (apart from the recovery postulate) and at the same time can be computed in polynomial time. We prove a representation theorem for McAllester contraction with respect to the basic AGM postulates (minus recovery), and two additional postulates. We then show that our contraction operation removes a set of beliefs which is least preferred, with respect to a natural interpretation of preference. Finally, we show how McAllester contraction can be used to define a revision operation which is also polynomial time, and prove a representation theorem for the revision operation.     

Reapproaching Ramsey: Conditionals and Iterated Belief Change in the Spirit of AGM

According to the Ramsey Test, conditionals reflect changes of beliefs: α?>?β is accepted in a belief state iff β is accepted in the minimal revision of it that is necessary to accommodate α. Since Gärdenfors’s seminal paper of 1986, a series of impossibility theorems (“triviality theorems”) has seemed to show that the Ramsey test is not a viable analysis of conditionals if it is combined with AGM-type belief revision models. I argue that it is possible to endorse that Ramsey test for conditionals while staying true to the spirit of AGM. A main focus lies on AGM’s condition of Preservation according to which the original belief set should be fully retained after a revision by information that is consistent with it. I use concrete representations of belief states and (iterated) revisions of belief states as semantic models for (nested) conditionals. Among the four most natural qualitative models for iterated belief change, two are identified that indeed allow us to combine the Ramsey test with Preservation in the language containing only flat conditionals of the form α?>?β. It is shown, however, that Preservation for this simple language enforces a violation of Preservation for nested conditionals of the form α?>?(β?>?γ). In such languages, no two belief sets are ordered by strict subset inclusion. I argue that it has been wrong right from the start to expect that Preservation holds in languages containing nested conditionals.     

Iterated Belief Change and the Recovery Axiom

The axiom of recovery, while capturing a central intuition regarding belief change, has been the source of much controversy. We argue briefly against putative counterexamples to the axiom—while agreeing that some of their insight deserves to be preserved—and present additional recovery-like axioms in a framework that uses epistemic states, which encode preferences, as the object of revisions. This makes iterated revision possible and renders explicit the connection between iterated belief change and the axiom of recovery. We provide a representation theorem that connects the semantic conditions we impose on iterated revision and our additional syntactical properties. We show interesting similarities between our framework and that of Darwiche–Pearl (Artificial Intelligence 89:1–29 1997). In particular, we show that intuitions underlying the controversial (C2) postulate are captured by the recovery axiom and our recovery-like postulates (the latter can be seen as weakenings of (C2)). We present postulates for contraction, in the same spirit as the Darwiche–Pearl postulates for revision, and provide a theorem that connects our syntactic postulates with a set of semantic conditions. Lastly, we show a connection between the contraction postulates and a generalisation of the recovery axiom. Portions of this paper were originally presented at ECAI 2002.     

Interrogative Belief Revision in Modal Logic

The well known AGM framework for belief revision has recently been extended to include a model of the research agenda of the agent, i.e. a set of questions to which the agent wishes to find answers (Olsson & Westlund in Erkenntnis, 65, 165–183, 2006). The resulting model has later come to be called interrogative belief revision. While belief revision has been studied extensively from the point of view of modal logic, so far interrogative belief revision has only been dealt with in the metalanguage approach in which AGM was originally presented. In this paper, I show how to model interrogative belief revision in a modal object language using a class of operators for questions. In particular, the solution I propose will be shown to capture the notion of K-truncation, a method for agenda update in the case of expansion constructed by Olsson & Westlund. Two case studies are conducted: first, an interrogative extension of Krister Segerberg’s system DDL, and then a similar extension of Giacomo Bonanno’s modal logic for belief revision. Sound and complete axioms will be provided for both of the resulting logics.     

Iterated belief change based on epistemic entrenchment

In this paper it is argued that, in order to solve the problem of iterated belief change, both the belief state and its input should be represented as epistemic entrenchment (EE) relations. A belief revision operation is constructed that updates a given EE relation to a new one in light of an evidential EE relation. It is shown that the operation in question satisfies generalized versions of the Gärdenfors revision postulates. The account offered is motivated by Spohn's ordinal conditionalization functions, and can be seen as the Jeffrization of a proposal considered by Rott.I am indebted John G. Bennett and Henry E. Kyburg. jr. for their insightful comments on an earlier draft of this paper. I thank the referees forErkenntnis who, apart from giving extended comments and suggestions, provided me with some hard-to-find relevant material. I also thank Prashanta Bandyopadhyay, Norman Foo, Maurice Pagnucco, Hans Rott and Mary-Anne Williams for their suggestions. The errors that remain are, of course, mine.     

A Counterexample to Six Fundamental Principles of Belief Formation

In recent years there has been a growing consensus that ordinary reasoning does not conform to the laws of classical logic, but is rather nonmonotonic in the sense that conclusions previously drawn may well be removed upon acquiring further information. Even so, rational belief formation has up to now been modelled as conforming to some fundamental principles that are classically valid. The counterexample described in this paper suggests that a number of the most cherished of these principles should not be regarded as valid for commonsense reasoning. An explanation of this puzzling failure is given, arguing that a problem in the theory of rational choice transfers to the realm of belief formation.     

The Rôle of Language In Belief Revision

Analytical tools that give precision to the concept of "independence of syntax" are developed in the form of a series of substitutivity principles. These principles are applied in a study of the rôle of language in belief revision theory. It is shown that sets of sentences can be used in models of belief revision to convey more information than what is conveyed by the combined propositional contents of the respective sets. It is argued that it would be unwise to programmatically restrain the use of sets of sentences to that of representing propositional contents. Instead, the expressive power of language should be used as fully as possible. Therefore, syntax-independence should not be seen as a criterion of adequacy for language-based models of information-processing, but rather as a property that emerges from some but not all the idealization processes through which such models are constructed.