5.5.1 Computing the most-likely tag sequence: A motivating example

The previous section showed that the HMM tagging algorithm chooses as the most likely tag sequence the one that maximizes the product of two terms; the probability of the sequence of tags, and the probability of each tag generating a word. In this section we ground these equations in a specific example, showing for a particular sentence how the correct tag sequence achieves a higher probability than one of the many possible wrong sequences.

We will focus on resolving the part-of-speech ambiguity of the word race, which can be a noun or verb in English, as we show in two examples modified from the Brown and Switchboard corpus. For this example, we will use the 87-tag Brown corpus tagset, because it has a specific tag for to, TO, used only when to is an infinitive; prepositional uses of to are tagged as IN. This will come in handy in our example. $ ^{1} $

In (5.36) race is a verb (VB) while in (5.37) race is a common noun (NN):

(5.36) Secretariat/NNP is/BEZ expected/VBN to/TO race/VB tomorrow/NR

People/NNS continue/VB to/TO inquire/VB the/AT reason/NN for/IN the/AT race/NN for/IN outer/JJ space/NN

Let's look at how race can be correctly tagged as a VB instead of an NN in (5.36). HMM part-of-speech taggers resolve this ambiguity globally rather than locally, picking the best tag sequence for the whole sentence. There are many hypothetically possible tag sequences for (5.36), since there are other ambiguities in the sentence (for example expected can be an adjective (JJ), a past tense/preterite (VBD) or a past participle (VBN)). But let's just consider two of the potential sequences, shown in Fig. 5.12. Note that these sequences differ only in one place; whether the tag chosen for race is VB or NN.

Almost all the probabilities in these two sequences are identical; in Fig. 5.12 we have highlighted in boldface the three probabilities that differ. Let's consider two of these, corresponding to $ P(t_i|t_{i-1}) $ and $ P(w_i|t_i) $. The probability $ P(t_i|t_{i-1}) $ in Figure 5.12a is $ P(\mathrm{VB}|\mathrm{TO}) $, while in Figure 5.12b the transition probability is $ P(\mathrm{NN}|\mathrm{TO}) $.

The tag transition probabilities $ P(\mathrm{NN}|\mathrm{TO}) $ and $ P(\mathrm{VB}|\mathrm{TO}) $ give us the answer to the question “How likely are we to expect a verb (noun) given the previous tag?” As we

saw in the previous section, the maximum likelihood estimate for these probabilities can be derived from corpus counts.

Since the (87-tag Brown tagset) tag TO is used only for the infinitive marker to, we expect that only a very small number of nouns can follow this marker (as an exercise, try to think of a sentence where a noun can follow the infinitive marker use of to). Sure enough, a look at the (87-tag) Brown corpus gives us the following probabilities, showing that verbs are about 500 times as likely as nouns to occur after TO:

$$ \begin{aligned}P(NN|TO)&=.00047\\P(VB|TO)&=.83\end{aligned} $$

Let's now turn to $ P(w_i|t_i) $, the lexical likelihood of the word race given a part-of-speech tag. For the two possible tags VB and NN, these correspond to the probabilities $ P(\text{race}|\text{VB}) $ and $ P(\text{race}|\text{NN}) $. Here are the lexical likelihoods from Brown:

$$ \begin{aligned}&P(race|NN)=.00057\\&P(race|VB)=.00012\\ \end{aligned} $$

Finally, we need to represent the tag sequence probability for the following tag (in this case the tag NR for tomorrow):

$$ \begin{aligned}&P(NR|VB)=.0027\\&P(NR|NN)=.0012\\ \end{aligned} $$

If we multiply the lexical likelihoods with the tag sequence probabilities, we see that the probability of the sequence with the VB tag is higher and the HMM tagger

correctly tags race as a VB in Fig. 5.12 despite the fact that it is the less likely sense of race:

$$ P(\mathrm{VB}|\mathrm{TO})P(\mathrm{NR}|\mathrm{VB})P(\mathrm{race}|\mathrm{VB})=.00000027 $$

$$ P(\mathrm{NN}|\mathrm{TO})P(\mathrm{NR}|\mathrm{NN})P(\mathrm{race}|\mathrm{NN})=.00000000032 $$