Let $x$ be the sequence of symbols and let $\pi$ be the sequence of states sampled from a hidden Markov model.
Question 1: The Viterbi, forward, and backward algorithms can all be applied to hidden Markov models to produce tables. What does the final computed column of each table represent?
Viterbi algorithm:
Forward algorithm:
Backward algorithm:
2) Forward Algorithm
$A = $
H
A
O
H
-0.5
-1.6
-1.6
A
-2.3
-1.2
-0.5
O
-1.2
-1.6
-0.7
$E =$
S
T
H
-0.4
-1.2
A
-1.6
-0.2
O
-0.7
-0.7
The weather this week was $x = (T, T, T, S)$. We want to find $P(x) = \sum\limits_\pi P(x,\pi)$.
Question 2: Using the forward algorithm, complete the table below to find $P(x)$. Assume that we start in each state with probability $a_0 = 1/3$ ($A_0 = $ ln 1/3 = -1.1). Round to 1dp.
The top cell from column 1 was calculated as $F_H(1) = E_H(T) + A_{0,H} = -1.2 - 1.1 = -2.3$
The top cell from column 2 was calculated as $F_H(2) = E_H(T) + log\{ exp(-2.3 - 0.5) + exp(-1.3 - 2.3) + exp(-1.8 - 1.2) \} = -1.2 - 2.0 = -3.2$
The middle cell from column 2 was calculated as $F_A(2) = E_A(T) + log\{ exp(-2.3 - 1.6) + exp(-1.3 - 1.2) + exp(-1.8 - 1.6) \} = -0.2 - 2.0 = -2.2$
Start
T
T
T
S
0
0
H
$-\infty$
-2.3
-3.2
A
$-\infty$
-1.3
-2.2
O
$-\infty$
-1.8
-2.0
What is $P(x)$?
3) Backward Algorithm
$A = $
H
A
O
H
-0.5
-1.6
-1.6
A
-2.3
-1.2
-0.5
O
-1.2
-1.6
-0.7
$E =$
S
T
H
-0.4
-1.2
A
-1.6
-0.2
O
-0.7
-0.7
Question 3: Using the backward algorithm, complete the table below to find $P(x)$. Assume that we have not modelled end states ($a_{k0} = 1$, $A_{k0} = $ ln 1 = 0). Round to 1dp.
The top cell from column 3 was calculated as $B_H(3) = log \{ exp(A_{HH} + E_H(S) + B_H(4)) + exp(A_{HA} + E_A(S) + B_A(4)) + exp(A_{HO} + E_O(S) + B_O(4)) \}$
$D$ is the data observed and $\theta$ is our model/hypothesis.
Question 4a: If we observe symbol sequence $x = (T,T,T,S)$ and we believe that $\pi = (A,O,O,H)$, then what is $D$ and what is $\theta$? Substitute these terms into the Bayesian equation above.
D:
$\theta$:
$P(\theta | D) = $
$$ P(\pi_i = k | x) = \frac{f_i(k) b_i(k)}{P(x)} $$
We can use the forward and backwards algorithms to calculate the probability of observing state k on the $i_\text{th}$ turn, $P(\pi_i = k | x)$, using the above equation.
Question 4b: Referring to the tables we made in Questions 2 and 3, what is the most probable state on the 1st day, given that the weather was $x = (T,T,T,S)$?
