HMM Programming Project


Due Tuesday 2/26 11:59 pm
Updated 2/23, PLEASE download the newest hmm.py and copy your code over. You will not pass the sanity checker without this new version.

This project should be completed individually.

What to submit: Follow the submission instructions. You should submit a modified hmm.py as well as a partners.txt file. Submit under project name p3.

For this project, you will need to implement four inference tasks on an HMM: filtering, prediction, smoothing, and computation of the most likely sequence (the viterbi algorithm). These are described in Section 15.2 of the book.

Denote the hidden states of the HMM by X(t) and the observations (evidence) by E(t). In the weather problem from the HMM Tutorial, X(t) would be either sunny, rainy, or foggy, and E(t) is yes or no to indicate if an umbrella was observed. We will use this model with prior probabilities P(sunny) = 0.5, P(rainy) = 0.25, P(foggy) = 0.25. The remaining probilities you need are specified in the tutorial (and also in the included hmm.py code below).

You will need to fill in the missing implementations of the following four functions in the included code:

Filtering:
Given observation sequence E(0), E(1), ..., E(T-1), compute P(X(T-1)|E(0), ..., E(T-1)).

Prediction:
Given observation sequence E(0), E(1), ..., E(T-1), compute P(X(T)|E(0), ..., E(T-1)).

Smoothing:
Given observation sequence E(0), E(1), ..., E(T-1), compute P(X(k)|E(0), ..., E(T-1)) for 0 <= k <= T-1.

Viterbi algorithm:
Given observation sequence E(0), E(1), ..., E(T-1), compute the most likely sequence of states: X(0), X(1), ..., X(T-1)

In addition to the weather model, whose probability tables are already given in the code, you will need to encode the probabilities for the HMM in Problem 15.12 of the Russell and Norvig AI book.

Files:

hmm.py

Test Data:

weather-test1-1000.txt
weather-test2-1000.txt
phone-test1.txt

Correct output on test data:

weather-test1-1000-output.txt
weather-test2-1000-output.txt
phone-test1-output.txt

To run your code on either the weather or phone example, use: python hmm.py [weather|phone] [data].

For example: python hmm.py weather weather-test1-1000.txt (to test weather model on weather-test1-1000.txt)

Your submission will be graded on additional test cases in this format.