4.10.1 Cross-Entropy for Comparing Models

In this section we introduce cross-entropy, and discuss its usefulness in comparing different probabilistic models. The cross-entropy is useful when we don't know the actual probability distribution $p$ that generated some data. It allows us to use some $m$, which is a model of $p$ (i.e., an approximation to $p$). The cross-entropy of $m$ on $p$ is defined by:

$$ H(p,m)=\lim_{n\to\infty}-\frac{1}{n}\sum_{W\in L}p(w_{1},\ldots,w_{n})\log m(w_{1},\ldots,w_{n}) $$

That is, we draw sequences according to the probability distribution p, but sum the log of their probabilities according to m.

Again, following the Shannon-McMillan-Breiman theorem, for a stationary ergodic process:

$$ H(p,m)=\lim_{n\to\infty}-\frac{1}{n}\log m(w_{1}w_{2}\ldots w_{n}) $$

This means that, as for entropy, we can estimate the cross-entropy of a model m on some distribution p by taking a single sequence that is long enough instead of summing over all possible sequences.

What makes the cross entropy useful is that the cross entropy $ H(p,m) $ is an upper bound on the entropy $ H(p) $. For any model m:

$$ H(p)\leq H(p,m) $$

This means that we can use some simplified model $m$ to help estimate the true entropy of a sequence of symbols drawn according to probability $p$. The more accurate $m$ is, the closer the cross entropy $H(p,m)$ will be to the true entropy $H(p)$. Thus the difference between $H(p,m)$ and $H(p)$ is a measure of how accurate a model is. Between two models $m_1$ and $m_2$, the more accurate model will be the one with the lower cross-entropy. (The cross-entropy can never be lower than the true entropy, so a model cannot err by underestimating the true entropy).

We are finally ready to see the relation between perplexity and cross-entropy as we saw it in Equation (4.62). Cross-entropy is defined in the limit, as the length of the observed word sequence goes to infinity. We will need an approximation to cross-entropy, relying on a (sufficiently long) sequence of fixed length. This approximation to the cross-entropy of a model $ M = P(w_i|w_{i-N+1}...w_{i-1}) $ on a sequence of words $ W $ is:

$$ H(W)=-\frac{1}{N}\log P(w_{1}w_{2}\ldots w_{N}) $$

The perplexity of a model P on a sequence of words W is now formally defined as the exp of this cross-entropy:

$$ \begin{align*}Perplexity(W)&=2^{H(W)}\\&=P(w_{1}w_{2}\ldots w_{N})^{-\frac{1}{N}}\\&=\sqrt[N]{\frac{1}{P(w_{1}w_{2}\ldots w_{N})}}\\&=\sqrt[N]{\prod_{i=1}^{N}\frac{1}{P(w_{i}|w_{1}\ldots w_{i-1})}}\end{align*} $$

4.11 ADVANCED: THE ENTROPY OF ENGLISH AND ENTROPY RATE CONSTANCY

As we suggested in the previous section, the cross-entropy of some model m can be used as an upper bound on the true entropy of some process. We can use this method to get an estimate of the true entropy of English. Why should we care about the entropy of English?

One reason is that the true entropy of English would give us a solid lower bound for all of our future experiments on probabilistic grammars. Another is that we can use the entropy values for English to help understand what parts of a language provide the most information (for example, is the predictability of English mainly based on word order, on semantics, on morphology, on constituency, or on pragmatic cues?). This can help us immensely in knowing where to focus our language-modeling efforts.

There are two common methods for computing the entropy of English. The first was employed by Shannon (1951), as part of his groundbreaking work in defining the field of information theory. His idea was to use human subjects, and to construct a psychological experiment that requires them to guess strings of letters. By looking at how many guesses it takes them to guess letters correctly we can estimate the probability of the letters, and hence the entropy of the sequence.

The actual experiment is designed as follows: we present a subject with some English text and ask the subject to guess the next letter. The subjects will use their knowledge of the language to guess the most probable letter first, the next most probable next, and so on. We record the number of guesses it takes for the subject to guess correctly. Shannon's insight was that the entropy of the number-of-guesses sequence is the same as the entropy of English. (The intuition is that given the number-of-guesses sequence, we could reconstruct the original text by choosing the "nth most probable" letter whenever the subject took n guesses). This methodology requires the use of letter guesses rather than word guesses (since the subject sometimes has to do an exhaustive search of all the possible letters!), so Shannon computed the per-letter entropy of English rather than the per-word entropy. He reported an entropy of 1.3 bits (for 27 characters (26 letters plus space)). Shannon's estimate is likely to be too low, since it is based on a single text (Jefferson the Virginian by Dumas Malone). Shannon notes that his subjects had worse guesses (hence higher entropies) on other texts (newspaper writing, scientific work, and poetry). More recent variations on the Shannon experiments include the use of a gambling paradigm where the subjects get to bet on the next letter (Cover and King, 1978; Cover and Thomas, 1991).

The second method for computing the entropy of English helps avoid the single-text problem that confounds Shannon's results. This method is to take a very good stochastic model, train it on a very large corpus, and use it to assign a log-probability to a very long sequence of English, using the Shannon-McMillan-Breiman theorem:

$$ H(English)\leq\lim_{n\to\infty}-\frac{1}{n}\log m(w_{1}w_{2}\ldots w_{n}) $$

For example, Brown et al. (1992a) trained a trigram language model on 583 million words of English (293,181 different types) and used it to compute the probability of

the entire Brown corpus (1,014,312 tokens). The training data include newspapers, encyclopedias, novels, office correspondence, proceedings of the Canadian parliament, and other miscellaneous sources.

They then computed the character entropy of the Brown corpus by using their word-trigram grammar to assign probabilities to the Brown corpus, considered as a sequence of individual letters. They obtained an entropy of 1.75 bits per character (where the set of characters included all the 95 printable ASCII characters).

The average length of English written words (including space) has been reported at 5.5 letters (Nádas, 1984). If this is correct, it means that the Shannon estimate of 1.3 bits per letter corresponds to a per-word perplexity of 142 for general English. The numbers we report earlier for the WSJ experiments are significantly lower than this, since the training and test set came from the same subsample of English. That is, those experiments underestimate the complexity of English (since the Wall Street Journal looks very little like Shakespeare, for example).

A number of scholars have independently made the intriguing suggestion that entropy rate plays a role in human communication in general (Lindblom, 1990; Van Son et al., 1998; Aylett, 1999; Genzel and Charniak, 2002; Van Son and Pols, 2003). The idea is that people speak so as to keep the rate of information being transmitted per second roughly constant, i.e., transmitting a constant number of bits per second, or maintaining a constant entropy rate. Since the most efficient way of transmitting information through a channel is at a constant rate, language may even have evolved for such communicative efficiency (Plotkin and Nowak, 2000). There is a wide variety of evidence for the constant entropy rate hypothesis. One class of evidence, for speech, shows that speakers shorten predictable words (i.e., they take less time to say predictable words) and lengthen unpredictable words (Aylett, 1999; Jurafsky et al., 2001; Aylett and Turk, 2004). In another line of research, Genzel and Charniak (2002, 2003) show that entropy rate constancy makes predictions about the entropy of individual sentences from a text. In particular, they show that it predicts that local measures of sentence entropy which ignore previous discourse context (for example the N-gram probability of sentence), should increase with the sentence number, and they document this increase in corpora. Keller (2004) provides evidence that entropy rate plays a role for the addressee as well, showing a correlation between the entropy of a sentence and the processing effort it causes in comprehension, as measured by reading times in eye-tracking data.

BIBLIOGRAPHICAL AND HISTORICAL NOTES

The underlying mathematics of the N-gram was first proposed by Markov (1913), who used what are now called Markov chains (bigrams and trigrams) to predict whether an upcoming letter in Pushkin's Eugene Onegin would be a vowel or a consonant. Markov classified 20,000 letters as V or C and computed the bigram and trigram probability that a given letter would be a vowel given the previous one or two letters. Shannon (1948) applied N-grams to compute approximations to English word sequences. Based on Shannon's work, Markov models were commonly used in engineering, linguistic, and

psychological work on modeling word sequences by the 1950s.

In a series of extremely influential papers starting with Chomsky (1956) and including Chomsky (1957) and Miller and Chomsky (1963), Noam Chomsky argued that “finite-state Markov processes”, while a possibly useful engineering heuristic, were incapable of being a complete cognitive model of human grammatical knowledge. These arguments led many linguists and computational linguists to ignore work in statistical modeling for decades.

The resurgence of N-gram models came from Jelinek, Mercer, Bahl, and colleagues at the IBM Thomas J. Watson Research Center, who were influenced by Shannon, and Baker at CMU, who was influenced by the work of Baum and colleagues. Independently these two labs successfully used N-grams in their speech recognition systems (Baker, 1990; Jelinek, 1976; Baker, 1975; Bahl et al., 1983; Jelinek, 1990). A trigram model was used in the IBM TANGORA speech recognition system in the 1970s, but the idea was not written up until later.

Add-one smoothing derives from Laplace's 1812 law of succession, and was first applied as an engineering solution to the zero-frequency problem by Jeffreys (1948) based on an earlier Add-K suggestion by Johnson (1932). Problems with the Add-one algorithm are summarized in Gale and Church (1994). The Good-Turing algorithm was first applied to the smoothing of N-gram grammars at IBM by Katz, as cited in Nádas (1984). Church and Gale (1991) give a good description of the Good-Turing method, as well as the proof. Sampson (1996) also has a useful discussion of Good-Turing. Jelinek (1990) summarizes this and many other early language model innovations used in the IBM language models.

A wide variety of different language modeling and smoothing techniques were tested through the 1980's and 1990's, including Witten-Bell discounting (Witten and Bell, 1991), varieties of class-based models (Jelinek, 1990; Kneser and Ney, 1993; Heeman, 1999; Samuelsson and Reichl, 1999), and others (Gupta et al., 1992). In the late 1990's, Chen and Goodman produced a very influential series of papers with a comparison of different language models (Chen and Goodman, 1996, 1998, 1999; Goodman, 2006). They performed a number of carefully controlled experiments comparing different discounting algorithms, cache models, class-based (cluster) models, and other language model parameters. They showed the advantages of Interpolated Kneser-Ney, which has since become one of the most popular current methods for language modeling. These papers influenced our discussion in this chapter, and are recommended reading if you have further interest in language modeling.

As we suggested earlier in the chapter, recent research in language modeling has focused on adaptation, on the use of sophisticated linguistic structures based on syntactic and dialogue structure, and on very large N-grams. For example in 2006, Google publicly released a very large set of N-grams that is a useful research resource, consisting of all the five-word sequences that appear at least 40 times from 1,024,908,267,229 words of running text; there are 1,176,470,663 five-word sequences using over 13 million unique words types (Franz and Brants, 2006). Large language models generally need to be pruned to be practical, using techniques such as Stolcke (1998) and Church et al. (2007).

4.12 SUMMARY

This chapter introduced the N-gram, one of the oldest and most broadly useful practical tools in language processing.

An N-gram probability is the conditional probability of a word given the previous N-1 words. N-gram probabilities can be computed by simply counting in a corpus and normalizing (the Maximum Likelihood Estimate) or they can be computed by more sophisticated algorithms. The advantage of N-grams is that they take advantage of lots of rich lexical knowledge. A disadvantage for some purposes is that they are very dependent on the corpus they were trained on.

• Smoothing algorithms provide a better way of estimating the probability of N-grams than Maximum Likelihood Estimation. Commonly used N-gram smoothing algorithms rely on lower-order N-gram counts via backoff or interpolation.

Both backoff and interpolation require discounting such as Kneser-Ney, Witten-Bell or Good-Turing discounting.

• N-gram language models are evaluated by separating the corpus into a training set and a test set, training the model on the training set, and evaluating on the test set. The perplexity $ 2^{H} $ of the language model on a test set is used to compare language models.

EXERCISES

4.1 Write out the equation for trigram probability estimation (modifying Eq. 4.14).

4.2 Write a program to compute unsmoothed unigrams and bigrams.

4.3 Run your N-gram program on two different small corpora of your choice (you might use email text or newsgroups). Now compare the statistics of the two corpora. What are the differences in the most common unigrams between the two? How about interesting differences in bigrams?

4.4 Add an option to your program to generate random sentences.

4.5 Add an option to your program to do Good-Turing discounting.

4.6 Add an option to your program to implement Katz backoff.

4.7 Add an option to your program to compute the perplexity of a test set.

4.8 (Adapted from Michael Collins). Prove Equation (4.27) given Equation (4.26) and any necessary assumptions. That is, show that given a probability distribution

defined by the GT formula in Equation (4.26) for the $N$ items seen in training, that the probability of the next, (i.e. $N+1$st) item being unseen in training can be estimated by Equation (4.27). You may make any necessary assumptions for the proof, including assuming that all $N_c$ are non-zero.

4.9 (Advanced) Suppose someone took all the words in a sentence and reordered them randomly. Write a program which take as input such a bag of words and produces as output a guess at the original order. You will need to an N-gram grammar produced by your N-gram program (on some corpus), and you will need to use the Viterbi algorithm introduced in the next chapter. This task is sometimes called bag generation.

4.10 The field of authorship attribution is concerned with discovering the author of a particular text. Authorship attribution is important in many fields, including history, literature, and forensic linguistics. For example Mosteller and Wallace (1964) applied authorship identification techniques to discover who wrote The Federalist papers. The Federalist papers were written in 1787-1788 by Alexander Hamilton, John Jay and James Madison to persuade New York to ratify the United States Constitution. They were published anonymously, and as a result, although some of the 85 essays were clearly attributable to one author or another, the authorship of 12 were in dispute between Hamilton and Madison. Foster (1989) applied authorship identification techniques to suggest that W.S.'s Funeral Elegy for William Peter might have been written by William Shakespeare (he turned out to be wrong on this one), and that the anonymous author of Primary Colors, the roman à clef about the Clinton campaign for the American presidency, was journalist Joe Klein (Foster, 1996).

A standard technique for authorship attribution, first used by Mosteller and Wallace, is a Bayesian approach. For example, they trained a probabilistic model of the writing of Hamilton and another model on the writings of Madison, then computed the maximum-likelihood author for each of the disputed essays. There are many complex factors that go into these models, including vocabulary use, word length, syllable structure, rhyme, grammar; see Holmes (1994) for a summary. This approach can also be used for identifying which genre a text comes from.

One factor in many models is the use of rare words. As a simple approximation to this one factor, apply the Bayesian method to the attribution of any particular text. You will need three things: a text to test and two potential authors or genres, with a large on-line text sample of each. One of them should be the correct author. Train a unigram language model on each of the candidate authors. You are only going to use the \textbf{singleton} unigrams in each language model. You will compute $ P(T|A_1) $, the probability of the text given author or genre $ A_1 $, by (1) taking the language model from $ A_1 $, (2) by multiplying together the probabilities of all the unigrams that only occur once in the “unknown” text and (3) taking the geometric mean of these (i.e., the nth root, where n is the number of probabilities you multiplied). Do the same for $ A_2 $. Choose whichever is higher. Did it produce the correct candidate?

Algoet, P. H. and Cover, T. M. (1988). A sandwich proof of the Shannon-McMillan-Breiman theorem. The Annals of Probability, 16(2), 899–909.

Aylett, M. P. (1999). Stochastic suprasegmentals - relationships between redundancy, prosodic structure and syllable duration. In Proceedings of the International Congress of Phonetic Sciences (ICPhS-99), San Francisco, California.

Aylett, M. P. and Turk, A. (2004). The smooth signal redundancy hypothesis: A functional explanation for relationships between redundancy, prosodic prominence, and duration in spontaneous speech. Language and Speech, 47(1), 31–56.

Bacchiani, M. and Roark, B. (2003). Unsupervised language model adaptation. In IEEE ICASSP-03, pp. 224–227.

Bacchiani, M., Roark, B., and Saraclar, M. (2004). Language model adaptation with MAP estimation and the perceptron algorithm. In HLT-NAACL-04, pp. 21–24.

Bahl, L. R., Jelinek, F., and Mercer, R. L. (1983). A maximum likelihood approach to continuous speech recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 5(2), 179–190.

Baker, J. K. (1975). The DRAGON system – An overview. IEEE Transactions on Acoustics, Speech, and Signal Processing, ASSP-23(1), 24–29.

Baker, J. K. (1975/1990). Stochastic modeling for automatic speech understanding. In Waibel, A. and Lee, K.-F. (Eds.), Readings in Speech Recognition, pp. 297–307. Morgan Kaufmann, Los Altos. Originally appeared in Speech Recognition, Academic Press, 1975.

Bates, R. (1997). The corrections officer: Can John Kidd save Ulysses. Lingua Franca, 7(8). October.

Baum, L. E. (1972). An inequality and associated maximization technique in statistical estimation for probabilistic functions of Markov processes. In Shisha, O. (Ed.), Inequalities III: Proceedings of the Third Symposium on Inequalities, University of California, Los Angeles, pp. 1–8. Academic Press.

Bellegarda, J. R. (2000). Exploiting latent semantic information in statistical language modeling. Proceedings of the IEEE, 89(8), 1279–1296.

Bellegarda, J. R. (1999). Speech recognition experiments using multi-span statistical language models. In IEEE ICASSP-99, pp. 717–720.

Berger, A. and Miller, R. (1998). Just-in-time language modeling. In IEEE ICASSP-98, Vol. II, pp. 705–708.

Brown, P. F., Della Pietra, S. A., Della Pietra, V. J., Lai, J. C., and Mercer, R. L. (1992a). An estimate of an upper bound for the entropy of English. Computational Linguistics, 18(1), 31–40.

Brown, P. F., Della Pietra, V. J., de Souza, P. V., Lai, J. C., and Mercer, R. L. (1992b). Class-based n-gram models of natural language. Computational Linguistics, 18(4), 467–479.

Bulyko, I., Ostendorf, M., and Stolcke, A. (2003). Getting more mileage from web text sources for conversational speech language modeling using class-dependent mixtures. In HL-TNAACL-03, Edmonton, Canada, Vol. 2, pp. 7–9.

Chen, S. F. and Goodman, J. (1996). An empirical study of smoothing techniques for language modeling. In ACL-96, Santa Cruz, CA, pp. 310–318.

Chen, S. F. and Goodman, J. (1998). An empirical study of smoothing techniques for language modeling. Tech. rep. TR-10-98, Computer Science Group, Harvard University.

Chen, S. F. and Goodman, J. (1999). An empirical study of smoothing techniques for language modeling. Computer Speech and Language, 13(359–394).

Chen, S. F., Seymore, K., and Rosenfeld, R. (1998). Topic adaptation for language modeling using unnormalized exponential models. In IEEE ICASSP-98, pp. 681–684. IEEE.

Chomsky, N. (1956). Three models for the description of language. IRE Transactions on Information Theory, 2(3), 113–124.

Chomsky, N. (1957). Syntactic Structures. Mouton, The Hague.

Chomsky, N. (1969). Quine's empirical assumptions. In Davidson, D. and Hintikka, J. (Eds.), Words and objections. Essays on the work of W. V. Quine, pp. 53–68. D. Reidel, Dordrecht.

Church, K., Hart, T., and Gao, J. (2007). Compressing trigram language models with Golomb coding. In EMNLP/CoNLL 2007, pp. 199–207.

Church, K. W. and Gale, W. A. (1991). A comparison of the enhanced Good-Turing and deleted estimation methods for estimating probabilities of English bigrams. Computer Speech and Language, 5, 19–54.

Church, K. W., Gale, W. A., and Kruskal, J. B. (1991). Appendix A: the Good-Turing theorem. In Computer Speech and Language (Church and Gale, 1991), pp. 19–54.

Clark, H. H. and Fox Tree, J. E. (2002). Using uh and um in spontaneous speaking. Cognition, 84, 73–111.

Clarkson, P. R. and Rosenfeld, R. (1997). Statistical language modeling using the CMU-Cambridge toolkit. In EUROSPEECH-97, Vol. 1, pp. 2707–2710.

Coccaro, N. and Jurafsky, D. (1998). Towards better integration of semantic predictors in statistical language modeling. In ICSLP-98, Sydney, Vol. 6, pp. 2403–2406.

Cover, T. M. and King, R. C. (1978). A convergent gambling estimate of the entropy of English. IEEE Transactions on Information Theory, 24(4), 413–421.

Cover, T. M. and Thomas, J. A. (1991). Elements of information theory. Wiley.

Demetriou, G., Atwell, E., and Souter, C. (1997). Large-scale lexical semantics for speech recognition support. In EUROSPEECH-97, pp. 2755–2758.

Dempster, A. P., Laird, N. M., and Rubin, D. B. (1977). Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society, 39(1), 1–21.

Foster, D. W. (1989). Elegy by W.S.: A Study in Attribution. Associated University Presses, Cranbury, NJ.

Foster, D. W. (1996). Primary culprit. New York, 29(8), 50–57. February 26.

Francis, W. N. (1979). A tagged corpus – problems and prospects. In Greenbaum, S., Leech, G., and Svartvik, J. (Eds.), Studies in English linguistics for Randolph Quirk, pp. 192–209. Longman.

Francis, W. N. and Kučera, H. (1982). Frequency Analysis of English Usage. Houghton Mifflin, Boston.

Franz, A. and Brants, T. (2006). All our n-gram are belong to you. http://googleresearch.blogspot.com/2006/08/all-our-n-gram-are-belong-to-you.html.

Gale, W. A. and Church, K. W. (1990). Estimation procedures for language context: poor estimates are worse than none. In COMPSTAT: Proceedings in Computational Statistics, pp. 69–74.

Gale, W. A. and Church, K. W. (1994). What is wrong with adding one?. In Oostdijk, N. and de Haan, P. (Eds.), Corpus-based Research into Language, pp. 189–198. Rodopi, Amsterdam.

Gale, W. A. and Sampson, G. (1995). Good-turing frequency estimation without tears. Journal of Quantitative Linguistics, 2, 217–237.

Genzel, D. and Charniak, E. (2002). Entropy rate constancy in text. In ACL-02.

Genzel, D. and Charniak, E. (2003). Variation of entropy and parse trees of sentences as a function of the sentence number. In EMNLP 2003.

Gildea, D. and Hofmann, T. (1999). Topic-based language models using EM. In EUROSPEECH-99, Budapest, pp. 2167–2170. http://www.cis.upenn.edu/dg-ildea/gildea_hofmann_99.ps.

Godfrey, J., Holliman, E., and McDaniel, J. (1992). SWITCHBOARD: Telephone speech corpus for research and development. In IEEE ICASSP-92, San Francisco, pp. 517–520. IEEE.

Good, I. J. (1953). The population frequencies of species and the estimation of population parameters. Biometrika, 40, 16–264.

Goodman, J. (2006). A bit of progress in language modeling: Extended version. Tech. rep. MSR-TR-2001-72, Machine Learning and Applied Statistics Group, Microsoft Research, Redmond, WA.

Gupta, V., Lennig, M., and Mermelstein, P. (1992). A language model for very large-vocabulary speech recognition. Computer Speech and Language, 6, 331–344.

Heeman, P. A. (1999). POS tags and decision trees for language modeling. In EMNLP/VLC-99, College Park, MD, pp. 129–137.

Holmes, D. I. (1994). Authorship attribution. Computers and the Humanities, 28, 87–106.

Iyer, R. M. and Ostendorf, M. (1999a). Modeling long distance dependencies in language: Topic mixtures versus dynamic cache model. IEEE Transactions on Speech and Audio Processing, 7.

Iyer, R. M. and Ostendorf, M. (1999b). Relevance weighting for combining multi-domain data for n-gram language modeling. Computer Speech and Language, 13(3), 267–282.

Iyer, R. M. and Ostendorf, M. (1997). Transforming out-of-domain estimates to improve in-domain language models. In EUROSPEECH-97, pp. 1975–1978.

Jeffreys, H. (1948). Theory of Probability. Clarendon Press, Oxford. 2nd edn Section 3.23.

Jelinek, F. (1976). Continuous speech recognition by statistical methods. Proceedings of the IEEE, 64(4), 532–557.

Jelinek, F. (1988). Address to the first workshop on the evaluation of natural language processing systems. December 7, 1988.

Jelinek, F. (1990). Self-organized language modeling for speech recognition. In Waibel, A. and Lee, K.-F. (Eds.), Readings in Speech Recognition, pp. 450–506. Morgan Kaufmann, Los Altos. Originally distributed as IBM technical report in 1985.

Jelinek, F. and Mercer, R. L. (1980). Interpolated estimation of Markov source parameters from sparse data. In Gelsema, E. S. and Kanal, L. N. (Eds.), Proceedings, Workshop on Pattern Recognition in Practice, pp. 381–397. North Holland, Amsterdam.

Johnson, W. E. (1932). Probability: deductive and inductive problems (appendix to). Mind, 41(164), 421–423.

Jurafsky, D., Bell, A., Gregory, M. L., and Raymond, W. D. (2001). Probabilistic relations between words: Evidence from reduction in lexical production. In Bybee, J. L. and Hopper, P. (Eds.), Frequency and the Emergence of Linguistic Structure, pp. 229–254. Benjamins, Amsterdam.

Jurafsky, D., Wooters, C., Tajchman, G., Segal, J., Stolcke, A., Fosler, E., and Morgan, N. (1994). The Berkeley restaurant project. In ICSLP-94, Yokohama, Japan, pp. 2139–2142.

Katz, S. M. (1987). Estimation of probabilities from sparse data for the language model component of a speech recogniser. IEEE Transactions on Acoustics, Speech, and Signal Processing, 35(3), 400–401.

Keller, F. (2004). The entropy rate principle as a predictor of processing effort: An evaluation against eye-tracking data. In EMNLP 2004, Barcelona, pp. 317–324.

Keller, F. and Lapata, M. (2003). Using the web to obtain frequencies for unseen bigrams. Computational Linguistics, 29, 459–484.

Kneser, R. (1996). Statistical language modeling using a variable context length. In ICSLP-96, Philadelphia, PA, Vol. 1, pp. 494–497.

Kneser, R. and Ney, H. (1993). Improved clustering techniques for class-based statistical language modelling. In EUROSPEECH-93, pp. 973–976.

Kneser, R. and Ney, H. (1995). Improved backing-off for m-gram language modeling. In IEEE ICASSP-95, Vol. 1, pp. 181–184.

Kuhn, R. and De Mori, R. (1990). A cache-based natural language model for speech recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 12(6), 570–583.

Kukich, K. (1992). Techniques for automatically correcting words in text. ACM Computing Surveys, 24(4), 377–439.

Kučera, H. (1992). The mathematics of language. In The American Heritage Dictionary of the English Language, pp. xxxiii. Houghton Mifflin, Boston.

Küçera, H. and Francis, W. N. (1967). Computational analysis of present-day American English. Brown University Press, Providence, RI.

LDC (1993). LDC Catalog: CSR-I (WSJ0) Complete. University of Pennsylvania. www.ldc.upenn.edu/Catalog/LDC93S6A.html.

Leech, G., Garside, R., and Bryant, M. (1994). CLAWS4: The tagging of the British National Corpus. In COLING-94, Kyoto, pp. 622–628.

Lidstone, G. J. (1920). Note on the general case of the Bayes-Laplace formula for inductive or a posteriori probabilities. Transactions of the Faculty of Actuaries, 8, 182–192.

Lindblom, B. E. F. (1990). Explaining phonetic variation: A sketch of the H&H theory. In Hardcastle, W. J. and Marchal, A. (Eds.), Speech Production and Speech Modelling, pp. 403–439. Kluwer.

Markov, A. A. (1913). Essai d'une recherche statistique sur le texte du roman "Eugene Onegin" illustrant la liaison des epreuve en chain ('Example of a statistical investigation of the text of "Eugene Onegin" illustrating the dependence between samples in chain'). Izvistia Imperatorskoi Akademii Nauk (Bulletin de l'Académie Impériale des Sciences de St.-Pétersbourg), 7, 153–162. English translation by Morris Halle, 1956.

Miller, G. A. and Chomsky, N. (1963). Finitary models of language users. In Luce, R. D., Bush, R. R., and Galanter, E. (Eds.), Handbook of Mathematical Psychology, Vol. II, pp. 419–491. John Wiley.

Miller, G. A. and Selfridge, J. A. (1950). Verbal context and the recall of meaningful material. American Journal of Psychology, 63, 176–185.

Mosteller, F. and Wallace, D. L. (1964). Inference and Disputed Authorship: The Federalist. Springer-Verlag. A second edition appeared in 1984 as Applied Bayesian and Classical Inference.

Nádas, A. (1984). Estimation of probabilities in the language model of the IBM speech recognition system. IEEE Transactions on Acoustics, Speech, Signal Processing, 32(4), 859–861.

Nakov, P. I. and Hearst, M. A. (2005). A study of using search engine page hits as a proxy for n-gram frequencies. In Proceedings of RANLP-05 (Recent Advances in Natural Language Processing), Borovets, Bulgaria.

Newell, A., Langer, S., and Hickey, M. (1998). The rôle of natural language processing in alternative and augmentative communication. Natural Language Engineering, 4(1), 1–16.

Ney, H., Essen, U., and Kneser, R. (1994). On structuring probabilistic dependencies in stochastic language modelling. Computer Speech and Language, 8, 1–38.

Niesler, T. R., Whittaker, E. W. D., and Woodland, P. C. (1998). Comparison of part-of-speech and automatically derived category-based language models for speech recognition. In IEEE ICASSP-98, Vol. 1, pp. 177–180.

Niesler, T. R. and Woodland, P. C. (1996). A variable-length category-based n-gram language model. In IEEE ICASSP-96, Atlanta, GA, Vol. I, pp. 164–167. IEEE.

Niesler, T. R. and Woodland, P. C. (1999). Modelling word-pair relations in a category-based language model. In IEEE ICASSP-99, pp. 795–798. IEEE.

Palmer, M. and Finin, T. (1990). Workshop on the evaluation of natural language processing systems. Computational Linguistics, 16(3), 175–181.

Plotkin, J. B. and Nowak, M. A. (2000). Language evolution and information theory. Journal of Theoretical Biology, 205(1), 147–159.

Rosenfeld, R. (1996). A maximum entropy approach to adaptive statistical language modeling. Computer Speech and Language, 10, 187–228.

Russell, S. and Norvig, P. (2002). Artificial Intelligence: A Modern Approach. Prentice Hall. Second edition.

Sampson, G. (1996). Evolutionary Language Understanding. Cassell, London.

Samuelsson, C. and Reichl, W. (1999). A class-based language model for large-vocabulary speech recognition extracted from part-of-speech statistics. In IEEE ICASSP-99, pp. 537–540. IEEE.

Shannon, C. E. (1948). A mathematical theory of communication. Bell System Technical Journal, 27(3), 379–423. Continued in the following volume.

Shannon, C. E. (1951). Prediction and entropy of printed English. Bell System Technical Journal, 30, 50–64.

Sparck Jones, K. and Galliers, J. R. (Eds.). (1996). Evaluating Natural Language Processing Systems. Springer.

Stolcke, A. (1998). Entropy-based pruning of backoff language models. In Proc. DARPA Broadcast News Transcription and Understanding Workshop, Lansdowne, VA, pp. 270–274.

Stolcke, A. (2002). Srilm - an extensible language modeling toolkit. In ICSLP-02, Denver, CO.

Stolcke, A. and Shriberg, E. (1996). Statistical language modeling for speech disfluencies. In IEEE ICASSP-96, Atlanta, GA, Vol. 1, pp. 405–408. IEEE.

Van Son, R. J. J. H., Koopmans-van Beinum, F. J., and Pols, L. C. W. (1998). Efficiency as an organizing principle of natural speech. In ICSLP-98, Sydney.

Van Son, R. J. J. H. and Pols, L. C. W. (2003). How efficient is speech?. Proceedings of the Institute of Phonetic Sciences, 25, 171–184.

Witten, I. H. and Bell, T. C. (1991). The zero-frequency problem: Estimating the probabilities of novel events in adaptive text compression. IEEE Transactions on Information Theory, 37(4), 1085–1094.

Zhou, G. and Lua, K. (1998). Word association and MI-trigger-based language modelling. In COLING/ACL-98, Montreal, Canada, pp. 1465–1471.

Zhu, X. and Rosenfeld, R. (2001). Improving trigram language modeling with the world wide web. In IEEE ICASSP-01, Salt Lake City, UT, Vol. I, pp. 533–536.

5

WORD CLASSES AND PART-OF-SPEECH TAGGING

Conjunction Junction, what's your function?

Bob Dorough, Schoolhouse Rock, 1973

A gnostic was seated before a grammarian. The grammarian said, 'A word must be one of three things: either it is a noun, a verb, or a particle.' The gnostic tore his robe and cried, "Alas! Twenty years of my life and striving and seeking have gone to the winds, for I laboured greatly in the hope that there was another word outside of this. Now you have destroyed my hope.' Though the gnostic had already attained the word which was his purpose, he spoke thus in order to arouse the grammarian.

Rumi (1207–1273), The Discourses of Rumi, Translated by A. J. Arberry

Dionysius Thrax of Alexandria (c. 100 B.C.), or perhaps someone else (exact authorship being understandably difficult to be sure of with texts of this vintage), wrote a grammatical sketch of Greek (a “technē”) which summarized the linguistic knowledge of his day. This work is the direct source of an astonishing proportion of our modern linguistic vocabulary, including among many other words, syntax, diphthong, clitic, and analogy. Also included are a description of eight parts-of-speech: noun, verb, pronoun, preposition, adverb, conjunction, participle, and article. Although earlier scholars (including Aristotle as well as the Stoics) had their own lists of parts-of-speech, it was Thrax’s set of eight which became the basis for practically all subsequent part-of-speech descriptions of Greek, Latin, and most European languages for the next 2000 years.

Schoolhouse Rock was a popular series of 3-minute musical animated clips first aired on television in 1973. The series was designed to inspire kids to learn multiplication tables, grammar, and basic science and history. The Grammar Rock sequence, for example, included songs about parts-of-speech, thus bringing these categories into the realm of popular culture. As it happens, Grammar Rock was remarkably traditional in its grammatical notation, including exactly eight songs about parts-of-speech.

Although the list was slightly modified from Thrax's original, substituting adjective and interjection for the original participle and article, the astonishing durability of the parts-of-speech through two millennia is an indicator of both the importance and the transparency of their role in human language.

More recent lists of parts-of-speech (or $ \text{tagsets} $) have many more word classes; 45 for the Penn Treebank (Marcus et al., 1993), 87 for the Brown corpus (Francis, 1979; Francis and Kučera, 1982), and 146 for the C7 tagset (Garside et al., 1997).

The significance of parts-of-speech (also known as POS, word classes, morphological classes, or lexical tags) for language processing is the large amount of information they give about a word and its neighbors. This is clearly true for major categories, (verb versus noun), but is also true for the many finer distinctions. For example these tagsets distinguish between possessive pronouns (my, your, his, her, its) and personal pronouns (I, you, he, me). Knowing whether a word is a possessive pronoun or a personal pronoun can tell us what words are likely to occur in its vicinity (possessive pronouns are likely to be followed by a noun, personal pronouns by a verb). This can be useful in a language model for speech recognition.

A word's part-of-speech can tell us something about how the word is pronounced. As Ch. 8 will discuss, the word content, for example, can be a noun or an adjective. They are pronounced differently (the noun is pronounced CONtent and the adjective conTENT). Thus knowing the part-of-speech can produce more natural pronunciations in a speech synthesis system and more accuracy in a speech recognition system. (Other pairs like this include Object (noun) and object (verb), Discount (noun) and discount (verb); see Cutler (1986)).

Parts-of-speech can also be used in stemming for informational retrieval (IR), since knowing a word's part-of-speech can help tell us which morphological affixes it can take, as we saw in Ch. 3. They can also enhance an IR application by selecting out nouns or other important words from a document. Automatic assignment of part-of-speech plays a role in parsing, in word-sense disambiguation algorithms, and in shallow parsing of texts to quickly find names, times, dates, or other named entities for the information extraction applications discussed in Ch. 22. Finally, corpora that have been marked for parts-of-speech are very useful for linguistic research. For example, they can be used to help find instances or frequencies of particular constructions.

This chapter focuses on computational methods for assigning parts-of-speech to words (part-of-speech tagging). Many algorithms have been applied to this problem, including hand-written rules (rule-based tagging), probabilistic methods (HMM tagging and maximum entropy tagging), as well as other methods such as transformation-based tagging and memory-based tagging. We will introduce three of these algorithms in this chapter: rule-based tagging, HMM tagging, and transformation-based tagging. But before turning to the algorithms themselves, let's begin with a summary of English word classes, and of various tagsets for formally coding these classes.

5.1 (MOSTLY) ENGLISH WORD CLASSES

Until now we have been using part-of-speech terms like noun and verb rather freely. In this section we give a more complete definition of these and other classes. Traditionally the definition of parts-of-speech has been based on syntactic and morphological function; words that function similarly with respect to what can occur nearby (their “syntactic distributional properties”), or with respect to the affixes they take (their morphological properties) are grouped into classes. While word classes do have tendencies toward semantic coherence (nouns do in fact often describe “people, places or things”, and adjectives often describe properties), this is not necessarily the case, and in general we don’t use semantic coherence as a definitional criterion for parts-of-speech.

Parts-of-speech can be divided into two broad supercategories: closed class types and open class types. Closed classes are those that have relatively fixed membership. For example, prepositions are a closed class because there is a fixed set of them in English; new prepositions are rarely coined. By contrast nouns and verbs are open classes because new nouns and verbs are continually coined or borrowed from other languages (e.g., the new verb to fax or the borrowed noun futon). It is likely that any given speaker or corpus will have different open class words, but all speakers of a language, and corpora that are large enough, will likely share the set of closed class words. Closed class words are also generally function words like of, it, and, or you, which tend to be very short, occur frequently, and often have structuring uses in grammar.

There are four major open classes that occur in the languages of the world; nouns, verbs, adjectives, and adverbs. It turns out that English has all four of these, although not every language does.

Noun is the name given to the syntactic class in which the words for most people, places, or things occur. But since syntactic classes like noun are defined syntactically and morphologically rather than semantically, some words for people, places, and things may not be nouns, and conversely some nouns may not be words for people, places, or things. Thus nouns include concrete terms like ship and chair, abstractions like bandwidth and relationship, and verb-like terms like pacing as in His pacing to and fro became quite annoying. What defines a noun in English, then, are things like its ability to occur with determiners (a goat, its bandwidth, Plato's Republic), to take possessives (IBM's annual revenue), and for most but not all nouns, to occur in the plural form (goats, abaci).

Nouns are traditionally grouped into proper nouns and common nouns. Proper nouns, like Regina, Colorado, and IBM, are names of specific persons or entities. In English, they generally aren't preceded by articles (e.g., the book is upstairs, but Regina is upstairs). In written English, proper nouns are usually capitalized.

In many languages, including English, common nouns are divided into count nouns and mass nouns. Count nouns are those that allow grammatical enumeration; that is, they can occur in both the singular and plural (goat/goats, relationship/relationships) and they can be counted (one goat, two goats). Mass nouns are used when something is conceptualized as a homogeneous group. So words like snow, salt, and communism are not counted (i.e., *two snows or *two communisms). Mass nouns can also appear without articles where singular count nouns cannot (Snow is white but not *Goat is

white).

The verb class includes most of the words referring to actions and processes, including main verbs like draw, provide, differ, and go. As we saw in Ch. 3, English verbs have a number of morphological forms (non-3rd-person-sg (eat), 3rd-person-sg (eats), progressive (eating), past participle (eaten)). A subclass of English verbs called auxiliaries will be discussed when we turn to closed class forms.

While many researchers believe that all human languages have the categories of noun and verb, others have argued that some languages, such as Riau Indonesian and Tongan, don't even make this distinction (Broschart, 1997; Evans, 2000; Gil, 2000).

The third open class English form is adjectives; semantically this class includes many terms that describe properties or qualities. Most languages have adjectives for the concepts of color (white, black), age (old, young), and value (good, bad), but there are languages without adjectives. In Korean, for example, the words corresponding to English adjectives act as a subclass of verbs, so what is in English an adjective ‘beautiful’ acts in Korean like a verb meaning ‘to be beautiful’ (Evans, 2000).

The final open class form, adverbs, is rather a hodge-podge, both semantically and formally. For example Schachter (1985) points out that in a sentence like the following, all the italicized words are adverbs:

Unfortunately, John walked home extremely slowly yesterday

What coherence the class has semantically may be solely that each of these words can be viewed as modifying something (often verbs, hence the name “adverb”, but also other adverbs and entire verb phrases). Directional adverbs or locative adverbs (home, here, downhill) specify the direction or location of some action; degree adverbs (extremely, very, somewhat) specify the extent of some action, process, or property; manner adverbs (slowly, slinkily, delicately) describe the manner of some action or process; and temporal adverb describe the time that some action or event took place (yesterday, Monday). Because of the heterogeneous nature of this class, some adverbs (for example temporal adverbs like Monday) are tagged in some tagging schemes as nouns.

The closed classes differ more from language to language than do the open classes. Here's a quick overview of some of the more important closed classes in English, with a few examples of each:

• prepositions: on, under, over, near, by, at, from, to, with

determiners: a, an, the

pronouns: she, who, I, others

conjunctions: and, but, or, as, if, when

auxiliary verbs: can, may, snould, are

• particles: up, down, on, off, in, out, at, by,

numerals: one, two, three, first, second, third

Prepositions occur before noun phrases; semantically they are relational, often indicating spatial or temporal relations, whether literal (on it, before then, by the house) or metaphorical (on time, with gusto, beside herself). But they often indicate other relations as well (Hamlet was written by Shakespeare, and [from Shakespeare] "And I did laugh $ \underline{\text{sans}} $ intermission an hour $ \underline{\text{by}} $ his dial"). Fig. 5.1 shows the prepositions of

English according to the CELEX on-line dictionary (Baayen et al., 1995), sorted by their frequency in the COBUILD 16 million word corpus of English. Fig. 5.1 should not be considered a definitive list, since different dictionaries and tagsets label word classes differently. Furthermore, this list combines prepositions and particles.

A particle is a word that resembles a preposition or an adverb, and is used in combination with a verb. When a verb and a particle behave as a single syntactic and/or semantic unit, we call the combination a phrasal verb. Phrasal verbs can behave as a semantic unit; thus they often have a meaning that is not predictable from the separate meanings of the verb and the particle. Thus turn down means something like ‘reject’, rule out means ‘eliminate’, find out is ‘discover’, and go on is ‘continue’; these are not meanings that could have been predicted from the meanings of the verb and the particle independently. Here are some examples of phrasal verbs from Thoreau:

So I went on for some days cutting and hewing timber...

Moral reform is the effort to throw off sleep...

Particles don't always occur with idiomatic phrasal verb semantics; here are more examples of particles from the Brown corpus:

...she had turned the paper over.

He arose slowly and brushed himself off.

He packed up his clothes.

We show in Fig. 5.2 a list of single-word particles from Quirk et al. (1985). Since it is extremely hard to automatically distinguish particles from prepositions, some tagsets (like the one used for CELEX) do not distinguish them, and even in corpora that do (like the Penn Treebank) the distinction is very difficult to make reliably in an automatic process, so we do not give counts.

A closed class that occurs with nouns, often marking the beginning of a noun phrase, is the determiners. One small subtype of determiners is the articles: English has three articles: a, an, and the. Other determiners include this (as in this chapter) and that (as in that page). A and an mark a noun phrase as indefinite, while the can mark it

as definite; definiteness is a discourse and semantic property that will be discussed in Ch. 21. Articles are quite frequent in English; indeed the is the most frequently occurring word in most corpora of written English. Here are COBUILD statistics, again out of 16 million words:

the: 1,071,676 a: 413,887 an: 59,359

Conjunctions are used to join two phrases, clauses, or sentences. Coordinating conjunctions like and, or, and but, join two elements of equal status. Subordinating conjunctions are used when one of the elements is of some sort of embedded status. For example that in “I thought that you might like some milk” is a subordinating conjunction that links the main clause I thought with the subordinate clause you might like some milk. This clause is called subordinate because this entire clause is the “content” of the main verb thought. Subordinating conjunctions like that which link a verb to its argument in this way are also called complementizers. Ch. 12 and Ch. 16 will discuss complementation in more detail. Table 5.3 lists English conjunctions.

Pronouns are forms that often act as a kind of shorthand for referring to some noun phrase or entity or event. Personal pronouns refer to persons or entities (you, she, I, it, me, etc.). Possessive pronouns are forms of personal pronouns that indicate

either actual possession or more often just an abstract relation between the person and some object (my, your, his, her, its, one's, our, their). Wh-pronouns (what, who, whom, whoever) are used in certain question forms, or may also act as complementizers (Frieda, who I met five years ago ...). Table 5.4 shows English pronouns, again from CELEX.

A closed class subtype of English verbs are the auxiliary verbs. Crosslinguistically, auxiliaries are words (usually verbs) that mark certain semantic features of a main verb, including whether an action takes place in the present, past or future (tense), whether it is completed (aspect), whether it is negated (polarity), and whether an action is necessary, possible, suggested, desired, etc. (mood).

English auxiliaries include the copula verb be, the two verbs do and have, along with their inflected forms, as well as a class of modal verbs. Be is called a copula because it connects subjects with certain kinds of predicate nominals and adjectives (He is a duck). The verb have is used for example to mark the perfect tenses (I have gone, I had gone), while be is used as part of the passive (We were robbed), or progressive (We are leaving) constructions. The modals are used to mark the mood associated with

the event or action depicted by the main verb. So can indicates ability or possibility, may indicates permission or possibility, must indicates necessity, and so on. Fig. 5.5 gives counts for the frequencies of the modals in English. In addition to the perfect have mentioned above, there is a modal verb have (e.g., I $ \underline{\text{have}} $ to go), which is very common in spoken English. Neither it nor the modal verb dare, which is very rare, have frequency counts because the CELEX dictionary does not distinguish the main verb sense (I $ \underline{\text{have}} $ three oranges, He $ \underline{\text{dared}} $ me to eat them), from the modal sense (There $ \underline{\text{has}} $ to be some mistake, $ \underline{\text{Dare}} $ I confront him?), from the non-modal auxiliary verb sense (I $ \underline{\text{have}} $ never seen that).

English also has many words of more or less unique function, including interjections (oh, ah, hey, man, alas, uh, um), negatives (no, not), politeness markers (please, thank you), greetings (hello, goodbye), and the existential there (there are two on the table) among others. Whether these classes are assigned particular names or lumped together (as interjections or even adverbs) depends on the purpose of the labeling.

5.2 TAGSETS FOR ENGLISH

The previous section gave broad descriptions of the kinds of syntactic classes that English words fall into. This section fleshes out that sketch by describing the actual tagsets used in part-of-speech tagging, in preparation for the various tagging algorithms to be described in the following sections.

There are a small number of popular tagsets for English, many of which evolved from the 87-tag tagset used for the Brown corpus (Francis, 1979; Francis and Kučera, 1982). The Brown corpus is a 1 million word collection of samples from 500 written texts from different genres (newspaper, novels, non-fiction, academic, etc.) which was assembled at Brown University in 1963–1964 (Kučera and Francis, 1967; Francis, 1979; Francis and Kučera, 1982). This corpus was tagged with parts-of-speech by first applying the TAGGIT program and then hand-correcting the tags.

Besides this original Brown tagset, two of the most commonly used tagsets are the small 45-tag Penn Treebank tagset (Marcus et al., 1993), and the medium-sized 61 tag C5 tagset used by the Lancaster UCREL project's CLAWS (the Constituent Likelihood Automatic Word-tagging System) tagger to tag the British National Corpus (BNC) (Garside et al., 1997). We give all three of these tagsets here, focusing on the

| Tag | Description | Example | Tag | Description | Example |

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

| CC | Coordin. Conjunction | and, but, or | SYM | Symbol | +,%, & |

| CD | Cardinal number | one, two, three | TO | “to” | to |

| DT | Determiner | a, the | UH | Interjection | ah, oops |

| EX | Existential ‘there’ | there | VB | Verb, base form | eat |

| FW | Foreign word | mea culpa | VBD | Verb, past tense | ate |

| IN | Preposition/sub-conj | of, in, by | VBG | Verb, gerund | eating |

| JJ | Adjective | yellow | VBN | Verb, past participle | eaten |

| JJR | Adj., comparative | bigger | VBP | Verb, non-3sg pres | eat |

| JJS | Adj., superlative | wildest | VBZ | Verb, 3sg pres | eats |

| LS | List item marker | 1, 2, One | WDT | Wh-determiner | which, that |

| MD | Modal | can, should | WP | Wh-pronoun | what, who |

| NN | Noun, sing. or mass | llama | WP$ | Possessive wh- | whose |

| NNS | Noun, plural | llamas | WRB | Wh-adverb | how, where |

| NNP | Proper noun, singular | IBM | $ | Dollar sign | $ |

| NNPS | Proper noun, plural | Carolinas | # | Pound sign | # |

| PDT | Predeterminer | all, both | “ | Left quote | ‘ or “ |

| POS | Possessive ending | ’s | ” | Right quote | ’ or ” |

| PRP | Personal pronoun | I, you, he | ( | Left parenthesis | [ , (, {, < |

| PRP$ | Possessive pronoun | your, one’s | ) | Right parenthesis | ], ), }, > |

| RB | Adverb | quickly, never | , | Comma | , |

| RBR | Adverb, comparative | faster | . | Sentence-final punc | . ! ? |

| RBS | Adverb, superlative | fastest | : | Mid-sentence punc | : ; ... - - |

| RP | Particle | up, off | | | |

smallest, the Penn Treebank set, and discuss difficult tagging decisions in that tag set and some useful distinctions made in the larger tagsets.

The Penn Treebank tagset, shown in Fig. 5.6, has been applied to the Brown corpus, the Wall Street Journal corpus, and the Switchboard corpus among others; indeed, perhaps partly because of its small size, it is one of the most widely used tagsets. Here are some examples of tagged sentences from the Penn Treebank version of the Brown corpus (we will represent a tagged word by placing the tag after each word, delimited by a slash):

(5.1) The/DT grand/JJ jury/NN commented/VBD on/IN a/DT number/NN of/IN other/JJ topics/NNS /.

(5.2) There/EX are/VBP 70/CD children/NNS there/RB

(5.3) Although/IN preliminary/JJ findings/NNS were/VBD reported/VBN more/RBR than/IN a/DT year/NN ago/IN /, the/DT latest/JJS results/NNS appear/VBP in/IN today/NN 's/POS New/NNP England/NNP Journal/NNP of/IN Medicine/NNP /,

Example (5.1) shows phenomena that we discussed in the previous section; the determiners the and a, the adjectives grand and other, the common nouns jury, number, and topics, the past tense verb commented. Example (5.2) shows the use of the EX tag to mark the existential there construction in English, and, for comparison, another use of there which is tagged as an adverb (RB). Example (5.3) shows the segmentation of the possessive morpheme 's, and shows an example of a passive construction,

‘were reported’, in which the verb reported is marked as a past participle (VBN), rather than a simple past (VBD). Note also that the proper noun New England is tagged NNP. Finally, note that since New England Journal of Medicine is a proper noun, the Treebank tagging chooses to mark each noun in it separately as NNP, including journal and medicine, which might otherwise be labeled as common nouns (NN).

Some tagging distinctions are quite hard for both humans and machines to make. For example prepositions (IN), particles (RP), and adverbs (RB) can have a large overlap. Words like around can be all three:

(5.4) Mrs./NNP Shaefer/NNP never/RB got/VBD around/RP to/TO joining/VBG

(5.5) All/DT we/PRP gotta/VBN do/VB is/VBZ go/VB around/IN the/DT corner/NN

(5.6) Chateau/NNP Petrus/NNP costs/VBZ around/RB 250/CD

Making these decisions requires sophisticated knowledge of syntax; tagging manuals (Santorini, 1990) give various heuristics that can help human coders make these decisions, and that can also provide useful features for automatic taggers. For example, two heuristics from Santorini (1990) are that prepositions generally are associated with a following noun phrase (although they also may be followed by prepositional phrases), and that the word around is tagged as an adverb when it means “approximately”. Furthermore, particles often can either precede or follow a noun phrase object, as in the following examples:

(5.7) She told off/RP her friends

(5.8) She told her friends off/RP.

Prepositions, on the other hand, cannot follow their noun phrase (* is used here to mark an ungrammatical sentence, a concept which we will return to in Ch. 12):

(5.9) She stepped off/IN the train

(5.10) *She stepped the train off/IN.

Another difficulty is labeling the words that can modify nouns. Sometimes the modifiers preceding nouns are common nouns like cotton below, other times the Treebank tagging manual specifies that modifiers be tagged as adjectives (for example if the modifier is a hyphenated common noun like income-tax) and other times as proper nouns (for modifiers which are hyphenated proper nouns like Gramm-Rudman):

(5.11) cotton/NN sweater/NN

(5.12) income-tax/JJ return/NN

(5.13) the/DT Gramm-Rudman/NP Act/NP

Some words that can be adjectives, common nouns, or proper nouns, are tagged in the Treebank as common nouns when acting as modifiers:

(5.14) Chinese/NN cooking/NN

(5.15) Pacific/NN waters/NNS

A third known difficulty in tagging is distinguishing past participles (VBN) from adjectives (JJ). A word like married is a past participle when it is being used in an eventive, verbal way, as in (5.16) below, and is an adjective when it is being used to express a property, as in (5.17):

(5.16) They were married/VBN by the Justice of the Peace yesterday at 5:00.

(5.17) At the time, she was already married/JJ.

Tagging manuals like Santorini (1990) give various helpful criteria for deciding how ‘verb-like’ or ‘eventive’ a particular word is in a specific context.

The Penn Treebank tagset was culled from the original 87-tag tagset for the Brown corpus. This reduced set leaves out information that can be recovered from the identity of the lexical item. For example the original Brown and C5 tagsets include a separate tag for each of the different forms of the verbs do (e.g. C5 tag "VDD" for did and "VDG" for doing), be, and have. These were omitted from the Treebank set.

Certain syntactic distinctions were not marked in the Penn Treebank tagset because Treebank sentences were parsed, not merely tagged, and so some syntactic information is represented in the phrase structure. For example, the single tag IN is used for both prepositions and subordinating conjunctions since the tree-structure of the sentence disambiguates them (subordinating conjunctions always precede clauses, prepositions precede noun phrases or prepositional phrases). Most tagging situations, however, do not involve parsed corpora; for this reason the Penn Treebank set is not specific enough for many uses. The original Brown and C5 tagsets, for example, distinguish prepositions (IN) from subordinating conjunctions (CS), as in the following examples:

(5.18) after/CS spending/VBG a/AT few/AP days/NNS at/IN the/AT Brown/NP Palace/NN Hotel/NN

(5.19) after/IN a/AT wedding/NN trip/NN to/IN Corpus/NP Christi/NP ./.

The original Brown and C5 tagsets also have two tags for the word to; in Brown the infinitive use is tagged TO, while the prepositional use as IN:

(5.20) to/TO give/VB priority/NN to/IN teacher/NN pay/NN raises/NNS

Brown also has the tag NR for adverbial nouns like home, west, Monday, and tomorrow. Because the Treebank lacks this tag, it has a much less consistent policy for adverbial nouns; Monday, Tuesday, and other days of the week are marked NNP, tomorrow, west, and home are marked sometimes as NN, sometimes as RB. This makes the Treebank tagset less useful for high-level NLP tasks like the detection of time phrases.

Nonetheless, the Treebank tagset has been the most widely used in evaluating tagging algorithms, and so many of the algorithms we describe below have been evaluated mainly on this tagset. Of course whether a tagset is useful for a particular application depends on how much information the application needs.

5.3 PART-OF-SPEECH TAGGING

TAGGING Part-of-speech tagging (or just tagging for short) is the process of assigning a part-of-speech or other syntactic class marker to each word in a corpus. Because tags are generally also applied to punctuation, tagging requires that the punctuation marks (period, comma, etc) be separated off of the words. Thus tokenization of the sort described in Ch. 3 is usually performed before, or as part of, the tagging process, separating commas, quotation marks, etc., from words, and disambiguating end-of-sentence

| Tag | Description | Example |

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

| ( ) | opening parenthesis | ( , [ ) |

| $ ^{{*}} $ | closing parenthesis | not n't |

| , | negator | , |

| - | comma | - |

| - | dash | - |

| : | sentence terminator | ; ? ! |

| : | colon | : |

| ABL | pre-qualifier | quite, rather, such |

| ABN | pre-quantifier | half, all, |

| ABX | pre-quantifier, double conjunction | both |

| AP | post-determiner | many, next, several, last |

| AT | article | a the an no a every |

| BE/BED | BEDZ/BEG/BEM/BEN/BER/BEZ | be/were/was/being/am/been/are/is |

| CC | coordinating conjunction | and or but either neither |

| CD | cardinal numeral | two, 2, 1962, million |

| CS | subordinating conjunction | that as after whether before |

| DO/DOD/DOZ | do, did, does | |

| DT | singular determiner, | this, that |

| DTI | singular or plural determiner | some, any |

| DTS | plural determiner | these those them |

| DTX | determiner, double conjunction | either, neither |

| EX | existential there | there |

| HV/HVD/HVG/HVN/HVZ | have, had, having, had, has | |

| IN | preposition | of in for by to on at |

| JJ | adjective | better, greater, higher, larger, lower |

| JJR | comparative adjective | main, top, principal, chief, key, foremost |

| JJS | semantically superlative adj. | best, greatest, highest, largest, latest, worst |

| JJT | morphologically superlative adj. | would, will, can, could, may, must, should |

| MD | modal auxiliary | time, world, work, school, family, door |

| NN | (common) singular or mass noun | father's, year's, city's, earth's |

| NNS | possessive singular common noun | years, people, things, children, problems |

| NNS | plural common noun | children's, artist's parent's years' |

| NNS | possessive plural noun | Kennedy, England, Rachel, Congress |

| NP | singular proper noun | Plato's Faulkner's Viola's |

| NPS | possessive singular proper noun | Americans Democrats Belgians Chinese Sox |

| NPS | plural proper noun | Yankees's, Gershwins's Earthmen's |

| NR | possessive plural proper noun | home, west, tomorrow, Friday, North, |

| NRS | adverbial noun | today's, yesterday's, Sunday's, South's |

| NRS | possessive adverbial noun | Sundays Fridays |

| OD | plural adverbial noun | second, 2nd, twenty-first, mid-twentieth |

| PN | ordinal numeral | one, something, nothing, anyone, none, |

| PN | nominal pronoun | one's someone's anyone's |

| PNS | possessive nominal pronoun | his their her its my our your |

| PPS | possessive personal pronoun | mine, his, ours, yours, theirs |

| PPS | second possessive personal pronoun | myself, herself |

| PPL | singular reflexive personal pronoun | ourselves, themselves |

| PPLS | plural reflexive pronoun | me, us, him |

| PPO | objective personal pronoun | he, she, it |

| PPS | 3rd. sg. nominative pronoun | I, we, they |

| PSS | other nominative pronoun | very, too, most, quite, almost, extremely |

| QL | qualifier | enough, indeed |

| QLP | post-qualifier | later, more, better, longer, further |

| RB | adverb | best, most, highest, nearest |

| RBR | comparative adverb | here, then |

| RBT | superlative adverb | |

| RN | nominal adverb | |

punctuation (period, question mark, etc) from part-of-word punctuation (such as in abbreviations like e.g. and etc.)

The input to a tagging algorithm is a string of words and a specified tagset of the kind described in the previous section. The output is a single best tag for each word. For example, here are some sample sentences from the ATIS corpus of dialogues about airtravel reservations that we will discuss in Ch. 12. For each we have shown a potential tagged output using the Penn Treebank tagset defined in Fig. 5.6 on page 9:

(5.21) Book/VB that/DT flight/NN /.

5.22) Does/VBZ that/DT flight/NN serve/VB dinner/NN ?/.

The previous section discussed some tagging decisions that are difficult to make for humans. Even in these simple examples, automatically assigning a tag to each word is not trivial. For example, book is ambiguous. That is, it has more than one possible usage and part-of-speech. It can be a verb (as in $ \underline{\text{book}} $ that flight or to $ \underline{\text{book}} $ the suspect) or a noun (as in hand me that $ \underline{\text{book}} $. or a $ \underline{\text{book}} $ of matches). Similarly that can be a determiner (as in Does $ \underline{\text{that}} $ flight serve dinner), or a complementizer (as in I thought $ \underline{\text{that}} $ your flight was earlier). The problem of POS-tagging is to resolve these ambiguities, choosing the proper tag for the context. Part-of-speech tagging is thus one of the many $ \underline{\text{disambiguation}} $ tasks we will see in this book.

How hard is the tagging problem? The previous section described some difficult tagging decisions; how common is tag ambiguity? It turns out that most words in English are unambiguous; i.e., they have only a single tag. But many of the most common words of English are ambiguous (for example can be an auxiliary ('to be able'), a noun ('a metal container'), or a verb ('to put something in such a metal container'). In fact, DeRose (1988) reports that while only 11.5% of English word types in the Brown corpus are ambiguous, over 40% of Brown tokens are ambiguous. Fig. 5.10 shows the number of word types with different levels of part-of-speech ambiguity from the Brown corpus. We show these computations from two versions of the tagged Brown corpus, the original tagging done at Brown by Francis and Kučera (1982), and the Treebank-3 tagging done at the University of Pennsylvania. Note that despite having more coarse-grained tags, the 45-tag corpus unexpectedly has more ambiguity than the 87-tag corpus.

Luckily, it turns out that many of the 40% ambiguous tokens are easy to disambiguate. This is because the various tags associated with a word are not equally likely. For example, a can be a determiner, or the letter a (perhaps as part of an acronym or an

initial). But the determiner sense of a is much more likely.

Most tagging algorithms fall into one of two classes: rule-based taggers and stochastic taggers. Rule-based taggers generally involve a large database of handwritten disambiguation rules which specify, for example, that an ambiguous word is a noun rather than a verb if it follows a determiner. The next section will describe a sample rule-based tagger, EngCG, based on the Constraint Grammar architecture of Karlsson et al. (1995b).

Stochastic taggers generally resolve tagging ambiguities by using a training corpus to compute the probability of a given word having a given tag in a given context. Sec. 5.5 describes the Hidden Markov Model or HMM tagger.

Finally, Sec. 5.6 will describe an approach to tagging called the transformation-based tagger or the Brill tagger, after Brill (1995). The Brill tagger shares features of both tagging architectures. Like the rule-based tagger, it is based on rules which determine when an ambiguous word should have a given tag. Like the stochastic taggers, it has a machine-learning component: the rules are automatically induced from a previously tagged training corpus.

5.4 RULE-BASED PART-OF-SPEECH TAGGING

The earliest algorithms for automatically assigning part-of-speech were based on a two-stage architecture (Harris, 1962; Klein and Simmons, 1963; Greene and Rubin, 1971). The first stage used a dictionary to assign each word a list of potential parts-of-speech. The second stage used large lists of hand-written disambiguation rules to winnow down this list to a single part-of-speech for each word.

Modern rule-based approaches to part-of-speech tagging have a similar architecture, although the dictionaries and the rule sets are vastly larger than in the 1960's.

One of the most comprehensive rule-based approaches is the Constraint Grammar approach (Karlsson et al., 1995a). In this section we describe a tagger based on this approach, the EngCG tagger (Voutilainen, 1995, 1999).

The EngCG ENGTWOL lexicon is based on the two-level morphology described in Ch. 3, and has about 56,000 entries for English word stems (Heikkilä, 1995), counting a word with multiple parts-of-speech (e.g., nominal and verbal senses of hit) as separate entries, and not counting inflected and many derived forms. Each entry is annotated with a set of morphological and syntactic features. Fig. 5.11 shows some selected words, together with a slightly simplified listing of their features; these features are used in rule writing.

Most of the features in Fig. 5.11 are relatively self-explanatory; SG for singular, -SG3 for other than third-person-singular. ABSOLUTE means non-comparative and non-superlative for an adjective, NOMINATIVE just means non-genitive, and PCP2 means past participle. PRE, CENTRAL, and POST are ordering slots for determiners (predeterminers (all) come before determiners (the): all the president's men). NOIN-DEFDETERMINER means that words like furniture do not appear with the indefinite determiner a. SV, SVO, and SVOO specify the subcategorization or complementation pattern for the verb. Subcategorization will be discussed in Ch. 12 and Ch. 16, but briefly SV means the verb appears solely with a subject (nothing occurred); SVO with a subject and an object (I showed the film); SVOO with a subject and two complements: She showed her the ball.

In the first stage of the tagger, each word is run through the two-level lexicon transducer and the entries for all possible parts-of-speech are returned. For example the phrase Pavlov had shown that salvation ... would return the following list (one line per possible tag, with the correct tag shown in boldface):

EngCG then applies a large set of constraints (as many as 3,744 constraints in the EngCG-2 system) to the input sentence to rule out incorrect parts-of-speech. The boldfaced entries in the table above show the desired result, in which the simple past tense tag (rather than the past participle tag) is applied to had, and the complementizer (CS) tag is applied to that. The constraints are used in a negative way, to eliminate tags that are inconsistent with the context. For example one constraint eliminates all readings of that except the ADV (adverbial intensifier) sense (this is the sense in the sentence it isn't that odd). Here's a simplified version of the constraint:

ADVERBIAL-THAT RULE

Given input: "that"

if

(+1 A/ADV/QUANT); /* if next word is adj, adverb, or quantifier */

(+2 SENT-LIM); /* and following which is a sentence boundary, */

(NOT -1 SVOC/A); /* and the previous word is not a verb like */

/* 'consider' which allows ads as object complements */

then eliminate non-ADV tags

else eliminate ADV tag

The first two clauses of this rule check to see that the that directly precedes a sentence-final adjective, adverb, or quantifier. In all other cases the adverb reading is eliminated. The last clause eliminates cases preceded by verbs like consider or believe which can take a noun and an adjective; this is to avoid tagging the following instance of that as an adverb:

I consider that odd

Another rule is used to express the constraint that the complementizer sense of that is most likely to be used if the previous word is a verb which expects a complement (like believe, think, or show), and if that is followed by the beginning of a noun phrase, and a finite verb.

This description oversimplifies the EngCG architecture; the system also includes probabilistic constraints, and also makes use of other syntactic information we haven't discussed. The interested reader should consult Karlsson et al. (1995b) and Voutilainen (1999).

5.5 HMM PART-OF-SPEECH TAGGING

The use of probabilities in tags is quite old; probabilities in tagging were first used by Stolz et al. (1965), a complete probabilistic tagger with Viterbi decoding was sketched by Bahl and Mercer (1976), and various stochastic taggers were built in the 1980s (Marshall, 1983; Garside, 1987; Church, 1988; DeRose, 1988). This section describes a particular stochastic tagging algorithm generally known as the Hidden Markov Model or HMM tagger. Hidden Markov Models themselves will be more fully introduced and defined in Ch. 6. In this section, we prefigure Ch. 6 a bit by giving an initial introduction to the Hidden Markov Model as applied to part-of-speech tagging.

Use of a Hidden Markov Model to do part-of-speech-tagging, as we will define it, is a special case of Bayesian inference, a paradigm that has been known since the work of Bayes (1763). Bayesian inference or Bayesian classification was applied successfully to language problems as early as the late 1950s, including the OCR work of Bledsoe in 1959, and the seminal work of Mosteller and Wallace (1964) on applying Bayesian inference to determine the authorship of the Federalist papers.

In a classification task, we are given some observation(s) and our job is to determine which of a set of classes it belongs to. Part-of-speech tagging is generally treated as a sequence classification task. So here the observation is a sequence of words (let's say a sentence), and it is our job to assign them a sequence of part-of-speech tags.

For example, say we are given a sentence like

Secretariat is expected to race tomorrow.

What is the best sequence of tags which corresponds to this sequence of words? The Bayesian interpretation of this task starts by considering all possible sequences of classes—in this case, all possible sequences of tags. Out of this universe of tag sequences, we want to choose the tag sequence which is most probable given the observation sequence of $n$ words $w_1^n$. In other words, we want, out of all sequences of $n$ tags $t_1^n$ the single tag sequence such that $P(t_1^n|w_1^n)$ is highest. We use the hat notation $\hat{\mathbf{x}}$ to mean “our estimate of the correct tag sequence”.

$$ \hat{t}_{1}^{n}=\underset{t_{1}^{n}}{\mathrm{a r g m a x}}P(t_{1}^{n}|w_{1}^{n}) $$

The function $ \argmax_x f(x) $ means “the $ x $ such that $ f(x) $ is maximized”. Equation (5.24) thus means, out of all tag sequences of length $ n $, we want the particular tag sequence $ t_1^n $ which maximizes the right-hand side. While (5.24) is guaranteed to give us the optimal tag sequence, it is not clear how to make the equation operational; that is, for a given tag sequence $ t_1^n $ and word sequence $ w_1^n $, we don’t know how to directly compute $ P(t_1^n | w_1^n) $.

The intuition of Bayesian classification is to use Bayes' rule to transform (5.24) into a set of other probabilities which turn out to be easier to compute. Bayes' rule is presented in (5.25); it gives us a way to break down any conditional probability $ P(x|y) $ into three other probabilities:

$$ P(x|y)=\frac{P(y|x)P(x)}{P(y)} $$

$$ \hat{t}_{1}^{n}=\underset{t_{1}^{n}}{\mathrm{argmax}}\frac{P(w_{1}^{n}|t_{1}^{n})P(t_{1}^{n})}{P(w_{1}^{n})} $$

We can then substitute (5.25) into (5.24) to get (5.26):

We can conveniently simplify 5.26 by dropping the denominator $ P(w_1^n) $. Why is that? Since we are choosing a tag sequence out of all tag sequences, we will be computing $ \frac{P(w_1^n|t_1^n)P(t_1^n)}{P(w_1^n)} $ for each tag sequence. But $ P(w_1^n) $ doesn’t change for each tag sequence; we are always asking about the most likely tag sequence for the same observation $ w_1^n $, which must have the same probability $ P(w_1^n) $. Thus we can choose the tag sequence which maximizes this simpler formula:

$$ \hat{t}_{1}^{n}=\underset{t_{1}^{n}}{\mathrm{a r g m a x}}P(w_{1}^{n}|t_{1}^{n})P(t_{1}^{n}) $$

To summarize, the most probable tag sequence $ \hat{t}_1^n $ given some word string $ w_1^n $ can be computed by taking the product of two probabilities for each tag sequence, and choosing the tag sequence for which this product is greatest. The two terms are the prior probability of the tag sequence $ P(t_1^n) $, and the likelihood of the word string $ P(w_1^n|t_1^n) $:

$$ \hat{t}_{1}^{n}=\underset{t_{1}^{n}}{\mathrm{a r g m a x}}\overbrace{P(w_{1}^{n}|t_{1}^{n})}^{\mathrm{l i k e l i h o o d}}\overbrace{P(t_{1}^{n})}^{\mathrm{p r i o r}} $$

Unfortunately, (5.28) is still too hard to compute directly. HMM taggers therefore make two simplifying assumptions. The first assumption is that the probability of a word appearing is dependent only on its own part-of-speech tag; that it is independent of other words around it, and of the other tags around it:

$$ P(w_{1}^{n}|t_{1}^{n})\;\approx\;\prod_{i=1}^{n}P(w_{i}|t_{i}) $$

The second assumption is that the probability of a tag appearing is dependent only on the previous tag, the bigram assumption we saw in Ch. 4:

$$ P(t_{1}^{n})\;\approx\;\prod_{i=1}^{n}P(t_{i}|t_{i-1}) $$

Plugging the simplifying assumptions (5.29) and (5.30) into (5.28) results in the following equation by which a bigram tagger estimates the most probable tag sequence:

$$ \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}}\prod_{i=1}^{n}P(w_{i}|t_{i})P(t_{i}|t_{i-1}) $$

Equation (5.31) contains two kinds of probabilities, tag transition probabilities and word likelihoods. Let's take a moment to see what these probabilities represent. The

tag transition probabilities, $ P(t_i|t_{i-1}) $, represent the probability of a tag given the previous tag. For example, determiners are very likely to precede adjectives and nouns, as in sequences like that/DT flight/NN and the/DT yellow/JJ hat/NN. Thus we would expect the probabilities $ P(\mathrm{NN}|\mathrm{DT}) $ and $ P(\mathrm{JJ}|\mathrm{DT}) $ to be high. But in English, adjectives don't tend to precede determiners, so the probability $ P(\mathrm{DT}|\mathrm{JJ}) $ ought to be low.

We can compute the maximum likelihood estimate of a tag transition probability $ P(\mathrm{NN}|\mathrm{DT}) $ by taking a corpus in which parts-of-speech are labeled and counting, out of the times we see DT, how many of those times we see NN after the DT. That is, we compute the following ratio of counts:

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

Let's choose a specific corpus to examine. For the examples in this chapter we'll use the Brown corpus, the 1 million word corpus of American English described earlier. The Brown corpus has been tagged twice, once in the 1960's with the 87-tag tagset, and again in the 1990's with the 45-tag Treebank tagset. This makes it useful for comparing tagsets, and is also widely available.

In the 45-tag Treebank Brown corpus, the tag DT occurs 116,454 times. Of these, DT is followed by NN 56,509 times (if we ignore the few cases of ambiguous tags). Thus the MLE estimate of the transition probability is calculated as follows:

$$ P(NN|DT)=\frac{C(DT,NN)}{C(DT)}=\frac{56,509}{116,454}=.49 $$

The probability of getting a common noun after a determiner, .49, is indeed quite high, as we suspected.

The word likelihood probabilities, $ P(w_i|t_i) $, represent the probability, given that we see a given tag, that it will be associated with a given word. For example if we were to see the tag VBZ (third person singular present verb) and guess the verb that is likely to have that tag, we might likely guess the verb is, since the verb to be is so common in English.

We can compute the MLE estimate of a word likelihood probability like $ P(\text{is}|\text{VBZ}) $ again by counting, out of the times we see VBZ in a corpus, how many of those times the VBZ is labeling the word is. That is, we compute the following ratio of counts:

$$ P(w_{i}|t_{i})=\frac{C(t_{i},w_{i})}{C(t_{i})} $$

In Treebank Brown corpus, the tag VBZ occurs 21,627 times, and VBZ is the tag for is 10,073 times. Thus:

$$ P(is|VBZ)=\frac{C(VBZ,is)}{C(VBZ)}=\frac{10,073}{21,627}=.47 $$

For those readers who are new to Bayesian modeling note that this likelihood term is not asking “which is the most likely tag for the word is”. That is, the term is not $ P(\text{VBZ}|\text{is}) $. Instead we are computing $ P(\text{is}|\text{VBZ}) $. The probability, slightly counterintuitively, answers the question “If we were expecting a third person singular verb, how likely is it that this verb would be is?”.

We have now defined HMM tagging as a task of choosing a tag-sequence with the maximum probability, derived the equations by which we will compute this probability, and shown how to compute the component probabilities. In fact we have simplified the presentation of the probabilities in many ways; in later sections we will return to these equations and introduce the deleted interpolation algorithm for smoothing these counts, the trigram model of tag historv. and a model for unknown words.

But before turning to these augmentations, we need to introduce the decoding algorithm by which these probabilities are combined to choose the most likely tag sequence.