# How to use Viterbi when there can be only one observation for a state

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?

-

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.

-