# Dynamic Programming vs Hidden Markov Models

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?

• For the first question - yes, for an HMM, as far as I know, you do need data (i.e. a sequence of observed states) to construct the most likely sequence of hidden states or even to construct a sequence of most likely states. I wouldn't really call this 'training' (I'd use the word training if you were using data to estimate a bunch of parameters, like the transition probability matrix). In this case, the question really just doesn't make sense if there were no data; the question is really based on a sequence of observed states. Nov 3, 2018 at 19:41
• For the second one, that's a very interesting statement, I do not really understand what the author means by an "invalid state transition". Nov 3, 2018 at 19:43
• @InfProbSciX - it's not so much that the state transitions themselves are invalid, it's that the sequence of "most likely" states don't need to obey the state transition rules. For example, the model might estimate that state $A$ is the most likely state at stage $10$, and $B$ is the most likely state at stage $11$, but the probability of transitioning from $A$ to $B$ between stages $10$ and $11$ is zero. The DP solution can't have that property. Nov 3, 2018 at 20:54

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.