CS47100: Introduction to Artificial Intelligence - Assignment 3: Probability and Uncertainty, Bayesian Networks and Pacman
CS47100 Assignment 3
Due date: Friday, Nov 10, 2023 (11:59 pm)
This assignment includes both written exercises and a programming component. Please follow the sub- mission instructions carefully. The “written” portion of the assignment must be typeset with LATEX us- ing the provided template. (Also on OverLeaf at https://www.overleaf.com/read/synckzdgfppw)
Part 1: Written Assignment (50 pts) Probability and Uncertainty (26 pts)
1. (8 pts) Properties of Random Variable
-
(a) (3 pts) Let X be a Bernoulli random, i.e., P (X = 1) = p and P (X = 0) = 1 − p. The variance of a random variable is defined as Var(X) = E(X2) − E(X)2. Compute E(2X) and Var(2X) in terms of p.
-
(b) (3pts)LetXandY bothbeaBernoullirandomandX⊥Y,i.e.,P(X=1)=p,P(X=0)= 1−p,P(Y =1)=pandP(Y =0)=1−p. ComputeE(X+Y)andVar(X+Y)intermsofp.
-
(c) (2 pts) Is the distribution of X+Y and 2X the same?
2. (10 pts) Basic Probability
-
(a) (2 pts) Which of the following expressions is guaranteed to be always true, given the random variables A, B, and C?
i. P(A,B)=P(A)P(B)−P(A|B) ii. P(A,B) = P(A)P(B)
iii. P(A,B)=P(A|B)P(B)+P(B|A)P(A) iv. P(A) = Pb∈B P(A|B = b)P(B = b)
v. P(A,C) = Pb∈B P(A|B = b)P(C|B = b)P(B = b) vi. P(A,B,C)=P(C|A)P(B|C,A)P(A)
-
(b) (2 pts) Assume that the domain of both A and B is {true and false} (A ∈ {true,false} and B ∈ {true, false}). What is P (B = true | A = false) by giving the following quantities?
1
2
P(B=true|A=true) = 1
3 4
-
(c) You witness a night-time hit-and-run accident involving a car in West Lafayette. Assuming that all cars in West Lafayette are black or gray. You swear, under oath, that the car you saw was black. Extensive testing shows that under dim lighting conditions, discrimination between black and gray is 70% reliable. In other words, if a car is gray, with a 70% chance it will appear gray under dim lighting conditions. Similarly, if a car is indeed black, the chance for it to appear black under dim lighting conditions is 70%.
P(A=true) =
P(B=true) =
1
-
(2 pts) Is it possible to calculate the most likely color for the fled car to help the police find the suspect? Show why or why not. (Hint: distinguish carefully between the proposition that the car is black and the proposition that it appears black.)
-
(4 pts) Now consider the case when you are given the additional information that 60 out of 100 cars in West Lafayette are black. Show whether or not it is possible to calculate the most likely color for the fled car.
3. (8 pts) Inference and Independence
-
(a) (5 pts) Let X1, X2 and Y be three discrete random variables. We want to calculate P (Y |X1, X2) but we do not possess any independence/conditional independence information about them. Suppose we know the probability distributions listed in each of the following five cases. Please show whether it is possible for us to calculate P (Y |X1, X2) and if yes, how to calculate.
i. P(X1|Y ), P(X2|Y ) and P(Y ) ii. P(X1),P(X2)andP(X1,X2|Y)
iii. P(X1,X2), P(Y) and P(X1,X2|Y)
iv. P(X1), P(X2), P(X1|Y ) and P(X2|Y )v. P(X1,X2), P(Y), P(X1|Y) and P(X2|Y)
-
(b) (3 pts) Now suppose you know that X1 ⊥ X2|Y (i.e., X1 and X2 are conditionally indepen- dent with each other given Y ). Now, which of the above cases is sufficient for us to calculate P (Y |X1, X2)? Justify your answers.
Bayesian Networks (24 pts)
4. (6 pts) For the below graph, determine whether the following independences can be guaranteed to be true or not. (Justify your answers)
(a) (2 pts) F ⊥ G|D (b) (2 pts) D ⊥ E|B (c) (2 pts) C ⊥ D|A
2
5. (4 pts) For the two graphs below, determine which variables are d-connected to A given S: (a) (2 pts) S = {B}
(b) (2 pts) S = {J}
3
6. (14 pts) Given a Bayesian network and corresponding conditional probability tables as following: P(H)
+h 0.6 P(E|H,S)
P(S) +s 0.9
P(A|S) +s +a 0.8 −s +a 0.1
+h +s +h −s −h +s −h −s
+e 0.9 +e 0.7 +e 0.8 +e 0.1
-
(a) (3 pts) Write down the joint distribution as it factorizes according to the graph above and calculate it.
-
(b) (3 pts) What is the probability that students attend classesP (+a)?
-
(c) (3 pts) What is the probability that students are studying, given that they attend the class?
-
(d) (3 pts)What is the probability that students study, given that they attend the class, pass the exam, and do the homework?
-
(e) (2 pts) What is the probability that students do homework, given that they study?
Submission
Upload your answers to the written questions as a pdf format file in Gradescope:
-
You should already have received an e-mail with the link to access Gradescope. If you haven’t,
let the TAs know.
-
For your pdf file, use the naming convention username hw#.pdf. For example, your TA with
username alice would name her pdf file for HW3 as alice hw3.pdf.
-
Use the provided LATEX template to typeset the assignment by editing the tex files under student response/ .
4
Part 2: Programming Assignment (50 pts)
For the programming assignments, we will use the Pacman project designed for the course CS188 at UC Berkeley: https://inst.eecs.berkeley.edu/~cs188/fa20/project4/ (Note that for this homework, we will be using the Fall 2020 version).
Please remember that solutions to any assignment should be your own. Using other people’s solutions, within or outside Purdue goes against the course’s academic honesty policy. The TAs will be using code similarity measures to detect plagiarism cases when grading the assignment.
In this assignment, we will use Pacman project 4. In project 4, you will design inference methods for Pacman agents to use to locate and eat invisible ghosts. As in HW1 and HW2, the assignment includes an autograder for you to grade your answers on your machine.
1. Complete Project 4, Questions 0-4 described on the Berkeley site. Submit your modified versions of and for grading. We will multiply your original score
returned by (10 pts in total) by 5.
Submission
Please upload the following files: bustersAgents.py and inference.py to Gradescope.
inference.py
bustersAgents.py
autograder.py
5
