2
$\begingroup$

I am trying to understand Mixture Markov Models in order to cluster a set of sequences that do not necessarily all have the same states occurring in them.

If I have several sequences that I am trying to fit a Mixture Markov Model to, how do I go about the fact that some of the chains contain a part of all possible states while the others might contain other states? For example:

sequence 1: 1 2 4 2 4 1

sequence 2: 3 2 3 3 3 3

sequence 3: 1 2 3 1 1 2

How would I define a transition probability matrix for each of the sequences, given that the set of possible states is {1,2,3,4}? In the context of Mixture Markov Modeling, shouldn't a transition probability matrix be 4x4 and contain transfer probabilities for each state from the collection -> each state of the collection?

Take for instance sequence1:

My understanding is that the TPM of sequence1 should be:

   1   2   3   4

1  0.5 0.5 0   0

2  1   0   0   0

3  0   0   0   0

4  0.5 0.5 0   0

This seems to be incorrect, since TPM is a stochastic matrix whose rows sum up to 1, and the third row is just all 0s. Should I completely remove state 3 if I am building a transition probability matrix of a specific sequence?

The reason I need to have a Markov chain for each sequence is that I am trying to calculate log-likelihood distance between each two sequences in order to build a distance matrix and get medoids for initializing the Mixture Markov Model.

The formula for distance that I am trying to use is:

$D(seq_i,seq_j)=1/2* log(p(seq_i|v_j)+p(seq_j|v_i))$, where

$v_i,v_j$ are the Markov Chains representing the sequences $seq_i$ and $seq_j$ correspondingly.

How would I define sequences 1,2,3 in terms of their transition probability matrices and single ML-estimated Markov chains representing each sequence?

Improve this question
$\endgroup$
9
  • $\begingroup$ You're right that a transition matrix should include all probabilities for transitioning between all states in a Markov process. And, your TPM for the first sequence is also correct - those are the transition probabilities for that sequence. In sequence 1, there is never a transition to or from the 3rd state (3 in this case). To get TPMs for all 3 sequences, repeat the procedure you used to create the TPM for sequence 1. $\endgroup$
    – learner
    Aug 20, 2013 at 17:05
  • $\begingroup$ @learner, thank you for your answer. I guess I need to understand better how to work with such matrices. Because if the matrix is like this, there will be some "funny" log-likelihood distances between sequences (e.g. -Infinity). How would I even cluster the sequences according to this? $\endgroup$
    – zima
    Aug 21, 2013 at 9:29
  • $\begingroup$ At least in the context of information theory, it is accepted that the log of 0 can be replaced with 0 (so that, say, variables with no entropy have 0 entropy instead of -Inf). You could define some replacement value to replace -Inf, or you could replace the 0's with some arbitrarily small value, such as 1e-17. $\endgroup$
    – learner
    Aug 21, 2013 at 12:03
  • $\begingroup$ hm, but in the sense of "distance" where i am assuming 0 is the smallest distance ( and the more negative the log measure is the farther the distance), to equate log(0) to 0 would mean distance between two completely different sequences would be 0. The approach of replacing -Inf by a very small number seems appealing to me - would it not interfere with the future results if the transition matrices will have a "technically" non-zero probability where it should be zero? Is this trick an acceptable move for machine learning/model fitting problems? $\endgroup$
    – zima
    Aug 21, 2013 at 16:10
  • $\begingroup$ @learner, if you don't mind answering one more doubt that I have - don't the rows of stochastic matrix have to sum to 1? if i have one row of almost zeros, would that even be a proper transition matrix? $\endgroup$
    – zima
    Aug 22, 2013 at 9:32

1 Answer 1

Reset to default
0
$\begingroup$

Just to summarize, if you substitute your 0 values with some very small value such as 1e-17, your impossible states will still be the furthers apart. As you are trying to derive some sort of ordering of your data, it doesn't matter whether your smallest value is -Inf or -39, as either number will be the smallest value in the dataset.

Improve this answer
$\endgroup$
2
  • $\begingroup$ if you don't mind answering, I have one more follow-up question.. I have noticed that by using such values, my sum of transition matrix rows can sometimes go over 1 ( and I think this is the reason why sometimes I get corresponding Dirichlet priors larger than 1).. How do I address that? Reduce the relative probabilities of the other transitions to accomodate assigning very small values instead of 0 to these 0-chance probabilities? Please correct me if I am wrong. $\endgroup$
    – zima
    Aug 29, 2013 at 13:55
  • $\begingroup$ You could try adjusting the remaining probabilities - $(0.5 - (1*10^{-17}))$ should be very close to $0.5$. $\endgroup$
    – learner
    Aug 30, 2013 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.