## 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