Hidden Markov Models › Parameter Estimation from Data

An HMM is only useful if we can learn its parameters from data. For POS tagging, we have access to annotated corpora where each word is labeled with its correct tag. This is supervised learning, and parameter estimation is straightforward: we count occurrences and normalize.

The intuition behind maximum likelihood estimation is simple: the best model is the one that assigns the highest probability to the observed data. If you saw the bigram "DT NN" a thousand times in training but "DT VB" only ten times, the data is telling you that determiners are followed by nouns far more often than by verbs, and your transition probabilities should reflect that. Maximum likelihood formalized this intuition into a precise estimation procedure.

The maximum likelihood estimates for HMM parameters are simple frequency ratios derived from counting occurrences in the training data. The estimates have a satisfying form: every probability is just the count of the event you care about divided by the count of the conditioning context. There are no free hyperparameters, no optimization loops, and no gradient descent. You count, you divide, and you are done.

For initial probabilities, we count how often each state starts a sequence:

$$\hat{\pi}_i = \frac{\text{count}(s_1 = i)}{\text{count}(\text{sequences})}$$

where:

• $\hat{\pi}_i$: the estimated probability of starting in state $i$
• $\text{count}(s_1 = i)$: the number of sequences that begin with state $i$
• $\text{count}(\text{sequences})$: the total number of sequences in the training data

For transition probabilities, we count how often state $j$ follows state $i$:

$$\hat{a}_{ij} = \frac{\text{count}(s_{t-1} = i, s_t = j)}{\text{count}(s_{t-1} = i)}$$

where:

• $\hat{a}_{ij}$: the estimated probability of transitioning from state $i$ to state $j$
• $\text{count}(s_{t-1} = i, s_t = j)$: the number of times state $i$ is immediately followed by state $j$
• $\text{count}(s_{t-1} = i)$: the total number of times state $i$ appears (except at sequence end)

For emission probabilities, we count how often state $i$ emits observation $o$:

$$\hat{b}_i(o) = \frac{\text{count}(s_t = i, o_t = o)}{\text{count}(s_t = i)}$$

where:

• $\hat{b}_i(o)$: the estimated probability of emitting observation $o$ from state $i$
• $\text{count}(s_t = i, o_t = o)$: the number of times state $i$ emits observation $o$
• $\text{count}(s_t = i)$: the total number of times state $i$ appears

In words: the initial probability of state $i$ is the fraction of sequences that start with $i$. The transition probability from $i$ to $j$ is the fraction of times $i$ is followed by $j$. The emission probability of $o$ from $i$ is the fraction of times state $i$ emits $o$.

Notice that each distribution is estimated independently. Transition probabilities depend only on pairs of consecutive tags; emission probabilities depend only on individual tag-word pairs. This independence makes estimation extremely fast and scales to large corpora without difficulty. The Brown corpus used below contains over 57,000 sentences and more than a million words; the entire parameter estimation completes in seconds.

Let's implement this with NLTK's tagged corpora. The Brown corpus contains over 57,000 sentences with POS tags, giving us enough data to estimate reliable probabilities. We'll use the Universal tagset, which maps the fine-grained Brown tags to 17 coarse categories for cleaner patterns.

: Emission probabilities for ambiguous words across POS tags. "Time" shows moderate noun vs. verb ambiguity. "Run" is more strongly verbal. "Set" has large probability from both noun and verb tags. This reflects its high ambiguity in English. {#tbl-emission-ambiguity}

The table reveals that "time" has higher emission probability from NOUN than VERB, but both are non-zero. This reflects lexical ambiguity. These patterns form the statistical backbone of HMM-based tagging.

A critical challenge emerges when we encounter words not seen during training. If a word $o$ never appeared with tag $i$, then $\hat{b}_i(o) = 0$. When we multiply by zero, the entire sequence probability becomes zero, making it impossible to tag sentences containing unknown words.

This is not a minor edge case. In real text, a significant fraction of words at test time will never have appeared in training. Technical documents use specialized vocabulary. Named entities change constantly. New words enter the language every year. An HMM tagger without a strategy for unknown words would completely fail on any non-trivial text.

Smoothing techniques address this problem. The simplest approach is add-one (Laplace) smoothing: add a small count to every word-tag combination before normalizing.

$$\hat{b}_i(o) = \frac{\text{count}(s_t = i, o_t = o) + 1}{\text{count}(s_t = i) + |V|}$$

where:

• $\hat{b}_i(o)$: the smoothed emission probability of observation $o$ from state $i$
• $\text{count}(s_t = i, o_t = o)$: the number of times state $i$ emits observation $o$ (zero for unseen combinations)
• $\text{count}(s_t = i)$: the total number of times state $i$ appears
• $|V|$: the vocabulary size (number of unique observations)

The numerator adds 1 to every count. This ensures no probability is ever zero. The denominator adds $|V|$ to compensate, keeping the probabilities properly normalized (summing to 1). This ensures every word has a non-zero probability from every tag, though the probability is very small for unseen combinations.