Reasoning about Requirements Evolution Using Clustered Belief Revision

During the development of system requirements, software system specifications are often inconsistent. Inconsistencies may arise for different reasons, for example, when multiple conflicting viewpoints are embodied in the specification, or when the specification itself is at a transient stage of evolution. These inconsistencies cannot always be resolved immediately. As a result, we argue that a formal framework for the analysis of evolving specifications should be able to tolerate inconsistency by allowing reasoning in the presence of inconsistency without trivialisation, and circumvent inconsistency by enabling impact analyses of potential changes to be carried out. This paper shows how clustered belief revision can help in this process. Clustered belief revision allows for the grouping of requirements with similar functionality into clusters and the assignment of priorities between them. By analysing the result of a cluster, an engineer can either choose to rectify problems in the specification or to postpone the changes until more information becomes available.

Pseudo-contractions in belief revision

Belief Revision addresses the problem of how to change epistemic states, usually represented in the literature by sets of logical sentences. Solid theoretical results were consolidated with the AGM paradigm, which deals with theories (logically closed sets of sentences). After that, the theory was extended to belief bases, that is, arbitrary sets of sentences. Besides all this theoretical framework, AI researchers face serious difficulties when trying to implement belief revision systems. One of the major complications is the closure required by AGM theory, which cannot be easily computed. Even belief bases, which do not require closure, seem to be improper for practical purposes, since their changes are usually very rigid (syntax dependent). Some operations, known as pseudo-contractions, are in the middle ground between belief set change and belief base change. In the present work we have proposed a new pseudo-contraction operation, studied its properties and characterized it. We have also found connections between this operator and some other pseudo-contractions.

Belief revision for adaptive negotiation agents

Existing negotiation agents are primitive in terms of what they can learn and how responsive they are towards the changing negotiation contexts. These weaknesses can be alleviated if an expressive representation language is used to represent negotiation contexts and a sound inference mechanism is applied to reason about the preferential changes arising in these negotiation contexts. This paper illustrates a novel adaptive negotiation agent model, which is underpinned by the well-known AGM belief revision logic. Our preliminary experiments show that the performance of the belief-based adaptive negotiation agents is promising.

Belief revision and small loops in Gallager-type error-correcting codes

DUE TO COPYRIGHT RESTRICTIONS ONLY AVAILABLE FOR CONSULTATION AT ASTON UNIVERSITY LIBRARY AND INFORMATION SERVICES WITH PRIOR ARRANGEMENT

Belief Propagation and Revision in Networks with Loops

Local belief propagation rules of the sort proposed by Pearl(1988) are guaranteed to converge to the optimal beliefs for singly connected networks. Recently, a number of researchers have empirically demonstrated good performance of these same algorithms on networks with loops, but a theoretical understanding of this performance has yet to be achieved. Here we lay the foundation for an understanding of belief propagation in networks with loops. For networks with a single loop, we derive ananalytical relationship between the steady state beliefs in the loopy network and the true posterior probability. Using this relationship we show a category of networks for which the MAP estimate obtained by belief update and by belief revision can be proven to be optimal (although the beliefs will be incorrect). We show how nodes can use local information in the messages they receive in order to correct the steady state beliefs. Furthermore we prove that for all networks with a single loop, the MAP estimate obtained by belief revisionat convergence is guaranteed to give the globally optimal sequence of states. The result is independent of the length of the cycle and the size of the statespace. For networks with multiple loops, we introduce the concept of a "balanced network" and show simulati.

Non-monotonic Reasoning and the Reversibility of Belief Change

Traditional approaches to nonmonotonic reasoning fail to satisfy a number of plausible axioms for belief revision and suffer from conceptual difficulties as well. Recent work on ranked preferential models (RPMs) promises to overcome some of these difficulties. Here we show that RPMs are not adequate to handle iterated belief change. Specifically, we show that RPMs do not always allow for the reversibility of belief change. This result indicates the need for numerical strengths of belief.

Managing Software Requirements Changes Based On Negotiation-Style Revision

For any proposed software project, when the software requirements specification has been established, requirements changes may result in not only a modification of the requirements specification but also a series of modifications of all existing artifacts during the development. Then it is necessary to provide effective and flexible requirements changes management. In this paper, we present an approach to managing requirements changes based on Booth’s negotiation-style framework for belief revision. Informally, we consider the current requirements specification as a belief set about the system-to-be. The request of requirements change is viewed as new information about the same system-to-be. Then the process of executing the requirements change is a process of revising beliefs about the system-to-be. We design a family of belief negotiation models appropriate for different processes of requirements revision, including the setting of the request of requirements change being fully accepted, the setting of the current requirements specification being fully preserved, and that of the current specification and the request of requirements change reaching a compromise. In particular, the prioritization of requirements plays an important role in reaching an agreement in each belief negotiation model designed in this paper.

Bridging Jeffrey's Rule, AGM Revision and Dempster Conditioning in the Theory of Evidence

Belief revision characterizes the process of revising an agent’s beliefs when receiving new evidence. In the field of artificial intelligence, revision strategies have been extensively studied in the context of logic-based formalisms and probability kinematics. However, so far there is not much literature on this topic in evidence theory. In contrast, combination rules proposed so far in the theory of evidence, especially Dempster rule, are symmetric. They rely on a basic assumption, that is, pieces of evidence being combined are considered to be on a par, i.e. play the same role. When one source of evidence is less reliable than another, it is possible to discount it and then a symmetric combination operation
is still used. In the case of revision, the idea is to let prior knowledge of an agent be altered by some input information. The change problem is thus intrinsically asymmetric. Assuming the input information is reliable, it should be retained whilst the prior information should be changed minimally to that effect. To deal with this issue, this paper defines the notion of revision for the theory of evidence in such a way as to bring together probabilistic and logical views. Several revision rules previously proposed are reviewed and we advocate one of them as better corresponding to the idea of revision. It is extended to cope with inconsistency between prior and input information. It reduces to Dempster
rule of combination, just like revision in the sense of Alchourron, Gardenfors, and Makinson (AGM) reduces to expansion, when the input is strongly consistent with the prior belief function. Properties of this revision rule are also investigated and it is shown to generalize Jeffrey’s rule of updating, Dempster rule of conditioning and a form of AGM revision.

On the Merit of Selecting Different Belief Merging Operators

Belief merging operators combine multiple belief bases (a profile) into a collective one. When the conjunction of belief bases is consistent, all the operators agree on the result. However, if the conjunction of belief bases is inconsistent, the results vary between operators. There is no formal manner to measure the results and decide on which operator to select. So, in this paper we propose to evaluate the result of merging operators by using three ordering relations (fairness, satisfaction and strength) over operators for a given profile. Moreover, a relation of conformity over operators is introduced in order to classify how well the operator conforms to the definition of a merging operator. By using the four proposed relations we provide a comparison of some classical merging operators and evaluate the results for some specific profiles.

Revising Partial Pre-Orders with Partial Pre-Orders: A Unit-Based Revision Framework

Belief revision studies strategies about how agents revise their belief states when receiving new evidence. Both in classical belief revision and in epistemic revision, a new input is either in the form of a (weighted) propositional formula or a total
pre-order (where the total pre-order is considered as a whole).
However, in some real-world applications, a new input can be a partial pre-order where each unit that constitutes the partial pre-order is important and should be considered individually. To address this issue, in this paper, we study how a partial preorder representing the prior epistemic state can be revised by another partial pre-order (the new input) from a different perspective, where the revision is conducted recursively on the individual units of partial pre-orders. We propose different revision operators (rules), dubbed the extension, match, inner and outer revision operators, from different revision points of view. We also analyze several properties for these operators.

Revision over Partial Pre-orders: A Postulational Study

Belief revision is the process that incorporates, in a consistent way,
a new piece of information, called input, into a belief base. When both belief
bases and inputs are propositional formulas, a set of natural and rational properties, known as AGM postulates, have been proposed to define genuine revision operations. This paper addresses the following important issue : How to revise a partially pre-ordered information (representing initial beliefs) with a new partially pre-ordered information (representing inputs) while preserving AGM postulates? We first provide a particular representation of partial pre-orders (called units) using the concept of closed sets of units. Then we restate AGM postulates in this framework by defining counterparts of the notions of logical entailment and logical consistency. In the second part of the paper, we provide some examples of revision operations that respect our set of postulates. We also prove that our revision methods extend well-known lexicographic revision and natural revision for both cases where the input is either a single propositional formula or a total pre-order.

Revision rules in the theory of evidence

Combination rules proposed so far in the Dempster-Shafer theory of evidence, especially Dempster rule, rely on a basic assumption, that is, pieces of evidence being combined are considered to be on a par, i.e. play the same role. When a source of evidence is less reliable than another, it is possible to discount it and then a symmetric combination operation is still used. In the case of revision, the idea is to let prior knowledge of an agent be altered by some input information. The change problem is thus intrinsically asymmetric. Assuming the input information is reliable, it should be retained whilst the prior information should
be changed minimally to that effect. Although belief revision is already an important subfield of artificial intelligence, so far, it has been little addressed in evidence theory. In this paper, we define the notion of revision for the theory of evidence and propose several different revision rules, called the inner and outer
revisions, and a modified adaptive outer revision, which better corresponds to the idea of revision. Properties of these revision rules are also investigated.