Dynamic Programming vs Hidden Markov Models

Question

I've just been introduced to machine learning, and one of the first topics I'm covering is an introduction to finite state transitions and their models. Specifically, right now, I'm on Hidden Markov Models (HMM). Reading this paper by Mark Stamp, he states that in finding the "most likely" sequence of hidden states, given a sequence of observations, that we must distinguish between two types of most likely. Please check my understanding of what he's saying.

I believe he's saying (in my own words): There's a way to interpret "most likely" as the sequence of states most likely to generate our sequence of observations. And there's another way of interpreting "most likely" that corresponds to finding the largest number of correct states, that is, those that match what actually happened.

For the latter, doesn't this mean we would have to know what the actual states were? And in that regard, does that mean this model would have to be trained?

And secondly, the main reason I'm posting is in regards to the following passage from the paper:

What does the author mean, when he says that the HMM solution does not require valid state transitions? But more importantly, to me, why would we be okay with non-valid state transitions?

Answer 1

Let's consider the two definitions of "most likely". The first definition is, as you state, the state sequence that is the "most likely" to have generated the observed values. Note that we are looking at the entire state sequence at once! Therefore, if, for example, the probability of transitioning from state $A$ to state $B$ equals zero, there cannot be a "most likely" state sequence which has state $A$ followed by state $B$ - according to this definition. Since dynamic programming implicitly forces the sequence it estimates to be a feasible one from the point of view of the state transitions, the DP solution will also respect valid state transitions, and will therefore generate the "most likely" sequence according to this definition.

However, another "most likely" sequence can be defined by selecting the most likely states at each stage irrespective of whether it is actually possible to transition between consecutive "most likely" states. This will maximize the expected number of correct states. Here we are looking at "most likely" from a stage-specific viewpoint, not a sequence-specific viewpoint. Naturally, if the probability of transitioning between $A$ and $B$ equals $0$, this will influence the HMM-calculated probability that the two hidden states are $A$ followed by $B$, but it only influences it, it doesn't ensure that it can't occur.

In neither case do we need to know the correct states; we are calculating the probabilities of the various states and sequences therefrom, and maximizing those probabilities, albeit under two different definitions of "maximum probability of a sequence". If we actually knew the correct states, we wouldn't bother to estimate them at all! As to whether we care if the sequence of estimates respects valid state transitions, that's problem-specific; sometimes we do and sometimes we don't.