Assignment 6


This assignment is due at the start of class on Wednesday.

Question 1. Consider this HMM (which comes from the example given in the current Wikipedia page on HMMs):

Wikipedia HMM example

Here is the same HMM represented in Python rather than as an image, taken from the same Wikipedia page:

states = ('Rainy', 'Sunny')
 
observations = ('walk', 'shop', 'clean')
 
start_probability = {'Rainy': 0.6, 'Sunny': 0.4}
 
transition_probability = {
   'Rainy' : {'Rainy': 0.7, 'Sunny': 0.3},
   'Sunny' : {'Rainy': 0.4, 'Sunny': 0.6},
   }
 
emission_probability = {
   'Rainy' : {'walk': 0.1, 'shop': 0.4, 'clean': 0.5},
   'Sunny' : {'walk': 0.6, 'shop': 0.3, 'clean': 0.1},
   }

Question 1(a) Create a PCFG that is equivalent to this HMM. That is, the PCFG should generate exactly the same sequences of symbols, with exactly the same probabilities. Briefly explain, in plain English, the strategy you took for converting an HMM to a PCFG. (You do not need to give this algorithmically; just provide an explanation that is simple and easy to read.)

Clarification. The HMM, as given, generates forever; that is, if you walk through the generative process as it's usually described, you never reach a point where you stop generating new symbols. (There's no probabilistic event in the model I've given you corresponding to "stop here in state i and don't take a transition to any state j".) Here's a simple way to address the issue: let's modify the HMM as follows to add a final state where, by definition, we stop generating. Specifically:
  Change A[Rainy,Rainy] to .6 (i.e. subtract .1 from the self-transition probability)
  Change A[Sunny,Sunny] to .5 (same)
  Add a special final state F
  Set A[Rainy,F] = A[Sunny,F] = .1
  Set B[F,"end"] = 1
  Make the input in question 1(b) the sequence shop, clean, end.

Question 1(b) Show that the probabilities P(shop clean | this HMM) and P(shop clean | your PCFG) are identical, by giving the calculation for both. (Use the Forward algorithm for the HMM, and the Inside algorithm, i.e. probabilistic CKY, for the PCFG.)

Question 2. Someone on Piazza created a question/answer thread about how one would train an HMM in an unsupervised, semi-supervised, and fully-supervised setting. My response discussed the fully unsupervised case (use EM) and the fully supervised case (everything's observable, so count and normalize, smoothing to make sure there are no zeroes, because zeroes are bad). I suggested, as a thought exercise, that you think about how you would adapt the training process using the forward-backward (a.k.a. Baum-Welch) algorithm to take advantage of a partially tagged corpus (or a tagged corpus plus an untagged corpus).

Well, this is too good a thought exercise to pass up, so I'm making it a real exercise, i.e. part of your homework. Suppose you had a corpus C1, containing words with their "true" part of speech tags, and a corpus C2, containing just words, with no tags. Obviously you could just ignore the tags in C1 and use EM, i.e. forward-backward, to train an HMM for part of speech tagging using the word sequences in both corpora, but you'd be ignoring potentially valuable information. (Recall from last week's assignment how purely unsupervised HMM training does not always give you nicely interpretable states as POS tags.) So, how would you take advantage of the fact that C1 gives you part of speech tags? Give a carefully thought out, clear explanation, using equations if or where they are appropriate.