DSCI 552: Programming Assignment 7 [Hidden Markov Models] solution

Description

Part 1: Implementation [7 points]

Consider a variable x with domain {1, 2, 3 … 10}. Let vt be the value of x at timestep t. vt+1 is equal to vt
– 1 or vt + 1 with probability 0.5 each, except when vt = 1 or vt = 10, in which case vt+1 = 2 or vt+1 = 9,
respectively.

At each timestep t, we also get noisy measurements of vt. That is, vt -1, vt or vt + 1 can be
returned with equal probabilities. Your task is to use a Hidden Markov Model to figure out the most likely
sequence of values v1 v2 … v10 when the observation sequence is 8, 6, 4, 6, 5, 4, 5, 5, 7, 9. At timestep t =
1, v1 can be any value in {1, 2, 3 … 10} with equal prior probabilities.

You can write your program in any programming language. However, you will have to implement the
algorithms yourself instead of using library functions. In your report, please provide a description of the
data structures you use, any code-level optimizations you perform, any challenges you face, and of
course, the requested outputs.

Submission Guidelines

In your report, please include the names of all group members and mention their individual contributions.

The maximum number of the members in a team is 2. The report should be in PDF format. Your
submission should include the code as well as the report. It is due before 04/27, 11:59pm in an archive
in zip, tar.gz or tar.xz format.

Only one submission is required for each group by one of the group
members.

Please submit your homework on D2L (do NOT email the homework to the instructor or the
TA).