We've been saying that you can make a part-of-speech tagger with HMMs and the Viterbi algorithm!
It turns out to be true.
For this exercise, you get most of the implementation of a POS tagger! It learns from the Brown corpus.
YOUR MISSION: complete the implementation of Viterbi by filling in the chart (called a "trellis" in the code) with the appropriate probabilities and storing the best path as you go.
When you're done, you should not only be able to predict the weather by getting calls from your friend about what they did that day, but you should also be able to pos-tag sentences!
Extensions to this exercise, if it turns out to be easy to do during a class period.
1. Add smoothing. This is completely unsmoothed, so it won't be able to tag sentences with (eg) words that it hasn't seen before. How could you fix that?
2. Add evaluation! How *good* is this tagger, anyway? What's the best way to evaluate it?
3. Compare against some other tagger. How well does it do against, say, the default tagger in NLTK?