The Viterbi Algorithm can be used to calculate the most likely path, based on observations in a Hidden Markov Model.

Using the same notations as Wikipedia, "each element T1[i, j] of T1 stores the probability of the most likely path so far X = (x[1] , x[2] , ... , x[j]) with x[j] = s[i] that generates Y = (y[1] , y[2] , ... , y[j]).

Now suppose, that the initial distribution $\pi$ is such that for one state the probability is 1 (let's call it state K), and for all other states it is 0. Also, let's say that in the emission matrix B all elements are strongly between 0 and 1 (i.e. 0 < B[i, j] < 1 for all i and j.

In this way 0 < T[K,1] < 1 and for all other states T[i,1] = 1.

Problem: For me, the part T[K,1] < 1 feels intuitively wrong. How can it be, that the first state is K, with probability 1, still the most likely path contains it with probability less than 1?

I understand that the reason must be something like: "There are more different paths. One where the first state is K, and the first observation is y1. One, where the first state is K, and the observation is y2. Etc.".

However, it is also true, that "no matter what the observation is, the first state is K with probability 1".

Question: What is the explanation for this (seeming) contradiction? (The best would be if it is "intuitive".)


Wikipedia is wrong. That's not what $T_1$ stores. Rather, $T_1$ stores the likelihood of a path... namely, the likelihood of the path that has the highest likelihood. What's the likelihood of a path $\hat{X}$? It is the probability of generating the output sequence $Y$ given that you followed the path $\hat{X}$, i.e., the probability $P(Y | \hat{X})$. Note that this is not the same as $P(\hat{X} | Y)$.

The probability $P(Y | \hat{X})$ might be less than 1, even if we're certain that $\hat{X}$ was the path that was followed. In particular, you can have $P(Y | \hat{X}) < 1$ even if $P(\hat{X}) = 1$. This can happen, for example, if there are multiple possible output sequences that could arise when following the path $\hat{X}$.

As usual, Wikipedia is not a primary source. Don't use Wikipedia as your only source for learning new material. It is helpful as a summary, but when you find something in Wikipedia that is confusing or that doesn't make sense, go to a primary source -- e.g., a highly reputed textbook. Wikipedia does have errors, poor writing, gaps in its explanation, and so on, so it is not a substitute for a high-quality primary source.

  • $\begingroup$ Thanks, that cleared it up quite a bit. I think the key is that T stores P(Y|X^) and not P(X) (as I thought originally) neither P(X|Y). $\endgroup$ – Attilio Jan 21 '18 at 15:53

Your Answer

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

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