CSEP 573 - Artificial Intelligence - Spring 2014

Written Assignment : Markov Chains and Bayes Nets

Due Date: Due June 4, 11:59pm in dropbox.

Problem 1: Markov Chains [20 points]

Consider the following process. You can be employed or unemployed. At each time step, you have a 1% chance of loosing your job and a 15% chance of moving from unemployment to employment (finding a new job!). Unless otherwise specified, assume that you have a 50% chance of being employed at time 1.

A. [5pts] Model this employment process as a Markov chain.

B. [5pts] If you start out employed, what is the probability of being employed at step three? Show all of your work.

C. [5pts] If you are unemployed at time 3, what is the probability that you started out employed at time 1

D. [5pts] What is the stationary distribution of the chain you defined?

Problem 2: 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 3: 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:

B. [3pts] What is P(b,i,¬m,g,j)?

C. [3pts] What is P(j,i,g | ¬m)?

Problem 4: Bayesian Review - Simple Spam [15 points]

According to extremely reliable sources (Wikipedia), 78% of email is spam. According to experiments conducted on my own inbox, 11% of spam email messages contain the word "Pills". In comparison, only 1% of non-spam email messages contain this word.

A. [5pts] What is the probability that a message contains the word "Pills" and is Spam?

B. [5pts] What is the probability that a message is Spam if it is known to contain the word "Pills"?

C. [5pts] What is the probability that a message does not contain the word "Pills" or is Spam?

Problem 5: Variable Elimination [30 points]

Consider the following Bayesian Network, with variables B, E, A, R, and W:


Consider computing the query P(B|W=true)

A. [7pt] Write the set of initial factors that would be created, after incorporating evidence. You do not need to write the full tables of numbers for each factor, just clearly indicate the function signature, e.g. P(X,Y,Z).
B. [10pt] Write, in order, the signatures for the new factors that get created when running the variable elimination algorithm with the variable elimination ordering A, E, R.
C. [7pt] Provide, if possible, a variable ordering that is more comptuationally efficient than the one in part B.
D. [6pt] Provide, if possible, a variable ordering that is less comptuationally efficient than the one in part B.