1
$\begingroup$

Suppose I have a large training set consisting of many strings of symbols.

$TS = \{Str_0, Str_1, ..., Str_n\}$

$Str_i = \{Sym_0 ... Sym_{len}\}$

These strings of symbols are each generated by the same Variable-order Markov process. Using this training set I can easily compute the needed conditional probability distributions for each symbol given a number of contexts i.e. $P(Sym_i|ctx_j)$ where $ctx_j$ is any subset of a string.

Once I have computed the transition matrix I am interested in computing the probability that some new string of symbols not found in the training set was also generated by the same Markov process. This feels like a goodness-of-fit calculation. Is it? If so what method should I use? If not what is the correct approach? Am I missing something?

$\endgroup$
4
  • $\begingroup$ Your question is a bit unclear but AFAICT computing the probability of a new string under a given markov model is not a "goodness-of-fit" calculation. You are simply summing over all possible values of the latent variables and adding up all the probabilities. Typically such calculation is done through dynamic programming. If your markov model is actually semi-markov (since you said variable order) then you can find implementations by googling "semi markov hmm dynamic programming". $\endgroup$
    – Pushpendre
    Feb 12, 2016 at 0:39
  • $\begingroup$ Does it help to clarify that I am unsure if the new string was computed by the same Markov process or if it is pure entropy or a simple string of zeros. I want to know how likely it is that this new string is "like" the others in the sense that they came from the same Markov process. $\endgroup$
    – nolandda
    Feb 12, 2016 at 0:49
  • $\begingroup$ I am still trying to understand the problem. That said, why couldn't you simply calculate the probability that your base/given markov process computed this string and then simply decide based on your loss function? For example, if you compute the probability that your markov process emitted the test string and it comes out to be 0.001 then it is unlikely that your model emitted this string. Depending on the amount of type-I, type-II error you are willing to allow, you can make a decision. $\endgroup$
    – Pushpendre
    Feb 12, 2016 at 3:21
  • $\begingroup$ Part 2: You can even think of 1 minus the probability as a statistic If you really want to. The null hypothesis is that the string was emitted by the model. If P > 0.05 you can reject the null hypothesis. $\endgroup$
    – Pushpendre
    Feb 12, 2016 at 3:22

0

Browse other questions tagged or ask your own question.