Milestone 1: Introduction to HMMs

First half of October 2003

Theory

Read two or three introductory texts on hidden Markov models. Recommendations:

Rabiner, L.R. (1989)
A tutorial on hidden Markov models and selected applications in speech recognition
Proceedings of the IEEE 77 (2), 257-286
Durbin, R., Eddy, S. R., Krogh, A. and Mitchison, G. (1998)
Biological sequence analysis. Probabilistic models of proteins and nucleic acids.
Cambridge University Press

You may also find my lecture notes or my book chapter useful. Alternatively, you can just browse the web for other introductory texts - you will certainly come across a lot of tutorials on this subject.

Practice

Problem 1

There are three states called birth, life, and death. A process always starts in state birth, from where the system makes a certain transition (meaning: with probability 1) into state life. In state life, some symbol is emitted (choose whatever you want). For each discrete time step, the system stays in state life with probability q. With probability 1-q, however, the system makes a transition into state death, where the process terminates. An illustration is given in the following figure:

You can think of this process as a simple HMM with three hidden states, of which only one state emits any symbol.

What does a typical sequence of states look like?
Derive an expression for the probability of observing a sequence of N emitted symbols, P(N).
Show that the probability is normalized: sum_N P(N)=1.
Tip: Apply the convergence theorem for geometric series.
Derive an expression for the expectation value of the sequence length, sum_N N P(N).
How does this expression depend on q? What do you get for q=0.99?
Tip: Derive an expression for sum_[N=1]^N' P(N) and for q sum_[N=1]^N' P(N), take the difference of these two expressions, solve for sum_[N=1]^N' P(N), and take the limit N' -> infinity.
Write a C/C++ program to simulate this system.
Set q=0.99. Generate a large number of sequences (say 1000) with your program and compute the average sequence length and its standard deviation.
Compare the empirically obtained average sequence length with the analytically derived expectation value to test if your program is working properly.

Problem 2

Implement a simple hidden Markov model in C or C++. The model should have K discrete hidden states and M discrete observed characters (the so-caller alphabet). Write the program such that these parameters can be defined by the user. Note that you need to implement the following:

the matrix of transition probabilities between the hidden states;
the matrix of emission probabilities (i.e., the probabilities of emitting a character given the hidden state);
the initial probability distribution on the alphabet.

That's all for now - you do not need to worry about inference and learning at this stage.

Now, assume you have two coins. State 1 corresponds to a fair coin with equal probabilities of heads and tails. State 2 corresponds to a biased coin, where the probability of the coin showing heads is four times as large as the probability of the coin showing tails. Assume that after tossing the coin, the two coins will be swapped with a probability of 0.1. Also, assume that each sequence of events will always be started with the fair coin.

Describe how this problem can be modelled with an HMM.
Use the C/C++ program you have written to simulate a few series of 100 coin tosses.

Problem 3

Replace the coin by a die. The initial, transition, and emission probabilities are as shown in the following figure.

Back to the previous page.