Assignment 3: Probability and Bayesian Networks Solution

Part 1: Probability (30 Points)




Q1 (10 Points)




Let A; B and C be three events with given probabilities where A[B represents events occurring together or by themselves (OR) and A \ B represents the events occurring together (AND):

P(A) = 0:4 P(A [ B) = 0:8 P(B \ (A [ C)) = 0:4




P(B) = 0:7 P(B \ C) = 0:2




P(C) = 0:3 P(C \ (A [ B)) = 0:2




Find the probabilities that:




1. (5 points) Exactly two of the event among A; B and C occurs.











































2. (5 points) None of the events A; B and C occurs.

















































1
Q2 (20 Points)




You made 1000 measurements of three Boolean random variables, A, B and C. However, you lost the data labels,but not the counts. As a result, you gave each variable a new name X1, X2 and X3. The table below shows the counts of the samples. You want to gure out the labels again using these counts, i.e. gure out which Xi corresponds to which random variable (among A; B; C). In addition to the counts, you know that:




A and B are mutually exclusive (i.e. they are independent) True value for A, is more common than the true value of B.




The table below shows the counts of the samples. Find the mapping between the original random variables and Xi’s.




X1
X2
X3
Counts
T
T
T
32








T
T
F
59








T
F
T
180








T
F
F
6








F
T
T
2








F
T
F
17








F
F
T
82








F
F
F
622












































































































































2
Part 2: BN Representation and Exact Inference (40 Points)




As part of a study regarding the role of COMP 341 on student happiness, we collected important data from ctional students that were previously enrolled in this class. In an entirely optional ctional survey that all ctional students were required to complete, we asked the following highly objective questions:




Do you party frequently? [Party: Yes/No]




Are you wicked smart? [Smart: Yes/No]




Are you creative? [Creative: Yes/No]




Did you do well on all your written homework assignments? [HW: Yes/No]




Do you play any kind of musical instrument? [Music: Yes/No]




Did you succeed in your Pacman Projects? [Project: Yes/No]




Did you succeed in your most important class (which is COMP 341)? [Success: Yes/No]




Are you currently Happy? [Happy: Yes/No]




Based on the ctional survey results and after consulting a ctional behavioral psychologist we obtained the following complete set of ctional conditional relationships:




HW depends only on Party and Smart




Music depends only on Smart and Creative Project depends only on Smart and Creative Success depends only on HW and Project




Happy depends only on Party, Music, and Success




Hence, we acquired the following ctional Bayesian Network(BN):

















































Q3 (12 Points)




Using the BN above, answer the following true/false questions.




Success is independent of Party given HW.






Smart is independent of Party given Success.






Creative is independent of Party given Happy.






Happy is independent of Smart given Music.






Success is independent of Smart given Project and HW.






Success is independent of Creative given Project.












3
Q4 (28 Points)




Using the Bayesian Network given above, answer the following questions. From now on, the node names will be shortened as follows: Creative, SmArt, Party, ProJect, Music, HomeWork, Success and Happy.




Part a (2 points) Write down the joint probability of this network with the highlighted characters as the corresponding variable names, i.e., P (C; A; P; J; M; W; S; H).




























Part b (2 points) How many parameters do we need to fully specify the Bayesian Network i.e., how many total entries should there be in the tables, ignoring that some probabilities need to sum up to 1?




























Part c (4 points) An alumni visits one of the course TAs for a small chat. The TA knows that the alumni is smart and creative, however the alumni does not want to provide the details of his night life (i.e. if he is partying or not). The TA wants to understand if he is currently happy or not. He uses variable elimination after the alumni leaves. What are his initial factors?














































Part d (4 points) TA suddenly receives a call from the professor. Apparently he remembers the alumni and says that he was very successful in his projects and homeworks. If the TA was to calculate his level of happiness with the newly acquired information using variable elimination, what would be the minimum size of the largest factor in terms of table length?




















































4



Part e (16 points) Carry out the variable elimination steps conceptually with starting from the situ-ation of part d. Make sure to name/enumerate your factors and use the words \join", \sum out" and \normalize" appropriately.




For example you have P (Bj + a), P (Cj + a), P (CjD) and the aim is to nd P (Dj + a):




Initial factors: f1(+a; B) = P (Bj + a), f2(+a; C) = P (Cj + a) and f3(C; D) = P (CjD)

Step 1: Join f2 and f3 to get f4(+a; C; D)




Step 2: Sum out C from f4 to get f5(+a; D)




Step 3: Normalize f5 to get the desired answer




Your answer:















































































































































































5
Part 3: BN Approximate Inference (30 Points)




Q5 (20 Points)




You are trying to x a car that is not starting and to follow the basic principles behind how a car operates, you come up with the following bayesian network:
























































































Part a (2 points) Mandatory Joint Distribution Question: What is the expression of P (B; M; G; I; S)?










Part b (4 points) You tried to start the engine and it worked. You know that the car’s battery is full and the starter motor is functional. Since your gas gauge is not accurate, you are not sure whether your car has enough fuel to start the next time. For some reason, you have recorded your previous observations given in the appendix of this document. Calculate P (S = true) according to this list.




























Part c (4 points) You realized that you also need to include evidence in your calculations to have a more accurate estimate of the probability. Calculate P (S = truejB = full; M = true) according to the list provided in the appendix of this document.











































6



Part d (10 points) You are still not satis ed with your calculations and want to have a more accurate idea. You decide to use likelihood weighting. Fill in the table below with the weight of each sample (not the total weight!). Then, calculate P (S = truejB = full; M = true).




B
M
I
G
S
Counts
Weights Per Sample














B = full
M = true
I = true
G = high
S = true
66
















B = full
M = true
I = true
G = low
S = true
1
















B = full
M = true
I = false
G = high
S = true
31
















B = full
M = true
I = false
G = low
S = true
0
















B = full
M = true
I = false
G = high
S = false
14
















B = full
M = true
I = false
G = low
S = false
19
















B = full
M = true
I = true
G = high
S = false
25
















B = full
M = true
I = true
G = low
S = false
44
























































































































































































7
Q6 (10 Points)




Answer the below questions based on the BN from the question 5 for Gibbs sampling.




Part a (2 points) Given fB = full; M = true; I = true; G = lowg, calculate the probability distribu-tion which will be used to sample S.

























Part b (6 points) Given fB = full; I = true; G = low; S = falseg, calculate the probability distribu-tion which will be used to sample M.





































































































































Part c (2 points) The next uniform sample you get in the range [0; 1) is 0.4. Based on your answer to part b, what would be the sample you chose for M?






















8
Submission




You are going to submit a SINGLE PDF FILE with your solutions on the blackboard site OR give your written homework to the TA, Onur Demiray. DO NOT DO BOTH!




You can use scanners, apps similar to CamScanner, your cameras or any other possible way to convert your homework submissions to a digital format.




Do not send your solutions in a picture format (e.g. JPG, PNG, BMP, TIFF, GIF, etc.). They PDF must have A4 paper size.




Any submission other than PDF format is going to receive a very large grade deduction.




While you are submitting, please make sure your scanned assignment is birght (i.e. that you are not submitting a dark page), this is important because we should be able to see what you wrote to grade your submission.



































































































































































9
Appendix: Samples for Q5




B = full
M = false
I = false
S = false
G = full










B = full
M = false
I = true
S = false
G = full










B = empty
M = true
I = false
S = false
G = full










B = empty
M = true
I = true
S = false
G = empty










B = full
M = true
I = true
S = true
G = full










B = empty
M = true
I = true
S = true
G = empty










B = empty
M = true
I = false
S = false
G = empty










B = full
M = true
I = true
S = true
G = empty










B = empty
M = true
I = false
S = true
G = full










B = empty
M = true
I = true
S = false
G = full










B = full
M = false
I = true
S = true
G = empty










B = full
M = true
I = true
S = false
G = empty










B = empty
M = false
I = true
S = false
G = empty










B = empty
M = false
I = true
S = false
G = empty










B = full
M = false
I = true
S = false
G = empty










B = empty
M = true
I = false
S = false
G = full










B = empty
M = true
I = true
S = false
G = empty










B = full
M = true
I = true
S = true
G = full










B = full
M = true
I = false
S = true
G = full










B = empty
M = false
I = true
S = true
G = empty










B = empty
M = true
I = false
S = false
G = empty










B = empty
M = false
I = false
S = false
G = full










B = full
M = false
I = true
S = false
G = empty










B = full
M = true
I = false
S = false
G = full










B = full
M = true
I = true
S = false
G = empty










B = full
M = true
I = false
S = true
G = full










B = full
M = true
I = false
S = false
G = empty










B = full
M = true
I = false
S = false
G = empty










B = full
M = true
I = true
S = false
G = full










B = empty
M = false
I = true
S = true
G = full










B = empty
M = true
I = true
S = false
G = empty










B = empty
M = false
I = false
S = true
G = full










B = full
M = true
I = true
S = false
G = full










B = empty
M = true
I = true
S = true
G = full










B = empty
M = false
I = false
S = false
G = full










B = empty
M = true
I = true
S = false
G = empty










B = empty
M = true
I = false
S = true
G = full










B = full
M = true
I = false
S = true
G = full










B = full
M = false
I = true
S = false
G = empty






































































10