CS 357: Natural Language Processing

A Hidden Markov Model, by hand

Dear Future Jeff: Doing this by hand is a bad idea. Next time, have them do a spreadsheet or a Python script. Love, Past Jeff. (Alternatively, a smaller example would be better.)

For this assignment, you will answer a few questions about a specific Hidden Markov Model. Hand in your answers on paper, and show your work.

Using the notation from Chapter 9 of Manning and Schütze, answer the following questions for the HMM μ shown below. Showing your work will include displaying diagrams of the alphas, betas, etc.

Draw a diagram of this HMM, like the one we had on the blackboard.

What is P(@@$#)? Answer this using the forward procedure (using only alphas), the backward procedure (using only betas), and using combinations of alphas and betas.

What is the most likely state sequence for the output "@@$#"?

Do a Baum-Welch parameter re-estimation for μ using the training observation "@@$#"?

Draw a diagram of retrained HMM.

What is P(@@$#) for the retrained HMM? (You don't need to compute this using all combinations of alphas and betas that would work--just one will suffice.) Is this probability larger than it was before retraining?

Here's the HMM in question:

S = {1, 2, 3} -- the set of states

K = {@, #, $} -- the output alphabet

π₁ = 0.7
π₂ = 0.2
π₃ = 0.1

a₁₁ = 0.3
a₁₂ = 0.3
a₁₃ = 0.4
a₂₁ = 0.4
a₂₂ = 0.6
a₂₃ = 0.0
a₃₁ = 0.0
a₃₂ = 0.5
a₃₃ = 0.5

b_11@ = 0.6
b_11# = 0.2
b_11$ = 0.2
b_12@ = 0.2
b_12# = 0.2
b_12$ = 0.6
b_13@ = 0.9
b_13# = 0.1
b_13$ = 0.0
b_21@ = 0.5
b_21# = 0.5
b_21$ = 0.0
b_22@ = 0.1
b_22# = 0.8
b_22$ = 0.1
b_23@ = 0.3
b_23# = 0.3
b_23$ = 0.4
b_31@ = 0.5
b_31# = 0.3
b_31$ = 0.2
b_32@ = 0.0
b_32# = 0.1
b_32$ = 0.9
b_33@ = 0.0
b_33# = 0.0
b_33$ = 1.0

By the way, I recognize that this assignment will be somewhat tedious. However, I believe that by going through these computations a couple times by hand, you will have a much better understanding of the algorithms than you can get by watching me do it. Feel free to work with other people to check your answers, but please do dig through the details yourself.

---

Jeff Ondich, Department of Mathematics and Computer Science, Carleton College, Northfield, MN 55057, (507) 646-4364, jondich@carleton.edu