Infobase Change: A First Approximation

Generalisations of theory change involving operations on arbitrary sets ofwffs instead of on belief sets (i.e., sets closed under a consequencerelation), have become known as base change. In one view, a base should bethought of as providing more structure to its generated belief set, whichmeans that it can be employed to determine the theory contraction operationassociated with a base contraction operation. In this paper we follow suchan approach as the first step in defining infobase change. We think of an infobase as a finite set of wffs consisting of independently obtainedbits of information. Taking AGM theory change (Alchourrón et al. 1985) as the general framework, we present a method that uses the structure of aninfobase B to obtain an AGM theory contraction operation for contractingthe belief set Cn(B). Both the infobase and the obtained theory contraction operation then play a role in constructing a unique infobasecontraction operation. Infobase revision is defined in terms of an analogueof the Levi Identity, and it is shown that the associated theory revisionoperation satisfies the AGM postulates for revision. Because every infobaseis associated with a unique infobase contraction and revision operation, the method also allows for iterated base change.     

Iterated belief revision, revised

The AGM postulates for belief revision, augmented by the DP postulates for iterated belief revision, provide widely accepted criteria for the design of operators by which intelligent agents adapt their beliefs incrementally to new information. These postulates alone, however, are too permissive: They support operators by which all newly acquired information is canceled as soon as an agent learns a fact that contradicts some of its current beliefs. In this paper, we present a formal analysis of the deficiency of the standard postulates alone, and we show how to solve the problem by an additional postulate of independence. We give a representation theorem for this postulate and prove that it is compatible with AGM and DP.     

Axiomatic characterization of the AGM theory of belief revision in a temporal logic

Since belief revision deals with the interaction of belief and information over time, branching-time temporal logic seems a natural setting for a theory of belief change. We propose two extensions of a modal logic that, besides the next-time temporal operator, contains a belief operator and an information operator. The first logic is shown to provide an axiomatic characterization of the first six postulates of the AGM theory of belief revision, while the second, stronger, logic provides an axiomatic characterization of the full set of AGM postulates.     

AGM Contraction and Revision of Rules

In this paper we study AGM contraction and revision of rules using input/output logical theories. We replace propositional formulas in the AGM framework of theory change by pairs of propositional formulas, representing the rule based character of theories, and we replace the classical consequence operator Cn by an input/output logic. The results in this paper suggest that, in general, results from belief base dynamics can be transferred to rule base dynamics, but that a similar transfer of AGM theory change to rule change is much more problematic. First, we generalise belief base contraction to rule base contraction, and show that two representation results of Hansson still hold for rule base contraction. Second, we show that the six so-called basic postulates of AGM contraction are consistent only for some input/output logics, but not for others. In particular, we show that the notorious recovery postulate can be satisfied only by basic output, but not by simple-minded output. Third, we show how AGM rule revision can be defined in terms of AGM rule contraction using the Levi identity. We highlight various topics for further research.     

Agent信念的遗忘修正方法

为了使信念修正能够满足最小改变原则,首先基于遗忘理论定义遗忘收缩算子,并且证明该算子满足必要AGM收缩假定;然后通过Levi Identity构建遗忘修正算子;最后给出遗忘修正方法和多次遗忘修正算法。实例分析表明,算法具有可行性和有效性,能够得到较满意的修正结果。     

一种广义信念修正的计算方法

AGM理论中新知识为单个语句，而实际上新知识通常是以多语句甚至无穷语句的形式出现．广义信念修正从理论上扩充了AGM系统，但在具体实现上还缺乏有效的算法．通过构造优序划分的方法解决信念间的关系问题，采用新知识的信度与冲突知识相关的方法解决新知识的信度问题．给出了一种基于链表的计算方法，从而解决了广义信念修正理论的信念库维护操作问题．     

Belief Revision by Sets of Sentences

The aim of this paper is to extend the system of belief revision developed by Alchourron,Gaerdenfors and Makinson(AGM)to a more general framework.This extension enables a treatment of revision not only by single sentences but also by any sets of entences,especially by infinite sets.The extended revision and contraction operators will be called general ones,respectively.A group of postulates for each operator is provided in such a way that it coincides with AGM‘s in the limit case.A notion of the nice-ordering partition is introduced to characterize the general contraction opeation.A computation-oriented approach is provided for belief revision operations.     

A model-based belief revision system

Numerous belief revision and update semantics have been proposed in the literature in the past few years, but until recently, no work in the belief revision literature has focussed on the problem of implementing these semantics, and little attention has been paid to algorithmic questions. In this paper, we present and analyze our update algorithms built in Immortal, a model-based belief revision system. These algorithms can work for a variety of model-based belief revision semantics proposed to date. We also extend previously proposed semantics to handle updates involving the equality predicate and function symbols and incorporate these extensions in our algorithms. As an example, we discuss the use of belief revision semantics to model the action-augmented envisioning problem in qualitative simulation, and we show the experimental results of running an example simulation in Immortal.     

A Thorough Axiomatization of a Principle of Conditional Preservation in Belief Revision

Although the crucial role of if-then-conditionals for the dynamics of knowledge has been known for several decades, they do not seem to fit well in the framework of classical belief revision theory. In particular, the propositional paradigm of minimal change guiding the AGM-postulates of belief revision proved to be inadequate for preserving conditional beliefs under revision. In this paper, we present a thorough axiomatization of a principle of conditional preservation in a very general framework, considering the revision of epistemic states by sets of conditionals. This axiomatization is based on a nonstandard approach to conditionals, which focuses on their dynamic aspects, and uses the newly introduced notion of conditional valuation functions as representations of epistemic states. In this way, probabilistic revision as well as possibilistic revision and the revision of ranking functions can all be dealt with within one framework. Moreover, we show that our approach can also be applied in a merely qualitative environment, extending AGM-style revision to properly handling conditional beliefs.     

On the revision of probabilistic beliefs using uncertain evidence

We revisit the problem of revising probabilistic beliefs using uncertain evidence, and report results on several major issues relating to this problem: how should one specify uncertain evidence? How should one revise a probability distribution? How should one interpret informal evidential statements? Should, and do, iterated belief revisions commute? And what guarantees can be offered on the amount of belief change induced by a particular revision? Our discussion is focused on two main methods for probabilistic revision: Jeffrey's rule of probability kinematics and Pearl's method of virtual evidence, where we analyze and unify these methods from the perspective of the questions posed above.     

Iterated Belief Change

Most existing formalizations treat belief change as a single-step process, and ignore several problems that become important when a theory, or belief state, is revised over several steps. This paper identifies these problems, and argues for the need to retain all of the multiple possible outcomes of a belief change step, and for a framework in which the effects of a belief change step persist as long as is consistently possible. To demonstrate that such a formalization is indeed possible, we develop a framework, which uses the language of PJ-default logic (Delgrande and Jackson 1991) to represent a belief state, and which enables the effects of a belief change step to persist by propagating belief constraints . Belief change in this framework maps one belief state to another, where each belief state is a collection of theories given by the set of extensions of the PJ-default theory representing that belief state. Belief constraints do not need to be separately recorded; they are encoded as clearly identifiable components of a PJ-default theory. The framework meets the requirements for iterated belief change that we identify and satisfies most of the AGM postulates (Alchourrón, Gärdenfors, and Makinson 1985) as well.     

Belief Revision: A Critique

We examine carefully the rationale underlying the approaches to belief change taken in the literature, and highlight what we view as methodological problems. We argue that to study belief change carefully, we must be quite explicit about the “ontology” or scenario underlying the belief change process. This is something that has been missing in previous work, with its focus on postulates. Our analysis shows that we must pay particular attention to two issues that have often been taken for granted: the first is how we model the agent's epistemic state. (Do we use a set of beliefs, or a richer structure, such as an ordering on worlds? And if we use a set of beliefs, in what language are these beliefs are expressed?) We show that even postulates that have been called “beyond controversy” are unreasonable when the agent's beliefs include beliefs about her own epistemic state as well as the external world. The second is the status of observations. (Are observations known to be true, or just believed? In the latter case, how firm is the belief?) Issues regarding the status of observations arise particularly when we consider iterated belief revision, and we must confront the possibility of revising by φ and then by ¬ φ.     

一种基于可信度的迭代信念修正方法

信念修正主要解决在接收到新信息时,如何对原有知识库进行操作的问题．经典的迭代信念修正主要关注信念修正的一致性,并未考虑多agent系统中信息具有不可靠性,以及信念修正过程对修正结果的影响．基于可信度的迭代信念修正方法,通过证据理论以及信度函数方法估计信息的可信度,并由此确定最优的最大协调子集作为信念修正的结果．基于可信度的迭代信念修正算子具有历史依赖性,即修正结果不仅与当前的信念集和接收到的新信息有关,也与信念集中曾经接收到的信息相关．     

Double preference relations for generalised belief change

Many belief change formalisms employ plausibility orderings over the set of possible worlds to determine how the beliefs of an agent ought to be modified after the receipt of a new epistemic input. While most such possible world semantics rely on a single ordering, we investigate the use of an additional preference ordering—representing, for instance, the epistemic context the agent finds itself in—to guide the process of belief change. We show that the resultant formalism provides a unifying semantics for a wide variety of belief change operators. By varying the conditions placed on the second ordering, different families of known belief change operators can be captured, including AGM belief contraction and revision, Rott and Pagnucco's severe withdrawal, the systematic withdrawal of Meyer et al., as well as the linear liberation and σ-liberation operators of Booth et al. Our approach also identifies novel classes of belief change operators worthy of further investigation.     

Belief extrapolation (or how to reason about observations and unpredicted change)

We give a logical framework for reasoning with observations at different time points. We call belief extrapolation the process of completing initial belief sets stemming from observations by assuming minimal change. We give a general semantics and we propose several extrapolation operators. We study some key properties verified by these operators and we address computational issues. We study in detail the position of belief extrapolation with respect to revision and update: in particular, belief extrapolation is shown to be a specific form of time-stamped belief revision. Several related lines of work are positioned with respect to belief extrapolation.     

NO Revision and NO Contraction

One goal of normative multi-agent system theory is to formulate principles for normative system change that maintain the rule-like structure of norms and preserve links between norms and individual agent obligations. A central question raised by this problem is whether there is a framework for norm change that is at once specific enough to capture this rule-like behavior of norms, yet general enough to support a full battery of norm and obligation change operators. In this paper we propose an answer to this question by developing a bimodal logic for norms and obligations called NO. A key to our approach is that norms are treated as propositional formulas, and we provide some independent reasons for adopting this stance. Then we define norm change operations for a wide class of modal systems, including the class of NO systems, by constructing a class of modal revision operators that satisfy all the AGM postulates for revision, and constructing a class of modal contraction operators that satisfy all the AGM postulates for contraction. More generally, our approach yields an easily extendable framework within which to work out principles for a theory of normative system change.     

Belief Fusion: Aggregating Pedigreed Belief States

We introduce a new operator – belief fusion– which aggregates the beliefs of two agents, each informed by a subset of sources ranked by reliability. In the process we definepedigreed belief states, which enrich standard belief states with the source of each piece of information. We note that the fusion operator satisfies the invariants of idempotence, associativity, and commutativity. As a result, it can be iterated without difficulty. We also define belief diffusion; whereas fusion generally produces a belief state with more information than is possessed by either of its two arguments, diffusion produces a state with less information. Fusion and diffusion are symmetric operators, and together define a distributive lattice. Finally, we show that AGM revision can be viewed as fusion between a novice and an expert. This revised version was published online in August 2006 with corrections to the Cover Date.     

Diversity of Agents and Their Interaction

Diversity of agents occurs naturally in epistemic logic, and dynamic logics of information update and belief revision. In this paper we provide a systematic discussion of different sources of diversity, such as introspection ability, powers of observation, memory capacity, and revision policies, and we show how these can be encoded in dynamic epistemic logics allowing for individual variation among agents. Next, we explore the interaction of diverse agents by looking at some concrete scenarios of communication and learning, and we propose a logical methodology to deal with these as well. We conclude with some further questions on the logic of diversity and interaction. This work was supported by the Chinese National Social Science Foundation (Grant Number: 04CZX011) and the Dutch Science Organization NWO.     

弱化矛盾信息的一种修正方法

信念修正中一个关键的问题就是对不一致信息的处理。文中提出一种新的策略，在对不一致信息的处理过程中，通过弱化矛盾信息而不是完全丢弃来维护知识库的一致性。这种方法遵循了最小改变原则，使信息丢失尽可能小从而保留了更多的有用信息。并讨论了其性质及满足AGM公设的情况。     

Distributed Belief Revision

In this paper, a distributed approach to belief revision is presented. It is conceived as a collective activity of a group of interacting agents, in which each component contributes with its own local beliefs. The integration of the different opinions is performed not by an external supervisor, but by the entire group through an election mechanism. Each agent exchanges information with the other components and uses a local belief revision mechanism to maintain its cognitive state consistent. We propose a model for local belief revision/integration based on what we called: Principle of Recoverability. Computationally, our way to belief revision consists of three steps acting on the symbolic part of the information, so as to deal with consistency and derivation, and two other steps working with the numerical weight of the information, so as to deal with uncertainty. In order to evaluate and compare the characteristics and performance of the centralized and of the distributed approaches, we made five different experiments simulating a simple society in which each agent is characterized by a degree of competence, communicates with some others, and revise its cognitive state. The results of these experiments are presented in the paper.