For this homework, do the following things:

1. The “occasionally dishonest casino” is a well-known application for HMMs.¹ In this problem, a casino uses two kinds of dice: fair and loaded. The latter are loaded so that 6 comes up half the time. The staff is instructed to switch between honest and loaded dice according to the probabilities shown in this state transition diagram.

   

   Do the following:

   1. Build an HMM-based model for this problem using Hamilton’s HMM module.
   2. Compute the following, assuming P(F₀) = <0.5, 0.5>:
      1. P(1₀)
      2. P(f₁)
      3. P(F₁ | 1₁)
      4. P(F₁ | 6₁)

      Here, 1_t means a roll of 1 at time t and f_t means using a fair die at time t. Do these computations manually and, if possible, using code from the lab (only!). Do your answers match those of Hamilton’s code?

   3. Estimate the most likely explanation for the following sequences of dice rolls:
      1. 6, 6, 6, 6, 6, 6
      2. 1, 2, 3, 4, 5, 6
      3. 100 random rolls and then a sequence 10 6s.
      4. The following well-known sequence attributed to Durbin (see Biological Sequence Analysis):

         3, 1, 5, 1, 1, 6, 2, 4, 6, 4, 4, 6, 6, 4, 4, 2, 4, 5, 3, 2, 1, 1, 3, 1, 6, 3, 1, 1, 6, 4, 1, 5, 2, 1, 3, 3, 6, 2, 5, 1, 4, 4, 5, 4, 3, 6, 3, 1, 6, 5, 6, 6, 2, 6, 5, 6, 6, 6, 6, 6

      Give a short explanation of your results.

Final project suggestions: (1) Build some natural language processing tools that use the Viterbi algorithm. For example, the AIMA code implements word separation (see text.py). (2) Build your own implementation of the HMM algorithms in Python (to replace Hamilton’s).

¹ This version is a symmetric version that will work with Hamilton’s HMM implementation.

Checking in

Submit the files specified above in Moodle under homework 7. We will grade your work according to the following criteria:

• Exercise 7.1 - Complete the program as specified above.
  • 40% - Exercise 1.a - Implement the specified application in a correct, efficient and understandable manner.
  • 30% - Exercise 1.b - Compute the given values manually and computationally as appropriate.
  • 30% - Exercise 1.c - Run the given test cases correctly.

The preliminary project proposal is submitted and graded separately; upload it here: submission site