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.     

Belief revision within fragments of propositional logic

Belief revision has been extensively studied in the framework of propositional logic, but just recently revision within fragments of propositional logic has gained attention. Hereby it is not only the belief set and the revision formula which are given within a certain language fragment, but also the result of the revision has to be located in the same fragment. So far, research in this direction has been mainly devoted to the Horn fragment of classical logic. Here we present a general approach to define new revision operators derived from known operators, such that the result of the revision remains in the fragment under consideration. Our approach is not limited to the Horn case but applicable to any fragment of propositional logic where the models of the formulas are closed under a Boolean function. Thus we are able to uniformly treat cases as dual Horn, Krom and affine formulas, as well.     

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.     

Preferential belief change using generalized epistemic entrenchment

A sentence A is epistemically less entrenched in a belief state K than a sentence B if and only if a person in belief state K who is forced to give up either A or B will give up A and hold on to B. This is the fundamental idea of epistemic entrenchment as introduced by Gärdenfors (1988) and elaborated by Gärdenfors and Makinson (1988). Another distinguishing feature of relations of epistemic entrenchment is that they permit particularly simple and elegant construction recipes for minimal changes of belief states. These relations, however, are required to satisfy rather demanding conditions. In the present paper we liberalize the concept of epistemic entrenchment by removing connectivity, minimality and maximality conditions. Correspondingly, we achieve a liberalization of the concept of rational belief change that does no longer presuppose the postulates of success and rational monotony. We show that the central results of Gärdenfors and Makinson are preserved in our more flexible setting. Moreover, the generalized concept of epistemic entrenchment turns out to be applicable also to relational and iterated belief changes.     

An AGM-style belief revision mechanism for probabilistic spatio-temporal logics

There is now extensive interest in reasoning about moving objects. A probabilistic spatio-temporal (PST) knowledge base (KB) contains atomic statements of the form “Object o is/was/will be in region r at time t with probability in the interval [?,u]”. In this paper, we study mechanisms for belief revision in PST KBs. We propose multiple methods for revising PST KBs. These methods involve finding maximally consistent subsets and maximal cardinality consistent subsets. In addition, there may be applications where the user has doubts about the accuracy of the spatial information, or the temporal aspects, or about the ability to recognize objects in such statements. We study belief revision mechanisms that allow changes to the KB in each of these three components. Finally, there may be doubts about the assignment of probabilities in the KB. Allowing changes to the probability of statements in the KB yields another belief revision mechanism. Each of these belief revision methods may be epistemically desirable for some applications, but not for others. We show that some of these approaches cannot satisfy AGM-style axioms for belief revision under certain conditions. We also perform a detailed complexity analysis of each of these approaches. Simply put, all belief revision methods proposed that satisfy AGM-style axioms turn out to be intractable with the exception of the method that revises beliefs by changing the probabilities (minimally) in the KB. We also propose two hybrids of these basic approaches to revision and analyze the complexity of these hybrid methods.     

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 in the situation calculus

John McCarthy's situation calculus has left an enduring mark on artificial intelligence research. This simple yet elegant formalism for modelling and reasoning about dynamic systems is still in common use more than forty years since it was first proposed. The ability to reason about action and change has long been considered a necessary component for any intelligent system. The situation calculus and its numerous extensions as well as the many competing proposals that it has inspired deal with this problem to some extent. In this paper, we offer a new approach to belief change associated with performing actions that addresses some of the shortcomings of these approaches. In particular, our approach is based on a well-developed theory of action in the situation calculus extended to deal with belief. Moreover, by augmenting this approach with a notion of plausibility over situations, our account handles nested belief, belief introspection, mistaken belief, and handles belief revision and belief update together with iterated belief change.     

Confluence operators and their relationships with revision,update and merging

In this paper we introduce confluence operators, that are inspired by the existing links between belief revision, update and merging operators. Roughly, update operators can be considered as pointwise revision, whereas revision operators can be considered as special case of merging operators. Confluence operators are to merging operators what update operators are to revision operators. Similarly, update operators can be considered as special case of confluence operators just as revision can be considered as special case of merging operators. Confluence operators gives all possible agreement situations from a set of belief bases.     

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.     

Dynamic belief revision operators

The AGM approach to belief change is not geared to provide a decent account of iterated belief change. Darwiche and Pearl have sought to extend the AGM proposal in an interesting way to deal with this problem. We show that the original Darwiche-Pearl approach is, on the one hand excessively strong and, on the other rather limited in scope. The later Darwiche-Pearl approach, we argue, although it addresses the first problem, still remains rather permissive. We address both these issues by (1) assuming a dynamic revision operator that changes to a new revision operator after each instance of belief change, and (2) strengthening the Darwiche-Pearl proposal. Moreover, we provide constructions of this dynamic revision operator via entrenchment kinematics as well as a simple form of lexicographic revision, and prove representation results connecting these accounts.     

一种基于群体信念协商的矛盾知识处理模型

一个智能体从周围环境中接收到多种知识,如何将这些知识合并成单一的、一致的知识是一个非常重要的问题,从信念修正中＂缩并＋添加＂得到启发,我们分两步解决这个问题.第一步弱化接收到的多种信息,使之一致,第二步进行简单的合并操作.本文主要研究了第一步,称为基于群体信念协商的矛盾知识处理模型,本文讨论了该模型的公理系统和该模型的过程实现,通过一个例子示范了这种模型下信息合并操作的具体实现过程.     

First-order logical filtering

Logical filtering is the process of updating a belief state (set of possible world states) after a sequence of executed actions and perceived observations. In general, it is intractable in dynamic domains that include many objects and relationships. Still, potential applications for such domains (e.g., semantic web, autonomous agents, and partial-knowledge games) encourage research beyond intractability results.In this paper we present polynomial-time algorithms for filtering belief states that are encoded as First-Order Logic (FOL) formulas. Our algorithms are exact in many cases of interest. They accept belief states in FOL without functions, permitting arbitrary arity for predicates, infinite universes of elements, and equality. They enable natural representation with explicit references to unidentified objects and partially known relationships, still maintaining tractable computation. Previous results focus on more general cases that are intractable or permit only imprecise filtering. Our algorithms guarantee that belief-state representation remains compact for STRIPS actions (among others) with unbounded-size domains. This guarantees tractable exact filtering indefinitely for those domains. The rest of our results apply to expressive modeling languages, such as partial databases and belief revision in FOL.     

Prioritized assertional-based removed sets revision of <Emphasis Type="Italic">DL</Emphasis>-<Emphasis Type="Italic">Lite</Emphasis> belief bases

In real world applications, information is often provided by multiple sources having different priority levels reflecting for instance their reliability. This paper investigates ”Prioritized Removed Sets Revision” (PRSR) for revising stratified DL-Lite knowledge bases when a new sure piece of information, called the input, is added. The strategy of revision is based on inconsistency minimization and consists in determining smallest subsets of assertions (prioritized removed sets) that should be dropped from the current stratified knowledge base in order to restore consistency and accept the input. We consider different forms of input: A membership assertion, a positive or a negative inclusion axiom. To characterize our revision approach, we first rephrase Hansson’s postulates for belief bases revision within a DL-Lite setting, we then give logical properties of PRSR operators. In some situations, the revision process leads to several possible revised knowledge bases where defining a selection function is required to keep results within DL-Lite fragment. The last part of the paper shows how to use the notion of hitting set in order to compute the PRSR outcome. We also study the complexity of PRSR operators, and show that, in some cases, the computational complexity of the result can be performed in polynomial time.     

Belief revision in structured probabilistic argumentation

In real-world applications, knowledge bases consisting of all the available information for a specific domain, along with the current state of affairs, will typically contain contradictory data, coming from different sources, as well as data with varying degrees of uncertainty attached. An important aspect of the effort associated with maintaining such knowledge bases is deciding what information is no longer useful; pieces of information may be outdated; may come from sources that have recently been discovered to be of low quality; or abundant evidence may be available that contradicts them. In this paper, we propose a probabilistic structured argumentation framework that arises from the extension of Presumptive Defeasible Logic Programming (PreDeLP) with probabilistic models, and argue that this formalism is capable of addressing these basic issues. The formalism is capable of handling contradictory and uncertain data, and we study non-prioritized belief revision over probabilistic PreDeLP programs that can help with knowledge-base maintenance. For belief revision, we propose a set of rationality postulates — based on well-known ones developed for classical knowledge bases — that characterize how these belief revision operations should behave, and study classes of operators along with theoretical relationships with the proposed postulates, including representation theorems stating the equivalence between classes of operators and their associated postulates. We then demonstrate how our framework can be used to address the attribution problem in cyber security/cyber warfare.     

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

Simulating belief systems of autonomous agents

Autonomous agents in computer simulations do not have the usual mechanisms to acquire information as do their human counterparts. In many such simulations, it is not desirable that the agent have access to complete and correct information about its environment. We examine how imperfection in available information may be simulated in the case of autonomous agents. We determine probabilistically what the agent may detect, through hypothetical sensors, in a given situation. These detections are combined with the agent's knowledge base to infer observations and beliefs. Inherent in this task is a degree of uncertainty in choosing the most appropriate observation or belief. We describe and compare two approaches — a numerical approach and one based on defeasible logic — for simulating an appropriate belief in light of conflicting detection values at a given point in time. We discuss the application of this technique to autonomous forces in combat simulation systems.     

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.     

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.