Project Option 4
CSE 415: Introduction to Artificial Intelligence
The University of Washington, Seattle, Autumn 2019
OPTION 4: Implementation and Application of Hidden Markov Models.

Provide Python 3.7-compatible implementations of either of two HMM algorithms so as to be able to demonstrate how these algorithms work. The first algorithm should be the Forward Algorithm, which takes a sequence of observations and uses that information to repeatedly estimate the a-posteriori probability distribution over the set of possible states.

The second algorithm ("Viterbi") should take a sequence of observations and use it to determine the most likely state sequence.

Applications: Choose an application domain in which to demonstrate your software. For this domain, either find or create reasonable-looking data that you can use for your algorithms. Design a suitable state space for each application, and develop a reasonable transition model and a reasonable emission model.

Here is a list of suggested application domains:

  1. speech recognition
  2. music recognition
  3. location tracking
  4. microbiological sequence recognition

Output formats: The ideal form of output for your program is a kind of annotated trellis diagram. This diagram shows a sequence of stages and the belief function associated with each stage. Such a diagram could be produced either with graphics (e.g., with Tkinter or the Python svgwrite module) on the screen or by printing out the sequence of belief functions in a sort of vertical format using print statements.

Here is an example of a trellis diagram for an application of HMMs to part-of-speech tagging in natural language processing


Example of a trellis diagram. This comes from www.endtoend.ai.

Test examples: Part of the testing, debugging, and demonstration of your code should focus on a simple test HMM that makes it obvious whether your algorithms are working correctly or not. We leave it to you to design such a test case, but the lead TA for this project option may choose to give you a specific test case.