Due Wednesday, April 4th.
This should be written up independently, although you are encouraged to discuss the assignment with others. However, verbatim copying of code is not acceptable - i.e. you should be exchanging ideas and not files.
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).
- Download this implementation in python (modified 3/28/7). 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 a significant amount of 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.