Next: Build an HMM Trainer Up: HMM Project Previous: HMM Project

### Simulate an HMM

First, build an HMM simulator so that you have a source of observations'' and a target to compare against. To do this, we will build an MM, and then we will proceed to hide'' it from the HMM trainer. I suggest creating code that can manage N states, numbered 0, ...  N - 1, and M different kinds of observations, numbered 0, ...  M - 1, and which produces observations of length T. In other words, N, M and T are parameters of your Markov model. Initially, I suggest that we attempt to train models where N = 3, M = 4 and T varies from 3 to 5. Here is an example.

If this above model splits its transition probabilities 3:1 in favor of going right'', then the transition probability matrix is as follows.

 ai, j 0 1 2 0 0.25 0.75 0 1 0 0.25 0.75 2 0 0 1

Let's assume that this model always starts in state 0.

 0 1 2 1 0 0

Finally, there are four observations, 0, 1, 2 and 3, with the following probabilities per state.

 bi(k) 0 1 2 3 0 0.5 0.5 0 0 1 0 0.5 0.5 0 2 0 0 0.5 0.5

To build the MM, use a Monte Carlo simulation. First, you'll need a random number generator. In C, use the random() function (see manual page), seeded by srandom() using the data from a call to time() (see manual page).1 Once random() is seeded, you can easily define a function randomint(lb, ub) that returns a random integer x in the range lb x <ub.2

int randomint (int lb, int ub) {
return lb + random() % (ub - lb);
}

You can also define a function that returns a random floating point number x in the range 0 x 1.

double randomreal () {
return ((double) random()) / RAND_MAX;
}

To generate a random choice over a given distribution, simply do the following. Assume we wish to generate the initial state according to .

1. Generate a random number x such that 0 x 1.
2. i 0.
3. x x -
4. While i < N and x > 0 do
5.    i i + 1
6.    x x -
7.   End while loop.
8. If i < N then i is the randomly selected state else error (sum of probabilities is < 1).
Use the above method to:

• select the initial state of the HMM,
• select the next state, and
• select the observation that appears in each state.
You are now ready to define a function that produces a single observation sequence.

function newsequence ( N, M,, a, b, T)

1. Create an HMM according to the given model.
2. Let s be the initial state, chosen according to .
3. Let O be the empty sequence of observations.
4. While length(O) < T do
5.   Let o be the observation for current state s, chosen according to bs.
6.    O = concatenate(O, o) (i.e., add o to the end of O).
7.    s next state according to as.
8.   End while loop.
9. Return O.

Next: Build an HMM Trainer Up: HMM Project Previous: HMM Project
Webmaster: Jim Schmolze, schmolze@eecs.tufts.edu.  [Get postscript version]