I understand that Viterbi finds the most probable sequence of states.

However, I want the probability of all possible sequences of states.

I understand that FB algorithm can be used to find the posterior marginals of all hidden state variables given a sequence of observations/emissions.

But what I want is the posterior marginals of all possible paths and not just the posterior marginal of a state for a particular time.

  • 1
    $\begingroup$ Unless you've got a special case in mind, I doubt that there's anything clever to be done. For $K$ states in a sequence with $T$ steps, you have $K^T$ sequences to enumerate (some sequences may have probability 0). Using caching and recursion could simplify the code, but it's gonna be tedious no matter what. What problem are you trying to solve, and how does computing the posterior marginals of all possible paths fit into solving it? $\endgroup$ – Sycorax Mar 2 at 4:51
  • $\begingroup$ I am using HMM for sequence alignment. I need the probability of each alignment for a part of my EM algorithm. I know that I can find the optimal alignment and its posterior probability using Needleman Wunsch(Viterbi for sequence alignment). But how do I compute the posterior probability for all possible alignments? $\endgroup$ – Duke Glacia Mar 2 at 13:45
  • 1
    $\begingroup$ Well, you'll compute it the direct way: the probability of all sequences of length $t=1$, then all sequences of length $t=2$, then $t=3$, and so on up to $t=T$. But the main benefit of the typical EM/Baum Welch algorithm for HMM is that you don't have to enumerate all possible sequences. I'm wondering if this is an XY problem: you want to use EM for sequence alignment in an HMM, but you're asking about how to compute the probabilities for all sequences. $\endgroup$ – Sycorax Mar 2 at 18:13
  • $\begingroup$ Sorry for the lack of clarity. I am not doing only alignment but rather I am trying to use an alignment algorithm(or get inspirations from it) to find the probability of getting the probability of suboptimal alignments. $\endgroup$ – Duke Glacia Mar 3 at 19:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.