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.     

Diagnostic reasoning with circumstantial evidence

Individuals often evaluate hypotheses about the cause of particular events on the basis of circumstantial evidence. This article describes a quantitative model of belief revision with circumstantial evidence. The model assumes that subjects revise belief on the basis of a cascaded reasoning process that combines beliefs about three premises—the association of a clue and a possible cause, and forward and backward implications of the clue—to revise belief in a causal hypothesis. Subjects in three experiments solved fictional murder mysteries, reporting on each trial a subset of the beliefs specified by the model. Experiment 1 demonstrates that the model provides a good account of the reasoning process, over several contexts in which clues are evaluated. Subjects appear to develop causal models that affect the interpretation of clues. Experiment 2 provides further evidence on the development of causal models and compares the present model with a model based on Bayes' theorem. Experiment 3 is a control experiment which demonstrates that the belief assessments used in Experiments 1 and 2 do not alter the process of belief revision. Tests of subjects' memory for suspect-clue associations provide further support for the hypothesis that subjects develop causal models of the true cause and demonstrate the contrast between reasoning with currently available information and retrospective access to the facts on which belief revision is based. The present view is compared with other theories of causal thinking and belief revision.     

Belief revision and uncertain reasoning

When a new piece of information contradicts a currently held belief, one has to modify the set of beliefs in order to restore its consistency. In the case where it is necessary to give up a belief, some of them are less likely to be abandoned than others. The concept of epistemic entrenchment is used by some AI approaches to explain this fact based on formal properties of the belief set (e.g., transitivity). Two experiments were designed to test the hypothesis that contrary to such views, (i) belief is naturally represented by degrees rather than in an all-or-nothing manner, (ii) entrenchment is primarily a matter of content and not only a matter of form, and (iii) consequently prior degree of belief is a powerful factor of change. The two experiments used Elio and Pelletier's (1997) paradigm in which participants were presented with full simple deductive arguments whose conclusion was denied, following which they were asked to decide which premise to revise.     

Belief change as change in epistemic entrenchment

In this paper, it is argued that 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, and an axiomatic characterization of this operation is given. Unlike most belief revision operations, the one developed here can handle both multiple belief revision and iterated belief revision.The authors are thankful to John G. Bennett, Henry E. Kyburg, Jr., Norman Foo, Pavlos Pepas, Maurizio Pagnucco, Bob Hadley, members of the Knowledge Systems Group at the University of Sydney and participants of the AI'93 workshop on Belief Revision: Bridging the Gap Between Theory and Practice at Melbourne where a version of this paper was presented, for their suggestions. The authors also express their gratitude to the two anonymous referees for Synthese for their excellent comments and suggestions. Of course it is only the authors that are responsible for the errors that remain.     

Belief Change as Propositional Update

This study examines the problem of belief revision, defined as deciding which of several initially accepted sentences to disbelieve, when new information presents a logical inconsistency with the initial set. In the first three experiments, the initial sentence set included a conditional sentence, a non-conditional (ground) sentence, and an inferred conclusion drawn from the first two. The new information contradicted the inferred conclusion. Results indicated that conditional sentences were more readily abandoned than ground sentences, even when either choice would lead to a consistent belief state, and that this preference was more pronounced when problems used natural language cover stories rather than symbols. The pattern of belief revision choices differed depending on whether the contradicted conclusion from the initial belief set had been a modus ponens or modus tollens inference. Two additional experiments examined alternative model-theoretic definitions of minimal change to a belief state, using problems that contained multiple models of the initial belief state and of the new information that provided the contradiction. The results indicated that people did not follow any of four formal definitions of minimal change on these problems. The new information and the contradiction it offered was not, for example, used to select a particular model of the initial belief state as a way of reconciling the contradiction. The preferred revision was to retain only those initial sentences that had the same, unambiguous truth value within and across both the initial and new information sets. The study and results are presented in the context of certain logic-based formalizations of belief revision, syntactic and model-theoretic representations of belief states, and performance models of human deduction. Principles by which some types of sentences might be more “entrenched” than others in the face of contradiction are also discussed from the perspective of induction and theory revision.     

Reversing the Levi identity

The AGM (Alchourrón-GÄrdenfors-Makinson) model of belief change is extended to cover changes on sets of beliefs that arenot closed under logical consequence (belief bases). Three major types of change operations, namely contraction, internal revision, and external revision are axiomatically characterized, and their interrelations are studied. In external revision, the Levi identity is reversed in the sense that onefirst adds the new belief to the belief base, and afterwards contracts its negation. It is argued that external revision represents an intuitively plausible way of revising one's beliefs. Since it typically involves the temporary acceptance of an inconsistent set of beliefs, it can only be used in belief representations that distinguish between different inconsistent sets of belief.     

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 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.     

Revising Beliefs Towards the Truth

Belief revision (BR) and truthlikeness (TL) emerged independently as two research programmes in formal methodology in the 1970s. A natural way of connecting BR and TL is to ask under what conditions the revision of a belief system by new input information leads the system towards the truth. It turns out that, for the AGM model of belief revision, the only safe case is the expansion of true beliefs by true input, but this is not very interesting or realistic as a model of theory change in science. The new accounts of non-prioritized belief revision do not seem more promising in this respect, and the alternative BR account of updating by imaging leads to other problems. Still, positive results about increasing truthlikeness by belief revision may be sought by restricting attention to special kinds of theories. Another approach is to link truthlikeness to epistemic matters by an estimation function which calculates expected degrees of truthlikeness relative to evidence. Then we can study how the expected truthlikeness of a theory changes when probabilities are revised by conditionalization or imaging. Again, we can ask under what conditions such changes lead our best theories towards the truth.     

Minimal Belief Change and the Pareto Principle

This paper analyzes the notion of a minimal belief change that incorporates new information. I apply the fundamental decision-theoretic principle of Pareto-optimality to derive a notion of minimal belief change, for two different representations of belief: First, for beliefs represented by a theory – a deductively closed set of sentences or propositions – and second for beliefs represented by an axiomatic base for a theory. Three postulates exactly characterize Pareto-minimal revisions of theories, yielding a weaker set of constraints than the standard AGM postulates. The Levi identity characterizes Pareto-minimal revisions of belief bases: a change of belief base is Pareto-minimal if and only if the change satisfies the Levi identity (for “maxichoice” contraction operators). Thus for belief bases, Pareto-minimality imposes constraints that the AGM postulates do not. The Ramsey test is a well-known way of establishing connections between belief revision postulates and axioms for conditionals (“if p, then q”). Pareto-minimal theory change corresponds exactly to three characteristic axioms of counterfactual systems: a theory revision operator that satisfies the Ramsey test validates these axioms if and only if the revision operator is Pareto-minimal. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

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.     

Towards a “Sophisticated” Model of Belief Dynamics. Part I: The General Framework

It is well-known that classical models of belief are not realistic representations of human doxastic capacity; equally, models of actions involving beliefs, such as decisions based on beliefs, or changes of beliefs, suffer from a similar inaccuracies. In this paper, a general framework is presented which permits a more realistic modelling both of instantaneous states of belief, and of the operations involving them. This framework is motivated by some of the inadequacies of existing models, which it overcomes, whilst retaining technical rigour in so far as it relies on known, natural logical and mathematical notions. The companion paper (Towards a “sophisticated” model of belief dynamics. Part II) contains an application of this framework to the particular case of belief revision. Presented by Hannes Leitgeb     

Contraction: On the Decision-Theoretical Origins of Minimal Change and Entrenchment

We present a decision-theoretically motivated notion of contraction which, we claim, encodes the principles of minimal change and entrenchment. Contraction is seen as an operation whose goal is to minimize loses of informational value. The operation is also compatible with the principle that in contracting A one should preserve the sentences better entrenched than A (when the belief set contains A). Even when the principle of minimal change and the latter motivation for entrenchment figure prominently among the basic intuitions in the works of, among others, Quine and Ullian (1978), Levi (1980, 1991), Harman (1988) and Gärdenfors (1988), formal accounts of belief change (AGM, KM – see Gärdenfors (1988); Katsuno and Mendelzon (1991)) have abandoned both principles (see Rott (2000)). We argue for the principles and we show how to construct a contraction operation, which obeys both. An axiom system is proposed. We also prove that the decision-theoretic notion of contraction can be completely characterized in terms of the given axioms. Proving this type of completeness result is a well-known open problem in the field, whose solution requires employing both decision-theoretical techniques and logical methods recently used in belief change.     

Severe Withdrawal (and Recovery)

The problem of how to remove information from an agent's stock of beliefs is of paramount concern in the belief change literature. An inquiring agent may remove beliefs for a variety of reasons: a belief may be called into doubt or the agent may simply wish to entertain other possibilities. In the prominent AGM framework for belief change, upon which the work here is based, one of the three central operations, contraction, addresses this concern (the other two deal with the incorporation of new information). Makinson has generalised this work by introducing the notion of a withdrawal operation. Underlying the account proffered by AGM is the idea of rational belief change. A belief change operation should be guided by certain principles or integrity constraints in order to characterise change by a rational agent. One of the most noted principles within the context of AGM is the Principle of Informational Economy. However, adoption of this principle in its purest form has been rejected by AGM leading to a more relaxed interpretation. In this paper, we argue that this weakening of the Principle of Informational Economy suggests that it is only one of a number of principles which should be taken into account. Furthermore, this weakening points toward a Principle of Indifference. This motivates the introduction of a belief removal operation that we call severe withdrawal. We provide rationality postulates for severe withdrawal and explore its relationship with AGM contraction. Moreover, we furnish possible worlds and epistemic entrenchment semantics for severe withdrawals.     

Revocable Belief Revision

Krister Segerberg proposed irrevocable belief revision, to be contrasted with standard belief revision, in a setting wherein belief of propositional formulas is modelled explicitly. This suggests that in standard belief revision is revocable: one should be able to unmake (‘revoke’) the fresh belief in the revision formula, given yet further information that contradicts it. In a dynamic epistemic logical setting for belief revision, for multiple agents, we investigate what the requirements are for revocable belief revision. By this we not merely mean recovering belief in non-modal propositions, as in the recovery principle for belief contraction, but recovering belief in modal propositions: beliefs about beliefs. These requirements are almost never met, a surprising result.     

Awareness and equilibrium

There has been a recent surge of interest among economists in developing models of doxastic states that can account for some aspects of human cognitive limitations that are ignored by standard formal models, such as awareness. Epistemologists purport to have a principled reason for ignoring the question of awareness: under the equilibrium conception of doxastic states they favour, a doxastic state comprises the doxastic commitments an agent would recognise were he fully aware, so the question of awareness plays no role. The objective of this paper is to scrutinize this argument. A thesis underlying the argument, which we call the independence of doxastic commitments with respect to awareness, is identified, and examples are given where it appears to be violated. By considering these examples, one can get an idea of the price of accepting this thesis. On the one hand, one can escape the conclusion that the thesis is violated, but only at the expense of another principle espoused by all major formal models of belief, which we call constant doxastic rest; and abandoning this principle necessitates extensive revision of current models of belief. On the other hand, there are epistemologically valid reasons for thinking that the thesis fails to hold in the examples, which have to be rebutted if the thesis, and the equilibrium justification for ignoring the issue of awareness, are to be retained.     

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.