# 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. – InfProbSciX Nov 3 '18 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". – InfProbSciX Nov 3 '18 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. – jbowman Nov 3 '18 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.

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.

• one quick follow up question: could you provide me maybe a real example of each case; (1) where we care about whether the hidden state sequence was possible and (2) where we do not? My guess is that (1) could be something like: what steps did a hacker take to achieve goal X? We care because we wouldn't want to allocate resources to some sequence that's not possible. And for (2) my guess: we are more concerned with what states a hacker utilized to achieve their goals, regardless if they followed a specific sequence of those states. – Zduff Nov 4 '18 at 23:15