CSE 473 - Artificial Intelligence - Spring 2013
Written Assignment 1: CSPs and Bayes Nets
Due Date: Due Fri May 24, 1:30pm in class or through the online dropbox.
|
|
|
Problem 1: Ordering Pizza [20 points]
You are ordering a pizza for friends, and your friends have a few constraints.
- Bill wants peperoni and/or sausage on the pizza
- Thomas wants sausage or green peppers but not both
- If the pizza does not have Canadian bacon, then Jill wants green peppers
- If the pizza has Canadian bacon, then Jessica wants green peppers
- Bob wants Candian bacon or peperoni but not both
- If the pizza has green peppers, then Susan also wants onions
A. [10 pts] Formulate the problem of ordering a pizza as a constraint satisfaction
problem.
B. [5 pts] Draw the constraint graph for this problem.
C. [5 pts] What about this constraint graph structure makes the problem easy or hard? (For this question, ignore the content of the constraints and just consider the structure of the constraint graph.)
Problem 2: CSPs [10 points]
When solving CSPs, explain why it is a good heuristic to choose the variable that is most constrained but the value that is least constrained.
Problem 3: Bayesian Modeling [20 points]
Consider the following modeling challenge, which might arise when working on a homework problem. You can either study hard or trick the TA into telling you the right answer. Given these choices, you might actually learn the material and you might also get a passing grade on the problem. All of these possibilities will happen with certain probabilities, that you are welcome to imagine however you like.
A. [14pts] Model this problem as a Bayesian network representing a joint distribution over four binary random variables. Since there is more than one possible answer, briefly motivate your choices.
B. [6pts] Write three independence assumptions that your network encodes.
Problem 4: Bayesian Politics [15 points]
Consider the above Bayes net.
The variables are boolean and describe aspects of a court trail. They indicate whether someone broke an election law (B), was indicted (I), whether the prosecutor was politically motivated (M), if the person was found guilty (G), and if they were ultimately put in jail (J).
A. [9pts] Which of the following are true:
- P(B,I,M) = P(B) P(I) P(M)
- P(J|G) = P(J|G,I)
- P(M|G,B,I) = P(M|G,B,I,J)
B. [3pts] What is P(b,i,¬m,g,j)?
C. [3pts] What is P(j,i,g | ¬m)?