Dempster–Shafer theory
The evidence theory of Dempster and Shafer 's a mathematical theory from the field of probability theory. It is used to assemble information from different sources into an overall statement, the credibility of these sources is taken into account in the calculation.
Representation
In the 1960s, Arthur Pentland Dempster published several articles on a theory for the settlement of evidence. The Dempster's work was further developed by Glenn Shafer and finally published in 1976. Since the theory is known as The Dempster - Shafer Theory of Evidence.
An evidence can be considered as an extension of a probability is being used instead of a one-dimensional two-dimensional measure: It is composed of the degree of For holding or the degree of confidence that the statement of a source is true (English: degree of belief ), and the plausibility of the event or of a probability range with a lower and upper limit.
The evidence theory is mainly used where unsafe statements of various sources need to be combined into an overall statement. The evidence theory can not be used in some situations, because the level of trust can not be quantified in a source. However, there are applications, such as in pattern recognition, which can be combined by means of the theory of evidence unreliable statements of various algorithms, so as to obtain a statement whose accuracy is better than that of any individual statement.
Illustrative Example
Suppose, due to the official weather report tomorrow will be nice weather. Suppose further that the weather can be trusted to 80%, which means that in 80% of cases, the weather provides an accurate prognosis. We can accept 80% now, then, that good weather will be tomorrow. But what about the other 20 %? Using the conventional probability theory, one could conclude that with a probability of 20 % the weather tomorrow will not be pretty. In this respect, the theory of Dempster and Shafer different from the theory of probability: In the remaining 20 % we do not know that the weather will not be pretty, but we know nothing. Since in 80 % of cases, the prognosis of the weather report is certainly correct, it is in 20% not sure. This means, however, that the statement of the weather report may be either right or wrong in 20 % of cases. The 20% will therefore not be attributed to the complement of the hypothesis but the set of all hypotheses.
This difference between the probability theory and the theory of Dempster and Shafer leads to further consequences. The in probability theory valid for a hypothesis set
Is no longer valid and can therefore based on the probability that a hypothesis is correct, no longer determine which is the probability that the hypothesis is not correct. It is therefore not enough faith for a hypothesis in some way combined with the belief that a hypothesis is wrong, must be expressed by a single value. Instead of a single value, a range of probability is used. The range is given by the lower limit and the upper limit, ie, the probability may be adopted by that the hypothesis is correct or not correct.
In the above example, the weather leads to evidence of good weather. But there is no reason to assume that tomorrow will not be nice weather. Based on the weather report, the probability of good weather is therefore in the range 0.8 to 1.0.
Combination of evidence
The official weather report says, as before, tomorrow should be nice weather. Another source, such as a weatherman, can be trusted only to 60 %, also thinks that good weather will be tomorrow. The following table shows how the evidence can be offset:
In three of four possible cases, the hypothesis is confirmed, since it is reliable sources. It must therefore be accepted with probability 48 % 12 % 32% = 92%, that the weather will be nice tomorrow. In the fourth case (8 %) can be made any statement about the hypothesis. This means now and.
In general, evidence supporting all a hypothesis that can be combined with:
And
And according to evidence, all speak with against a hypothesis
And
If contradictory evidence to be combined, we assume that the weatherman claims that the weather will be nice, results in the following situations:
The variant in which both statements are true, it is now impossible: If both claim the opposite, both of which may not be reliable. After Dempster and Shafer all possible cases are rescaled so that the sum of all probabilities again 1 shows that all the values for the possible cases are divided by the sum of all values for the possible cases. This results in:
It can be assumed to be about 62 % so now that the weather will be nice, and to about 23 %, that the weather will not be pretty. The probability range for nice weather is so limited by the values of 0.62 and 0.77 (1 - 0:23 ). Two contradictory evidence ( for hypothesis ) and ( against the hypothesis) can therefore be charged to:
And
Approach to several hypotheses
In the previous examples, only the case was considered of a hypothesis. In addition, two important conditions for the theory of Dempster and Shafer were not mentioned: The hypotheses must be mutually exclusive and the hypothesis space must be complete, ie, the correct hypothesis must be present in the set of existing hypotheses. The following describes the procedure for the general case with multiple, competing hypotheses is considered.
In the first example were 20 %, where the weather is unreliable, not awarded to the complement of the hypothesis, but both the hypothesis itself as well as its complement, as the weather in the 20 % are right or may be wrong. If there are several hypotheses, the remaining evidence, ie the proportion of evidence that can be awarded no hypothesis is mapped according to the totality of the existing hypotheses (). The allotment to all of the hypotheses is therefore useful because it is assumed that the hypothesis space is complete.
Several hypotheses exist, then an evidence for an hypothesis is also an evidence against the hypothesis other and vice versa. The evidence against the other hypotheses, however, similar to the rest of evidence, not divided among the other hypotheses, but attributed to the totality of all other hypotheses.
An example of a case with a plurality of hypothesis: Assume a digital image representing a character is to be classified. There are three hypotheses: The image can an 'A', a ' R' or 'B' represent, ie the hypothesis space consists of the set = {' A', ' R ', ' B '}. Next, we assume that there exists evidence of 0.2 for ' R' and an evidence of 0.6 against 'A'. This results in a radical and evidence. The evidence against 'A' is an evidence for ' R' and 'B'. The following table summarizes the situation:
The evidence of the intersections resulting from the product of the evidence of the amounts that are cut. The range of probability of the hypothesis set is given by:
And
In words: the belief that one of the hypotheses is correct is given by the sum of the evidence from all parts of the hypothesis set and the sum of all the evidence of all subsets of the complement of the hypothesis set. For example, this leads to:
The belief interval for ' A' is thus 0-1 - 0.68, ie 0 to 0:32. That for ' R' is 0.2 to 1-0, ie 0.2 to 1; and that is for ' B' 0-1 - 0.2, ie 0 to 0.8.
Now comes another evidence, then the values are in the following table:
The result is now an evidence for the empty set, which is not possible, it must be there completely. As described above, the evidence for the potential values must be scaled. This gives finally:
Calculation method
If a set of competing hypotheses is present, may need to be considered subsets ( from the power set of ). If the evidence gathered in any order, then the cost of an algorithm is exponential. However, it can be shown (Ref.: Barnett 1981) that an algorithm is created with only linear overhead when evidence will be charged in swift order. The process is described without proof in the following.
For each of the competing hypotheses to all the evidence for the hypothesis will be charged:
And according to all the evidence against the hypothesis. The collected evidence for and against the hypothesis can now be combined:
And
If a hypothesis is present, applies
And
If several hypotheses exist, then it must be considered that any evidence for a hypothesis also an evidence against ( for ) is (about) all other hypotheses. This evidence must be included so that the result is:
And
Where and and
This algorithm may be used when only evidence for or against individual hypotheses exist, ie not present when evidence for or against sets of hypotheses. In addition, the hypotheses must be mutually exclusive and be the set of hypotheses completely.
The latter condition is often not met in practice, that it is not ensured that the correct hypothesis is part of the solution volume. As a solution to this problem can be added to the set of competing hypotheses further, which is representative for all other possible hypotheses. This extension leads to a simplification of the algorithm described above result, if there is no evidence for or against this hypothesis are present, so is. This leads namely to ensure that all products that contain or are to 0 and therefore does not need to be calculated.