Hidden Markov Models › The Two HMM Assumptions

HMMs make two key independence assumptions that simplify computation. These assumptions trade off modeling power for tractability. Without them, exact inference over sequences would require considering every possible combination of hidden states, which grows exponentially with sequence length. With them, dynamic programming algorithms like Viterbi can find exact solutions in polynomial time. Understanding these assumptions deeply will help you know when HMMs are appropriate and when you need a more expressive model.

The first assumption is the Markov property: the probability of transitioning to a state depends only on the current state, not on the full history.

$$P(s_t \,|\, s_1, s_2, \ldots, s_{t-1}) = P(s_t \,|\, s_{t-1})$$

where:

• $s_t$: the state at position $t$ (what we want to predict)
• $s_1, s_2, \ldots, s_{t-1}$: the full history of previous states
• $s_{t-1}$: only the immediately preceding state

The equation states that knowing the entire history provides no additional information beyond knowing just the previous state. For POS tagging, this means the probability of a tag depends only on the previous tag, not on tags from earlier in the sentence. If the previous tag is DT (determiner), the probability of NN (noun) is the same regardless of what came before the determiner.

This is a strong assumption. Consider "the old old man" versus "the very old man." After seeing "old" once, the probability of another adjective might differ from seeing "old" for the first time. A first-order HMM cannot capture this distinction. Higher-order HMMs condition on the previous two or three tags rather than just one, which helps. A second-order HMM replaces $P(s_t \mid s_{t-1})$ with $P(s_t \mid s_{t-2}, s_{t-1})$, giving the model memory of the last two tags. The downside is that the transition table grows quadratically with tag set size: for $|S|$ tags, a first-order model has $|S|^2$ transition parameters, while a second-order model has $|S|^3$. For a 40-tag set like Penn Treebank, that difference is 1,600 versus 64,000 parameters, requiring substantially more training data for reliable estimates.

The second assumption is output independence: the probability of an observation depends only on the current state, not on other observations or states.

$$P(o_t \,|\, s_1, \ldots, s_n, o_1, \ldots, o_{t-1}, o_{t+1}, \ldots, o_n) = P(o_t \,|\, s_t)$$

where:

• $o_t$: the observation at position $t$ (the word we see)
• $s_1, \ldots, s_n$: all hidden states in the sequence
• $o_1, \ldots, o_{t-1}, o_{t+1}, \ldots, o_n$: all other observations (past and future words)
• $s_t$: only the current hidden state

The equation states that the probability of emitting a particular word depends solely on the current tag, not on any surrounding context. For POS tagging, this means the word "bank" has the same emission probability from the NN state regardless of surrounding words. The model cannot use the context "river bank" to increase the probability of the noun interpretation, nor can it use "bank account" to do the same. All disambiguation must happen indirectly through transition probabilities.

This is perhaps the most consequential limitation of HMMs for NLP. In natural language, the meaning and function of a word are heavily influenced by its neighbors. The word "light" is more likely an adjective after "a" and before "lunch" than after "switch" and before "on." A model that ignores this surrounding evidence will make systematic errors on ambiguous words. Conditional Random Fields, which you will study in a later chapter, address exactly this limitation by allowing the model to condition on arbitrary features of the surrounding context when making labeling decisions.