Due Friday, April 4th.
This lab can be done individually or with one other person.
In this lab you will be learning more about HMMs - hidden Markov models - and the Viterbi algorithm for finding the most probable state path.
- Check out Yusuke Shinyama's Toy Viterbi Decoder to get a feel for the algorithm. It may also be helpful to read other online articles (wikipedia, etc).
- Here an implementation of the Viterbi algorithm in python; it is also uploaded on each server so you can copy it (don't edit the original). Use it to test the Viterbi algorithm's output for a 100-state path of the following HMM: suppose that a crooked casino has a coin-tossing game in which the coin is either fair or loaded. If it is a fair coin, heads and tails are equally likely. If loaded, heads come up 80 percent of the time. The probability that the casino will switch coins between flips is 10 percent. For 100 flips, what percentage of the coin states does the Viterbi algorithm correctly identify? What happens if the loaded coins come up heads 60 percent of the time?
- For extra credit, re-write the implementation so that it computes with the logs of the probabilities, so that floating-point underflows are avoided. You are highly encouraged to do this, and I am happy to help.