T-61.5020 Statistical Natural Language Processing
Exercises 5 -- Markov chains and Hidden Markov Models
Version 1.0

1.

You have studied the changes of the weather. Every day 12am you have looked at the sky and wrote down whether it is sunny ($S_1$), cloudy ($S_2$) or rainy ($S_3$). From these observations you have calculated the following transition probabilities:

$$A=\left[ \begin{array}{ccc} 0.8 & 0.15 & 0.05 \\ 0.4 & 0.5 & 0.1 \\ 0.3 & 0.3 & 0.4 \\ \end{array} \right]$$

Element $a_{ij}$ stands for transition from state $S_i$ to state $S_j$. E.g. the probability that it is sunny day after a cloudy one is $0.4$.

a)

Draw Markov chain for the weather.

b)

Today it is cloudy. What is the probability of the following sequence of five days: Tomorrow it rains, day after tomorrow is cloudy, and after it we have three sunny days.

c)

On average, how many successive sunny days there are?

2.

You are on holidays in Hawaii when you begin to wonder what kind of weather it would be in home. The local newspapers tell only the temperature of the region. However, you can estimate the probability $P(x< -5^\circ C ~\vert~ q=S_1) = b_1(x \le -5^\circ C)$, i.e. that it is over 5 degrees of frost in a sunny day. And more:

$$\begin{array}{lcc} b_1(x \le -5^\circ C ) &=&0.8\\ b_1(-5^\... ...^\circ C ) &=&0.4\\ b_3(x \ge 5^\circ C )&=&0.3\\ \end{array}$$

When you left home, it was a sunny day there.

a)

After three days the holiday ends and it is time to fly back. You want to estimate what kind of weather it is when you come back, in order to dress appropriately. The temperatures in the home town were $7^\circ C$, $3^\circ C$ and $-8^\circ C$. Calculate the probabilities of the three weather types on the day of returning. It is recommended to use the forward algorithm, brute force will be very time consuming.

b)

In the airplane you speculate what kind of weather it has been in home during the holidays. Find the most probable state sequence. Viterbi algorithm uses the least number of calculations.