Due on paper at 8:30AM Monday, 5/16/05.
Consider a Hidden Markov Model with three states (1, 2, and 3) and a set of output symbols {Ape, Bat, Cat, Dog}. Using the notation from the cola/ice-tea/lemonade example in Chapter 9 of Manning & Schütze's Foundations of Statistical Natural Language Processing, suppose a[i,j] and b[i,j,k] for our HMM are as follows.
j=1 2 3 i=1 .7; .1, .2, .3, .4 .2; .3, .3, .3, .1 .1; .2, .2, .4, .2 2 .3; .2, .3, .5, 0 .1; .2, .1, .3, .4 .6; .2, .4, .2, .2 3 .5; .5, .2, .2, .1 0; -, -, -, - .5; .4, .1, .3, .2 Start state probabilities: π = (.5,.3,.2)
For example, if you are in state 2, there is a probability a[2,3] = .6 of moving to state 3 on the next time step, and a probability b[2,3,Bat] = .4 of emitting the symbol "Bat" when you do so.
Compute the probability that this machine, when started up and run for four time steps, will emit "Ape Cat Bat Cat".
Compute the most likely state sequence leading to the "Ape Cat Bat Cat" output.
Use the observed sequence "Ape Cat Bat Cat" to train the HMM. Show the resulting HMM.
Using the trained HMM, compute the proability of "Ape Cat Bat Cat" again. Is this probability larger than it was with the original HMM?