Consider the Dishonest Casino example that we have discussed in our lecture and assignment. Assume the model parameters are given in Figure 6.1 below (which is same as what you used in assignment 3). 0.4 0.6 0.6 Transition probability FAIR LOADED Emission probabilities 0.4 P(1F) = 1/6 P(2|F) = 1/6 P(31F) = 1/6 P(41F) = 1/6 P(5F) = 1/6 P(61F) = 1/6 Emission probabilities P(1L) = 1/10 P(21L) = 1/10 P(31L) = 1/10 P(4L) = 1/10 P(51L) = 1/10 P(6L) = 1/2 Start/initial probabilities P(Z = F) = 1/2 P(z = L) = 1/2 Figure 6.1 An HMM Model 1) Viterbi Algorithm Given the following observation sequence: X = 2; 6; 6 Use the Viterbi algorithm described bellow (which is same as what you used in assignment 3). The Viterbi Algorithm Input: x = X4......Xn, and the model @ = (T, A, E) Initialization (for k = 1 to K): VA(1) = (ex,x) Tex (note that {rx} are the initial probabilities) Ptr (1) = 0; Iteration (for t = 1 to n-1, and for k' = 1 to K): V (t+1) = (ekx) maxk (ak.KV (t)), where k = 1 to K. Ptrt+1) = argmaxk (akko V(t)) (Ptr is used remember the paths) Termination and trackback: P(x, z*) = max Vin) Traceback to find the optimal hidden-state sequence z* using the Ptr matrix Figure 6.2 The Viterbi Algorithm a) Manually follow the above Viterbi algorithm to fill out the V matrix and Ptr matrix. (Note that for the V matrix, the number you filled out can be multiplication of several fractions such as xor or can be i. You can choose whichever form convenient to you). 12 1 1 The V Matrix t = 1 t=2 t = 3 k = 1 (Fair) k = 2 (Loaded) ! 1 1 observation "2" "6" "6" The Ptr Matrix t=1 t=2 t=3 0 k = 1 (Fair) 0 k = 2 (Loaded) 1 observation "2" "6" "6" Consider the Dishonest Casino example that we have discussed in our lecture and assignment. Assume the model parameters are given in Figure 6.1 below (which is same as what you used in assignment 3). 0.4 0.6 0.6 Transition probability FAIR LOADED Emission probabilities 0.4 P(1F) = 1/6 P(2|F) = 1/6 P(31F) = 1/6 P(41F) = 1/6 P(5F) = 1/6 P(61F) = 1/6 Emission probabilities P(1L) = 1/10 P(21L) = 1/10 P(31L) = 1/10 P(4L) = 1/10 P(51L) = 1/10 P(6L) = 1/2 Start/initial probabilities P(Z = F) = 1/2 P(z = L) = 1/2 Figure 6.1 An HMM Model 1) Viterbi Algorithm Given the following observation sequence: X = 2; 6; 6 Use the Viterbi algorithm described bellow (which is same as what you used in assignment 3). The Viterbi Algorithm Input: x = X4......Xn, and the model @ = (T, A, E) Initialization (for k = 1 to K): VA(1) = (ex,x) Tex (note that {rx} are the initial probabilities) Ptr (1) = 0; Iteration (for t = 1 to n-1, and for k' = 1 to K): V (t+1) = (ekx) maxk (ak.KV (t)), where k = 1 to K. Ptrt+1) = argmaxk (akko V(t)) (Ptr is used remember the paths) Termination and trackback: P(x, z*) = max Vin) Traceback to find the optimal hidden-state sequence z* using the Ptr matrix Figure 6.2 The Viterbi Algorithm a) Manually follow the above Viterbi algorithm to fill out the V matrix and Ptr matrix. (Note that for the V matrix, the number you filled out can be multiplication of several fractions such as xor or can be i. You can choose whichever form convenient to you). 12 1 1 The V Matrix t = 1 t=2 t = 3 k = 1 (Fair) k = 2 (Loaded) ! 1 1 observation "2" "6" "6" The Ptr Matrix t=1 t=2 t=3 0 k = 1 (Fair) 0 k = 2 (Loaded) 1 observation "2" "6" "6
