Description

dey00011
1 Q3.i
Initially the likelihood of W and H will be (1,1) as both of them are leaf node with no children. Therefore, initial condition of the belief propagation algorithm would be:
Table 1: Initial condition
X BEL(X) π(X) λ(X)
R – (0.2,0.8) –
S – (0.1,0.9) –
W – – (1,1)
H – – (1,1)
As in the first step, W and H will pass (1,1) to their parents,
λ(R) = λ(W)λ(H) = (1,1).
Similarly, λ(S) will be (1,1). Now, we can compute BEL(R) and BEL(S) as follows:
BEL(R) = λ(R).π(R) = (0.2,0.8)
BEL(S) = λ(S).π(S) = (0.1,0.9).
Therefore, we arrive at the following:
Table 2: Step 1
X BEL(X) π(X) λ(X)
R (0.2,0.8) (0.2,0.8) (1,1)
S (0.1,0.9) (0.1,0.9) (1,1)
W – – (1,1)
H – – (1,1)
Once, we calculate the belief of the parents, it can be propagated to the children i.e. W and H to update their priors. Then, we have the following:
.
Therefore,
πW = (P(W = T|R = T) ∗ 0.2P(W = T|R = F) ∗ 0.8,
P(W = F|R = T) ∗ 0.2 + P(W = F|R = F) ∗ 0.8)
= ((1)(0.2) + (0.2)(0.8),(0)(0.2) + (0.8)(0.8)) = (0.36,0.64).
and,
.
Hence,
πH = (P(H = T|R = T,S = T) ∗ 0.2 ∗ 0.1 + P(H = T|R = F,S = T) ∗ 0.8 ∗ 0.1
+ P(H = T|R = T,S = F) ∗ 0.2 ∗ 0.9 + P(H = T|R = F,S = F) ∗ 0.8 ∗ 0.9,
P(H = F|R = T,S = T) ∗ 0.2 ∗ 0.1 + P(H = F|R = F,S = T) ∗ 0.8 ∗ 0.1,
+ P(H = F|R = T,S = F) ∗ 0.2 ∗ 0.9 + P(H = F|R = F,S = F) ∗ 0.8 ∗ 0.9)
= (0.02 + 0.072 + 0.18,0.008 + 0.72) = (0.272,0.728).
Therefore, after this step we arrive at the following:
Table 3: Step 2
X BEL(X) π(X) λ(X)
R (0.2,0.8) (0.2,0.8) (1,1)
S (0.1,0.9) (0.1,0.9) (1,1)
W – (0.36,0.64) (1,1)
H – (0.272,0.728) (1,1)
Next, we can calculate the belief of W and H as follows:
BEL(W) = ((0.36)(1),(0.64)(1)) = (0.36,0.64)
BEL(H) = ((0.272)(1),(0.728)(1)) = (0.272,0.728).
Thus we can update the table as follows:
Table 4: Step 3
X BEL(X) π(X) λ(X)
R (0.2,0.8) (0.2,0.8) (1,1)
S (0.1,0.9) (0.1,0.9) (1,1)
W (0.36,0.64) (0.36,0.64) (1,1)
H (0.272,0.728) (0.272,0.728) (1,1)
Therefore, the belief that Watson’s grass is wet is 0.36.
2 Q3.ii
As calculated previously, the belief that Holmes’s grass is wet is 0.272.
3 Q3.iii
If Holmes observes that his grass is wet, we need to update the table as follows:
Table 5: Step 3
X BEL(X) π(X) λ(X)
R (0.2,0.8) (0.2,0.8) (1,1)
S (0.1,0.9) (0.1,0.9) (1,1)
W (0.36,0.64) (0.36,0.64) (1,1)
H (1,0) (0.272,0.728) (1,0)
This message has to be passed on to R and S. Using the formula λX(Ui) = Xλ(X) X P(X|U1,…,Uk) Y πX(Uk),
X Uk,k6=i k6=i
and following the same procedure as shown in Q3.i, we can compute the following table:
Table 6: Step 4
X BEL(X) π(X) λ(X)
R (0.74,0.26) (0.2,0.8) (1,0.09)
S (0.338,0.662) (0.1,0.9) (0.92,0.2)
W (0.788,0.212) (0.788,0.212) (1,1)
H (1,0) (0.272,0.728) (1,0)
Therefore, the belief that Watson’s grass is wet is 0.788.
4 Q3.iii
Now, if Holmes observes that Watson’s grass is also wet as well as his own, then we need to update the belief of node W as well and the table is shown below:
Table 7: Step 4
X BEL(X) π(X) λ(X)
R (0.74,0.26) (0.2,0.8) (1,0.09)
S (0.338,0.662) (0.1,0.9) (0.92,0.2)
W (1,0) (0.788,0.212) (1,0)
H (1,0) (0.272,0.728) (1,0)
Then, this message has to be passed on to R and we need to update the prior π(R). We can use the following formulas for these:
λX(Ui) = Xλ(X) X P(X|U1,…,Uk) Y πX(Uk),
X Uk,k6=i k6=i
n
π(X) = X P(X|U1,…,Uk)YπX(Ui).
U1,…,Uk i=1
Then we can compute the beliefs using BEL(X) = λ(X)π(X) as we did in Q3.i. We can arrive at the following:
BEL(s) = (0.16,0.84).
Therefore, the belief that the sprinkler was on is 0.16.