Belief and plausibility

Belief (German: credibility ) and plausibility (ger .: plausibility ) are fundamental concepts in Glenn Shafer's theory of evidence . Evidence theory models uncertainty that arises not only from chance (as in probability theory ) but also from incomplete knowledge. It is used e.g. B. artificial intelligence , in particular in the construction of knowledge-based systems ( knowledge-based systems ), in the representation of knowledge ( knowledge representation ), with knowledge summary ( knowledge aggregation ), and increasing knowledge ( knowledge propagation ).

Introductory description

Be a finite universe . For example, these are the possible answers to a problem. It is certain that one answer is correct, but it is uncertain which it is. A distinction is made between the following cases: ${\displaystyle U=\{u_{1},u_{2},\dots ,u_{n}\}}$ ${\displaystyle u_{i}}$

• total evidence : one has maximum knowledge in the sense that all probabilities for the occurrence of the are known, i. H. the probability distribution over is uniquely determined. The uncertainty depends only on chance. ${\displaystyle u_{i}}$ ${\displaystyle U}$
• Partial evidence : One has only incomplete knowledge about the probability distribution and can therefore only specify bounds for the probability for an event . The lower bound is in any case credible as a possible probability and is therefore called “Belief”, the upper bound for the possible probability is still plausible and is therefore called plausibility. The uncertainty now depends not only on chance, but also on the lack of knowledge. ${\displaystyle U}$ ${\displaystyle A\subset U}$
• total ignorance : one has no knowledge of . The probabilities for can only be said to be between zero and one, i.e. H. there is total uncertainty. ${\displaystyle U}$ ${\displaystyle A\subset U}$

example

Cigarettes have been stolen. The thieves can only be Peter, Paul or Egon, so . The following level of knowledge is available: Anyone could have committed the theft alone, and with the probabilities ${\displaystyle U=\{{\text{Peter}},{\text{Paul}},{\text{Egon}}\}}$

${\displaystyle P({\text{Peter}})=0{,}1;\quad P({\text{Paul}})=0{,}2;\quad P({\text{Egon}})=0{,}3}$.

But mostly Peter and Paul steal together, rarely do all three go on tour, i. H. the still missing probability of divides z. B. in ${\displaystyle 0{,}4}$

${\displaystyle P({\text{Peter}},{\text{Paul}})=0{,}3;\quad P({\text{Peter}},{\text{Paul}},{\text{Egon}})=P(U)=0{,}1}$.

From this one can calculate the limits for the probability of the perpetrators: ${\displaystyle \operatorname {Prob} }$

${\displaystyle 0{,}1\leq \operatorname {Prob} ({\text{Peter}})\leq 0{,}5;\quad 0{,}2\leq \operatorname {Prob} ({\text{Paul}})\leq 0{,}6;\quad 0{,}3\leq \operatorname {Prob} ({\text{Egon}})\leq 0{,}4}$.

Formal description of belief and plausibility

Let be the power set of , a probability measure on, and the set of all subsets of that have a positive probability (i.e. a positive part of the evidence ). One only carries that part of the probability (the evidence) that is not already carried by subsets of , see also the example above. is evidence body (Engl. body of evidence ). The probability measure for is often called evidence for . If so , then there is total evidence, in the case of it there is total ignorance. Belief and plausibility are now defined by ${\displaystyle {\mathcal {P}}(U)}$ ${\displaystyle U}$ ${\displaystyle P}$ ${\displaystyle {\mathcal {P}}(U)}$ ${\displaystyle F(P):=\{B\in {\mathcal {P}}(U):P(B)>0\}}$ ${\displaystyle U}$ ${\displaystyle B\in F(P)}$ ${\displaystyle B}$ ${\displaystyle F(P)}$ ${\displaystyle P}$ ${\displaystyle {\mathcal {P}}(U)}$ ${\displaystyle U}$ ${\displaystyle F(P)=\{\{u_{1}\},\{u_{2}\},\dots ,\{u_{n}\}\}}$ ${\displaystyle F(P)=\{U\}}$

${\displaystyle \operatorname {Bel} (A)=\sum _{B\in F(P):B\subseteq A}P(B);\quad \quad \operatorname {Pl} (A)=1-\operatorname {Bel} ({\overline {A}})=\sum _{B\in F(P):B\cap A\neq \emptyset }P(B);\quad \quad A\in {\mathcal {P}}(U)}$.

It always applies . For a total evidence one has and for a total ignorance one has . is a normalized completely monotonic capacitance , is a normalized completely alternating capacitance. ${\displaystyle \operatorname {Bel} (A)\leq \operatorname {Pl} (A)}$ ${\displaystyle \operatorname {Bel} (A)=\operatorname {Pl} (A)=\operatorname {Prob} (A)}$ ${\displaystyle \operatorname {Bel} (A)=0;\quad \operatorname {Pl} (A)=1}$ ${\displaystyle \operatorname {Bel} }$ ${\displaystyle \operatorname {Pl} }$

Example (continued)

The following values ​​result: ${\displaystyle F(P)=\{{\text{Peter}},{\text{Paul}},{\text{Egon}},\{{\text{Peter,Paul}}\},U\}}$

	Peter	Paul	Egon	Peter or Paul	Peter or Egon	Paul or Egon
Belief	0.1	0.2	0.3	0.6	0.4	0.5
plausibility	0.5	0.6	0.4	0.7	0.8	0.9

The probability that Peter is the thief is between and , the probability that it is Peter or Paul is between and etc. ${\displaystyle \operatorname {Prob} }$ ${\displaystyle 0{,}1}$ ${\displaystyle 0{,}5}$ ${\displaystyle 0{,}6}$ ${\displaystyle 0{,}7}$

Dempster's rule of combinations

Dempster's combination rule (Engl. Dempster rule of combination ) is an essential tool of the evidence theory. This rule can be used to combine different pieces of evidence into one new piece of evidence. Betwo different evidences on the sameandtheir bodies of evidence. The combined evidenceresults from: ${\displaystyle P_{1},P_{2}}$ ${\displaystyle U}$ ${\displaystyle F(P_{1}),F(P_{2})}$ ${\displaystyle P_{1}\oplus P_{2}}$

${\displaystyle {\begin{aligned}&P_{1}\oplus P_{2}(A)&&=\sum _{B\in F(P_{1}),C\in F(P_{2}):B\cap C=A}P_{1}(B)\cdot P_{2}(C)/(1-K);\\&K&&=\sum _{B\in F(P_{1}),C\in F(P_{2}):B\cap C=\emptyset }P_{1}(B)\cdot P_{2}(C);\quad A\in {\mathcal {P}}(U).\end{aligned}}}$

${\displaystyle P_{1}\oplus P_{2}}$only takes into account the "consensus parts" of the two pieces of evidence ; H. for one only those who "generate" accordingly . All with will not be considered because there are evidence items that have nothing in common, that are in conflict with each other. The size in the denominator is therefore also called the conflict between the two evidences . ${\displaystyle P_{1},P_{2}}$ ${\displaystyle A\in {\mathcal {P}}(U)}$ ${\displaystyle B\in F(P_{1}),C\in F(P_{2})}$ ${\displaystyle A}$ ${\displaystyle B\cap C=A}$ ${\displaystyle B\in F(P_{1}),C\in F(P_{2})}$ ${\displaystyle B\cap C=\emptyset }$ ${\displaystyle K}$ ${\displaystyle P_{1},P_{2}}$

Example (continued)

We also use the theft example from above . Be the evidence from the example above and another evidence that Egon with , Peter and Paul with and all together with as perpetrators. with the corresponding probabilities is listed in the following two tables: ${\displaystyle U=\{{\text{Peter}},{\text{Paul}},{\text{Egon}}\}}$ ${\displaystyle P_{1}}$ ${\displaystyle P_{2}}$ ${\displaystyle 0{,}3}$ ${\displaystyle 0{,}6}$ ${\displaystyle 0{,}1}$ ${\displaystyle F(P_{1},F(P_{2}))}$

${\displaystyle F(P_{1})}$							${\displaystyle F(P_{2})}$
Peter	Paul	Egon	Peter and Paul	all ( ) ${\displaystyle =U}$			Egon	Peter and Paul	all ( ) ${\displaystyle =U}$
0.1	0.2	´0.3	0.3	0.1			0.3	0.6	0.1

Let us first calculate the conflict: There are 4 disjoint pairs between the two evidences, namely (Peter, Egon), (Paul, Egon), (Egon, Peter and Paul) and (Peter and Paul, Egon), i.e. H. it surrenders . So the denominator in Dempster's rule is . Let's calculate for example . There are two pairs as an average even (Peter), namely (Peter, Peter and Paul) and (Peter, all ( )), i.e. H. is in the numerator of the rule , so it results . The following table shows the overall result: ${\displaystyle K=0{,}1\cdot 0{,}3+0{,}2\cdot 0{,}3+0{,}3\cdot 0{,}6+0{,}3\cdot 0{,}3=0{,}36}$ ${\displaystyle 1-K=0{,}64}$ ${\displaystyle P_{1}\oplus P_{2}({\text{Peter}})}$ ${\displaystyle =U}$ ${\displaystyle 0{,}1\cdot 0{,}6+0{,}1\cdot 0{,}1=0{,}07}$ ${\displaystyle P_{1}\oplus P_{2}({\text{Peter}})=0{,}07/0{,}64=0{,}109}$

${\displaystyle P_{1}\oplus P_{2}}$
Peter	Paul	Egon	Peter and Paul	all ( ) ${\displaystyle =U}$
0.109	0.219	0.234	0.422	0.016

properties

• Total ignorance is the "one element" of Dempster's rule; H. it applies: . ${\displaystyle I}$ ${\displaystyle P\oplus I=P}$
• Total evidence coupled with any evidence results in total evidence, although this applies. ${\displaystyle P_{T}}$ ${\displaystyle P}$ ${\displaystyle P_{T}\oplus P\neq P_{T}}$
• Be two total pieces of evidence on with . Then there is total evidence with the probabilities ${\displaystyle P_{1},P_{2}}$ ${\displaystyle U}$ ${\displaystyle P_{1}(\{u_{i}\})=p_{i}^{(1)},\quad P_{2}(\{u_{i}\})=p_{i}^{(2)};\quad u_{i}\in U;\quad i=1,\cdots ,n}$ ${\displaystyle P_{1}\oplus P_{2}}$

${\displaystyle (p_{1}\oplus p_{2})_{i}={\frac {p_{i}^{(1)}\cdot p_{i}^{(2)}}{\sum _{j=1}^{n}p_{j}^{(1)}\cdot p_{j}^{(2)}}};\quad i=1,\cdots ,n}$.

If one interprets as a priori probability and as (current) likelihood distribution , then this formula is identical to Bayes' formula for determining the a posteriori probability . ${\displaystyle P_{1}}$ ${\displaystyle P_{2}}$

criticism

${\displaystyle P_{1}\oplus P_{2}}$"Forgets" the parts of the conflict between and , which often goes against intuition, especially when it is large . Be z. B. . Let the evidence be given by and the evidence through . Then it is determined by , i. H. the great conflict between and is forgotten. For example, if there are three films and describe Paul and Paula's interests in them, then that may go because they agree on the consensus film . But if and the opinion of two doctors describe, it is completely counterintuitive that you can use the small consensus partial retreats. ${\displaystyle P_{1}}$ ${\displaystyle P_{2}}$ ${\displaystyle K}$ ${\displaystyle U=\{A,B,C\}}$ ${\displaystyle P_{1}}$ ${\displaystyle P_{1}(\{A\})=0{,}99;\quad P_{1}(\{C\})=0{,}01}$ ${\displaystyle P_{2}}$ ${\displaystyle P_{2}(\{B\})=0{,}99;\quad P_{2}(\{C\})=0{,}01}$ ${\displaystyle P_{1}\oplus P_{2}}$ ${\displaystyle P_{1}\oplus P_{2}(\{C\})=1}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A,B,C}$ ${\displaystyle P_{1},P_{2}}$ ${\displaystyle C}$ ${\displaystyle A={\text{Gehirntumor}};\quad B={\text{Gehirnhautentzündung}};\quad C={\text{Gehirnerschütterung}}}$ ${\displaystyle P_{1},P_{2}}$ ${\displaystyle {\text{Gehirnerschütterung}}}$

However, it must be noted that in the above example the doctor obviously has total evidence that it cannot be meningitis, because he gives this option a plausibility of exactly zero. The doctor, on the other hand, has total evidence that no tumor is present. Since there is definitive evidence for one of the options that they are out of the question , it also seems intuitively more understandable to withdraw to the residual hypothesis that the patient has a concussion, even if none of the doctors assumed it was likely. Another pathological aspect of this example is that the doctors are 100% sure that they cannot be wrong, but nevertheless estimate very poorly. ${\displaystyle P_{1}}$ ${\displaystyle P_{2}}$ ${\displaystyle ({Pl}(A)={Pl}(B)=0)}$

Further developments

There are many modifications and further developments, for example with regard to the exponential complexity of the Dempster rule, but also the criticism of the Dempster rule.

literature

• G. Shafer: Perspectives on the theory and practice of belief functions. In: International Journal of Approximate Reasoning. 3, 1990, pp. 1-40.
• G. Shafer, J. Pearl (Ed.): Readings in Uncertain Reasoning. Morgan Kaufmann, 1990.
• J. Pearl: Reasoning with Belief Functions: Analysis of Compatibility , The International Journal of Approximate Reasoning 4 (1990), 363-389. doi : 10.1016 / 0888-613X (90) 90013-R
• R. Kruse, E. Schwecke, J. Heinsohn: Uncertainty and Vagueness in Knowledge Based Systems , Springer 1991
• RR Yager, L. Lui: Classic works of the Dempster-Shafer theory of belief functions , Springer 2008

Individual evidence

1. ^ Glenn Shafer: A Mathematical Theory of Evidence. Princeton University Press 1976.
2. ^ AP Dempster: A generalization of Bayesian inference. Journal of the Royal Statistical Society. Series B 30, 1968, pp. 205-247 full text
3. ↑ Gordon, J. and EH Shortliffe: The Dempster-Shafer Theory of Evidence , in: Rule-Based Expert Systems: The MYCIN Experiments of the Stanford Heuristic Programming Project (eds. Buchanan, BG and EH Shortliffe), Addison-Wesley 1984, 272-292 MYCIN project
4. ↑ Shenoy, PP and G. Shafer, Propagating belief functions using local computations, IEEE Expert 1 (1986) 43-52
5. ↑ Ruspini, E .: The logical foundations of evidential reasoning , SRI Technical Note 408, 1986 (revised 1987)
6. ^ Wilson, N .: The assumptions behind Dempster's rule , in: Proceedings of the 9th Conference on Uncertainty in Artificial Intelligence , pages 527-534, Morgan Kaufmann Publishers 1993, San Mateo, CA, USA
7. ↑ Voor Braak, F .: On the justification of Dempster's rule of combination , Artificial Intelligence 48.1991, 171-197