Artificial Intelligence Homework #4 solution

Description

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

1. (2 points) What is P (S₂ = hungry|B₂ = calm)?

2. (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

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

Solution 1:

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 (X⁰|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(X₃ = B|X₁ = A, X₂ = B)?

3. (3 Points) Finally we consider the full filtering problem in which we compute P (X_n|E₁, . . . , E_n). Let “A B B C D” be the sequence of observed

key strokes. What is the current belief state of the model? That is, compute P (X_n = x|E₁ = A, E₂ = B, E₃ = B, E₄ = C, E₅ = D) for all x and n = 2, 3, 4, 5.

Hint:

X

P (X_n|E₁, …, E_n) ∝ P (E_n|X_n) P (X_n|x_n−1)B(x_n−1)

^xn−1

Solution 2:

Problem 3 (Bayes Nets) – 8 Points:

5