- Data mining
- Data preprocessing
- Data visualization
- Data warehousing
- Databases
- Decision support systems
- Decision Trees
- Deep Learning
- Deliberative agents
- Dempster-Shafer theory
- Denoising Diffusion Probabilistic Models
- Design of experiments
- Diagnostics
- Differential Evolution
- Differential privacy
- Digital libraries
- Digital signal processing
- Digital Twins
- Dimensionality reduction
- Direct search methods
- Discriminant analysis
- Distributed artificial intelligence
- Distributed computing
- Distributed control systems
- Distributed systems
- Document analysis
- Domain Adaptation
- Domain knowledge
- Domain-specific languages
- Dynamic models
- Dynamic programming
- Dynamic programming languages
What is Dempster-Shafer theory
Dempster-Shafer Theory: A Beginner’s Guide
Introduction
Dempster-Shafer Theory (DST) is a mathematical framework for reasoning about uncertainty, which was first proposed by Arthur Dempster and Glenn Shafer in the 1960s. The theory is based on the idea of belief functions rather than probabilities, which allows for more flexibility in handling uncertain and incomplete information. DST has found applications in fields such as artificial intelligence, decision making, fault diagnosis, and risk assessment, among others. In this article, we will provide a comprehensive introduction to DST, including its basic concepts, key properties, and examples of its use in practice.
Belief Functions
Before diving into DST, it is important to understand the concept of a belief function. In traditional probability theory, a probability distribution assigns a probability value to each possible outcome of a random event. In contrast, a belief function assigns a degree of belief (or plausibility) to each possible outcome, but does not require these degrees of belief to sum up to one. This allows for more flexibility in dealing with uncertainty and ambiguity. Let us consider an example.
Suppose we want to predict whether it will rain tomorrow. We can assign a probability of 0.6 to the event of rain, and a probability of 0.4 to the event of no rain. However, what if we are not completely sure whether it will rain or not? In that case, we can use a belief function which assigns a degree of belief to each possible scenario. For instance, we might assign a degree of belief of 0.4 to “it will rain,” 0.3 to “it will not rain,” and 0.3 to “I am not sure.” Note that the degrees of belief do not add up to one, as with probabilities.
Basic Concepts
Now that we understand belief functions, let us turn to the main concepts of DST. The theory is based on sets, which can represent events or propositions. The key elements of DST are:
- Elementary hypotheses (or basic events): these are the smallest and most basic elements of uncertainty, represented as singleton sets. For instance, “it will rain tomorrow” is an elementary hypothesis.
- Focal elements (or hypotheses): these are sets of elementary hypotheses which represent uncertain or incomplete information. For instance, the set {“it will rain tomorrow,” “it will not rain tomorrow”} represents all the possible outcomes of our prediction.
- Mass functions (or belief functions): these are functions which assign degrees of belief to focal elements, and satisfy certain axioms. In particular, a mass function must assign a mass of zero to the empty set (corresponding to no information), and a mass of one to the entire set (corresponding to complete certainty).
- Belief and plausibility: given a mass function, we can calculate two measures of uncertainty: the belief of a set A is the sum of the masses of all the focal elements which include A, while the plausibility of A is the sum of the masses of all the focal elements which intersect A. Intuitively, belief represents the lower bound of uncertainty (how much we believe A), while plausibility represents the upper bound of uncertainty (how much we can accept A).
These concepts may seem confusing at first, but they become clearer with examples. Let us consider the following scenario.
Suppose we want to predict whether a person will develop diabetes based on their age, weight, and family history. Let us assume that there are three elementary hypotheses: D (the person has diabetes), P (the person does not have diabetes), and Q (we are not sure if the person has diabetes). We can define the following focal elements:
- {D}
- {P}
- {Q}
- {D, P} (we know that the person either has diabetes or not)
- {D, Q}
- {P, Q}
- {D, P, Q}
Now we can assign a mass function to these focal elements based on the available information. For instance, we might assign a mass of 0.3 to {D} (indicating some evidence for diabetes), a mass of 0.1 to {P}, a mass of 0.6 to {Q} (representing uncertainty), and a mass of zero to all other focal elements (which are incompatible with the available information). Note that the total mass adds up to one, as required.
We can now calculate the belief and plausibility of each elementary hypothesis. For instance, the belief of {D} is the sum of the masses of focal elements which include {D}, namely:
- {D}
- {D, P}
- {D, Q}
- {D, P, Q}
Thus, the belief of {D} is 0.9. Similarly, the plausibility of {D} is the sum of the masses of focal elements which intersect {D}, namely:
- {D}
- {D, P}
- {D, Q}
- {D, P, Q}
- {P, Q}
Thus, the plausibility of {D} is 1.0. Note that belief is always less than or equal to plausibility, as belief represents the lower bound of uncertainty.
Key Properties
DST has several key properties which make it a useful tool for reasoning under uncertainty:
- Flexibility: belief functions allow for more flexibility than probability distributions, as they can represent uncertain and incomplete information using focal elements and mass functions.
- Certainty factors: DST allows for the representation of certainty factors or degrees of belief in hypotheses, which can be useful in expert systems and decision making.
- Inference rules: DST has a set of inference rules, such as the Dempster’s rule of combination, which allow for combining pieces of evidence from different sources into a single mass function and updating it as new evidence becomes available.
- Conflict handling: DST can deal with conflicting evidence by assigning different masses to conflicting focal elements, and computing belief and plausibility accordingly. In addition, DST can detect and quantify the inconsistency of evidence.
- Non-monotonicity: DST allows for non-monotonic reasoning, meaning that adding new evidence may decrease the level of belief in a hypothesis, rather than increase it, if the evidence is inconsistent with prior beliefs.
These properties make DST a powerful tool for reasoning under uncertainty, particularly in situations where probabilities are difficult to estimate or not available.
Applications
DST has found applications in many fields, including:
- Decision making: DST can be used to assess the uncertainty and risk associated with different courses of action, and to make decisions based on maximum expected utility.
- Fault diagnosis: DST can be used to diagnose faults in complex systems using evidence from multiple sources, such as sensors, alarms, and expert knowledge.
- Information fusion: DST can be used to combine information from multiple sources, such as data from sensors, simulations, and expert opinions, to improve the overall accuracy and reliability of a model or prediction.
- Risk assessment: DST can be used to assess the risk and potential impact of different scenarios or hazards, and to prioritize actions based on their expected consequences.
- Natural language processing: DST can be used to model uncertain or ambiguous statements in natural language, such as “John is happy but tired,” by assigning degrees of belief to different interpretations.
These applications show the versatility and usefulness of DST in various domains, where uncertainty and incomplete information are common.
Conclusion
Dempster-Shafer Theory is a mathematical framework for reasoning under uncertainty, which provides a flexible and powerful tool for dealing with uncertain and incomplete information. The theory is based on belief functions, which assign degrees of belief to sets of elementary hypotheses, and satisfy certain axioms. DST has several key properties, including flexibility, certainty factors, inference rules, conflict handling, and non-monotonicity, which make it a useful tool in many applications, such as decision making, fault diagnosis, information fusion, risk assessment, and natural language processing, among others. By understanding the basic concepts and properties of DST, practitioners can apply the theory to real-world problems and benefit from its strengths.