Written Assignment 4: Solution
Deadline: November 24th, 2020
Instruction: You may discuss these problems with classmates, but please complete the write- ups individually. (This applies to BOTH undergraduates and graduate students.) Remember the collaboration guidelines set forth in class: you may meet to discuss problems with classmates, but you may not take any written notes (or electronic notes, or photos, etc.) away from the meeting. Your answers must be typewritten, except for figures or diagrams, which may be hand-drawn. Please submit your answers (pdf format only) on Canvas.
Q1. Bayes Nets: Independence (25 points)
Consider the following Bayesian network with 10 variables {X1, X2, . . . , X10}.
X1
X2
X3
X8
X4
X7 X6
X X10 9
X5
Which of the following statements are true: 1. X6 ⊥X1 |X2,X4
Answer. True 2. X6 ⊥X9 |X4
Answer. False 3. X3 ⊥X9 |X8
Answer. False
4. X1 ⊥X2 |X6 Answer. False
1
5. X4 ⊥X8 |X3,X7 Answer. True
Q2. Bayes Nets: Inference (45 points)
Assume the following Bayes Net and corresponding CPTs.
Compute the following conditional probabilities (hint: use the variable elimination method): 1. P(B=1|E=1)
Answer. Hidden variables are A, C, D. We will perform variable elimination using this order. Eliminate A: f1(B) = P (a)P (B | a)
a
Eliminate C: f2(B,D,E = 1) = P(c | B)P(E = 1 | C,D) c
Eliminate D: f3(B,E = 1) = P(d | B)f2(B,d,E = 1) d
Join all remaining factors: f4(B, E = 1) = f1(B) × f3(B, E = 1) Normalization: P(B=1|E=1)= f4(B=1,E=1)
f4(B = 0, E = 1) + f4(B = 1, E = 1) 2
We obtain the following tables:
B
D
E=1
f2(B,D,E = 1)
0
0
1
0.64
0
1
1
0.2
1
0
1
0.64
1
1
1
0.2
B
f1(B)
0
0.24
1
0.76
B
E=1
f3(B,E = 1)
0
1
0.552
1
1
0.464
B
E=1
f4(B,E = 1)
0
1
0.13248
1
1
0.35264
Therefore, P (B = 1 | E = 1) = 0.727 2. P(A=1|C =0,E =0)
Answer. Hidden variables are B, D. We will perform variable elimination using this order. Eliminate B: f1(A,C = 0,D) = P(b | A)P(C = 0 | b)P(D | b)
b
Eliminate D: f2(A,C = 0,E = 0) = f1(A,C = 0,d)P(E = 0 | C = 0,d) d
Join all remaining factors: f3(A,C = 0,E = 0) = P(A)f2(A,C = 0,E = 0) Normalization: P(A=1|C =0,E =0)= f3(A=1,C =0,E =0)
We obtain the following tables:
f3(A = 0, C = 0, E = 0) + f3(A = 1, C = 0, E = 0)
A
C=0
D
f1(A,C = 0,D)
0
0
0
0.408
0
0
1
0.192
1
0
0
0.384
1
0
1
0.216
A
C=0
E= 0
f2(A,C = 0,E = 0)
0
0
0
0.2352
1
0
0
0.2496
A
C=0
E= 0
f3(A,C = 0,E = 0)
0
0
0
0.04704
1
0
0
0.19968
Therefore, P (A = 1 | C = 0, E = 0) = 0.809 3. P(B=1|D=1)
3
Answer. Hidden variables are A, C, E. We will perform variable elimination using this order. Eliminate A: f1(B) = P (a)P (B | a)
a
Eliminate C: f2(B,D = 1,E) = P(c | B)P(E | C,D = 1) c
Eliminate E: f3(B,D = 1) = f2(B,D = 1,E) e
Join all remaining factors: f4(B, D = 1) = f1(B)f3(B, D = 1)P (D = 1 | B) Normalization: P(B=1|D=1)= f4(B=1,D=1)
We obtain the following tables:
f4(B = 1, D = 1) + f4(B = 0, D = 1)
B
D=1
E
f2(B,D = 1,E)
0
1
0
0.8
0
1
1
0.2
1
1
0
0.8
1
1
1
0.2
B
f1(B)
0
0.24
1
0.76
B
D=1
f3(B,D = 1)
0
1
1.0
1
1
1.0
B
D=1
f4(B,D = 1)
0
1
0.048
1
1
0.304
Therefore, P (B = 1 | D = 1) = 0.8636
4
Q3. Bayes Nets: Sampling (30 points)
In this question, we will work with the same Bayes net and CPTs as Q2.
Q3.1. Rejection Sampling (7 points) In this question, we will perform rejection sampling to estimate P(C = 1 | B = 1,E = 1). Perform one round of rejection sampling, using the random samples given in the table below. Variables are sampled in the order A, B, C, D, E.
Note that the sampling attempt should stop as soon as you discover that the sample will be rejected. In that case mark the assignment of that variable and write “none” for the rest of the variables. When generating random samples, use as many values as needed from the table below, which we generated independently and uniformly at random from [0, 1). Use numbers from left to right. To sample a binary variable W with probability P(W = 0) = p and P(W =1)=1−pusingavalueafromthetable,chooseW =0ifa
6