Inappropriate use of Dempster's rule of combination has led some authors to reject the Dempster-Shafer model, arguing that it leads to supposedly unacceptable conclusions when defaults are involved. A most classic example is about the penguin Tweety. This paper will successively present: the origin of the miss-management of the Tweety example; two types of default; the correct solution for both types based on the transferable belief model (our interpretation of the Dempster-Shafer model (Shafer 1976, Smets 1988)); Except when explicitly stated, all belief functions used in this paper are simple support functions, i.e. belief functions for which only one proposition (the focus) of the frame of discernment receives a positive basic belief mass with the remaining mass being given to the tautology. Each belief function will be described by its focus and the weight of the focus (e.g. m(A)=.9). Computation of the basic belief masses are always performed by vacuously extending each belief function to the product space built from all variables involved, combining them on that space by Dempster's rule of combination, and projecting the result to the space corresponding to each individual variable.

In this paper, we suggest marrying Dempster-Shafer (DS) theory with Knowledge Representation (KR). Born out of this marriage is the definition of "Dempster-Shafer Belief Bases", abstract data types representing uncertain knowledge that use DS theory for representing strength of belief about our knowledge, and the linguistic structures of an arbitrary KR system for representing the knowledge itself. A formal result guarantees that both the properties of the given KR system and of DS theory are preserved. The general model is exemplified by defining DS Belief Bases where First Order Logic and (an extension of) KRYPTON are used as KR systems. The implementation problem is also touched upon.

A FRAMEWORK FOR NONMONOTONIC REASONING ABOUT PROBABILISTIC ASSUMPTIONS-- The Problem Marvin S. Cohen Decision Science Consortium, Inc. Attempts to replicate probabilistic reasoning in expert systems have typically overlooked a critical ingredient of that process. The application of such models is often an iterative process, in which the plausibility of the results confirms or disconfirms the validity of assumptions made in building the model. In current expert systems, by contrast, probabilistic information is encapsulated within modular rules (involving, for example, "certainty factors"), and there is no mechanism for reviewing the overall form of the probability argument or the validity of the judgments entering into it. It involves the design of an expert system inference framework in which probabilistic statements and rules are regarded as assumptions which are explicitly tracked and reevaluated when they lead to conflict among different sources of evidence or lines of reasoning. Two conceptions of conflict and conflict resolution have been implicit in most approaches to this area. From one point of view, divergence among lines of reasoning can be regarded as stochastic; it is expected to occur some small percentage of the time, due to the chance accumulation of small errors or "noise" in an imperfect process of "measurement". From another point of view, however, divergence can be regarded as a result of faulty beliefs; that is, conflicting results are taken as evidence that one or more premises or forms of argument that led to the conflict are mistaken.

In the 1940's, a physicist named Cox provided the first formal justification for the axioms of probability based on the subjective or Bayesian interpretation. He showed that if a measure of belief satisfies several fundamental properties, then the measure must be some monotonic transformation of a probability. In this paper, measures of change in belief or belief updates are examined. In the spirit of Cox, properties for a measure of change in belief are enumerated. It is shown that if a measure satisfies these properties, it must satisfy other restrictive conditions. For example, it is shown that belief updates in a probabilistic context must be equal to some monotonic transformation of a likelihood ratio. It is hoped that this formal explication of the belief update paradigm will facilitate critical discussion and useful extensions of the approach.

There currently exists a gap between the theories proposed by the probability and uncertainty and the needs of Artificial Intelligence research. These theories primarily address the needs of expert systems, using knowledge structures which must be pre-compiled and remain static in structure during runtime. Many Al systems require the ability to dynamically add and remove parts of the current knowledge structure (e.g., in order to examine what the world would be like for different causal theories). This requires more flexibility than existing uncertainty systems display. In addition, many Al researchers are only interested in using "probabilities" as a means of obtaining an ordering, rather than attempting to derive an accurate probabilistic account of a situation. This indicates the need for systems which stress ease of use and don't require extensive probability information when one cannot (or doesn't wish to) provide such information. This paper attempts to help reconcile the gap between approaches to uncertainty and the needs of many AI systems by examining the control issues which arise, independent of a particular uncertainty calculus. when one tries to satisfy these needs. Truth Maintenance Systems have been used extensively in problem solving tasks to help organize a set of facts and detect inconsistencies in the believed state of the world. These systems maintain a set of true/false propositions and their associated dependencies. However, situations often arise in which we are unsure of certain facts or in which the conclusions we can draw from available information are somewhat uncertain. The non-monotonic TMS 12] was an attempt at reasoning when all the facts are not known, but it fails to take into account degrees of belief and how available evidence can combine to strengthen a particular belief. This paper addresses the problem of probabilistic reasoning as it applies to Truth Maintenance Systems. It describes a belief Maintenance System that manages a current set of beliefs in much the same way that a TMS manages a set of true/false propositions. If the system knows that belief in fact is dependent in some way upon belief in fact2, then it automatically modifies its belief in facts when new information causes a change in belief of fact2. It models the behavior of a TMS, replacing its 3-valued logic (true, false, unknown) with an infinite valued logic, in such a way as to reduce to a standard TMS if all statements are given in absolute true/false terms. Belief Maintenance Systems can, therefore, be thought of as a generalization of Truth Maintenance Systems, whose possible reasoning tasks are a superset of those for a TMS.

RUM (Reasoning with Uncertainty Module), is an integrated software tool based on a KEE, a frame system implemented in an object oriented language. RUM's architecture is composed of three layers: representation, inference, and control. The representation layer is based on frame-like data structures that capture the uncertainty information used in the inference layer and the uncertainty meta-information used in the control layer. The inference layer provides a selection of five T-norm based uncertainty calculi with which to perform the intersection, detachment, union, and pooling of information. The control layer uses the meta-information to select the appropriate calculus for each context and to resolve eventual ignorance or conflict in the information. This layer also provides a context mechanism that allows the system to focus on the relevant portion of the knowledge base, and an uncertain-belief revision system that incrementally updates the certainty values of well-formed formulae (wffs) in an acyclic directed deduction graph. RUM has been tested and validated in a sequence of experiments in both naval and aerial situation assessment (SA), consisting of correlating reports and tracks, locating and classifying platforms, and identifying intents and threats. An example of naval situation assessment is illustrated. The testbed environment for developing these experiments has been provided by LOTTA, a symbolic simulator implemented in Flavors. This simulator maintains time-varying situations in a multi-player antagonistic game where players must make decisions in light of uncertain and incomplete data. RUM has been used to assist one of the LOTTA players to perform the SA task.

Department of Computer Science Brown University Providence, RI 02912 Abstract In general, the best explanation for a given observation makes no promises on how good it is with respect to other alternative explanations. A major deficiency of message-passing schemes for belief revision in Bayesian networks is their inability to generate alternatives beyond the second best. In this paper, we present a general approach based on linear constraint systems that naturally generates alternative explanations in an orderly and highly efficient manner. This approach is then applied to cost-based abduction problems as well as belief revision in Bayesian networks. INTRODUCTION We are constantly faced with the problem of explaining the observations we have gathered with our senses. Our explanations are constructed by assuming certain facts or hypotheses which support our observations. For example, suppose I decide to phone my friend Tony at the office.

The local computation technique (Shafer et al. 1987, Shafer and Shenoy 1988, Shenoy and Shafer 1986) is used for propagating belief functions in so called a Markov Tree. In this paper, we describe an efficient implementation of belief function propagation on the basis of the local computation technique. The presented method avoids all the redundant computations in the propagation process, and so makes the computational complexity decrease with respect to other existing implementations (Hsia and Shenoy 1989, Zarley et al. 1988). We also give a combined algorithm for both propagation and re-propagation which makes the re-propagation process more efficient when one or more of the prior belief functions is changed.

The compatibility of quantitative and qualitative representations of beliefs was studied extensively in probability theory. It is only recently that this important topic is considered in the context of belief functions. In this paper, the compatibility of various quantitative belief measures and qualitative belief structures is investigated. Four classes of belief measures considered are: the probability function, the monotonic belief function, Shafer's belief function, and Smets' generalized belief function. The analysis of their individual compatibility with different belief structures not only provides a sound b

Traditional approaches to non-monotonic 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.