Assignment 3- Part I/II Probabilistic Reasoning Solution

Problem 1 (15 points): Consider the following Bayesian network, where variables A through E are all Boolean valued.




Note: there is a typo in the image, it should be P (A = true) = 0:2 instead of P (D = true) = 0:2 .











































c) What is the probability that A is false given that the four other variables are all known to be

a) What is the probability that all five of these Boolean variables are simultaneously true?

true?




[Hint: You have[Hint:tocomputeTrytousethethejointdefinitiprobabilitynoftheconditionaldistributionprobability.ThestructureandthestructureoftheBayesianofthenetworknetwork. suggests how

For probabilities that can not be computed directly from the network, remember the follow-

the joint probability distribution is decomposed to the conditional probabilities available.]

ing normalization trick: if P( ) = α · ƒ ( ) and P(¬ ) = α · ƒ (¬ ), then you can compute the normalization factor as α = ƒ 1.ƒ0¬ , since P( ) + P(¬ ) = 1.0.]




b) What is the probability that all five of these()+Boolean() variables are simultaneously false?




[Hint: Answer(15 points)similarly to above.]




Question 3: For this problem, check the Variable Elimination algorithm in your book. Also consider

c) What is the probability that A is false given that the four other variables are all known to be true?

the Bayesian network from the “burglary” example.




Problem 2 (15 points):







Burglary
P(B)
Earthquake
P(E)
.001
.002










Alarm




B E




t t




t f




t f f



P(A)




.95




.94




.29




.001



A
P(J)


A P(M)
JohnCalls t
.90
MaryCalls
t
.70
f
.05


f
.01









Burglary JohnsCalls = true; M aryCalls = true)
and show in detail the calculations that take
a) Calculate P (a) Apply variablej
elimination to the query:
place. Use your book to confirm that your answer is correct.




P(B rg ry|JohnsC s = tr e, M ryC s = tr e)
b) Suppose a Bayesian network has the from of a chain: a sequence of Boolean variables X1; : : : Xn where


and show in detail the calculations that take place. Use your book to confirm that your answer
P arents(X
is
f
X
g
for i = 2; : : : ; n. What is the complexity of computing P (X
j
X = true) using enu-
) =






i


correcti1.


1


n
meration? What is the complexity with variable elimination?

b) Count the number of arithmetic operations performed (additions, multiplications, divisions), and compare it against the number of operations performed by the tree enumeration algo-




Problem 3 (20 points):rithmSuppose. you are working for a financial institution and you are asked to implement a fraud detection system. You plan to use the following information:




When the card holder is travelling abroad, fraudulent transactions are more likely since tourists are prime targets for thieves. More precisely, 1% of transactions are fraudulent when the card holder is travelling, where as only 0:4% of the transactions are fraudulent when she is not travelling. On average, 5% of all transactions happen while the card holder is travelling. If a transaction is fraudulent, then the likelihood of a foreign purchase increases, unless the card holder happens to be travelling. More precisely, when the card holder is not travelling, 10% of the fraudulent transactions are foreign purchases where as only 1% of the legitimate transactions are foreign purchases. On the other hand, when the card holder is travelling, then 90% of the transactions are foreign purchases regardless of the legitimacy of the transactions.




Purchases made over the internet are more likely to be fraudulent. This is especially true for card holders who don’t own any computer. Currently, 75% of the population owns a computer or smart phone and for those card holders, 1% of their legitimate transactions are done over the internet, however this percentage increases to 2% for fraudulent
transactions. For those who don’t own any computer or smart phone, a mere 0:1% of their legitimate transactions is done over the internet, but that number increases to 1:1% for fraudulent transactions. Unfortunately, the credit card company doesn’t know whether a card holder owns a computer or smart phone, however it can usually guess by verifying whether any of the recent transactions involve the purchase of computer related accessories. In any given week, 10% of those who own a computer or smart phone purchase (with their credit card) at least one computer related item as opposed to just 0:1% of those who don’t own any computer or smart phone.




Construct a Bayes Network to identify fraudulent transactions.



What to hand in: Show the graph defining the network and the Conditional Probability Tables associated with each node in the graph. This network should encode the information stated above. Your network should contain exactly six nodes, corresponding to the following binary random variables:




OC : card holder owns a computer or smart phone.




Fraud : current transaction is fraudulent.




Trav : card holder is currently travelling.




FP : current transaction is a foreign purchase.




IP : current purchase is an internet purchase.




CRP : a computer related purchase was made in the past week.




The arcs defining your Network should accurately capture the probabilistic dependencies between these variables.




What is the prior probability (i.e., before we search for previous computer related purchases and before we verify whether it is a foreign and/or an internet purchase) that the current transaction is a fraud? What is the probability that the current transaction is a fraud once we have verified that it is a foreign transaction, but not an internet purchase and that the card holder purchased computer related accessories in the past week?
What to hand in: Indicate the two queries (i.e., P r(variablesjevidence)) you used to compute those two probabil-ities. Show each step of the calculation