Creating Hidden Markov Models with TANGRAM-II

When creating an HMM, the most cumbersome job is designing its chain structure (or structures, if the HMM is hierarchical). This is especially true when the chain has a large number of states. Imagine having to specify, manually, every transition of a $30$ state hidden Markov model. This means you would have to write $30 \times 30 = 900$ values! For this reason, TANGRAM-II allows the user to create a hidden Markov model chain structure with Tangram-II's Model Specification Module, using the objects therein, and load it directly into the HMM Module.

The basic idea behind this method is to have the HMM Module interpret the state transition matrix created by TANGRAM-II for the model designed by the user, and, from it, extract the necessary information to assemble the hidden Markov chain. So all the user has to do is build his hidden Markov model in TANGRAM-II, using its objects, events, and messages, have TANGRAM-II generate the state transition matrix that represents it and, finally, have the HMM Module load the created HMM model. Next, we will explain how this can be done, using a simple example.

The first step is to open Tangram-II's Model Specification Module, shown in Figure . This can be done by clicking the Model Specification button, in Tangram-II's Modeling Environment, shown in Figure .

Figure: Opening Tangram-II's Model Specification Module

[]

[]

Now, we can create our Markov model just like we would create a normal Tangram-II model. Let's have a look.

Suppose we want to create a hierarchical Gilbert hidden Markov model (a description of this type of HMM can be found in section of this manual and in the work of [#!fernando2006!#]) with $30$ hidden states, and the following characteristics:

i)

Every transition $(S_i,S_{i+1})$, in the hidden (upper-level) chain, occurs with a $0.5$ probability. If $S_i$ is the chain's last state, there is a transition to itself, also with a $0.5$ probability.

ii)

Every transition $(S_i,S_{i-1})$, in the hidden (upper-level) chain, occurs with a $0.4$ probability. If $S_i$ is the chain's first state, there is a transition to itself, also with a $0.4$ probability.

iii)

Every transition $(S_i,S_i)$, in the hidden (upper-level) chain, occurs with a $0.1$ probability.
Note: The transitions defined here do not expunge the transitions defined in (i) and (ii), for the first and last states. Thus, transition $(S_0, S_0) = 0.1 + 0.4$ and transition $(S_N, S_N) = 0.1 + 0.5$, where $S_0$ represents the first state and $S_N$ represents the last state.

iv)

There are no other transitions in the hidden chain, i.e, all other transitions have a $0.0$ probability of occurring.

v)

In every hidden state $S_i$, the transition probability from lower-level state $I_0$ to lower-level state $I_1$ is $0.9$, and the transition from lower-level state $I_1$ to lower-level state $I_0$ is $0.5$.

vi)

In every hidden state $S_i$, the probability of starting in lower-level state $I_1$ is $0.7$.

Let's start by building the upper-level chain. To this purpose, we will use the Markov_Chain Tangram-II object, illustrated in Figure . This object defines, by default, the state variable $N$, which describes the states of the Markov chain, and the constans $FWD\_RATE$, $BCK\_RATE$ and $MAX\_CHAIN\_SIZE$ which describe, respectively, the transition rate from state $S_i$ to state $S_{i+1}$; the transition rate from state $S_{i-1}$ to state $S_i$; and the total number of states of the chain. Since the upper-level chain we are looking to build has $30$ states, our first step will be to set $MAX\_CHAIN\_SIZE=29$^8.1. Next, we will specify the transition probabilities between the chain's states.

Every event in TANGRAM-II has a rate associated with it, which defines the rate at which the event occurs. When reading the state transition matrix created by TANGRAM-II, which specifies the rate at which transitions occur, the HMM Module will assume that every rate is, actually, a probability. For this reason, it is easy, for the user, to specify the transition probabilities for the Markov chain he is creating. All he has to do is set the rate of the event which describes the transition to the same value as the probability he wishes that transition to have. Thus, in our case, the event that describes transitions $(S_i,S_{i+1})$ (the Forward_Transition event) will have its rate set to $0.5$, which can be done by assigning this value to the constant $FWD\_RATE$. Similarly, the event which describes transitions $(S_i,S_{i-1})$ (the Backward_Transition event) will have its rate set to $0.4$, which can be done by assigning this value to the constant $BCK\_RATE$. The two remaining events in the Markov_Chain object, ZerotoZero_Transition event and NtoN_Transition event, will have to have their rates changed to $BCK\_RATE$ and $FWD\_RATE$, respectively, in order to satisfy the chain border conditions described in $(i)$ and $(ii)$.

Figure: Tangram-II's Markov Chain object.

This takes care of characteristics $(i)$ and $(ii)$. Figure shows our Tangram-II model so far, and Figure shows the upper-level Markov chain we have created up to now, by using the Markov_Chain object.

Figure: (a)Tangram-II model with the Markov_Chain object, and (b) the partial upper-level Markov chain created with it.

[]

[]

To finalize our upper-level chain, there is, still, one thing left to do: address characteristic $(iii)$. To this purpose, we will create a new event, in the Markov_Chain object, which we will call Same_ST, that does not change the value of the state variable N. Its rate will have, of course, the same value as the transition probability we specified in characteristic $(iii)$, which is $0.1$.

event = Same_ST( EXP, 0.1 )
condition = ( TRUE )
action =
{ 
    int n; 

    n  = N;
    
    set_st( "N", n  );
};

An so, we have finished building our upper-level Markov chain. Our next step will be to assemble the hierarchical chain, i.e., the Gilbert model that we want to put inside each hidden state. To build it, we will use the On_Off_Source object from TANGRAM-II. It will have one state variable, called Status, which will indicate the state that the model is currently in (if it is in state $I_0$ or $I_1$), and four events. Each event will describe one possible transition of the chain, i.e., transitions $I_0$ to $I_1$, $I_0$ to $I_0$, etc., and will have its rate set accordingly to $(v)$, as shown below:

Events=
event = I0_to_I1( EXP, 0.9 )
condition = ( Status == 0 )
action =
{
    int status;
    
    status = 1;
    
    set_st( "Status", status );
};

This takes care of characteristic $(v)$, and now there is only characteristic $(vi)$ left. In a hierarchical model, every lower-level state has an initial probability, i.e, a probability of being chosen as the starting state, once a transition to its upper-level state has happened. For this reason, the On_Off_Source object needs to know when the upper-level chain has made a transition, so it can choose its initial state. In order to do this, we will have to introduce a slight modification in the Markov_Chain object events. Every time a hidden transition event happens, it will have to send a message to the On_Off_Source object, informing it that a upper-level transition has happened. So, as an example, the Forward_Transition event of the Markov_Chain object will have a message routine introduced to it as follows:

Events=
event= Forward_Transition ( EXP, FWD_RATE )
condition= ( N < MAX_CHAIN_SIZE )
action =
{ 
    int n;

    n = N + 1;

    /* Send message to lower-level chain */
    msg( LOWER_LEVEL_PORT,  all, n  );

    set_st( "N", n  );
};

and the On_Off_Source object will deal with it in the following way:

Messages=
msg_rec = LOWER_LEVEL_PORT
action =
{ 
    set_st( "Status", 0 );
} : prob = 0.3;
{ 
    set_st( "Status", 1 );
} : prob = 0.7;

And we are done! Figure shows the model we have just created in TANGRAM-II, and Figure its corresponding hierarchical Gilbert hidden Markov chain structure.

Figure: (a)Tangram-II model created. (b)Hierarchical Gilbert hidden Markov model build with the model of (a).

[]

[]

This concludes the structure design part. But before loading this model into the HMM Module, TANGRAM-II has to, first, generate the state transition matrix of the model. This can be done with Tangram-II's Mathematical Model Generation module, shown in Figure .

Figure: Mathematical Model Generation Module (a) selection button; (b) state space generation interface.

[]

[]