1. HMM Decoding: Viterbi Algorithm (75 points):
For the HMM shown below, please perform the following:
a. (25 points) Manually build the Viterbi trellis to compute the most likely weather
sequences for each of the two observation sequences, 331122313 and 331123312.
b. (50 points) Programmatically implement the Viterbi algorithm to compute the
most likely weather sequence and probability for any given observation sequence.
Example observation sequences: 331, 122313, 331123312, etc.
2. Maximum Entropy Modeling (25 points):
Consider the following Maximum Entropy features and weights:
f1 f2 f3 f4 f5 f6
Tags VB 0 0.75 0 0.10 0.15 0
NN 0.3 0 0.9 0 0 -0.2
Compute the best tag for the word “race” in the following sentences:
a. Secretariat/NNP is/VBZ expected/VBN to/TO race/?? tomorrow/NN
b. the/DT race/?? for/IN outer/JJ space/NN