Classic Works of the Dempster-Shafer Theory of Belief Functions

Frontmatter

1. Classic Works of the Dempster-Shafer Theory of Belief Functions: An Introduction

Abstract

In this chapter, we review the basic concepts of the theory of belief functions and sketch a brief history of its conceptual development. We then provide an overview of the classic works and examine how they established a body of knowledge on belief functions, transformed the theory into a computational tool for evidential reasoning in artificial intelligence, opened up new avenues for applications, and became authoritative resources for anyone who is interested in gaining further insight into and understanding of belief functions.

Liping Liu, Ronald R. Yager

2. New Methods for Reasoning Towards Posterior Distributions Based on Sample Data

Abstract

This paper redefines the concept of sampling from a population with a given parametric form, and thus leads up to some proposed alternatives to the existing Bayesian and fiducial arguments for deriving posterior distributions. Section 2 spells out the basic assumptions of the suggested class of sampling models, and Sect. 3 suggests a mode of inference appropriate to the sampling models adopted. A novel property of these inferences is that they generally assign upper and lower probabilities to events concerning unknowns rather than precise probabilities as given by Bayesian or fiducial arguments. Sections 4 and 5 present details of the new arguments for binomial sampling with a continuous parameter p and for general multinomial sampling with a finite number of contemplated hypotheses. Among the concluding remarks, it is pointed out that the methods of Sect. 5 include as limiting cases situations with discrete or continuous observables and continuously ranging parameters.

Arthur P. Dempster

3. Upper and Lower Probabilities Induced by a Multivalued Mapping

Abstract

A multivalued mapping from a space X to a space S carries a probability measure defined over subsets of X into a system of upper and lower probabilities over subsets of S. Some basic properties of such systems are explored in Sects. 1 and 2. Other approaches to upper and lower probabilities are possible and some of these are related to the present approach in Sect. 3. A distinctive feature of the present approach is a rule for conditioning, or more generally, a rule for combining sources of information, as discussed in Sects. 4 and 5. Finally, the context in statistical inference from which the present theory arose is sketched briefly in Sect. 6.

Arthur P. Dempster

4. A Generalization of Bayesian Inference

Abstract

Procedures of statistical inference are described which generalize Bayesian inference in specific ways. Probability is used in such a way that in general only bounds may be placed on the probabilities of given events, and probability systems of this kind are suggested both for sample information and for prior information. These systems are then combined using a specified rule. Illustrations are given for inferences about trinomial probabilities, and for inferences about a monotone sequence of binomial pi. Finally, some comments are made on the general class of models which produce upper and lower probabilities, and on the specific models which underlie the suggested inference procedures.

Arthur P. Dempster

5. On Random Sets and Belief Functions

Hung T. Nguyen

6. Non-Additive Probabilities in the Work of Bernoulli and Lambert

Glenn Shafer

7. Allocations of Probability

Abstract

This paper studies belief functions, set functions which are normalized and monotone of order 8. The concepts of continuity and condensability are defined for belief functions, and it is shown how to extend continuous or condensable belief functions from an algebra of subsets to the corresponding power set. The main tool used in this extension is the theorem that every belief function can be represented by an allocation of probability i.e., by a n-homomorphism into a positive and completely additive probability algebra. This representation can be deduced either from an integral representation due to Choquet or from more elementary work by Revuz and Honeycutt.

Glenn Shafer

8. Computational Methods for A Mathematical Theory of Evidence

Abstract

Many knowledge-based expert systems employ numerical schemes to represent evidence, rate competing hypotheses, and guide search through the domain’s problem space. This paper has two objectives: first, to introduce one such scheme, developed by Arthur Dempster and Glen Shafer, to a wider audience; second, to present results that can reduce the computation-time complexity from exponential to linear, allowing this scheme to be implemented in many more systems. In order to enjoy this reduction, some assumptions about the structure of the type of evidence represented and combined must be made. The assumption made here is that each piece of the evidence either confirms or denies a single proposition rather than a disjunction. For any domain in which the assumption is justified, the savings are available.

Jeffrey A. Barnett

9. Constructive Probability

Glenn Shafer

10. Belief Functions and Parametric Models

Abstract

The theory of belief functions assesses evidence by fitting it to a scale of canonical examples in which the meaning of a message depends on chance. In order to analyse parametric statistical problems within the framework of this theory, we must specify the evidence on which the parametric model is based. This article gives several examples to show how the nature of this evidence affects the analysis. These examples also illustrate how the theory of belief functions can deal with problems where the evidence is too weak to support a parametric model.

Glenn Shafer

11. Entropy and Specificity in a Mathematical Theory of Evidence

Abstract

We review Shafer’s theory of evidence. We then introduce the concepts of entropy and specificity in the framework of Shafer’s theory. These become complementary aspects in the indication of the quality of evidence.

Ronald R. Yager

12. A Method for Managing Evidential Reasoning in a Hierarchical Hypothesis Space

Abstract

Although informal models of evidential reasoning have been successfully applied in automated reasoning systems, it is generally difficult to define the range of their applicability. In addition, they have not provided a basis for consistent management of evidence bearing on hypotheses that are related hierarchically. The Dempster–Shafer (D-S) theory of evidence is appealing because it does suggest a coherent approach for dealing with such relationships. However, the theory’s complexity and potential for computational inefficiency have tended to discourage its use in reasoning systems. In this paper we describe the central elements of the D-S theory, basing our exposition on simple examples drawn from the field of medicine. We then demonstrate the relevance of the D-S theory to a familiar expert-system domain, namely the bacterial-organism identification problem that lies at the heart of the mycin system. Finally, we present a new adaptation of the D-S approach that achieves computational efficiency while permitting the management of evidential reasoning within an abstraction hierarchy

Jean Gordon, Edward H. Shortliffe

13. Languages and Designs for Probability Judgment

Abstract

Theories of subjective probability are viewed as formal languages for analyzing evidence and expressing degrees of belief. This article focuses on two probability language, the Bayesian language and the language of belief functions [199]. We describe and compare the semantics (i.e., the meaning of the scale) and the syntax (i.e., the formal calculus) of these languages. We also investigate some of the designs for probability judgment afforded by the two languages.

Glenn Shafer, Amos Tversky

14. A Set-Theoretic View of Belief Functions

Logical Operations and Approximations by Fuzzy Sets

Abstract

A body of evidence in the sense of Shafer can be viewed as an extension of a probability measure, but as a generalized set as well. In this paper we adopt the second point of view and study the algebraic structure of bodies of evidence on a set, based on extended set union, intersection and complementation. Several notions of inclusion are exhibited and compared to each other. Inclusion is used to compare a body of evidence to the product of its projections. Lastly, approximations of a body of evidence under the form of fuzzy sets are derived, in order to squeeze plausibility values between two grades of possibility. Through all the paper, it is pointed out that a body of evidence can account for conjunctive as well as a disjunctive information, i.e. the focal elements can be viewed either as sets of actual values or as restrictions on the (unique) value of a variable.

Didier Dubois, Henri Prade

15. Weights of Evidence and Internal Conflict for Support Functions

Abstract

Shafer [1] defined weights of evidence and the weight of internal conflict for separable support functions. He also formulated a conjecture, the weight-of-conflict conjecture, which implies that these definitions can be extended in a natural way to all support functions. In this paper I show that the extension to support functions can be carried out whether or not the weight-of-conflict conjecture is true.

Nevin L. Zhang

16. A Framework for Evidential-Reasoning Systems

Abstract

Evidential reasoning is a body of techniques that supports automated reasoning from evidence. It is based upon the Dempster-Shafer theory of belief functions. Both the formal basis and a framework for the implementation of automated reasoning systems based upon these techniques are presented. The formal and practical approaches are divided into four parts (1) specifying a set of distinct propositional spaces, each of which delimits a set of possible world situations (2) specifying the interrelationships among these propositional spaces (3) representing bodies of evidence as belief distributions over these propositional spaces and (4) establishing paths for the bodies of evidence to move through these propositional spaces by means of evidential operations, eventually converging on spaces where the target questions can be answered.

John D. Lowrance, Thomas D. Garvey, Thomas M. Strat

17. Epistemic Logics, Probability, and the Calculus of Evidence

Abstract

This paper, presents, results, of, the, application, to epistemic, logic structures of the method proposed by Carnap for the development of logical foundations of probability theory. These results, which provide firm conceptual bases for the Dempster-Shafer calculus of evidence, are derived by exclusively using basic concepts from probability and modal logic theories, without resorting to any other theoretical notions or structures.

A form of epistemic logic (equivalent in power to the modal system S5), is used to define a space of possible worlds or states of affairs. This space, called the epistemic universe, consists of all possible combined descriptions of the state of the real world and of the state of knowledge that certain rational agents have about it. These representations generalize those derived by Carnap, which were confined exclusively to descriptions of possible states of the real world.

Probabilities defined on certain classes of sets of this universe, representing different states of knowledge about the world, have the properties of the major functions of the Dempster-Shafer calculus of evidence: belief functions and mass assignments. The importance of these epistemic probabilities lies in their ability to represent the effect of uncertain evidence in the states of knowledge of rational agents. Furthermore, if an epistemic probability is extended to a probability function defined over subsets of the epistemic universe that represent true states of the real world, then any such extension must satisfy the well-known interval bounds derived from the Dempster-Shafer theory.

Application of this logic-based approach to problems of knowledge integration results in a general expression, called the additive combination formula, which can be applied to a wide variety of problems of integration of dependent and independent knowledge. Under assumptions of probabilistic independence this formula is equivalent to Dempster’s rule of combination.

Enrique H. Ruspini

18. Implementing Dempster’s Rule for Hierarchical Evidence

Abstract

This article gives an algorithm for the exact implementation of Dempster’s rule in the case of hierarchical evidence. This algorithm is computationally efficient, and it makes the approximation suggested by Gordon and Shortliffe unnecessary. The algorithm itself is simple, but its derivation depends on a detailed understanding of the interaction of hierarchical evidence.

Glenn Shafer, Roger Logan

19. Some Characterizations of Lower Probabilities and Other Monotone Capacities through the use of Möbius Inversion

Abstract

Monotone capacities (on finite sets) of finite or infinite order (lower probabilities) are characterized by properties of their Möbius inverses. A necessary property of probabilities dominating a given capacity is demonstrated through the use of Gale’s theorem for the transshipment problem. This property is shown to be also sufficient if and only if the capacity is monotone of infinite order. A characterization of dominating probabilities specific to capacities of order 2 is also proved.

Alain Chateauneuf, Jean-Yves Jaffray

20. Axioms for Probability and Belief-Function Propagation

Abstract

In this paper, we describe an abstract framework and axioms under which exact local computation of marginals is possible. The primitive objects of the framework are variables and valuations. The primitive operators of the framework are combination and marginalization. These operate on valuations. We state three axioms for these operators and we derive the possibility of local computation from the axioms. Next, we describe a propagation scheme for computing marginals of a valuation when we have a factorization of the valuation on a hypertree. Finally we show how the problem of computing marginals of joint probability distributions and joint belief functions fits the general framework.

Prakash P. Shenoy, Glenn Shafer

21. Generalizing the Dempster–Shafer Theory to Fuzzy Sets

Abstract

With the desire to manage imprecise and vague information in evidential reasoning, several attempts have been made to generalize the Dempster–Shafer (D–S) theory to deal with fuzzy sets. However, the important principle of the D–S theory, that the belief and plausibility functions are treated as lower and upper probabilities, is no longer preserved in these generalizations. A generalization of the D–S theory in which this principle is maintained is described. It is shown that computing the degree of belief in a hypothesis in the D–S theory can be formulated as an optimization problem. The extended belief function is thus obtained by generalizing the objective function and the constraints of the optimization problem. To combine bodies of evidence that may contain vague information, Dempster’s rule is extended by 1) combining generalized compatibility relations based on the possibility theory, and 2) normalizing combination results to account for partially conflicting evidence. Our generalization not only extends the application of the D–S theory but also illustrates a way that probability theory and fuzzy set theory can be integrated in a sound manner in order to deal with different kinds of uncertain information in intelligent systems

John Yen

22. Bayesian Updating and Belief Functions

Abstract

In a wide class of situations of uncertainty, the available information concerning the event space can be described as follows: There exists a true probability that is only known to belong to a certain set P of probabilities; moreover, the lower envelope f of P is a belief function, i.e., a nonadditive measure of a particular type, and characterizes P, i.e., P is the set of all probabilities that dominate f. This is in particular the case when data result from large-scale sampling with incomplete observations. This study is concerned with the effect of conditioning on such situations. The natural conditioning rule is here the Bayesian rule: there exists a posterior probability after the observation of event E, and it is known to be located in P ^E, the set of conditionals of the members of P. An explicit expression for the Möbius transform φ^E of f ^E in terms of φ, the transform of f, is found and Fagin and Halpern’s earlier finding that the lower envelope f ^E of P ^E is itself a belief function is derived from it. However, f ^E no longer characterizes P ^E (not all probabilities dominating f ^E belong to it), unless f satisfy further stringent conditions that are both necessary and sufficient. The difficulties resulting from this fact are discussed and suggestions to cope with them are made.

Jean-Yves Jaffray

23. Belief-Function Formulas for Audit Risk

Abstract

This article relates belief functions to the structure of audit risk and provides formulas for audit risk under certain simplifying assumptions. These formulas give plausibilities of error in the belief-function sense.

We believe that belief-function plausibility represents auditors’ intuitive understanding of audit risk better than ordinary probability. The plausibility of a statement, within belief-function theory, measures the extent to which we lack evidence against the statement. High plausibility for error indicates only a lack of assurance, not positive evidence that there is error. Before collecting, analyzing, and aggregating the evidence, an auditor may lack any assurance that a financial statement is correct, and in this case will attribute very high plausibility to material misstatement. This high plausibility does not necessarily indicate any evidence that the statement is materially misstated, and hence, it is inappropriate to interpret it as a probability of material misstatement.

The SAS No. 47 formula for audit risk is based on a very simple structure for audit evidence. The formulas we derive in this article are based on a slightly more complex but still simplified structure, together with other simplifying assumptions. We assume a tree-type structure for the evidence, assume that all evidence is affirmative and that each variable in the tree is binary. All these assumptions can be relaxed. As they are relaxed, however, the formulas become more complex and less informative, and it then becomes more useful to think in terms of computer algorithms rather than in terms of formulas (Shafer and Shenoy 1988).

In general, the structure of audit evidence corresponds to a network of variables. We derive formulas only for the case in which each item of evidence bears either on all the audit objectives of an account or on all the accounts in the financial statement, as in Fig. 1, so that the network is a tree. Usually, however, there will be some evidence that bears on some but not all objectives for an account, on some but not all accounts, or on objectives at different levels; in this case, the network will not be a tree.

We assume that all evidence is affirmative because this is the situation treated by the SAS No. 47 formula and because belief-function formulas become significantly more complex when affirmative and negative evidence is combined. This complexity is due primarily to the renormalization involved in Dempster’s rule for combining belief functions.

The variables in the network or tree represent various audit objectives, accounts, and the financial statement as a whole. We assume these variables are binary. For example, we assume that an account either is or is not materially misstated. This assumption is clearly too restrictive for most audit practice. Often, for example, an auditor must consider immaterial errors in individual accounts that could produce a material error in the financial statement when they are aggregated.

We derive formulas for plausibility of material misstatement at three levels: the financial statement level, the account level, and the audit objective level. The formula at the audit objective level resembles the SAS No. 47 formula,^1 but the formulas at the other two levels are significantly different. Because our model does distinguish evidence gathered at the three different levels, audits based on our formulas are sometimes significantly more efficient^2 than audits based on the SAS No. 47 model or on the simpler Bayesian models.

Rajendra P. Srivastava, Glenn R. Shafer

24. Decision Making Under Dempster–Shafer Uncertainties

Abstract

We are concerned here with the problem of selecting an optimal alternative in situations in which there exists some uncertainty in our knowledge of the state of the world. We show how the Dempster–Shafer belief structure provides a unifying framework for representing various types of uncertainties. We also show how the OWA aggregation operators provide a unifying framework for decision making under ignorance. In particular we see how these operators provide a formulation of a type epistemic probabilities associated with our degree of optimism.

Ronald R. Yager

25. Belief Functions: The Disjunctive Rule of Combination and the Generalized Bayesian Theorem

Abstract

We generalize the Bayes’ theorem within the transferable belief model framework. The Generalized Bayesian Theorem (GBT) allows us to compute the belief over a space Θ given an observation x⊆ X when one knows only the beliefs over X for every θ_i ∈ Θ. We also discuss the Disjunctive Rule of Combination (DRC) for distinct pieces of evidence. This rule allows us to compute the belief over X from the beliefs induced by two distinct pieces of evidence when one knows only that one of the pieces of evidence holds. The properties of the DRC and GBT and their uses for belief propagation in directed belief networks are analysed. The use of the discounting factors is justfied. The application of these rules is illustrated by an example of medical diagnosis.

Philippe Smets

26. Representation of Evidence by Hints

Abstract

This paper introduces a mathematical model of a hint as a body of imprecise and uncertain information. Hints are used to judge hypotheses: the degree to which a hint supports a hypothesis and the degree to which a hypothesis appears as plausible in the light of a hint are defined. This leads in turn to support- and plausibility functions. Those functions are characterized as set functions which are normalized and monotone or alternating of order ∞. This relates the present work to G. Shafer’s mathematical theory of evidence. However, whereas Shafer starts out with an axiomatic definition of belief functions, the notion of a hint is considered here as the basic element of the theory. It is shown that a hint contains more information than is conveyed by its support function alone. Also hints allow for a straightforward and logical derivation of Dempster’s rule for combining independent and dependent bodies of information. This paper presents the mathematical theory of evidence for general, infinite frames of discernment from the point of view of a theory of hints.

Jürg Kohlas, Paul-André Monney

27. Combining the Results of Several Neural Network Classifiers

Abstract

Neural networks and traditional classifiers work well for optical character recognition; however, it is advantageous to combine the results of several algorithms to improve classification accuracies. This paper presents a combination method based on the Dempster–Shafer theory of evidence, which uses statistical information about the relative classification strengths of several classifiers. Numerous experiments show the effectiveness of this approach. The method allows 15—30% reduction of misclassification error compared to the best individual classifier.

Galina Rogova

28. The Transferable Belief Model

Abstract

Smets, P. and R. Kennes, The transferable belief model, Artificial Intelligence 66 (1994) 191–234.

We describe the transferable belief model, a model for representing quantified beliefs based on belief functions. Beliefs can be held at two levels: (1) a credal level where beliefs are entertained and quanti?ed by belief functions, (2) a pignistic level where beliefs can be used to make decisions and are quantified by probability functions. The relation between the belief function and the probability function when decisions must be made is derived and justified. Four paradigms are analyzed in order to compare Bayesian, upper and lower probability, and the transferable belief approaches.

Philippe Smets, Robert Kennes

29. A k-Nearest Neighbor Classification Rule Based on Dempster-Shafer Theory

Abstract

In this paper, the problem of classifying an unseen pattern on the basis of its nearest neighbors in a recorded data set is addressed from the point of view of Dempster-Shafer theory. Each neighbor of a sample to be classified is considered as an item of evidence that supports certain hypotheses regarding the class membership of that pattern. The degree of support is defined as a function of the distance between the two vectors. The evidence of the k nearest neighbors is then pooled by means of Dempster’s rule of combination. This approach provides a global treatment of such issues as ambiguity and distance rejection, and imperfect knowledge regarding the class membership of training patterns. The effectiveness of this classification scheme as compared to the voting and distance-weighted k-NN procedures is demonstrated using several sets of simulated and real-world data

Thierry Denœux

30. Logicist Statistics II: Inference

Abstract

A perspective on statistical inference is proposed that is broad enough to encompass modern Bayesian and traditional Fisherian thinking, and interprets frequentist theory in a way that gives appropriate weights to both science and mathematics, and to both objective and subjective elements. The aim is to inject new thinking into a field held back by a longstanding lack of consensus.

Arthur P. Dempster

Backmatter