- HOME

Final Project Report. MATH 127.

Course taken during Fall 2002 page compiled on July 2, 2015 at 12:08am

1 Example HMM

2 Forward algorithm

2.1 Calculation of the alpha's using logarithms

3 Backward algorithm

4 Viterbi algorithm

5 Conﬁguration ﬁle description

6 Conﬁguration ﬁle examples

6.1 Example 1. Casino example

6.2 Example 2. Homework problem 4.1

7 SHMM User interface

8 Source code description

9 Installation instructions

2 Forward algorithm

2.1 Calculation of the alpha's using logarithms

3 Backward algorithm

4 Viterbi algorithm

5 Conﬁguration ﬁle description

6 Conﬁguration ﬁle examples

6.1 Example 1. Casino example

6.2 Example 2. Homework problem 4.1

7 SHMM User interface

8 Source code description

9 Installation instructions

Abstract

Hidden Markov Models (HMM) main algorithms (forward, backward, and Viterbi) are outlined, and a GUI based implementation (in MATLAB) of a basic HMM is included along with a user guide. The implementation uses a ﬂexible plain text conﬁguration ﬁle format for describing the HMM.

1 Example HMM

2 Forward algorithm

2.1 Calculation of the alpha's using logarithms

3 Backward algorithm

4 Viterbi algorithm

5 Conﬁguration ﬁle description

6 Conﬁguration ﬁle examples

6.1 Example 1. Casino example

6.2 Example 2. Homework problem 4.1

7 SHMM User interface

8 Source code description

9 Installation instructions

2 Forward algorithm

2.1 Calculation of the alpha's using logarithms

3 Backward algorithm

4 Viterbi algorithm

5 Conﬁguration ﬁle description

6 Conﬁguration ﬁle examples

6.1 Example 1. Casino example

6.2 Example 2. Homework problem 4.1

7 SHMM User interface

8 Source code description

9 Installation instructions

Introduction

This report is part of my ﬁnal term project for the course MATH 127, Mathematics department, Berkeley, CA, USA

I have taken this course as an extension student in the fall of 2002 to learn about computational methods in biology. The course is titled “Mathematical and Computational Methods in Molecular Biology” and given by Dr. Lior Pachter.

This report contains a detailed description of the three main HMM algorithms. An implementation (in MATLAB) was completed. See page 41 for detailed description of the implementation, including a user guide.

In the area of computational biology, HMMs are used in the following areas:

- 1.
- Pattern ﬁnding (Gene ﬁnding[3]).
- 2.
- multiple sequence alignments.
- 3.
- protein or RNA secondary structure prediction.
- 4.
- data mining and classiﬁcation.

Deﬁnitions and notations

To explain HMM, a simple example is used.

Assume we have a sequence. This could be a sequence of letters, such as DNA or protein sequence, or a sequence of numerical values (a general form of a signal) or a sequence of symbols of any other type. This sequence is called the observation sequence.

Now, we examine the system that generated this sequence. Each symbol in the observation sequence is generated when the system was in some speciﬁc state. The system will continuously ﬂip-ﬂop between all the diﬀerent states it can be in, and each time it makes a state change, a new symbol in the sequence is emitted.

In most instances, we are more interested in analyzing the system states sequence that generated the observation sequence. To be able to do this, we model the system as a stochastic model which when run, would have generated this sequence. One such model is the hidden Markov model. To put this in genomic perspective, if we are given a DNA sequence, we would be interested in knowing the structure of the sequence in terms of the location of the genes, the location of the splice sites, and the location of the exons and intron among others.

What we know about this system is what states it can be in, the probability of changing from one state to another, and the probability of generating a speciﬁc type of element from each state. Hence, associated with each symbol in the observation sequence is the state the system was in when it generated the symbol.

When looking a sequence of letter (a string) such as “ACGT ”, we do not know which state the system was in when it generated, say the letter ‘C'. If the system have states that it can be in, then the letter ‘C' could have been generated from any one of those states.

From the above brief description of the system, we see that there are two stochastic processes in progress at the same time. One stochastic process selects which state the system will switch to each time, and another stochastic process selects which type of element to be emitted when the system is in some speciﬁc state.

We can imagine a multi-faced coin being ﬂipped to determine which state to switch to, and yet another such coin being ﬂipped to determine which symbol to emit each time we are in a state.

In this report, the type of HMM that will be considered will be time-invariant. This means that the probabilities that describe the system do not change with time: When an HMM is in some state, say , and there is a probability to generate the symbol from this state, then this probability do not change with time (or equivalent, the probability do not change with the length of the observation sequence).

In addition, we will only consider ﬁrst-order
HMM.^{1}

An HMM is formally deﬁned^{2}
as a ﬁve-tuple:

- 1.
- Set of states . These are the ﬁnite number of states the system can be in at any one
time.
It is possible for the system to be in what is referred to as silent states in which no symbol is generated. Other than the special start and the end silent states (called the states), all the system states will be active states (meaning the system will generate a symbol each time it is in one of these states).

When we want to refer to the state the system was in when it generated the element at position in the observation sequence , we write . The initial state, which is the silent state the system was in initially, is written as . When we want to refer to the name of the state the system was in when it generated the symbol at position we write .

- 2.
- is the probability of the system changing from state to state .
For a system with number of states, there will be a transition matrix of size which gives the state transition probability between any 2 states.

- 3.
- is the emission probability. It is the probability of emitting the symbol seen at position
in the observation sequence when the system was in state .
As an example of the emission probability, assume that the observed sequence is and assume that the system can be in any one of two states . Then we write the probability of emitting the ﬁrst symbol when the system is in state as .

We could also write the above as , since the symbol is located at the ﬁrst position of the sequence. In the above observation sequence, since the letter occurred in the ﬁrst and third positions, then will have the same value as , since in both cases, the same type of letter is being emitted, which is the symbol .

- 4.
- Set of initial probabilities for all states . We imagine a special silent start state from
which the initial active state is selected according to the probability . see ﬁgure 1 on page 6
for illustration.

For a system with number of states, there will be such probabilities. So for some state, say , the probability of this state being the ﬁrst state the system starts in is given by . Notice that another notation for the initial probability is , and this is used in [1] and other publication.

- 5.
- The set of possible observation sequences . We imagine the system running and generating an observation sequence each time according to the emission probability distribution and according to the state sequence associated with this observation sequence. The collection of possible observation sequences is the language of the system. The unique alphabets that make up the observation sequences are the allowed alphabet of the language. As an example, an HMM used to model DNA sequences would have as its alphabets, while one used to model protein sequences would have the 20 amino acids as its alphabets.

So, to summarize how this model generates an observation sequence: The system starts in state . Then based the probability distribution called the initial state probability, a state is selected. Then based on the emission probability distribution for this state, the symbol at position is selected and generated. Then a new state is selected based on the transition probability distribution and the process repeats again as above. This process is continued until the last symbol is generated.

The sequence generated by the system is called the observation sequence . The symbol at position in the sequence is called or . We write to mean that the symbol at position is .

In the implementation of HMM for this project, the length of each output symbol is limited to one character.

For a system with states, and an observation sequence of length , the number of possible state sequences that could have generated this observation sequence is . Each one of these possible state sequences is of length since the system will generate one symbol for each state transition as we are considering that there will not be any silent states other than the start and end states.

As an example, given a system with with states , and an observation sequence of ‘GCT' of length , then there are or possible state sequences. They are

One of these 8 state sequences is the most likely one to have
occurred.^{3}

To summarize the above discussion, imagine we have a system with states , and that the possible symbols or alphabets of the system it can generate are . Figure 2 on page 9 shows one such possible state sequence and the associated observation sequence .

The questions one could ask about the above HMM system are:

- 1.
- Given a sequence of symbols of length that represents the output of the system (the observation sequence), determine the probability of the system generating this sequence up to and including . This is solved using the forward algorithm .
- 2.
- Given a sequence of symbols that represents the output of the system (the observations),
determine the probability that some speciﬁc symbol in the observation sequence was generated
when the system was in some speciﬁc state.
This is solved using the forward-backward algorithm (). As an example, we can ask about the probability that some DNA nucleotide from a large DNA sequence was part of an exon, where an exon is one of the possible system states.

- 3.
- Given a sequence of symbols of length that represents the output of the system (the
observation sequence), determine the most likely state transition sequence the system would have
undergone in order to generate this observation sequence.
This is solved using the Viterbi algorithm . Note again that the sequence of states will have the same length as the observation sequence .

The above problems are considered HMM analysis problems. There is another problem, which is the training or identiﬁcation problem whose goal is to estimate the HMM parameters (the set of probabilities) we discussed on page 5 given some set of observation sequences taken from the type of data we wish to use the HMM to analyze. As an example, to train the HMM for gene ﬁnding for the mouse genome, we would train the HMM on a set of sequences taken from this genome.

One standard algorithm used for HMM parameter estimation (or HMM training) is called Baum-Welch, and is a specialized algorithm of the more general algorithm called EM (for expectation maximization). In the current MATLAB implementation, this algorithm is not implemented, but could be easily added later if time permits.

A small observation: In these notations, and in the algorithms described below, I use the value as the ﬁrst position (or index) of any sequence instead of the more common used in languages such as C, C++ or Java. This is only for ease of implementation as I will be using MATLAB for the implementation of these algorithms, and MATLAB uses and not as the starting index of an array. This made translating the algorithms into MATALAB code much easier.

Graphical representations of an HMM

There are two main methods to graphically represent an HMM. One method shows the time axis (or the position in the observation sequence) and the symbols emitted at each time instance (called the trellis diagram). The other method is a more concise way of representing the HMM, but does not show which symbol is emitted at what time instance.

To describe each representation, I will use an example, and show how the example can be represented graphically in both methods.

Throughout this report, the following HMM example is used for illustration. The HMM conﬁguration ﬁle for the example that can be used with the current implementation is shown. Each diﬀerent HMM state description (HMM parameters) is written in a plain text conﬁguration ﬁle and read by the HMM implementation. The format of the HMM conﬁguration ﬁle is described on page 41.

Assume the observed sequence is . This means that was the ﬁrst symbol emitted, seen at time , and is the second symbol seen at time , and so forth. Notice that we imagine that the system will write out each symbol to the end of the current observation sequence.

Next, Assume the system can be in any one of two internal states .

Assume the state transition matrix to be as follows

And for the initial probabilities , assume the following

And ﬁnally for the emission probabilities , there are unique symbols that are generated in this example (the alphabets of the language of the observation sequence), and they are . So there will be emission probabilities, symbols for each state, and given we have states, then we will have a total of emission probabilities. Assume they are given by the following emission matrix:

The ﬁrst (non-time dependent) graphical representation of the above example is shown in ﬁgure 3 on page 13

In this representation, each state is shown as a circle (node). State transitions are represented by a directed edge between the states. Emission of a symbol is shown as an edge leaving the state with the symbol at the end of the edge.

Initial probability are shown as edges entering into the state from state (not shown). We imagine that there is a silent start state which all states originate from. The system cannot transition to state , it can only transition out of it.

The second graphical representation is a more useful way to represent an HMM for the description of the algorithms. This is called the trellis diagram.

Draw a grid, where time ﬂows from left to right. On top of the grid show the symbols being emitted at each time instance. Each horizontal line in this grid represents one state, with state transitions shown as sloping edges between the nodes in the grid.

See ﬁgure 4 on page 16 for the graphical representation for the same example above using the trellis representation.

On each line segment in the grid, we draw an arrow from position to and label this arrow by the state transition probability from the state where the start of the arrow was to the state where the end of the arrow is. The weight of the edge is the state transition probability.

Notice that the edge can only be horizontal or slopped in direction. We can not have vertical edges, since we must advance by one time step to cause a state transition to occur. This means there will be as many internal states transitions as the number of time steps, or equivalently, as the number of symbols observed or the length of the observation sequence.

To use the above example in SHMM, we need to write down the state description. The format of writing down the state description is given on page 41. This below is the SHMM conﬁguration ﬁle for the above example.

<states>

S

T

<init_prob>

0.4

0.6

<symbols>

A,C,T

<emit_prob>

#emit probability from S state

0.4,0.4,0.2

#emit probability from T state

0.25,0.55,0.2

<tran_prob>

0.7, 0.3

0.4, 0.6

S

T

<init_prob>

0.4

0.6

<symbols>

A,C,T

<emit_prob>

#emit probability from S state

0.4,0.4,0.2

#emit probability from T state

0.25,0.55,0.2

<tran_prob>

0.7, 0.3

0.4, 0.6

HMM algorithms

Given the above notations and deﬁnitions, we are ready to describe the HMM algorithms.

Here we wish to ﬁnd the probability that some observation sequence of length was generated by the system which has states. We want to ﬁnd the probability of the sequence up to and including , in other words, the probability of the sequence .

The most direct an obvious method to ﬁnd this probability, is to enumerate all the possible state transition sequences the system could have gone through. Recall that for an observation sequence of length there will be possible state transition sequences.

For each one of these state transition sequences (that is, we ﬁx the state transition sequence), we then ﬁnd the probability of generating the observation sequence for this one state transition sequence.

After ﬁnding the probability of generating the observation sequence for each possible state transition sequence, we sum all the resulting probabilities to obtain the probability of the observation sequence being generated by the system.

As an example, for a system with states and observation sequence a partial list of the possible state sequences we need to consider is shown in ﬁgure 5 on page 20.

We can perform the above algorithm as follows:

Find the probability of the system emitting the symbol from . This is equal to the probability of emitting the symbol from state multiplied by the probability of being in state .

Next, ﬁnd the probability of generating the sequence . This is equal to the probability of emitting the sequence (which we found from above), multiplied by the probability of moving from state to state , multiplied by the probability of emitting the symbol from state .

Next, ﬁnd the probability of generating the sequence . This is equal to the probability of emitting the sequence (which we found from above), multiplied by the probability of moving from state to state , multiplied by the probability of emitting the symbol from state .

We continue until we ﬁnd the probability of emitting the full sequence

Obviously the above algorithm is not eﬃcient. There are possible state sequences, and for each one we have to perform multiplications, resulting in multiplications in total.

For an observation sequence of length and a system with states, we have to wait a very long time for this computation to complete.

A much improved method is the algorithm. The idea of the algorithm, is that instead of ﬁnding the probability for each diﬀerent state sequence separately and then summing the resulting probabilities, we scan the sequence from left to right, one position at a time, but for each position we calculate the probability of generating the sequence up to this position for all the possible states.

Let us call the probability of emitting the sequence as . And we call the probability of emitting when the system was in state when emitting as .

So, the probability of emitting the sequence will be equal to the probability of emitting the same sequence but with being emitted from one state say , this is called , plus the probability of emitting the same sequence but with being emitted from another state, say , this is called , and so forth until we have covered all the possible states. In other words is the for all states .

Each is found by multiplying the for each of the states, by the probability of moving from each of those states to state , multiplied by the probability of emitting from state . This step is illustrated in ﬁgure 6 on page 23.

Each time we calculate for some state k, we store this value, and use it when calculating . Hence We only need to store the for one position earlier since we are working with a ﬁrst-order HMM here. This means we need space requirements for two columns each of length of the number of states .

From above, we see that we have reduced the running time of the direct method, to with the method.

The following is a more formal description of the algorithm to ﬁnd for one state, say state .

Initialization step:

What the above says is that , initially (at position ) and for state , is equal to the probability of the HMM starting initially in state multiplied by the probability of emitting the symbol found at from state .

Iterative step:

What the above says, is that at position when in state , is the sum of all the from one observation earlier collected from all the states, multiplied by the probability of transition from each of those states to the state , multiplied by the probability of emitting the symbol when in state .

I will illustrate this iterative step for one time step, using the same example from above, and using the grid representation of an HMM to ﬁnd . Since there are 2 states in this example, we need to calculate the iterative step for each state.

When the system is in state at we obtain the diagram shown in ﬁgure 7 on page 26.

In the above example, to ﬁnd , we obtain

is found similarly, and is shown in ﬁgure 8 on page 29.

In the above example, for we obtain

Hence, to ﬁnd the probability of the sequence up to and including , the ﬁnal answer would be

Due to numerical issues (underﬂow) which will occur when multiplying probabilities (values less than 1.0) repeatedly as we calculate the in the forward direction, the log of the probabilities will be used instead, and multiplications become summations. Any logarithm for a base greater than can be used. In the MATLAB implementation, I used the natural logarithms .

Initially, all the probabilities (this includes the initial state probabilities , the state transition probabilities matrix , and the emission probabilities matrix ) are converted to and stored in cache for later access, this speeds the implementation by not having to call the log function each time the program is run for diﬀerent observation sequence but for the same HMM.

Assume the system has states , and we wish to ﬁnd the for the observation sequence up to and including when the state at was . We obtain

Taking the log of the above results in

Now, looking at the term , this is the same as . Here, we know the values of , and not (recall that we have converted all the probabilities to log initially for performance purposes). So we need to ﬁnd given and .

This is done using the following transformation

Applying the above transformation to many terms being summed, and not just two, is straightforward. Take as the ﬁrst term, and let be the rest of the terms (the tail of the expression), we then apply the above transformation recursively to the tail to compute the log of the sum of the probabilities as long as the tail is of length greater than one element. As shown below.

Where

Now repeat the above process to ﬁnd .

Where now .

Continue the above recursive process, until the expression contains one term to obtain

This is a sketch of a function which accomplishes the above.

function Log_Of_Sums(A: array 1..n of probabilities) returns double IS

begin

IF (length(A)>2) THEN

return( log(A[1]) + log( 1 + exp( Log_of_Sums(A[2..n])) - log( A[1] )));

ELSE

return( log(A[1] + log( 1 + exp( A[2] - log( A[1] )));

END

end log_Of_Sums

begin

IF (length(A)>2) THEN

return( log(A[1]) + log( 1 + exp( Log_of_Sums(A[2..n])) - log( A[1] )));

ELSE

return( log(A[1] + log( 1 + exp( A[2] - log( A[1] )));

END

end log_Of_Sums

The number of states is usually much less than the number of observations, so there is no problems (such as stack overﬂow issues) with using recursion in this case.

Here we are interested in ﬁnding the probability that some part of the sequence was generated when the system was in some speciﬁc state.

For example, we might want to ﬁnd, looking at a DNA sequence , the probability that some nucleotide at some position, say was generated from an exon, where an exon is one of the possible states the system can be in.

Let such state be . Let the length of the sequence be , then we need to obtain . In the following, when is written without subscripts, it is understood to stand for the whole sequence . Also is the same as .

Using Baye's probability rule we get

But the joint probability can be found from

Looking at the equation above, we see that is nothing but , which is deﬁned as the probability of the sequence with being generated from state .

The second quantity is found using the backward algorithm as described below.

Initialization step:

For each state , let

recursive step:

Where the sum above is done over all states. Hence

Where is found by running the forward algorithm to the end of the observed sequence , so . Hence we obtain

To illustrate this algorithm, Using the grid HMM diagram, I will use the example on page 11, to answer the question of what is the probability of the observation at position (which is the letter 'A') coming from state S, given the observation ATACC.

In the above, we will run the forward algorithm from position 1 to position 3, then run the backward algorithm from the end of the sequence back to position 3. (In practice, the forward and backward are calculated once for all the states and all the positions (that is, for all the nodes in the trellis diagram) and stored for later lookup). See ﬁgure 9 on page 35 for an illustration.

Initialization step:

recursive step: .

At time , we get

The above quantities are calculated using the parameters in this example, resulting in

at time we get

The above quantities are calculated using the parameters in this example, resulting in

And so forth, until we reach

This completes the iterative step of the backward algorithm. From the above we see that Now, apply the forward algorithm from position 1 to position 5, and ﬁnd .

I will not show this step here, since the forward algorithm is already described above. But if we calculate it, we will get

So

Where is the same as , that is, the forward algorithm found at the end of the sequence . can be found to be , so

The Viterbi algorithm is used to ﬁnd the most likely state transition sequence associated with some observation sequence .

Since one symbol is generated each time the system switches to a new state, the state sequence will be of the same length as that of the observation sequence .

In this algorithm, we need to calculate for each position, where means the probability of the most likely state path ending in state when generating the symbol at position in the observation sequence.

If we know for each state , then we can easily ﬁnd for each state , since we just need to ﬁnd the most probable state transition from each state to each state .

The following algorithm ﬁnds at position for state .

Initialization step:

Find at position for all states. Assume we have states, , then

Now we need to calculate for the rest of the sequence.

Assume we have states , then to ﬁnd for each of these states at each time step we do the following: (this below shows ﬁnding for some state )

iterative step:

The above is illustrated in ﬁgure 10 on page 40.

Now that we have found for each state at each position , we can ﬁnd the most likely state sequence up to any position by ﬁnding which state had the largest at each position.

Design and user guide of SHMM

To help understand HMMs more, I have implemented, in MATLAB, a basic HMM with a GUI user interface for ease of use. This tool accepts an HMM description (model parameters) from a plain text conﬁguration ﬁle. The tool (called SHMM, for simple HMM) implements the forward, backward, and Viterbi algorithms. This implementation is for a ﬁrst order HMM model.

Due to lack of time to implement an HMM for an order greater than a ﬁrst order, which is needed to enable this tool to be used for such problems as gene ﬁnding (to detect splice sites, start of exon, etc…). This implementation therefor is restricted to one character look-ahead on the observation sequence. However, even with this limitation, this tool can be useful for learning how HMM's work.

SHMM takes as input a plain text conﬁguration ﬁle (default .hmm extension), which contains the description of the HMM (states, initial probabilities, emission probabilities, symbols and transition probabilities). And the user is asked to type in the observation sequence in a separate window for analysis.

The conﬁguration ﬁle is broken into 5 sections. The order of the sections must be as shown below. All 5 sections must exist. Each section starts with the name of the section, contained inside a left and a right brackets. No space is allowed after or before . The entries in the ﬁle are case sensitive. So a state called 'sunny' will be taken as diﬀerent from a state called 'SUNNY'. The same applies to the characters allowed in the observation sequence: the letter 'g' is taken as diﬀerent from 'G'.

The sections, and the order in which they appear in the conﬁguration ﬁle, must be as this, from top to bottom:

- 1.
- <states>
- 2.
- <init_prob>
- 3.
- <symbols>
- 4.
- <emit_prob>
- 5.
- <tran_prob>

In the <states> sections, the names of the states are listed. One name per line. Names must not contain a space.

In the <init_prob> section, the initial probabilities of being in each state are listed. One per line. One number per line. The order of the states is assumed the same as the order in the <states> section. This means the initial probability of being in the ﬁrst state listed in the <states> section will be assumed to be the ﬁrst number in the <init_prob> section.

In the <symbols> section, the observation symbols are listed. Each symbol must be one character long, separated by a comma. Can use as many lines as needed to list all the symbols. The symbol must be an alphanumeric character.

In the <emit_prob> section, we list the probability of emitting each symbol from each state. The order of the states is assumed to be the same order of the states as in the <states> section.

The emission probability for each symbol is read. The order of the symbols is taken as the same order shown in the symbols section. The emission probabilities are separated by a comma. One line per state. See examples below.

In the <tran_prob>, we list the transition probability matrix. This is the probability of changing state from each state to another. One line represent one row in the matrix. Entries are separated by a comma. One row must occupy one line only. The order of the rows is the same as the order of the states shown in the <states> section.

For example, if we have 2 states S1,S2, then the ﬁrst line will be the row that represents S1->S1, and S1->S2 transition probabilities. Where S1->S1 is in position 1,1 of matrix, and S1->S2 will be in position 1,2 in the matrix. See example below for illustration.

Comments in the conﬁguration ﬁle are supported. A comment can start with the symbol #. Any line that starts with a # is ignored and not parsed. The comment symbol # must be in the ﬁrst position of the line.

To help illustrate the format of the HMM conﬁguration ﬁle, I will show an annotated conﬁguration ﬁle for the casino example shown in the book 'Biological sequence analysis' by Durbin et. all[1], page 54. In this example, we have 2 dies, one is a fair die, and one is a loaded die. The following is the HMM conﬁguration ﬁle.

# example HMM configuration file for Durbin, page 54

# die example.

<states>

fair

loaded

<init_prob>

#fair init prob

0.5

#loaded init prob

0.5

<symbols>

1,2,3,4,5,6

<emit_prob>

#emit probability from fair state

1/6, 1/6, 1/6, 1/6, 1/6, 1/6

#emit probability from fair state

1/10, 1/10, 1/10, 1/10, 1/10, 1/10

<tran_prob>

0.95, 0.05

0.1, 0.9

# die example.

<states>

fair

loaded

<init_prob>

#fair init prob

0.5

#loaded init prob

0.5

<symbols>

1,2,3,4,5,6

<emit_prob>

#emit probability from fair state

1/6, 1/6, 1/6, 1/6, 1/6, 1/6

#emit probability from fair state

1/10, 1/10, 1/10, 1/10, 1/10, 1/10

<tran_prob>

0.95, 0.05

0.1, 0.9

See ﬁgure 11 on page 45 for description of each ﬁeld in the HMM conﬁguration ﬁle.

To help better understand the format of the HMM conﬁguration ﬁle, I will show below a number of HMM states and with the conﬁguration ﬁle for each.

This example is taken from page 54, Durbin et. all book [1]. See ﬁgure 12 on page 48

This example is taken from Math 127 course, homework problem 4.1, Fall 2002.

Figure 14 on page 54 shows the SHMM GUI. To start using SHMM, the ﬁrst thing to do is to load the HMM conﬁguration ﬁle which contains the HMM parameters. SHMM will parse the ﬁle and will display those parameters. Next, type into the observation sequence window the observation sequence itself. This sequence could be cut and pasted into the window as well. Spaces and new lines are ignored.

Next, hit the top right RUN button. This will cause SHMM to evaluate the , and for each node in the trellis diagram, and will display all these values. For the calculations, the nodes in the trellis diagram which are on the Viterbi path have a ‘*' next to them.

To invoke the algorithm, enter the position in the observation and the state name and hit the small RUN button inside the window titled Alpha Beta.

To modify the HMM parameters and run SHMM again, simply use an outside editor to do the changes in the HMM conﬁguration ﬁle, then load the ﬁle again into SHMM using the ‘Open' button.

The following is a list of all the MATLAB ﬁles that make up SHMM, with a brief description of each ﬁle. At the end of this report is the source code listing.

- nma_hmmGUI.ﬁg: The binary description of the GUI itself. It is automatically generated by MATLAB using GUIDE.
- nma_hmmGUI.m: The MATLAB code that contains the properties of each component in the GUI.
- nma_hmm_main.m: This is the main function, which loads the GUI and initializes SHMM.
- nma_hmm_callbacks.m: The callbacks which are called when the user activate any control on the GUI.
- nma_readHMM.m:
- nma_hmmBackward.m: The function which calculates .
- nma_hmmForward.m: The function which calculates .
- nma_hmm_veterbi.m: The function which calculates .
- nma_hmmEmitProb.m: A utility function which returns the emission probability given a symbol and a state.
- nma_trim.m: A utility function which removes leading and trailing spaces from a string.
- getPosOfState.m: A utility function which returns position of state in an array given the state name.
- nma_logOfSums.m: A utility function which calculates the log of sum of logs for the computation.
- nma_logOfSumsBeta.m: A utility function which calculates the log of sum of logs for the computation.

Included on the CDROM are 2 ﬁles: setup.exe and unix.tar. The ﬁle setup.exe is the installer for windows. On windows, simply double click the ﬁle setup.exe and follow the instructions. When installation is completed, an icon will be created on the desktop called MATH127. Double click on this icon to open. Then 2 icons will appear. One of them is titled HMM. Double click on that to start SHMM. A GUI will appear.

On Unix (Linux or Solaris), no installer is supplied. Simply untar the ﬁle math127.zip. This will create the same tree that the installer would create on windows. The tree contains a folder called src, which contains the source code needed to run SHMM from inside matlab. To run SHMM on Unix, cd to the folder where you untarred the ﬁle math127.tar, which will be called MATH127 by default, and navigate to the src folder for the HMM project. Then run the ﬁle nma_hmm_main from inside MATLAB console to start SHMM.

This report is in .ps format, and the original .tex ﬁle and the diagram ﬁles are included in the doc folder.

Example HMM conﬁguration ﬁles for use with SHMM are included in the conf folder.