ARTIFICIAL INTELLIGENCE (E016330)

GHENT UNIVERSITY
AY 2024/2025
Professor Aleksandra Pizurica
Asst: Niels Vyncke, Nicolas Vercheval
E-mail: ai@[Link]

Solutions: Probabilistic reasoning over time

1. Consider the following simple Hidden Markov Model with state variables Xt and observation
(evidence) variables Ot , which are shaded below.

Suppose that O1 = A and O2 = B is observed.

(a) Use the Forward Algorithm to compute the probability distribution

P(X2 | O1 = A, O2 = B).

Show your work.

(b) Use the Viterbi algorithm to compute the maximum probability sequence X1 , X2 .
Show your work.

Solution:

(a) In theory slides for Temporal Probability Models, we have seen that a filtered estimate
is given by:
X
P(Xt+1 | e1:t+1 ) = α P(et+1 | Xt+1 ) P(Xt+1 | xt )P (xt | e1:t ) .
xt
| {z }
P(Xt+1 |e1:t )

and we denoted this procedure as the forward algorithm:

f1:t+1 = α Forward(f1:t , et+1 ), where f1:t = P(Xt |e1:t )

1
 Now, it easily follows that:
X
P(X2 | O1 = A, O2 = B) = α P(O2 = B | X2 ) P(X2 | x1 )P (x1 | O1 = A)
x1
 
P (O1 = A | x1 = 1)P (x1 = 1) P (O1 = A | x1 = 0)P (x1 = 0)
= αh0.5, 0.1i h0.2, 0.8i + h0.6, 0.4i
P (O1 = A) P (O1 = A)
α
= h0.5, 0.1i [h0.2, 0.8i · 0.5 · 0.7 + h0.6, 0.4i · 0.9 · 0.3]
P (O1 = A)
| {z }
:=α0
= α0 h0.5, 0.1i [h0.07, 0.28i + h0.162, 0.108i]
= α0 h0.116, 0.0388i = h0.75, 0.25i.

(b) We know that the Viterbi algorithm is defined by the recurrence relation:
m1:t+1 = max P(x1 , . . . , xt , Xt+1 | e1:t+1 )
x1 ...xt
 
= α P(et+1 | Xt+1 ) max P(Xt+1 | xt ) max P(x1 , . . . , xt−1 , Xt | e1:t )
xt x1 ...xt−1

The first step is filtering:

1 2
m1:1 = hM1:1 , M1:1 i = P(X1 |O1 = A) = α P(A|X1 )P(X1 ) = αh0.5, 0.9ih0.7, 0.3i
= αh0.35, 0.27i = h0.565, 0.435i
Then we evaluate the two possible ways to reach state 1 at time instant 2:
1 1 2
M1:2 = αP (O2 = B|X2 = 1) max{P (X2 = 1|X1 = 1)M1:1 , P (X2 = 1|X1 = 0)M1:1 }
| ×{z0.565}, 0.6
= 0.5 max{0.2 | ×{z0.435}}α = 0.1305α
0.113 0.261

The second term was larger, i.e., the transition from the state X1 = 0 was chosen
and this is indicated in the trellis diagram (left subfigure). Similarly,
2 1 2
M1:2 = αP (O2 = B|X2 = 0) max{P (X2 = 0|X1 = 1)M1:1 , P (X2 = 0|X1 = 0)M1:1 }
| ×{z0.565}, 0.4
= 0.1 max{0.8 | ×{z0.435}}α = 0.0452α
0.452 0.174

The transition from X1 = 1 was chosen (we denote this in the trellis diagram, mid-
dle subfigure) It is not necessary to calculate the normalized values with actual α
(although that will help when the sequence is longer in order not to have too small
numbers). Obviously, the state 1 is most probable at the end, so tracing back we
obtain the most likely sequence: X1 = 0, X2 = 1.

2
2. (Old exam question) Suppose you returned from holidays and due to the current Covid-19
regulations have to stay in quarantine for two weeks. You are staying in a good ventilated,
but windowless basement room in your home. To make time go by faster, you want to develop
a simple weather forecast system that only gives prognosis for average daily weather (W )
characterized as being either sunny (s), rainy (r) or foggy (f ), i.e., w ∈ {s, rf }.
You will make the system more sophisticated by making use of some indirect evidence that you
get by observing the caretaker that visits you each morning. In particular you pay attention
to whether the caretaker caries an umbrella or not. You assume that the probability that the
caretaker carries an umbrella is 0.1 if the weather is sunny, 0.8 if the weather is rainy and 0.3
if it is foggy.
Based on some statistical data that you could find for Ghent region in Belgium, you set
probabilities of tomorrow’s weather based on today’s weather as in the table below.

Tomorrow’s weather
Sunny Rainy F oggy
Sunny 0.8 0.05 0.15
Today’s weather
Rainy 0.2 0.6 0.2
F oggy 0.2 0.3 0.5

(a) Draw the corresponding state transition diagram that represents the transition model
with the state transition probabilities.
(b) Specify the sensor model with an appropriate table.
(c) Suppose first you discard the information that you can obtain by observing the caretaker.
What is the probability that it will be rainy two days from now given that today is foggy?
(d) You have no idea anymore about what the weather was before you landed in the basement
and it is your second day there. What is the probability that on this day 2 of your
quarantine the weather outside is sunny provided that the caretaker didn’t carry the
umbrella on day 1 and caries it on day 2?
(e) On the first 3 days your umbrella observations are: {no umbrella, umbrella, umbrella}.
Find the most probable weather-sequence using the Viterbi algorithm.

3
Solution:

(a) We obtain the following diagram:

(b) The only piece of evidence you have is whether the person who comes into the room
is carrying an umbrella or not.

Weather Probability of umbrella

Sunny 0.1
Rainy 0.8
F oggy 0.3

(c) There are three ways to get from foggy today to rainy two days from now:

{f oggy, f oggy, rainy}, {f oggy, rainy, rainy} and {f oggy, sunny, rainy}.

Therefore we have to sum over these paths. Let us use the shorter notation {r, s, f }
and denote by Wn the weather on day n. We obtain:

P (W3 = r | W1 = f ) = P (W3 = r | W1 = f, W2 = f )P (W2 = f | W1 = f )

+ P (W3 = r | W1 = f, W2 = s)P (W2 = s | W1 = f )
+ P (W3 = r | W1 = f, W2 = r)P (W2 = r | W1 = f )
= P (W3 = r | W2 = f )P (W2 = f | W1 = f )
+ P (W3 = r | W2 = s)P (W2 = s | W1 = f )
+ P (W3 = r | W2 = r)P (W2 = r | W1 = f )
= 0.3 · 0.5 + 0.05 · 0.2 + 0.6 · 0.3 = 0.34.

(d) Here we have a filtering task:

X
P(Xt+1 | e1:t+1 ) = α P(et+1 | Xt+1 ) P(Xt+1 | xt )P (xt | e1:t ).
xt

4
 By assuming that the weather on day one is equiprobable, we obtain the following:
X
P(W2 | U1 = f, U2 = t) = α P(U2 = t | W2 ) P(W2 | w1 )P (w1 | U1 = f )
w1
= α h0.1, 0.8, 0.3i[h0.8, 0.05, 0.15i P (W1 = s | U1 = f )
+ h0.2, 0.6, 0.2i P (W1 = r | U1 = f )
+ h0.2, 0.3, 0.5i P (W1 = f | U1 = f )]
α 1
= [h0.8, 0.05, 0.15i P (U1 = f | W1 = s)
P (U1 = f ) 3
| {z }
:=α0
+h0.2, 0.6, 0.2i P (U1 = f | W1 = r) + h0.2, 0.3, 0.5i P (U1 = f | W1 = f )]
= α0 h0.1, 0.8, 0.3i[h0.8, 0.05, 0.15i0.9 + h0.2, 0.6, 0.2i0.2 + h0.2, 0.3, 0.5i0.7]
= α0 h0.1, 0.8, 0.3i[h0.72, 0.045, 0.135i + h0.04, 0.12, 0.04i + h0.14, 0.21, 0.35i]
= α0 h0.1, 0.8, 0.3i h0.9, 0.375, 0.525i = α0 h0.09, 0.3, 0.1575i ≈ h0.164, 0.548, 0.287i

So, we obtain that

P (W2 = s | U1 = f, U2 = t) = 0.164.

(e) The Viterbi algorithm is defined by the recurrence relation:

m1:t+1 = max P(x1 , . . . , xt , Xt+1 | e1:t+1 )

x1 ...xt
 
= α P(et+1 | Xt+1 ) max P(Xt+1 | xt ) max P(x1 , . . . , xt−1 , Xt | e1:t )
xt x1 ...xt−1

To visualize the algorithm, consider the following state trellis, a graph of states and
transitions over time:

The most likely sequence is: W3 = r, W2 = r and W1 = f .

5
3. (Old exam question) Sam has bought an AI agent to be his companion helping him to keep
good mood during the exam period. The AI agent can analyse facial expressions and adjust
accordingly lighting in the room, music and tell some jokes to stimulate this way different
activities like studying or relaxing. During the first day, the agent is just observing Sam’s
facial expressions and based on average observations in given time intervals infers the type of
Sam’s activity in those corresponding intervals.
Suppose that the time interval is set to one hour and that Sam’s activity during each time
interval is either Studying (S) or playing V ideo games (V ). His facial expression that the
agent observes is either Grinning (G) or F rowning (F ).

(a) Based on the available information from the given state space diagram, write the tables for
the transition and sensor models and any other if available from the problem description.
Use Di to denote the random variable (RV) representing what Sam is doing in hour i and
denote by Oi the observation RV in that time slot.

(b) If in the second hour Sam is Studying, what’s the probability that in the fourth hour he
is playing V ideo games? Assume the model from (a).
(c) Under the model in (a), what is the probability that Sam is studying in the second hour
if the observation sequence for the first two hours is {Grinning, F rowning}?
(d) Using the same model, the agent recalculates the probabilities of Sam’s activity during
hour 2, after observing that his facial expression during hour 3 is Grinning. Show
this calculation and the updated probabilities of the activities in the specified time slot.
Comment on this result.
(e) Suppose now that Sam’s activities also include ChattingW ithF riend (C) and the set of
his observable facial expressions is extended with two others: Excited (E) and Bored (B).
The transition model and the sensor model are given by the two matrices below:

6
 For example, the probability that Sam is chatting with a friend in the hour i + 1 if he was
studying during the hour i is P (C|S) = T3,1 = 0.8 and the probability that he is playing
video games if he was studying the hour before is P (V |S) = T2,1 = 0.1. He is grinning
with probability 0.05 while studying and with probability 0.4 while chatting.
The agent observes the following sequence of facial expressions: {Grinning, Excited, F rowning}.
Which sequence of activities does it infer by applying the Viterbi algorithm? Write the
resulting sequence and mark it on the trellis diagram!

Solution:

(a) We obtain the following:

(b) Denote the state in hour i by Di which can be S = Studying and V = V ideo games.
We obtain the following:
P (D4 = V | D2 = S) = P (D4 = V | D3 = V, D2 = S)P (D3 = V | D2 = S)
+ P (D4 = V | D3 = S, D2 = S)P (D3 = S | D2 = S)
= P (D4 = V | D3 = V )P (D3 = V | D2 = S) + P (D4 = V | D3 = S)P (D3 = S | D2 = S)
= 0.6 · 0.2 + 0.2 · 0.8 = 0.28

(c) We are asked to calculate P (D2 = S | O1 = G, O2 = F ), which is a filtering task.

We have the following:
X
P(D2 | O1 = G, O2 = F ) = α P(O2 = F | D2 ) P(D2 | d1 )P (d1 | O1 = G)
d1

=α h0.8, 0.3i [P(D2 | D1 = S)P (D1 = S | O1 = G) + P(D2 | D1 = V )P (D1 = V | O1 = G)]

=α h0.8, 0.3i (h0.8, 0.2i0.267 + h0.4, 0.6i0.733) = αh0.8, 0.3ih0.5, 0.5i ≈ h0.72, 0.28i
Thus we conclude: P (D2 = S | O1 = G, O2 = F ) = 0.72
Note that we also calculated
P(D1 | O1 = G) = α P(O1 = G | D1 )P(D1 ) = αh0.2, 0.7i · h0.56, 0.44i
= αh0.112, 0.308i ≈ h0.267, 0.733i

7
 and
X
P(D1 ) = P(D1 | d0 )P (d0 ) = h0.8, 0.2i0.4 + h0.4, 0.6i0.6 = h0.56, 0.44i
d0

(d) Here we have to calculate P(D2 | O1 = G, O2 = F, O3 = G), which is a smoothing

task. We have the following:

P(D2 | o1:3 ) = αP(D2 | o1:2 )P(o3 | D2 ) = α h0.72, 0.28i · h0.3, 0.5i

= α h0.216, 0.14i ≈ h0.6, 0.4i

We also had to calculate

X
P(O3 = G | D2 ) = P (O3 = G | d3 )P(d3 | D2 )
d3

= 0.2 · h0.8, 0.4i + 0.7 · h0.2, 0.6i = h0.3, 0.5i

Note also that

P(D2 | O1 = G, O2 = F ) = h0.72, 0.28i

P(D2 | O1 = G, O2 = F, O3 = G) = h0.6, 0.4i

We have that the smoothed probability of studying is 0.6 which is smaller than the
filtered probability of studying which is 0.72. This is because of the persistence in
video game playing (and much larger probability of grinning during video games than
during studying).

(e) We know that the Viterbi algorithm is defined by the recurrence relation:

m1:t+1 = max P(x1 , . . . , xt , Xt+1 | e1:t+1 )

x1 ...xt
 
= α P(et+1 | Xt+1 ) max P(Xt+1 | xt ) max P(x1 , . . . , xt−1 , Xt | e1:t )
xt x1 ...xt−1

The first step is filtering:

1 2 3
m1:1 = hM1:1 , M1:1 , M1:1 i = P(X1 |O1 = G) = α P(G|X1 )P(X1 )
 
1 1 1 α
= αh0.05, 0.15, 0.4i , , = h0.05, 0.15, 0.4i = h0.08, 0.25, 0.67i
3 3 3 3
|{z}
α0

Then we evaluate the possible ways to reach state Studying at time instant 2:
1 1 2 3
M1:2 = αP (O2 = E|X2 = S) max{P (S|S)M1:1 , P (S|V )M1:1 , P (S|C)M1:1 }
| ×
= 0.65 max{0.1 {z0.08}, |0.2 ×
{z0.25}, |0.2 ×
{z0.67}}α = 0.0871α
0.008 0.05 0.1345

8
The third term is the largest, i.e., the transition from the state X1 = C was chosen
and this is indicated in the trellis diagram. Similarly, to reach state V ideoGaming
at time instant 2:

2 1 2 3
M1:2 = αP (O2 = E|X2 = V ) max{P (V |S)M1:1 , P (V |V )M1:1 , P (V |C)M1:1 }
| ×
= 0.1 max{0.1 {z0.08}, |0.7 × | ×
{z0.25}, 0.7 {z0.67}}α = 0.0469α
0.008 0.175 0.469

The transition from X1 = C was chosen (we denote this in the trellis diagram).
Finally, we obtain for state Chatting at time instant 2:

3 1 2 3
M1:2 = αP (O2 = E|X2 = C) max{P (C|S)M1:1 , P (C|V )M1:1 , P (C|C)M1:1 }
| ×
= 0.3 max{0.8 | ×
{z0.08}, 0.1 | ×
{z0.25}, 0.1 {z0.67}}α = 0.02α
0.064 0.025 0.067

Now we will calculate the normalized values with actual α as this will help when the
sequence is longer in order not to have too small numbers. Thus, for α = 6.493 we
have that
m1:2 = h0.565, 0.3, 0.135i.

Similarly, as we did before, we do now at time instant 3. We obtain the following:

1 1 2 3
M1:3 = αP (O3 = F |X2 = S) max{P (S|S)M1:2 , P (S|V )M1:2 , P (S|C)M1:2 }
= 0.05 max{0.1 × 0.3}, 0.2
| ×{z0.565}, |0.2 {z | ×{z0.135}}α = 0.003α
0.0565 0.06 0.027
2 1 2 3
M1:3 = αP (O3 = F |X2 = V ) max{P (V |S)M1:2 , P (V |V )M1:2 , P (V |C)M1:2 }
| ×{z0.565}, 0.7
= 0.7 max{0.1 | {z× 0.3}, |0.7 ×{z0.135}}α = 0.147α
0.0565 0.21 0.0945
3 1 2 3
M1:3 = αP (O3 = F |X2 = C) max{P (C|S)M1:2 , P (C|V )M1:2 , P (C|C)M1:2 }
| ×{z0.565}, |0.1 {z
= 0.25 max{0.8 × 0.3}, 0.1
| ×{z0.135}}α = 0.113α
0.452 0.03 0.0135

By normalizing the obtained values, where α = 3.8, we have that

m1:3 = h0.01, 0.558, 0.43i.

Obviously, the state V ideoGaming is most probable at the end, so tracing back
we obtain the most likely sequence: X1 = Chatting, X2 = V ideoGaming, X3 =
V ideoGaming.

9
10