Question 2(5 marks) This question deals with a small toy model and is more easily done by hand rather than by using algorithms. (i.e. I want you to do it by inspection rather than by using the algorithms. The idea is to see if you understand the terminology of HMMs.) Define a hidden Markov model with the following parameters: three states E1, Ez and Es together with beginning state B and end state &; a matrix of transition probabilities 0 1/2 0 1/2 0 ) 1/5 1/5 2/5 1/5 II = 0 1/6 1/3 1/3 1/6 (1) 0 3/10 1/5 1/5 3/10 0 0 0 0 where the first and last columns refer to the beginning and end states respectively; an alphabet of emitted letters A = {A, B, C} and emission probabilities 91 (A) = 1/2, q1 (B) = 1/2, 41 (C) = 0, 92(A) = 0, q2(B) = 1/2, q2(C) = 1/2, (2) 43(A) = 1/2, q3(B) = 0, 43(C) = 1/2. (i) Write out all possible state sequences for the observed letter sequence r = A, B, A. (3) (ii) Which of these is the most likely state sequence? (iii) What is the total probability P(x) of the observed sequence r? (iv) For each state E;, i = 1, 2,3, what is the probability that E, was the state visited at the second time step, given the above observed letter sequence? (v) If one were to use the algorithms derived in lectures, which algorithm would be appropriate for answering each of parts (ii), (iii) and (iv)