The original Peter Paul and Mary example from P. Smets
Ref.: Smets, P. (1988) Belief Functions. Non-Standard Logics for Automated Reasoning (P. Smets, A. Mandani, D. Dubois, H. Prade, ed.), Academic Press, New York, p. 254-286
The facts (from Smets’s example)
Witness 1: A janitor who was asleep claims he heard the victim yelling and then saw a small man running out of the victim’s house. Peter and John are men. John and Mary are small.
Witness 2: An old lady with a bad sighting, who lives across the street from the victim and who saw the crime through her window and claims the murderer was much taller than the victim. Peter is a tall man.
Witness 3: Peter’s girlfriend testifies that Peter was at her home far away from the victim’s house when the crime happened. An alibi, pointing to John or Mary..
Firstly, I show how to solve the problem by pooling the evidence with Dempster’s Rule. Secondly, I solve the same problem with a belief network.
1. The pooling of evidence
We consider one variable with 3 values: \[Culprit = \{Peter, John, Mary\}\] We assess (giving a weight) the three pieces of evidence collected on the crime scene.
We combine them with Dempster’s Rule.
## Witness1, A janitor asleep## witness1 specnb mass
## 1 Peter + John 1 0.5
## 2 John + Mary 2 0.2
## 3 frame 3 0.3## Add all singletons in order to view results later## witness1_plus_singl specnb mass status
## 1 Peter 1 0 1
## 2 John 2 0 1
## 3 Mary 3 0 1
## 4 Peter + John 4 0.5 0
## 5 John + Mary 5 0.2 0
## 6 frame 6 0.3 0## Witness2, An old lady with bad sighting saw a tall man## tall specnb mass
## 1 Peter 1 0.6
## 2 frame 2 0.4Combination by Dempster’s Rule
Consider the first two witness. Witness1 says a man (m = 0.5), small (m = 0.2). Witness2 says a tall man (Peter, m = 0.6).
## Combination of witnesses 1 and 2## Peter John Mary mass bel disbel unc plau rplau
## Peter 1 0 0 0.55 0.55 0.09 0.36 0.91 2.00
## John 0 1 0 0.00 0.00 0.55 0.45 0.45 0.45
## Mary 0 0 1 0.00 0.00 0.77 0.23 0.23 0.23
## Peter + John 1 1 0 0.23 0.77 0.00 0.23 1.00 4.40
## John + Mary 0 1 1 0.09 0.09 0.55 0.36 0.45 0.50
## frame 1 1 1 0.14 1.00 0.00 0.00 1.00 Inf## Conflict between evidence## [1] 0.12Peter (a tall man) is the more plausible culprit (belief of 0.55 with plausibility ratio of 2). This is the one for which the two pieces of evidence are the less contradictory. John and Mary are small, Mary is a woman They have each one a belief score of 0, since no evidence points exactly toward them.
Adding a third piece of evidence
Peter’s girlfriend says Peter was with him all night. We use Dempster’s Rule to combine her testimony with the previous results.
## Witness 3, the girlfriend clears Peter## girlfriend specnb mass
## 1 John + Mary 1 1
## 2 frame 2 0## $mbp
## Peter John Mary mass bel disbel unc plau rplau
## John 0 1 0 0.5 0.5 0.0 0.5 1.0 2.0
## Mary 0 0 1 0.0 0.0 0.5 0.5 0.5 0.5
## Peter 1 0 0 0.0 0.0 1.0 0.0 0.0 0.0
## John + Mary 0 1 1 0.5 1.0 0.0 0.0 1.0 Inf
## Peter + John 1 1 0 0.0 0.5 0.0 0.5 1.0 2.0
## frame 1 1 1 0.0 1.0 0.0 0.0 1.0 Inf
##
## $Conflict
## [1] 0.6We see from the results that Peter remains the more plausible culprit His plausibility ratio is now of one, instead of 2. The result can vary from 2 to 0, depending of the degree of doubt we cast on the testimony of the girlfriend.
2. Solving the same problem using a belief network
Facts and relations
Instead of viewing the three suspects Peter, John, Mary as value of a variable, we consider them as binary variables.
Peter: \[P = \{yes, no\}\] John: \[J = \{yes, no\}\] Mary: \[M = \{yes, no\}\] We assess the evidence of witness 1 in the product space \(F_{PJM} = \prod(P, J, M)\).
We assess the evidence of witness 2 in the space \(F_{P}\).
We assess the evidence of witness 3 in the product space \(F_{JM} = \prod(J, M)\).
To obtain the correct marginals, we need to add a relation between the three binary variables. For example, we want to obtain the same result if we put \(Peter = \{no\}\) instead of \((John, Mary) =\{\{yes, no\}, \{no, yes\}\}\) for witness 3. The following relation serves this purpose.
In the product space \(F_{PJM} = \prod(P, J, M)\), we consider the union of three subsets: \(\{Peter, ¬John, ¬Mary\}, \{¬Peter, John, ¬Mary\}, \{¬Peter, ¬John, Mary\}\), where “¬” means “negation”. We put a mass of 1 to this relation. This relation says simply that the culprit is one of the three suspects and there is only one culprit. We could interpret this as the statement of the detective.
## witness 1 induced relation## The description matrix of the relation## yes no yes no yes no
## [1,] 1 0 0 1 0 1
## [2,] 0 1 1 0 0 1
## [3,] 0 1 1 0 0 1
## [4,] 0 1 0 1 1 0
## [5,] 1 1 1 1 1 1## the testimony Peter or John (0.5), John or Mary (0.2) in the product space## witness1_rel specnb mass
## 1 yes no no + no yes no 1 0.5
## 2 no yes no + no no yes 2 0.2
## 3 frame 3 0.3## Evidence for witness 2## Peter (.6)## witness2 specnb mass
## 1 yes 1 0.6
## 2 frame 2 0.4## witness 3 induced relation## The description matrix of the relation## yes no yes no
## [1,] 0 1 1 0
## [2,] 1 0 0 1
## [3,] 1 1 1 1## The testimony John or Mary (1) expressed in the product space## witness3_rel specnb mass
## 1 yes no + no yes 1 1
## 2 frame 2 0## Defining a relation linking the three variables in PxJxM## Linking the variables## Detective's assumption expressed in the product space## PJM_rel specnb mass
## 1 yes no no + no yes no + no no yes 1 1
## 2 frame 2 0Finally we have 3 variables, one piece of evidence against Peter, two evidences expressed as relations and a relation between suspects.
We construct the hypergraph and use the peeling algorithm to obtain the belief function of the variable Culprit.
The Hypergraph
## Encode pieces of evidence and relations with an incidence matrix
## The incidence matrix of the Hypergraph
## r_W1 ev_W2 r_W3 r_Detective
## Peter 1 1 0 1
## John 1 0 1 1
## Mary 1 0 1 1
## information on variables necessary for the Peeling algorithm
## [[1]]
## r_W1 ev_W2 r_W3 r_Detective
## Peter 1 1 0 1
## John 1 0 1 1
## Mary 1 0 1 1
##
## [[2]]
## [1] "Peter" "John" "Mary"
##
## [[3]]
## [1] "witness1_rel" "witness2" "witness3_rel" "PJM_rel"
Study of extensions and combinations
## Combining in the product space P x J x M## We use witness1_rel relation as a reference to extend the others.## Extend Witness2 on PJM## w2_xtnd specnb mass
## 1 yes yes yes + yes yes no + yes no yes + yes no no 1 0.6
## 2 frame 2 0.4## Extend Witness 3 on PJM## w3_xtnd specnb mass
## 1 yes yes no + yes no yes + no yes no + no no yes 1 1
## 2 frame 2 0## Combining the three relations on PJM## Combining w2_xtnd with witness1_rel## rel_comb## rel_comb specnb mass
## 1 ø 1 0.12
## 2 yes no no 2 0.3
## 3 yes no no + no yes no 3 0.2
## 4 no yes no + no no yes 4 0.08
## 5 yes yes yes + yes yes no + yes no yes + yes no no 5 0.18
## 6 frame 6 0.12## Combining rel_comb with w3_xtnd## rel_comb2## rel_comb2 specnb mass
## 1 ø 1 0.42
## 2 no yes no 2 0.2
## 3 yes no no 3 0
## 4 no yes no + no no yes 4 0.08
## 5 yes yes no + yes no yes 5 0.18
## 6 yes no no + no yes no 6 0
## 7 yes yes no + yes no yes + no yes no + no no yes 7 0.12
## 8 yes yes yes + yes yes no + yes no yes + yes no no 8 0
## 9 frame 9 0## Redo the combinations with a modifiied representation of witness 3## Define w3 par ¬Peter (1), instead of jojn or Mary## witness3b specnb mass
## 1 no 1 1
## 2 frame 2 0## Extend Witness 3 on PJM## w3b_xtnd specnb mass
## 1 no yes yes + no yes no + no no yes + no no no 1 1
## 2 frame 2 0## combining with w3b_xtnd.## Note the differennce with the preceding result## rel_comb2b specnb mass
## 1 ø 1 0.6
## 2 no yes no 2 0.2
## 3 yes no no 3 0
## 4 no yes no + no no yes 4 0.08
## 5 yes no no + no yes no 5 0
## 6 no yes yes + no yes no + no no yes + no no no 6 0.12
## 7 yes yes yes + yes yes no + yes no yes + yes no no 7 0
## 8 frame 8 0## Combining rel_comb2 rith PJM_rel## rel_comb3 specnb mass
## 1 ø 1 0.6
## 2 no yes no 2 0.2
## 3 yes no no 3 0
## 4 no yes no + no no yes 4 0.2
## 5 yes no no + no yes no 5 0
## 6 yes yes no + yes no yes 6 0
## 7 yes no no + no yes no + no no yes 7 0
## 8 yes yes no + yes no yes + no yes no + no no yes 8 0
## 9 yes yes yes + yes yes no + yes no yes + yes no no 9 0
## 10 frame 10 0## Combining rel_comb2b rith PJM_rel## rel_comb3b specnb mass
## 1 ø 1 0.6
## 2 no yes no 2 0.2
## 3 yes no no 3 0
## 4 no yes no + no no yes 4 0.2
## 5 yes no no + no yes no 5 0
## 6 yes no no + no yes no + no no yes 6 0
## 7 no yes yes + no yes no + no no yes + no no no 7 0
## 8 yes yes yes + yes yes no + yes no yes + yes no no 8 0
## 9 frame 9 0## Now we obtain the same result## rel_comb3_norm specnb mass
## 1 no yes no 1 0.5
## 2 yes no no 2 0
## 3 no yes no + no no yes 3 0.5
## 4 yes no no + no yes no 4 0
## 5 yes yes no + yes no yes 5 0
## 6 yes no no + no yes no + no no yes 6 0
## 7 yes yes no + yes no yes + no yes no + no no yes 7 0
## 8 yes yes yes + yes yes no + yes no yes + yes no no 8 0
## 9 frame 9 0## [1] 0.6## rel_comb3b_norm specnb mass
## 1 no yes no 1 0.5
## 2 yes no no 2 0
## 3 no yes no + no no yes 3 0.5
## 4 yes no no + no yes no 4 0
## 5 yes no no + no yes no + no no yes 5 0
## 6 no yes yes + no yes no + no no yes + no no no 6 0
## 7 yes yes yes + yes yes no + yes no yes + yes no no 7 0
## 8 frame 8 0## [1] 0.6## Compute marginals## Peter## m_P specnb mass
## 1 no 1 1
## 2 yes 2 0
## 3 frame 3 0## John or Mary## m_JM specnb mass
## 1 yes no 1 0.5
## 2 no no 2 0
## 3 yes no + no yes 3 0.5
## 4 yes no + no no 4 0
## 5 yes no + no yes + no no 5 0
## 6 frame 6 0## John## m_J specnb mass
## 1 yes 1 0.5
## 2 no 2 0
## 3 frame 3 0.5## Mary## m_M specnb mass
## 1 no 1 0.5
## 2 frame 2 0.5Computation of the belief function of the variable of interest, using the peeling algorithm
Our variable of interest is one of the three suspects. We have to choose an order of elimination of the variables manually, since we don’t have an algorithm at our disposal yet, and call the peeling three times For example, we can choose to eliminate Peter first, then John to know about Mary.
Hence, the peeling is not very useful here, We can answer all our questions in the product space \(F_{PJM} = \prod(P, J, M)\).
## Elimination order : 1 2
## r_W1 ev_W2 r_W3 r_Detective
## Peter 1 1 0 1
## John 1 0 1 1
## Mary 1 0 1 1
## Hg matrix 1 1 1 1 0 0 0 1 1 1 1 1
## i = : 1 . Eliminating variable no 1 : Peter
## rels numbers to elim 1 2 4
## Relations to combine: witness1_rel witness2 PJM_relRelations to combine: witness1_rel witness2 PJM_rel
## combining extended relation number : 1
##
## combining extended relation number : 2
##
## combining extended relation number : 3
## eliminating variable 1
## graph updated
## r_W1 ev_W2 r_W3 r_Detective R5
## Peter 0 0 0 0 0
## John 0 0 1 0 1
## Mary 0 0 1 0 1
## relations updated witness1_rel witness2 witness3_rel PJM_rel rel5
## i = : 2 . Eliminating variable no 2 : John
## rels numbers to elim 3 5
## Relations to combine: witness3_rel rel5
## combining extended relation number : 1
##
## combining extended relation number : 2
## eliminating variable 2
## graph updated
## r_W1 ev_W2 r_W3 r_Detective R5 R6
## Peter 0 0 0 0 0 0
## John 0 0 0 0 0 0
## Mary 0 0 0 0 0 1
## relations updated witness1_rel witness2 witness3_rel PJM_rel rel5 rel6
## rels numbers to combine 6
## Peeling ended## Result for the variable of interest## yes no mass bel disbel unc plau rplau
## no 0 1 0.5 0.5 0 0.5 1 2
## frame 1 1 0.5 1.0 0 0.0 1 Inf## Contradiction Indice: 0.5454545