Lab 9: Inference and Learning for Discrete-State HMMs

Lab 9: Inference and Learning for Discrete-State HMMs#

This lab is adapted from AM207 (Harvard). Data files are in the book’s data/ folder.

Hide code cell content

 
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import sys
from hmmlearn import hmm
%matplotlib inline

Problem Description: Discrete State Space HMM#

In this problem you should use a Hidden Markov Model to correct typos in a text without using a dictionary. Your data is in two different text files:

  • Shakespeare_correct.txt contains the words of some sonnets from Shakespeare

  • Shakespeare_typos.txt contains the same text, but now some of the characters are corrupted

For convenience both text files only contain lower case letters a-z and spaces.

We will be using the hmmlearn package for python to implement as well as perform learning and inference for HMM models.

In this lab, we will study applications involving sequential data with discrete values. In particular, we will model text as sequences of letters. The application we study will be typo correction - the task of inferring the correct text given a text littered with typos. Alternatively, you can also consider this an instance of decryption - the task of inferring the true message given an encrypted message.

Part I: Setting Up the Model#

To set up the HMM, answer the following:

  • What are the latent states and what are the observed states?

  • How should we parametrize the transition between the latent states, \(p(X_{n+1} | X_n)\)?

    Hint: this will be a matrix, called the transition matrix.

  • How should we parametrize the emission of an observation given a latent state, \(p(Y_{n+1}|X_{n+1})\)?

    Hint: this will be a matrix, called the emission matrix.

Part II: Learning#

How does one learn the dynamics of the system that generates Shakespeare and how does one learn the dynamics of the system that generates typos? There are two options: we can learn the dynamics using domain knowledge (our understanding of how language and typing works) or we can learn the dynamics that maximizes the observed data log-likelihood.

  • Estimate the transition matrix using the letter to next letter frequencies in the true text. Estimate the letter to typo frequencies using either the true text and the typo text, or using your domain knowledge on the layout of the qwerty keyboard.

  • Estimate the transition and emission matrices that maximizes the observed data log-likelihood of the typo text.

Part III: Inference#

Inference algorithms like filtering, smoothing and most probable latent sequence for HMM’s with discrete state spaces are similar to those for HMM’s with continuous state spaces.

  • For transition and emission matrices you learned using EM, infer the most probable latent sequence for typo-littered texts of length 100, 500, 1000, and 2000. Report the error correction rate you observe.

  • For transition and emission matrices that you constructed yourself, infer the most probable latent sequence for typo-littered texts of length 100, 500, 1000, and 2000. Report the error correction rate you observe.

  • Which set of dynamics give you better error correction rates?

Example for constructing the transition and emission matrices from domain knowledge.#

#compute emission and transmission matrices
#where S is a correct string and X is a corrupted string
#and alpha is an alphabet
def make_matrices(S, X, alpha):
    trans = np.zeros((len(alpha), len(alpha)))
    emit = np.zeros((len(alpha), len(alpha)))
    
    bigrams_cor = [S[i:i + 2] for i in range(len(S) - 1)] #bigrams from S
    bigrams_typo = zip(S, X) #bigrams from coupling corresponding letter in S and X
    
    #filters the list of bigrams for ones beginning with the letter'x'
    filter_x = lambda x, grams: [gram for gram in grams if gram[0] == x]
    
    for i in range(len(alpha)):
        count_i = S.count(alpha[i]) #frequency of the i-th letter
        bigrams_i_cor = filter_x(alpha[i], bigrams_cor) #bigrams beginning with i-th letter
        bigrams_i_typo = filter_x(alpha[i], bigrams_typo) #bigrams beginning with i-th letter
        
        for j in range(len(alpha)):
            if len(bigrams_i_cor) > 0:
                #frequency of bigrams in with the j-th letter follows the i-th
                count_j = [gram[1] for gram in bigrams_i_cor].count(alpha[j])
            else:
                count_j = 0
            #prob j-th letter follows i-th in correct text
            trans[i, j] = (count_j + 1.) / (count_i  + 2.) 
            
            if len(bigrams_i_typo) > 0:
                #frequency of bigrams in with the j-th letter follows the i-th
                count_j = [gram[1] for gram in bigrams_i_typo].count(alpha[j])
            else:
                count_j = 0
                
            #prob j-th letter is corrupted to the i-th letter 
            emit[i, j] = (count_j + 1.) / (count_i + 2.) 
            
    return trans, emit

Example code for working with the hmmlearn api#

model = hmm.MultinomialHMM(n_components=3)
model.startprob_ = np.array([0.6, 0.3, 0.1])
model.transmat_ = np.array([[0.7, 0.2, 0.1],
                            [0.7, 0.2, 0.1],
                            [0.7, 0.2, 0.1]])
model.emissionprob_ = np.array([[0.7, 0.2, 0.1],
                                [0.7, 0.2, 0.1],
                                [0.7, 0.2, 0.1]])
X, Z = model.sample(5000)

remodel = hmm.MultinomialHMM(n_components=3, n_iter=1000)
remodel.fit(X)
Z2 = remodel.predict(X)

remodel.transmat_

array([[0.3618139 , 0.22163496, 0.41655114],
       [0.36287858, 0.2182283 , 0.41889312],
       [0.36207611, 0.22224947, 0.41567442]])
Contents