5.8.4 Combining Taggers

The various part-of-speech tagging algorithms we have described can also be combined. The most common approach to tagger combination is to run multiple taggers in parallel on the same sentence, and then combine their output, either by voting or by training another classifier to choose which tagger to trust in a given context. Brill and Wu (1998), for example, combined unigram, HMM, TBL, and maximum-entropy taggers by voting via a higher-order classifier, and showed a small gain over the best of the four classifiers. In general, this kind of combination is only useful if the taggers have complementary errors, and so research on combination often begins by checking to see if the errors are indeed different from different taggers. Another option is to combine taggers in series. Hajic et al. (2001) apply this option for Czech, using the rule-based approach to remove some of the impossible tag possibilities for each word, and then an HMM tagger to choose the best sequence from the remaining tags.

5.9 ADVANCED: THE NOISY CHANNEL MODEL FOR SPELLING

The Bayesian inference model introduced in Sec. 5.5 for tagging has another interpretation: as an implementation of the noisy channel model, a crucial tool in speech recognition and machine translation.

In this section we introduce this noisy channel model and show how to apply it to the task of correcting spelling errors. The noisy channel model is used in Microsoft Word and in many search engines, and in general is the most widely used algorithm for correcting any kind of single-word spelling error, including non-word spelling errors and for real-word spelling errors.

Recall that non-word spelling errors are those which are not English words (like receive for receive), and we can detect these by simply looking for any word not in a dictionary. We saw in Sec. ?? that candidate corrections for some spelling errors could be found by looking for words that had a small edit distance to the misspelled word.

The Bayesian models we have seen in this chapter, and the noisy channel model, will give us a better way to find these corrections. Furthermore, we'll be able to use the noisy channel model for contextual spell checking, which is the task of correcting real-word spelling errors like the following:

They are leaving in about fifteen minuets to go to her house.

The study was conducted mainly by John Black.

Since these errors have real words, we can't find them by just flagging words not in the dictionary, and we can't correct them just using edit distance alone. But note that words around the candidate correction in about fifteen minutes make it a much more probable word sequence than the original in about fifteen minuets. The noisy channel model will implement this idea via N-gram models.

The intuition of the noisy channel model (see Fig. 5.23) is to treat the misspelled word as if a correctly-spelled word had been 'distorted' by being passed through a noisy communication channel. This channel introduces "noise" in the form of substitutions or other changes to the letters which makes it hard to recognize the "true" word. Our

goal is then to build a model of the channel. Given this model, we then find the true word by taking every word of the language, passing each word through our model of the noisy channel, and seeing which one comes the closest to the misspelled word.

This noisy channel model, like the HMM tagging architecture we saw earlier, is a special case of Bayesian inference. We see an observation $ O $ (a misspelled word) and our job is to find the word w which generated this misspelled word. Out of all possible words in the vocabulary V we want to find the word w such that $ P(w|O) $ is highest, or:

$$ \underset{(w\in V)}{\hat{w}}=\underset{(argmax P(w|O)}{\mathrm{P}(w|O)} $$

As we saw for part-of-speech tagging, we will use Bayes rule to turn the problem around (and note that, as for tagging, we can ignore the denominator):

$$ \hat{w}=\underset{w\in V}{\argmax}\frac{P(O|w)P(w)}{P(O)}=\underset{w\in V}{\argmax}P(O|w)P(w) $$

To summarize, the noisy channel model says that we have some true underlying word $w$, and we have a noisy channel which modifies the word into some possible misspelled surface form. The probability of the noisy channel producing any particular observation sequence $O$ is modeled by $P(O|w)$. The probability distribution over possible hidden words is modeled by $P(w)$. The most probable word $\hat{w}$ given that we've seen some observed misspelling $O$ can be computed by taking the product of the word prior $P(w)$ and the observation likelihood $P(O|w)$ and choosing the word for which this product is greatest.

Let's apply the noisy channel approach to correcting non-word spelling errors. This approach was first suggested by Kernighan et al. (1990); their program, correct, takes words rejected by the Unix spell program, generates a list of potential correct

words, ranks them according to Eq. (5.54), and picks the highest-ranked one. We'll apply the algorithm to the example misspelling across. The algorithm has two stages: proposing candidate corrections and scoring the candidates.

In order to propose candidate corrections Kernighan et al. make the reasonable (Damerau, 1964) simplifying assumption that the correct word will differ from the misspelling by a single insertion, deletion, substitution, or transposition. The list of candidate words is generated from the typo by applying any single transformation which results in a word in a large on-line dictionary. Applying all possible transformations to acess yields the list of candidate words in Fig. 5.24.

The second stage of the algorithm scores each correction by Equation 5.54. Let t represent the typo (the misspelled word), and let c range over the set C of candidate corrections. The most likely correction is then:

$$ \underset{(c\in C)}{\hat{c}=\operatornamewithlimits{a r g m a x}{}}~\overbrace{P(t|c)}^{\mathrm{l i k e l i h o o d~p r i o r}}~\overbrace{P(c)}^{\mathrm{p r i o r}} $$

The prior probability of each correction $ P(c) $ is the language model probability of the word c in context; for in this section for pedagogical reasons we'll make the simplifying assumption that this is the unigram probability $ P(c) $, but in practice in spelling correction this is extended to trigram or 4-gram probabilities. Let's use the corpus of Kernighan et al. (1990), which is the 1988 AP newswire corpus of 44 million words. Since in this corpus the word actress occurs 1343 times out of 44 million, the word acres 2879 times, and so on, the resulting unigram prior probabilities are as follows:

How can we estimate $ P(t|c) $? It is very difficult to model the actual channel perfectly (i.e. computing the exact probability that a word will be mistyped) because it would require knowing who the typist was, whether they were left-handed or right-handed, and many other factors. Luckily, it turns out we can get a pretty reasonable estimate of $ p(t|c) $ just by looking at simple local context factors, because the most important factors predicting an insertion, deletion, transposition are the identity of the correct letter itself, how the letter was misspelled, and the surrounding context. For example, the letters m and n are often substituted for each other; this is partly a fact about their identity (these two letters are pronounced similarly and they are next to each other on the keyboard), and partly a fact about context (because they are pronounced similarly, they occur in similar contexts). Kernighan et al. (1990) used a simple model of this sort. They estimated e.g. $ p(across|across) $ just using the number of times that the letter e was substituted for the letter o in some large corpus of errors. This is represented by a confusion matrix, a square $ 26 \times 26 $ matrix which represents the number of times one letter was incorrectly used instead of another. For example, the cell labeled $ [o,e] $ in a substitution confusion matrix would give the count of times that e was substituted for o. The cell labeled $ [t,s] $ in an insertion confusion matrix would give the count of times that t was inserted after s. A confusion matrix can be computed by coding a collection of spelling errors with the correct spelling and then counting the number of times different errors occurred (Grudin, 1983). Kernighan et al. (1990) used four confusion matrices, one for each type of single error:

• del[x, y] contains the number of times in the training set that the characters xy in the correct word were typed as x.

ins[x,y] contains the number of times in the training set that the character x in the correct word was typed as xy.

• sub[x, y] the number of times that x was typed as y.

• trans[x,y] the number of times that xy was typed as yx.

Note that they chose to condition their insertion and deletion probabilities on the previous character; they could also have chosen to condition on the following character. Using these matrices, they estimated $ p(t|c) $ as follows (where $ c_p $ is the $ p $th character of the word $ c $):

$$ P(t|c)=\left\{\begin{array}{l}\frac{\mathrm{d e l}_{[c_{p-1},c_{p}]}}{\mathrm{c o u n t}_{[c_{p-1}c_{p}]}},\text{if}\text{deletion}\\ \frac{\mathrm{i n s}_{[c_{p-1},t_{p}]}}{\mathrm{c o u n t}_{[c_{p-1}]}},\text{if}\text{insertion}\\ \frac{\mathrm{s u b}_{[t_{p},c_{p}]}}{\mathrm{c o u n t}_{[c_{p}]}},\text{if}\text{substitution}\\ \frac{\mathrm{t r a n s}_{[c_{p},c_{p+1}]}}{\mathrm{c o u n t}_{[c_{p}c_{p+1}]}},\text{if}\text{transposition}\end{array}\right. $$

Fig. 5.25 shows the final probabilities for each of the potential corrections; the unigram prior is multiplied by the likelihood (computed using Equation (5.56) and the confusion matrices). The final column shows the “normalized percentage”.

This implementation of the Bayesian algorithm predicts acres as the correct word (at a total normalized percentage of 45%), and actress as the second most likely word.

| c | freq(c) | p(c) | p(t|c) | p(t|c)p(c) | % |

| --- | --- | --- | --- | --- | --- |

| actress | 1343 | .0000315 | .000117 | $ 3.69 \times 10^{-9} $ | 37% |

| cress | 0 | .000000014 | .00000144 | $ 2.02 \times 10^{-14} $ | 0% |

| caress | 4 | .0000001 | .00000164 | $ 1.64 \times 10^{-13} $ | 0% |

| access | 2280 | .000058 | .000000209 | $ 1.21 \times 10^{-11} $ | 0% |

| across | 8436 | .00019 | .0000093 | $ 1.77 \times 10^{-9} $ | 18% |

| acres | 2879 | .000065 | .0000321 | $ 2.09 \times 10^{-9} $ | 21% |

| acres | 2879 | .000065 | .0000342 | $ 2.22 \times 10^{-9} $ | 23% |

Unfortunately, the algorithm was wrong here: The writer's intention becomes clear from the context: … was called a “stellar and versatile actress whose combination of sass and glamour has defined her…”. The surrounding words make it clear that actress and not acres was the intended word. This is the reason that in practice we use trigram (or larger) language models in the noisy channel model, rather than unigrams. Seeing whether a bigram model of $ P(c) $ correctly solves this problem is left as Exercise 5.10 for the reader.

The algorithm as we have described it requires hand-annotated data to train the confusion matrices. An alternative approach used by Kernighan et al. (1990) is to compute the matrices by iteratively using this very spelling error correction algorithm itself. The iterative algorithm first initializes the matrices with equal values; thus any character is equally likely to be deleted, equally likely to be substituted for any other character, etc. Next the spelling error correction algorithm is run on a set of spelling errors. Given the set of typos paired with their corrections, the confusion matrices can now be recomputed, the spelling algorithm run again, and so on. This clever method turns out to be an instance of the important EM algorithm (Dempster et al., 1977) that we will discuss in Ch. 6.