5.5.4 Extending the HMM algorithm to trigrams

We mentioned earlier that HMM taggers in actual use have a number of sophistications not present in the simplified tagger as we have described it so far. One important missing feature has to do with the tag context. In the tagger described above, we assume that the probability of a tag appearing is dependent only on the previous tag:

$$ \begin{array}{c} P(t_{1}^{n})~\approx~\displaystyle\prod_{i=1}^{n} P(t_{i}|t_{i-1})\end{array} $$

Most modern HMM taggers actually use a little more of the history, letting the probability of a tag depend on the two previous tags:

$$ \begin{array}{c} P(t_{1}^{n}) \approx \prod_{i=1}^{n} P(t_{i}|t_{i-1},t_{i-2})\end{array} $$

In addition to increasing the window before a tagging decision, state-of-the-art HMM taggers like Brants (2000) let the tagger know the location of the end of the sentence by adding dependence on an end-of-sequence marker for $ t_{n+1} $. This gives the following equation for part of speech tagging:

$$ \hat{t}_{1}^{n}=\underset{t_{1}^{n}}{\mathrm{a r g m a x}}P(t_{1}^{n}|w_{1}^{n})\approx\underset{t_{1}^{n}}{\mathrm{a r g m a x}}\left[\prod_{i=1}^{n}P(w_{i}|t_{i})P(t_{i}|t_{i-1},t_{i-2})\right]P(t_{n+1}|t_{n}) $$

In tagging any sentence with (5.41), three of the tags used in the context will fall off the edge of the sentence, and hence will not match regular words. These tags, $ t_{-1} $, $ t_{0} $, and $ t_{n+1} $, can all be set to be a single special ‘sentence boundary’ tag which is added to the tagset. This requires that sentences passed to the tagger have sentence boundaries demarcated, as discussed in Ch. 3.

There is one large problem with (5.41); data sparsity. Any particular sequence of tags $ t_{i-2}, t_{i-1}, t_i $ that occurs in the test set may simply never have occurred in the training set. That means we cannot compute the tag trigram probability just by the maximum likelihood estimate from counts, following Equation (5.42):

$$ P(t_{i}|t_{i-1},t_{i-2})=\frac{C(t_{i-2},t_{i-1},t_{i})}{C(t_{i-2},t_{i-1})}: $$

Why not? Because many of these counts will be zero in any training set, and we will incorrectly predict that a given tag sequence will never occur! What we need is a way to estimate $ P(t_i|t_{i-1},t_{i-2}) $ even if the sequence $ t_{i-2},t_{i-1},t_i $ never occurs in the training data.

The standard approach to solve this problem is to estimate the probability by combining more robust, but weaker estimators. For example, if we've never seen the tag sequence PRP VB TO, so we can't compute $ P(\mathrm{TO}|\mathrm{PRP},\mathrm{VB}) $ from this frequency, we still could rely on the bigram probability $ P(\mathrm{TO}|\mathrm{VB}) $, or even the unigram probability $ P(\mathrm{TO}) $. The maximum likelihood estimation of each of these probabilities can be computed from a corpus via the following counts:

$$ \mathrm{T r i g r a m s}\hat{P}(t_{i}|t_{i-1},t_{i-2})=\frac{C(t_{i-2},t_{i-1},t_{i})}{C(t_{i-2},t_{i-1})} $$

$$ \mathrm{Bigrams}\quad\hat{P}(t_{i}|t_{i-1})~=~\frac{C(t_{i-1},t_{i})}{C(t_{i-1})} $$

$$ \mathrm{U n i g r a m s}\qquad\hat{P}(t_{i})\;=\;\frac{C(t_{i})}{N} $$

How should these three estimators be combined in order to estimate the trigram probability $ P(t_i|t_{i-1},t_{i-2}) $? The simplest method of combination is linear interpolation. In linear interpolation, we estimate the probability $ P(t_i|t_{i-1}t_{i-2}) $ by a weighted sum of the unigram, bigram, and trigram probabilities:

$$ \begin{array}{c} P(t_{i}|t_{i-1}t_{i-2})~=~\lambda_{1}\hat{P}(t_{i}|t_{i-1}t_{i-2})+\lambda_{2}\hat{P}(t_{i}|t_{i-1})+\lambda_{3}\hat{P}(t_{i})\end{array} $$

We require $ \lambda_1 + \lambda_2 + \lambda_3 = 1 $, insuring that the resulting P is a probability distribution. How should these $ \lambda_s $ be set? One good way is deleted interpolation, developed by Jelinek and Mercer (1980). In deleted interpolation, we successively delete each trigram from the training corpus, and choose the $ \lambda_s $ so as to maximize the likelihood of the rest of the corpus. The idea of the deletion is to set the $ \lambda_s $ in such a way as to generalize to unseen data and not overfit the training corpus. Fig. 5.19 gives the Brants (2000) version of the deleted interpolation algorithm for tag trigrams.

Brants (2000) achieves an accuracy of 96.7% on the Penn Treebank with a trigram HMM tagger. Weischedel et al. (1993) and DeRose (1988) have also reported accuracies of above 96% for HMM tagging. (Thede and Harper, 1999) offer a number of augmentations of the trigram HMM model, including the idea of conditioning word likelihoods on neighboring words and tags.

The HMM taggers we have seen so far are trained on hand-tagged data. Kupiec (1992), Cutting et al. (1992), and others show that it is also possible to train an HMM tagger on unlabeled data, using the EM algorithm that we will introduce in Ch. 6. These taggers still start with a dictionary which lists which tags can be assigned to which words; the EM algorithm then learns the word likelihood function for each tag, and the tag transition probabilities. An experiment by Merialdo (1994), however, indicates that with even a small amount of training data, a tagger trained on hand-tagged data worked better than one trained via EM. Thus the EM-trained “pure HMM” tagger is probably best suited to cases where no training data is available, for example when tagging languages for which there is no previously hand-tagged data.

function DELETED-INTERPOLATION(corpus) returns $ \lambda_1, \lambda_2, \lambda_3 $

$ \lambda_1 \leftarrow 0 $

$ \lambda_2 \leftarrow 0 $

$ \lambda_3 \leftarrow 0 $

foreach trigram $ t_1, t_2, t_3 $ with $ f(t_1, t_2, t_3) > 0 $

depending on the maximum of the following three values

case $ \frac{C(t_1, t_2, t_3) - 1}{C(t_1, t_2) - 1} $: increment $ \lambda_3 $ by $ C(t_1, t_2, t_3) $

case $ \frac{C(t_2, t_3) - 1}{C(t_2) - 1} $: increment $ \lambda_2 $ by $ C(t_1, t_2, t_3) $

case $ \frac{C(t_3) - 1}{N - 1} $: increment $ \lambda_1 $ by $ C(t_1, t_2, t_3) $

end

end

normalize $ \lambda_1, \lambda_2, \lambda_3 $

return $ \lambda_1, \lambda_2, \lambda_3 $

5.6 TRANSFORMATION-BASED TAGGING

Transformation-Based Tagging, sometimes called Brill tagging, is an instance of the Transformation-Based Learning (TBL) approach to machine learning (Brill, 1995), and draws inspiration from both the rule-based and stochastic taggers. Like the rule-based taggers, TBL is based on rules that specify what tags should be assigned to what words. But like the stochastic taggers, TBL is a machine learning technique, in which rules are automatically induced from the data. Like some but not all of the HMM taggers, TBL is a supervised learning technique; it assumes a pre-tagged training corpus.

Samuel et al. (1998) offer a useful analogy for understanding the TBL paradigm, which they credit to Terry Harvey. Imagine an artist painting a picture of a white house with green trim against a blue sky. Suppose most of the picture was sky, and hence most of the picture was blue. The artist might begin by using a very broad brush and painting the entire canvas blue. Next she might switch to a somewhat smaller white brush, and paint the entire house white. She would just color in the whole house, not worrying about the brown roof, or the blue windows or the green gables. Next she takes a smaller brown brush and colors over the roof. Now she takes up the blue paint on a small brush and paints in the blue windows on the house. Finally she takes a very fine green brush and does the trim on the gables.

The painter starts with a broad brush that covers a lot of the canvas but colors a lot of areas that will have to be repainted. The next layer colors less of the canvas, but also makes less “mistakes”. Each new layer uses a finer brush that corrects less of the picture, but makes fewer mistakes. TBL uses somewhat the same method as this

painter. The TBL algorithm has a set of tagging rules. A corpus is first tagged using the broadest rule, that is, the one that applies to the most cases. Then a slightly more specific rule is chosen, which changes some of the original tags. Next an even narrower rule, which changes a smaller number of tags (some of which might be previously changed tags).