Artificial Intelligence Homework #4 solution

Problem 1 (HMMs) – 5 Points: Due to all the headache of virus outbreak and studying from home, your eating schedule has gone out of whack. On a given day at home, your state is either very hungry or you’ve eaten so much food that you’ve become very sleepy. You have an observable mood behavior of being either hopeful, calm, or violently angry. Your given HMM model is:









P(S1)







hungry
1







sleepy
0





















P (St|St−1 = hungry)


hungry




1/4






sleepy




3/4






















P (St|St−1 = sleepy)



hungry



3/4






sleepy



1/4





















P (Bt|St = hungry)



hopeful


1/4






calm


1/4






angry


1/2




















P (Bt|St = sleepy)



hopeful

1/4






calm

3/4






angry

0





    (a) (2 points) What is P (S2 = hungry|B2 = calm)?

    (b) (1 points) Your friend obtains the following utility (depending on your state) when talking to you. What is the expected utility of your friend talking to you if your friend hadn’t observed your mood behavior?

S2
U
hungry
-2
sleepy
3

    (c) (2 points) Now what is your friend’s expected utility if your friend sees you are calm?

Solution 1:



2





Problem 2 (Typing Simulation) – 7 Points: For this problem, you will be playing a typing simulation. Let random variable E represent the observed key press, and X represent the hidden (intended) key press. We have a language with 4 letters (A, B, C, D), and a keyboard arranged as a circle.

    • B C  D


At any time, the probability of hitting the intended key is 50%, and the probability of hitting the neighboring keys is 25%. For example, P (E|X = B):
0.25
0.5

    • 0.25

We will construct a filtering model for constructing the belief state for this problem.

(a) (2 Points) Assume the following prior distribution over letters:

x
P(X=x)
A
0.4
B
0.2
C
0.1
D
0.3

Calculate the conditional probability table (CPT) P (X = x|E = e) for all x and e.

(b) (2 Points) Consider the following letter transition model for P (X0|X):


A’
B’
C’
D’
Begin
1
0
0
0
A
0.5
0.5
0
0
B
0
0.5
0.5
0
C
0.5
0
0
0.5
D
0.25
0.25
0.25
0.25

For this problem we are concerned with true (hidden) state sequences, as opposed to observations. What is the probability under this model of the sequence of letters "A B B C D"? How about "A A B A"? What is P(X3 = B|X1 = A, X2 = B)?

    (c) (3 Points) Finally we consider the full filtering problem in which we compute P (Xn|E1, . . . , En). Let "A B B C D" be the sequence of observed

3





key strokes. What is the current belief state of the model? That is, compute P (Xn = x|E1 = A, E2 = B, E3 = B, E4 = C, E5 = D) for all x and n = 2, 3, 4, 5.

Hint:

X
P (Xn|E1, ..., En) ∝ P (En|Xn)    P (Xn|xn−1)B(xn−1)
xn−1

Solution 2:












































4





Problem 3 (Bayes Nets) – 8 Points:

Consider the Bayes net shown below, BrokeElectionLaw, I = Indicted, M = G = F oundGuilty, and J = Jailed.

with Boolean variables B = P oliticallyM otivatedP rosecutor,
















    (a) (3 points) Which of the following are asserted by the network structure? Briefly explain.

        (i) P(B, I, M) = P(B)P(I)P(M)

        (ii) P(J|G) = P(J|G, I)

        (iii) P(M|G, B, I) = P(M|G, B, I, J)

    (b) (2 points) Calculate the value of P (b, i, ¬m, g, j).

    (c) (2 points) Calculate the probability that someone goes to jail given that they broke the law, have been indicted, and face a politically motivated prosecutor.

    (d) (1 point) Suppose we want to add the variable P = P residentialP ardon to the network; draw the new network and briefly explain any links you add.

Solution 3:













5