ISSUE: How variable state should be selected in Hidden Markov Model (HMM)?

HMM & SIMPLE MARKOV: Under Markov process, the output depends on state. The output is visible, thus, observable. State that produces output is not visible. Each state has probability distribution over all possible output. Therefore, the sequence of output generated by HMM provides information about sequence states. Recall that in simple Markov, the state is directly visible to observers. The only parameter is state transition probability. However, in Hidden Markov Model, the state producing the output is not directly visible, i.e. latent. Only the output that depends on state is visible.

Suppose that we have a data sequence: u = {u1, u2, ..., uT}. In this case, there are 53 time series observations; therefore the last term is u53. Now, every ut is generated by a hidden state called St. This underlying (latent) state St follows a Markov chain, that is: (i) given the present, the future is independent of the past or simply that the future event depends on the most recent event. the distant past is of no consequence. Thus:

P(St+1 | St, St-1, ..., S0) = P(St-1 | St)

From St-1 to St, there is a transition probability which may be summarized as:

aki = P(St+1 = I | St = k)

... where k,i = 1, 2, ... M where M represents a total number of states. The initial number of states is pk. (reads pi sub-k). The total sum of the transition probabilities adds up to 1 and the total sum of pk is also add up to 1. NOW, the states are:

S(S1, S2, ... , ST) = P(S2 | S1)P(S3|S2) ... P(ST | ST-1)

This probability of pk may be written as:

S(S1, S2, ... , ST) = pkas1s2as2s3 ... aST-1,ST

For a given state ST, the observation ut is independent of other observation and state.

HOW DOES IT WORK?

Markov Process:          X0........A.......X1......A.......X2......A.......XT-1

                                         B                  B                B                  B

Observations:              O0................O1..............O2 ............. OT-1

What does it mean? A Markov process X0 produces an observation O0 via a hidden process B. Then moving from Xo to X1, there is a transition process A. This A has its own probability called transition aki. Matrix A = {aki} is an N X N where

aki = P(state gi at t+1 | state gi at t)

A is row stochastic. Matrix B = {bj(k)} is N X M with

bj(k) = P(observed k at t | state gi at t).

Thus, HMM is defined by A, B, p and dimension N and M. The formal statement for HMM is:

Lambda = (A, B, p)

NOW, consider a generic sequence X = (X0, X2, X3) with corresponding observations O = (O0, O2, O3). Then pxo is the probability of starting in state X0; that bx0(O0) is the probability of initially observing O0 and axo,x1 is the probability of the transition for X0 to X1. Therefore, the probability P(X) is give as:

P(X) = px0bx0(O0)ax0x1(O0)ax1x2b2bx2(O2)ab3bx3(O3)

In the present case, find P(53) by using the above generic sequence as a model. Extend the sequence to O53.Your matrix A is 53 X 53 and matrix B is 53 X 20. Thus:

P(53) = px0bx0(O0)ax0x1(O0)ax1x2b2bx2(O2) ...   ...   ab53bx53(O53)

Thank you Paul for consideration.

The database include 20 subset, and 20 label corresponding to each subset.

Observation variables include 53 time series. I suppose that these observations are ordered, because they are time dependent. Also they have a dynamic behaviour in each subset. In other words, the variables changed in a class.

There is no limitation for number of samples for training HMM. I have a huge database.

I would be appreciate for your answer in advance.

Dear Mahdieh,

If I understand well, you have several time series, each one belonging to one of the possible 20 classes (labels), right?

Then the goal should be, given a new time serie, classify it in one of the 20 classes.

A common approach for classification with HMMs is that you train 20 HMMs, one for each class, with the time series corresponding to that class. Then, when you have to classify a new time serie with an unknown label, you should calculate the loglikelihood of this time series given all the HMM_i, with 1

ISSUE: How variable state should be selected in Hidden Markov Model (HMM)?

HMM & SIMPLE MARKOV: Under Markov process, the output depends on state. The output is visible, thus, observable. State that produces output is not visible. Each state has probability distribution over all possible output. Therefore, the sequence of output generated by HMM provides information about sequence states. Recall that in simple Markov, the state is directly visible to observers. The only parameter is state transition probability. However, in Hidden Markov Model, the state producing the output is not directly visible, i.e. latent. Only the output that depends on state is visible.

Suppose that we have a data sequence: u = {u1, u2, ..., uT}. In this case, there are 53 time series observations; therefore the last term is u53. Now, every ut is generated by a hidden state called St. This underlying (latent) state St follows a Markov chain, that is: (i) given the present, the future is independent of the past or simply that the future event depends on the most recent event. the distant past is of no consequence. Thus:

P(St+1 | St, St-1, ..., S0) = P(St-1 | St)

From St-1 to St, there is a transition probability which may be summarized as:

aki = P(St+1 = I | St = k)

... where k,i = 1, 2, ... M where M represents a total number of states. The initial number of states is pk. (reads pi sub-k). The total sum of the transition probabilities adds up to 1 and the total sum of pk is also add up to 1. NOW, the states are:

S(S1, S2, ... , ST) = P(S2 | S1)P(S3|S2) ... P(ST | ST-1)

This probability of pk may be written as:

S(S1, S2, ... , ST) = pkas1s2as2s3 ... aST-1,ST

For a given state ST, the observation ut is independent of other observation and state.

HOW DOES IT WORK?

Markov Process:          X0........A.......X1......A.......X2......A.......XT-1

                                         B                  B                B                  B

Observations:              O0................O1..............O2 ............. OT-1

What does it mean? A Markov process X0 produces an observation O0 via a hidden process B. Then moving from Xo to X1, there is a transition process A. This A has its own probability called transition aki. Matrix A = {aki} is an N X N where

aki = P(state gi at t+1 | state gi at t)

A is row stochastic. Matrix B = {bj(k)} is N X M with

bj(k) = P(observed k at t | state gi at t).

Thus, HMM is defined by A, B, p and dimension N and M. The formal statement for HMM is:

Lambda = (A, B, p)

NOW, consider a generic sequence X = (X0, X2, X3) with corresponding observations O = (O0, O2, O3). Then pxo is the probability of starting in state X0; that bx0(O0) is the probability of initially observing O0 and axo,x1 is the probability of the transition for X0 to X1. Therefore, the probability P(X) is give as:

P(X) = px0bx0(O0)ax0x1(O0)ax1x2b2bx2(O2)ab3bx3(O3)

In the present case, find P(53) by using the above generic sequence as a model. Extend the sequence to O53.Your matrix A is 53 X 53 and matrix B is 53 X 20. Thus:

P(53) = px0bx0(O0)ax0x1(O0)ax1x2b2bx2(O2) ...   ...   ab53bx53(O53)

Thank you for reply....

But, actually my problem is in the following form:

each subset is monolabel:

subset1:

label                        1        1     ......................    1    

observation             O1,1    O1,2 .........................O1,t

                                O2,1    O2,2..........................O2,t

                                     ...               ...                     .....          ..

                              O53,1   O53,2 ......................O53,t

subset 2

label                 2    2 ................................. 2

observation    O1,1 O1,2 .........................O1,t

                       O2,1 O2,2..........................O2,t

                        ...     ...       .....                   ..

                      O53,1 O53,2 .......................O53,t

and the database includes 20 subsets as mentioned above and they are monolabel. There are no limitation on number of samples (t can be 1000 or 100000000.....)

my problem is: 

the transient and emission matix is not defined and should be learned based on database.

I select label vector as state variable and train HMM based on database....

But my question is:

Is there any way to define any other state variable instead of label ??

Read this paper :

P. VRIGNAT, M. AVILA, F. DUCULTY, S. AUPETIT, M. SLIMANE, F. KRATZ, Maintenance policy: degradation laws versus Hidden Markov Model availability indicator, Proceedings of the Institution of Mechanical Engineers, Part O: Journal of Risk and Reliability, 226(2), pp. 137-155, 2012. (Winner of the SAGE Best Paper Prize in 2012 by the editorial board of Journal of Risk and Reliability)

Dear Mahdieh,

As I firstly suspected, this is the classic classification problem, in which you have to learn a HMM for each subset, by using the relative time series. Such as, you use the Ov,t ,with 1

See my US patent #7912717, "Method for uncovering hidden Markov models," 2011.

It's a maximum likelihood method for finding the best way of adding hidden states and transitions to a set of observed states and transitions to get a hidden Markov model.  It builds on the graphical model to maximize the likelihood that the set of observed timeseries came from a new model with one additional transition.  It uses a kind of AIC to determine when to stop adding hidden transitions (namely, when the best way of adding a single hidden transition, with 2 degrees of freedom for transition rates, is not significantly better in loglikelihood than the next best way of adding a hidden transition).  It overcomes the combinatorial complexity of searching all possible graphical models by letting the data determine how the graph is built one step at a time, of all possible ways that add one transition.  It's based on the free software QUB from SUNY Buffalo Physiology Dept.  Patents are pending elsewhere (and granted in Singapore).  Notice that it doesn't find a model that isn't justified by the data.  This is not the same as saying it doesn't work.  Miraculously, it does work sometimes.

Are you asking how you can select the optimum number of states for your HMM?

look at this:

https://www.researchgate.net/publication/283889476_A_Doubly_Hierarchical_Dirichlet_Process_Hidden_Markov_Model_with_a_Non-Ergodic_Structure

Article A Doubly Hierarchical Dirichlet Process Hidden Markov Model ...