2. [20 Points] Viterbi POS tags Consider a simple HMM POS tagger with only five tags (plus the beginning and end of sentence markers, s> and ). The transition probabilities for this HMM are given by the table on the left below, where cell [i.j] is the probability of transitioning from state i to j (i.e., P(state, Istate)). A subset of the output probabilities are given by the table on the right, where c j is the probability of state i outputting word j (i.e., P(word, state)). CD PRP NN VB VBD 0 .5 20 3 0 CD .2 0.3 .2 .2 PRP .10 3 4 N .05 .15 .2 .25 .305 VB 0 2 6 0 0 2 VBD 0 .6 0 0.3 one cat dog bit 0 RP .02 0 00 NN 05 03 .04 .007 0 0 03 0 VBD 0 0 006 VB Hand-simulate the Viterbi algorithm in order to compute highest probability tag sequence for the given sentence: "one dog bit" That is, fill in the cells in the following table, where cell [it] should contain the Viterbi value for state j at time t, and you should also use backpointers to keep track of the best path. The rows of the table are already labeled with the different states, and the columns are already labeled with the observations at each time step Hint: For this particular HMM, a lot of the cells will have zeros in them. Try to work out ahead of time which these are, so you only need to do the Viterbi computations for the oth er cells Assume probability of P() 1.0 one do bit CD PRP VB VBD