5.5.2 Formalizing Hidden Markov Model taggers

Now that we have seen the equations and some examples of choosing the most probable tag sequence, we show a brief formalization of this problem as a Hidden Markov Model (see Ch. 6 for the more complete formalization).

The HMM is an extension of the finite automata of Ch. 3. Recall that a finite automaton is defined by a set of states, and a set of transitions between states that are taken based on the input observations. A weighted finite-state automaton is a simple augmentation of the finite automaton in which each arc is associated with a probability, indicating how likely that path is to be taken. The probability on all the arcs leaving a node must sum to 1. A Markov chain is a special case of a weighted automaton in which the input sequence uniquely determines which states the automaton will go through. Because they can't represent inherently ambiguous problems, a Markov chain is only useful for assigning probabilities to unambiguous sequences.

While the Markov chain is appropriate for situations where we can see the actual conditioning events, it is not appropriate in part-of-speech tagging. This is because in part-of-speech tagging, while we observe the words in the input, we do not observe the part-of-speech tags. Thus we can't condition any probabilities on, say, a previous part-of-speech tag, because we cannot be completely certain exactly which tag applied to the previous word. A Hidden Markov Model (HMM) allows us to talk about both observed events (like words that we see in the input) and hidden events (like part-of-speech tags) that we think of as causal factors in our probabilistic model.

An HMM is specified by the following components:

$$ Q=q_1q_2\ldots q_N\qquad\qquad\mathrm{~a~s e t~o f~}N\mathrm{~s t a t e s} $$

$$ A=a_{11}a_{12}\ldots a_{n1}\ldots a_{nn} $$

$$ A, $$

$$ a_{ij} $$

$$ O=o_{1}o_{2}\ldots o_{T} $$

$$ \begin{array}{r}{\sum_{j=1}^{n}a_{i j}=1}\end{array}\forall i $$

a sequence of T observations, each one drawn from a vocabulary $ V = \nu_1, \nu_2, ..., \nu_V $.

$$ \boldsymbol{B}=\boldsymbol{b}_{i}(o_{t}) $$

A sequence of observation likelihoods:, also called emission probabilities, each expressing the probability of an observation $ o_{t} $ being generated from a state i.

a special start state and end (final) state which are not associated with observations, together with transition probabilities $ a_{01}a_{02}...a_{0n} $ out of the start state and $ a_{1}F a_{2F}...a_{nF} $ into the end state.

An HMM thus has two kinds of probabilities; the A transition probabilities, and the B observation likelihoods, corresponding respectively to the prior and likelihood probabilities that we saw in equation (5.31). Fig. 5.13 illustrates the prior probabilities in an HMM part-of-speech tagger, showing 3 sample states and some of the A transition probabilities between them. Fig. 5.14 shows another view of an HMM part-of-speech tagger, focusing on the word likelihoods B. Each hidden state is associated with a vector of likelihoods for each observation word.