Description
B. Problems:
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:
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