Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

I want to calculate the best state sequence for a observation sequence. To do that, I want to use Viterbi algorithm.

In my problem, there are two properties:

  1. There can be only one observation possibility for a state. However the opposite is not true : an observation can be generated by more than one states.

  2. States have a certain order. e.g. state Y can follow state X, but state X cannot follow state Y.

More formally with a very simple case:

  • States : $Q=q_{a1},q_{a2},q_{b1}, q_{b2}$
  • State transitions : $A=[P(q_{b1}|q_{a1})=k, P(q_{b2}|q_{a1})=l, P(q_{b1}|q_{a2})=m, P(q_{b2}|q_{a2})=n]$, the rest ($P(q_{a1}|q_{a1})$, $P(q_{a1}|q_{b1})$, etc) is $0$ because of property (2)
  • $k+l=1$, $m+n=1$
  • Observations : $O=o_{a},o_{b}$
  • where $length(Q) > length(O)$
  • $P(o_{a}|q_{a1})=1, P(o_{a}|q_{a2})=1, P(o_{b}|q_{b1})=1, P(o_{b}|q_{b1})=1$ because of property (1)
  • Observation likelihoods = $Q(q_{a1}|o_{a})=f, Q(q_{a2}|o_{a})=g, Q(q_{b1}|o_{b})=h, Q(q_{b2}|o_{b})=j$
  • $f+g=1$, $h+j=1$

So,

  • For example, for $q_{a1}$, observation is always $o_{a}$.
  • But $o_{a}$ can be generated from $q_{a1}$ or $q_{a2}$.

The question is : what is the most likely state sequence for given observation sequence $o_{a} o_{b}$ ? $q_{a1}q_{b1}$ or $q_{a1}q_{b2}$ or $q_{a2}q_{b1}$ or $q_{a2}q_{b2}$

To solve this problem I read that Viterbi is the way to go. However, I have a more specific model and applying Viterbi for this model is not really efficient. A lot of 0's and 1's in the calculation.

Any directions for a better model / algorithm?

share|improve this question
add comment

1 Answer

Since Viterbi has complexity $O(N^2T)$ where

  • $N$ = number of states
  • $T$ = length of observation sequence

one can get the biggest speed improvement by reducing the states to consider during the recursion step.

Suggestion: Instead of looking for a separately published algorithm, rewrite Viterbi yourself. Create a map beforehand where all possible state transitions are stored. Then, during the recursion step, consider only the target states where a given transition from the current source state exists.

By adding a second map with key=state and value=created observation you can reduce the number of states to consider even more.

Dropping states during recursion is equivalent to set the probability for the overall path to 0. By dropping these paths as soon as the current path probability is set to zero, the number of paths to considers decreases as the algorithm proceeds.

BUT: I would expect that a good implementation already consider all these points.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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