5.9.1 Contextual Spelling Error Correction

As we mentioned above, the noisy channel approach can also be applied to detect and correct real-word spelling errors, errors that result in an actual word of English. This can happen from typographical errors (insertion, deletion, transposition) that accidentally produce a real word (e.g., there for three), or because the writer substituted the wrong spelling of a homophone or near-homophone (e.g., dessert for desert, or piece for peace). The task of correcting these errors is also called context-sensitive spell correction. A number of studies suggest that between 25% and 40% of spelling

errors are valid English words (Kukich, 1992); some of Kukich's examples include

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

The design an construction of the system will take more than a year.

Can they lave him my messages?

The study was conducted mainly by John Black.

We can extend the noisy channel model to deal with real-word spelling errors by generating a candidate spelling set for every word in a sentence (Mays et al., 1991). The candidate set includes the word itself, plus every English word that would be generated from the word by either typographical modifications (letter insertion, deletion, substitution), or from a homophone list. The algorithm then chooses the spelling for each word that gives the whole sentence the highest probability. That is, given a sentence $ W = \{w_1, w_2, \ldots, w_k, \ldots, w_n\} $, where $ w_k $ has alternative spelling $ w'_k $, $ w''_k $, etc., we choose the spelling among these possible spellings that maximizes $ P(W) $, using the N-gram grammar to compute $ P(W) $.

More recent research has focused on improving the channel model $ P(t|c) $, such as by incorporating phonetic information, or allowing more complex errors (Brill and Moore, 2000; Toutanova and Moore, 2002). The most important improvement to the language model $ P(c) $ is to use very large contexts, for example by using the very large set of 5-grams publicly released by Google in 2006 (Franz and Brants, 2006). See Norvig (2007) for a nice explanation and Python implementation of the noisy channel model; the end of the chapter has further pointers.

5.10 SUMMARY

This chapter introduced the idea of parts-of-speech and part-of-speech tagging. The main ideas:

• Languages generally have a relatively small set of closed class words, which are often highly frequent, generally act as function words, and can be very ambiguous in their part-of-speech tags. Open class words generally include various kinds of nouns, verbs, adjectives. There are a number of part-of-speech coding schemes, based on tagsets of between 40 and 200 tags.

• Part-of-speech tagging is the process of assigning a part-of-speech label to each of a sequence of words. Rule-based taggers use hand-written rules to distinguish tag ambiguity. HMM taggers choose the tag sequence which maximizes the product of word likelihood and tag sequence probability. Other machine learning models used for tagging include maximum entropy and other log-linear models, decision trees, memory-based learning, and transformation-based learning.

• The probabilities in HMM taggers are trained on hand-labeled training corpora, combining different N-gram levels using deleted interpolation, and using sophisticated unknown word models.

Given an HMM and an input string, the Viterbi algorithm is used to decode the optimal tag sequence.

Taggers are evaluated by comparing their output from a test set to human labels for that test set. Error analysis can help pinpoint areas where a tagger doesn't perform well.

BIBLIOGRAPHICAL AND HISTORICAL NOTES

The earliest implemented part-of-speech assignment algorithm may have been part of the parser in Zellig Harris's Transformations and Discourse Analysis Project (TDAP), which was implemented between June 1958 and July 1959 at the University of Pennsylvania (Harris, 1962). Previous natural language processing systems had used dictionaries with part-of-speech information for words, but have not been described as performing part-of-speech disambiguation. As part of its parsing, TDAP did part-of-speech disambiguation via 14 hand-written rules, whose use of part-of-speech tag sequences prefigures all the modern algorithms, and which were run in an order based on the relative frequency of tags for a word. The parser/tagger was reimplemented recently and is described by Joshi and Hopely (1999) and Karttunen (1999), who note that the parser was essentially implemented (in a very modern way) as a cascade of finite-state transducers.

Soon after the TDAP parser was the Computational Grammar Coder (CGC) of Klein and Simmons (1963). The CGC had three components: a lexicon, a morphological analyzer, and a context disambiguator. The small 1500-word lexicon included exceptional words that could not be accounted for in the simple morphological analyzer, including function words as well as irregular nouns, verbs, and adjectives. The morphological analyzer used inflectional and derivational suffixes to assign part-of-speech classes. A word was run through the lexicon and morphological analyzer to produce a candidate set of parts-of-speech. A set of 500 context rules were then used to disambiguate this candidate set, by relying on surrounding islands of unambiguous words. For example, one rule said that between an ARTICLE and a VERB, the only allowable sequences were ADJ-NOUN, NOUN-ADVERB, or NOUN-NOUN. The CGC algorithm reported 90% accuracy on applying a 30-tag tagset to articles from the Scientific American and a children's encyclopedia.

The TAGGIT tagger (Greene and Rubin, 1971) was based on the Klein and Simmons (1963) system, using the same architecture but increasing the size of the dictionary and the size of the tagset (to 87 tags). For example the following sample rule, which states that a word x is unlikely to be a plural noun (NNS) before a third person singular verb (VBZ):

x VBZ $ \rightarrow $ not NNS

TAGGIT was applied to the Brown corpus and, according to Francis and Kučera (1982, p. 9), “resulted in the accurate tagging of 77% of the corpus” (the remainder of the Brown corpus was tagged by hand).

In the 1970s the Lancaster-Oslo/Bergen (LOB) corpus was compiled as a British English equivalent of the Brown corpus. It was tagged with the CLAWS tagger (Marshall, 1983, 1987; Garside, 1987), a probabilistic algorithm which can be viewed as an

approximation to the HMM tagging approach. The algorithm used tag bigram probabilities, but instead of storing the word-likelihood of each tag, tags were marked either as rare ( $ P(\text{tag}|\text{word}) < .01 $) infrequent ( $ P(\text{tag}|\text{word}) < .10 $), or normally frequent ( $ P(\text{tag}|\text{word}) > .10 $),

The probabilistic PARTS tagger of Church (1988) was very close to a full HMM tagger. It extended the CLAWS idea to assign full lexical probabilities to each word/tag combination, and used Viterbi decoding to find a tag sequence. Like the CLAWS tagger, however, it stored the probability of the tag given the word:

$$ P(\operatorname{tag}|\operatorname{word})*P(\operatorname{tag}|\text{previous}n\operatorname{tags}) $$

rather than using the probability of the word given the tag, as an HMM tagger does:

$$ P(\mathrm{word}|\mathrm{tag})*P(\mathrm{tag}|\mathrm{previous}\;n\;\mathrm{tags}) $$

Later taggers explicitly introduced the use of the Hidden Markov Model, often with the EM training algorithm (Kupiec, 1992; Merialdo, 1994; Weischedel et al., 1993), including the use of variable-length Markov models (Schütze and Singer, 1994).

Most recent tagging algorithms, like the HMM and TBL approaches, we have discussed, are machine-learning classifiers which estimate the best tag-sequence for a sentence given various features such as the current word, neighboring parts-of-speech or words, and unknown word features such as orthographic and morphological features. Many kinds of classifiers have been used to combine these features, including decision trees (Jelinek et al., 1994; Magerman, 1995), maximum entropy models (Ratnaparkhi, 1996), other log-linear models (Franz, 1996), memory-based learning (Daelemans et al., 1996), and networks of linear separators (SNOW) (Roth and Zelenko, 1998). Most machine learning models seem to achieve relatively similar performance given similar features, roughly 96-97% on the Treebank 45-tag tagset on the Wall Street Journal corpus. As of the writing of this chapter, the highest performing published model on this WSJ Treebank task is a log-linear tagger that uses information about neighboring words as well as tags, and a sophisticated unknown-word model, achieving 97.24% accuracy (Toutanova et al., 2003). Most such models are supervised, although there is a beginning to be work on unsupervised models (Schütze, 1995; Brill, 1997; Clark, 2000; Banko and Moore, 2004; Goldwater and Griffiths, 2007).

Readers interested in the history of parts-of-speech should consult a history of linguistics such as Robins (1967) or Koerner and Asher (1995), particularly the article by Householder (1995) in the latter. Sampson (1987) and Garside et al. (1997) give a detailed summary of the provenance and makeup of the Brown and other tagsets. More information on part-of-speech tagging can be found in van Halteren (1999).

Algorithms for spelling error detection and correction have existed since at least Blair (1960). Most early algorithm were based on similarity keys like the Soundex algorithm discussed in the exercises on page ?? (Odell and Russell, 1922; Knuth, 1973). Damerau (1964) gave a dictionary-based algorithm for error detection; most error-detection algorithms since then have been based on dictionaries. Damerau also gave a correction algorithm that worked for single errors. Most algorithms since then have relied on dynamic programming, beginning with Wagner and Fischer (1974). Kukich (1992) is the definitive survey article on spelling error detection and correction.

Modern algorithms are based on statistical or machine learning algorithm, following e.g., Kashyap and Oommen (1983) and Kernighan et al. (1990). Recent approaches to spelling include extensions to the noisy channel model (Brill and Moore, 2000; Toutanova and Moore, 2002) as well as many other machine learning architectures such as Bayesian classifiers, (Gale et al., 1993; Golding, 1997; Golding and Schabes, 1996), decision lists (Yarowsky, 1994), transformation based learning (Mangu and Brill, 1997) latent semantic analysis (Jones and Martin, 1997) and Winnow (Golding and Roth, 1999). Hirst and Budanitsky (2005) explore the use of word relatedness; see Ch. 20. Noisy channel spelling correction is used in a number of commercial applications, including the Microsoft Word contextual spell checker.

EXERCISES

5.1 Find one tagging error in each of the following sentences that are tagged with the Penn Treebank tagset:

a. I/PRP need/VBP a/DT flight/NN from/IN Atlanta/NN

b. Does/VBZ this/DT flight/NN serve/VB dinner/NNS

c. I/PRP have/VB a/DT friend/NN living/VBG in/IN Denver/NNP

d. What/WDT flights/NNS do/VBP you/PRP have/VB from/IN Milwaukee/NNP to/IN Tampa/NNP

e. Can/VBP you/PRP list/VB the/DT nonstop/JJ afternoon/NN flights/NNS

5.2 Use the Penn Treebank tagset to tag each word in the following sentences from Damon Runyon's short stories. You may ignore punctuation. Some of these are quite difficult; do your best.

a. It is a nice night.

b. This crap game is over a garage in Fifty-second Street...

c. ...Nobody ever takes the newspapers she sells...

d. He is a tall, skinny guy with a long, sad, mean-looking kisser, and a mournful voice.

e. ...I am sitting in Mindy's restaurant putting on the gefillte fish, which is a dish I am very fond of,...

f. When a guy and a doll get to taking peeks back and forth at each other, why there you are indeed.

5.3 Now compare your tags from the previous exercise with one or two friend's answers. On which words did you disagree the most? Why?

5.4 Now tag the sentences in Exercise 5.2 using the more detailed Brown tagset in Fig. 5.7.

5.5 Implement the TBL algorithm in Fig. 5.21. Create a small number of templates and train the tagger on any POS-tagged training set you can find.

5.6 Implement the “most-likely tag” baseline. Find a POS-tagged training set, and use it to compute for each word the tag which maximizes $ p(t|w) $. You will need to implement a simple tokenizer to deal with sentence boundaries. Start by assuming all unknown words are NN and compute your error rate on known and unknown words. Now write at least 5 rules to do a better job of tagging unknown words, and show the difference in error rates.

5.7 Recall that the Church (1988) tagger is not an HMM tagger since it incorporates the probability of the tag given the word:

$$ P(\operatorname{tag}|\operatorname{word})*P(\operatorname{tag}|\text{previous}n\operatorname{tags}) $$

rather than using the likelihood of the word given the tag, as an HMM tagger does:

$$ P(\mathrm{word}|\mathrm{tag})*P(\mathrm{tag}|\mathrm{previous}\;n\;\mathrm{tags}) $$

As a gedanken-experiment, construct a sentence, a set of tag transition probabilities, and a set of lexical tag probabilities that demonstrate a way in which the HMM tagger can produce a better answer than the Church tagger, and another example in which the Church tagger is better.

5.8 Build an HMM tagger. This requires (1) that you have implemented the Viterbi algorithm from this chapter and Ch. 6, (2) that you have a dictionary with part-of-speech information and (3) that you have either (a) a part-of-speech-tagged corpus or (b) an implementation of the Forward Backward algorithm. If you have a labeled corpus, train the transition and observation probabilities of an HMM tagger directly on the hand-tagged data. If you have an unlabeled corpus, train using Forward Backward.

5.9 Now run your algorithm on a small test set that you have hand-labeled. Find five errors and analyze them.

5.10 Compute a bigram grammar on a large corpus and reestimate the spelling correction probabilities shown in Fig. 5.25 given the correct sequence... was called a “stellar and versatile across whose combination of sass and glamour has defined her...”. Does a bigram grammar prefer the correct word actress?

5.11 Read Norvig (2007) and implement one of the extensions he suggests to his Python noisy channel spell checker.

Baayen, R. H., Piepenbrock, R., and Gulikers, L. (1995). The CELEX Lexical Database (Release 2) [CD-ROM]. Linguistic Data Consortium, University of Pennsylvania [Distributor], Philadelphia, PA.

Baayen, R. H. and Sproat, R. (1996). Estimating lexical priors for low-frequency morphologically ambiguous forms. Computational Linguistics, 22(2), 155–166.

Bahl, L. R. and Mercer, R. L. (1976). Part of speech assignment by a statistical decision algorithm. In Proceedings IEEE International Symposium on Information Theory, pp. 88–89.

Banko, M. and Moore, R. C. (2004). A study of unsupervised part-of-speech tagging. In COLING-04.

Bayes, T. (1763). An Essay Toward Solving a Problem in the Doctrine of Chances, Vol. 53. Reprinted in Facsimiles of two papers by Bayes, Hafner Publishing Company, New York, 1963.

Blair, C. R. (1960). A program for correcting spelling errors. Information and Control, 3, 60–67.

Brants, T. (2000). TnT: a statistical part-of-speech tagger. In Proceedings of the sixth conference on Applied natural language processing, Seattle, WA, pp. 224–231. Morgan Kaufmann.

Brill, E. (1995). Transformation-based error-driven learning and natural language processing: A case study in part-of-speech tagging. Computational Linguistics, 21(4), 543–566.

Brill, E. (1997). Unsupervised learning of disambiguation rules for part of speech tagging. Unpublished manuscript.

Brill, E. and Moore, R. C. (2000). An improved error model for noisy channel spelling correction. In ACL-00, Hong Kong, pp. 286–293.

Brill, E. and Wu, J. (1998). Classifier combination for improved lexical disambiguation. In COLING/ACL-98, Montreal, Canada, pp. 191–195.

Broschart, J. (1997). Why Tongan does it differently. Linguistic Typology, 1, 123–165.

Charniak, E., Hendrickson, C., Jacobson, N., and Perkowitz, M. (1993). Equations for part-of-speech tagging. In AAAI-93, Washington, D.C., pp. 784–789. AAAI Press.

Church, K. W. (1988). A stochastic parts program and noun phrase parser for unrestricted text. In Second Conference on Applied Natural Language Processing, pp. 136–143. ACL.

Clark, A. (2000). Inducing syntactic categories by context distribution clustering. In CoNLL-00.

Cohen, P. R. (1995). Empirical Methods for Artificial Intelligence. MIT Press.

Cutler, A. (1986). $ \underline{\text{Forbear}} $ is a homophone: Lexical prosody does not constrain lexical access. Language and Speech, 29, 201–219.

Cutting, D., Kupiec, J., Pedersen, J., and Sibun, P. (1992). A practical part-of-speech tagger. In Third Conference on Applied Natural Language Processing, pp. 133–140.

Daelemans, W., Zavrel, J., Berck, P., and Gillis, S. (1996). MBT: A memory based part of speech tagger-generator. In Ejerhed, E. and Dagan, I. (Eds.), Proceedings of the Fourth Workshop on Very Large Corpora, pp. 14–27.

Damerau, F. J. (1964). A technique for computer detection and correction of spelling errors. Communications of the ACM, 7(3), 171–176.

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.

Dermatas, E. and Kokkinakis, G. (1995). Automatic stochastic tagging of natural language texts. Computational Linguistics, 21(2), 137–164.

DeRose, S. J. (1988). Grammatical category disambiguation by statistical optimization. Computational Linguistics, 14, 31–39.

Dietterich, T. G. (1998). Approximate statistical tests for comparing supervised classification learning algorithms. Neural Computation, 10(7), 1895–1924.

Dimitrova, L., Ide, N., Petkevic, V., Erjavec, T., Kaalep, H. J., and Tufis, D. (1998). Multext-East: parallel and comparable corpora and lexicons for six Central and Eastern European languages. In COLING/ACL-98, Montreal, Canada.

Džeroski, S., Erjavec, T., and Zavrel, J. (2000). Morphosyntactic Tagging of Slovene: Evaluating PoS Taggers and Tagsets. In LREC-00, Paris, pp. 1099–1104.

Erjavec, T. (2004). Multext-east version 3: Multilingual morphosyntactic specifications, lexicons and corpora. In LREC-04, pp. 1535–1538. ELRA.

Evans, N. (2000). Word classes in the world's languages. In Booij, G., Lehmann, C., and Mugdan, J. (Eds.), Morphology: a Handbook on Inflection and Word Formation, pp. 708–732. Mouton, Berlin.

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.

Franz, A. (1996). Automatic Ambiguity Resolution in Natural Language Processing. Springer-Verlag, Berlin.

Gale, W. A., Church, K. W., and Yarowsky, D. (1992). Estimating upper and lower bounds on the performance of word-sense disambiguation programs. In Proceedings of the 30th ACL, Newark, DE, pp. 249–256.

Gale, W. A., Church, K. W., and Yarowsky, D. (1993). A method for disambiguating word senses in a large corpus. Computers and the Humanities, 26, 415–439.

Garside, R. (1987). The CLAWS word-tagging system. In Garside, R., Leech, G., and Sampson, G. (Eds.), The Computational Analysis of English, pp. 30–41. Longman, London.

Garside, R., Leech, G., and McEnery, A. (1997). Corpus Annotation. Longman, London and New York.

Gil, D. (2000). Syntactic categories, cross-linguistic variation and universal grammar. In Vogel, P. M. and Comrie, B. (Eds.), Approaches to the Typology of Word Classes, pp. 173–216. Mouton.

Golding, A. R. and Roth, D. (1999). A winnow based approach to context-sensitive spelling correction. Machine Learning, 34(1-3), 107–130. Special Issue on Machine Learning and Natural Language.

Golding, A. R. (1997). A bayesian hybrid method for context-sensitive spelling correction. In Proceedings of the Third Workshop on Very Large Corpora, Boston, MA, pp. 39–53.

Golding, A. R. and Schabes, Y. (1996). Combining trigram-based and feature-based methods for context-sensitive spelling Correction. In ACL-96, Santa Cruz, CA, pp. 71–78.

Goldwater, S. and Griffiths, T. L. (2007). A fully Bayesian approach to unsupervised part-of-speech tagging. In ACL-07, Prague, Czech Republic.

Greene, B. B. and Rubin, G. M. (1971). Automatic grammatical tagging of English. Department of Linguistics, Brown University, Providence, Rhode Island.

Grudin, J. T. (1983). Error patterns in novice and skilled transcription typing. In Cooper, W. E. (Ed.), Cognitive Aspects of Skilled Typewriting, pp. 121–139. Springer-Verlag.

Hajič, J. (2000). Morphological tagging: Data vs. dictionaries. In Proceedings of ANLP-NAACL Conference. Seattle.

Hajič, J. and Hladká, B. (1998). Tagging inflective languages: Prediction of morphological categories for a rich, structured tagset. In COLING/ACL-98, Montreal, Canada.

Hajič, J., Krbec, P., Květoň, P., Oliva, K., and Petkevič, V. (2001). Serial Combination of Rules and Statistics: A Case Study in Czech Tagging. In ACL-01, Toulouse, France, pp. –.

Hakkani-Tür, D., Oflazer, K., and Tür, G. (2002). Statistical morphological disambiguation for agglutinative languages. Journal of Computers and Humanities, 36(4).

Harris, Z. S. (1962). String Analysis of Sentence Structure. Mouton, The Hague.

Heikkilä, J. (1995). A TWOL-based lexicon and feature system for English. In Karlsson, F., Voutilainen, A., Heikkilä, J., and Anttila, A. (Eds.), Constraint Grammar: A Language-Independent System for Parsing Unrestricted Text, pp. 103–131. Mouton de Gruyter, Berlin.

Hirst, G. and Budanitsky, A. (2005). Correcting real-word spelling errors by restoring lexical cohesion. Natural Language Engineering, 11, 87–111.

Householder, F. W. (1995). Dionysius Thrax, the technai, and Sextus Empiricus. In Koerner, E. F. K. and Asher, R. E. (Eds.), Concise History of the Language Sciences, pp. 99–103. Elsevier Science, Oxford.

Jelinek, F., Lafferty, J. D., Magerman, D. M., Mercer, R. L., Ratnaparkhi, A., and Roukos, S. (1994). Decision tree parsing using a hidden derivation model. In ARPA Human Language Technologies Workshop, Plainsboro, N.J., pp. 272–277. Morgan Kaufmann.

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.

Jones, M. P. and Martin, J. H. (1997). Contextual spelling correction using latent semantic analysis. In Proceedings of the 5th Conference on Applied Natural Language Processing (ANLP'97), Washington, D.C., pp. 166–173.

Joshi, A. K. and Hopely, P. (1999). A parser from antiquity. In Kornai, A. (Ed.), Extended Finite State Models of Language, pp. 6–15. Cambridge University Press.

Karlsson, F., Voutilainen, A., Heikkilä, J., and Anttila, A. (1995a). Constraint Grammar — A language-independent system for parsing unrestricted text. Mouton de Gruyter, Berlin.

Karlsson, F., Voutilainen, A., Heikkilä, J., and Anttila, A. (Eds.). (1995b). Constraint Grammar: A Language-Independent System for Parsing Unrestricted Text. Mouton de Gruyter, Berlin.

Karttunen, L. (1999). Comments on Joshi. In Kornai, A. (Ed.), Extended Finite State Models of Language, pp. 16–18. Cambridge University Press.

Kashyap, R. L. and Oommen, B. J. (1983). Spelling correction using probabilistic methods. Pattern Recognition Letters, 2, 147–154.

Kernighan, M. D., Church, K. W., and Gale, W. A. (1990). A spelling correction program based on a noisy channel model. In COLING-90, Helsinki, Vol. II, pp. 205–211.

Klein, S. and Simmons, R. F. (1963). A computational approach to grammatical coding of English words. Journal of the Association for Computing Machinery, 10(3), 334–347.

Knuth, D. E. (1973). Sorting and Searching: The Art of Computer Programming Volume 3. Addison-Wesley, Reading, MA.

Koerner, E. F. K. and Asher, R. E. (Eds.). (1995). Concise History of the Language Sciences. Elsevier Science, Oxford.

Kruskal, J. B. (1983). An overview of sequence comparison. In Sankoff, D. and Kruskal, J. B. (Eds.), Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison, pp. 1–44. Addison-Wesley, Reading, MA.

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

Kupiec, J. (1992). Robust part-of-speech tagging using a hidden Markov model. Computer Speech and Language, 6, 225–242.

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

Magerman, D. M. (1995). Statistical decision-tree models for parsing. In ACL-95, pp. 276–283.

Mangu, L. and Brill, E. (1997). Automatic rule acquisition for spelling correction. In ICML 1997, Nashville, TN, pp. 187–194.

Marcus, M. P., Santorini, B., and Marcinkiewicz, M. A. (1993). Building a large annotated corpus of English: The Penn treebank. Computational Linguistics, 19(2), 313–330.

Marshall, I. (1983). Choice of grammatical word-class without GGlobal syntactic analysis: Tagging words in the LOB corpus. Computers and the Humanities, 17, 139–150.

Marshall, I. (1987). Tag selection using probabilistic methods. In Garside, R., Leech, G., and Sampson, G. (Eds.), The Computational Analysis of English, pp. 42–56. Longman, London.

Mays, E., Damerau, F. J., and Mercer, R. L. (1991). Context based spelling correction. Information Processing and Management, 27(5), 517–522.

McCallum, A., Freitag, D., and Pereira, F. C. N. (2000). Maximum Entropy Markov Models for Information Extraction and Segmentation. In ICML 2000, pp. 591–598.

Megyesi, B. (1999). Improving brill's pos tagger for an agglutinative language. In EMNLP/VLC-99, College Park, MA.

Merialdo, B. (1994). Tagging English text with a probabilistic model. Computational Linguistics, 20(2), 155–172.

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.

Norvig, P. (2007). How to write a spelling corrector. http://www.norvig.com/spell-correct.html.

Odell, M. K. and Russell, R. C. (1918/1922). U.S. Patents 1261167 (1918), 1435663 (1922)†. Cited in Knuth (1973).

Oravecz, C. and Dienes, P. (2002). Efficient stochastic part-of-speech tagging for Hungarian. In LREC-02, Las Palmas, Canary Islands, Spain, pp. 710–717.

Quirk, R., Greenbaum, S., Leech, G., and Svartvik, J. (1985). A Comprehensive Grammar of the English Language. Longman, London.

Ratnaparkhi, A. (1996). A maximum entropy part-of-speech tagger. In EMNLP 1996, Philadelphia, PA, pp. 133–142.

Robins, R. H. (1967). A Short History of Linguistics. Indiana University Press, Bloomington.

Roche, E. and Schabes, Y. (1997). Deterministic part-of-speech tagging with finite-state transducers. In Roche, E. and Schabes, Y. (Eds.), Finite-State Language Processing, pp. 205–239. MIT Press.

Roth, D. and Zelenko, D. (1998). Part of speech tagging using a network of linear separators. In COLING/ACL-98, Montreal, Canada, pp. 1136–1142.

Sampson, G. (1987). Alternative grammatical coding systems. In Garside, R., Leech, G., and Sampson, G. (Eds.), The Computational Analysis of English, pp. 165–183. Longman, London and New York.

Samuel, K., Carberry, S., and Vijay-Shanker, K. (1998). Computing dialogue acts from features with transformation-based learning. In Chu-Carroll, J. and Green, N. (Eds.), Applying Machine Learning to Discourse Processing. Papers from the 1998 AAAI Spring Symposium, pp. 90–97. Technical Report SS-98-01.

Samuelsson, C. (1993). Morphological tagging based entirely on Bayesian inference. In 9th Nordic Conference on Computational Linguistics NODALIDA-93. Stockholm.

Santorini, B. (1990). Part-of-speech tagging guidelines for the Penn Treebank project. 3rd revision, 2nd printing.

Schachter, P. (1985). Parts-of-speech systems. In Shopen, T. (Ed.), Language Typology and Syntactic Description, Volume I, pp. 3–61. Cambridge University Press.

Schütze, H. (1995). Distributional part-of-speech tagging. In EACL-95.

Schütze, H. and Singer, Y. (1994). Part-of-speech tagging using a variable memory Markov model. In Proceedings of the 32nd ACL, Las Cruces, NM, pp. 181–187.

Stolz, W. S., Tannenbaum, P. H., and Carstensen, F. V. (1965). A stochastic approach to the grammatical coding of English. Communications of the ACM, 8(6), 399–405.

Thede, S. M. and Harper, M. P. (1999). A second-order Hidden Markov Model for part-of-speech tagging. In ACL-99, College Park, MA, pp. 175–182.

Toutanova, K., Klein, D., Manning, C. D., and Singer, Y. (2003). Feature-rich part-of-speech tagging with a cyclic dependency network. In HLT-NAACL-03.

Toutanova, K. and Moore, R. C. (2002). Pronunciation modeling for improved spelling correction. In ACL-02, Philadelphia, PA, pp. 144–151.

Tseng, H., Jurafsky, D., and Manning, C. D. (2005). Morphological features help pos tagging of unknown words across language varieties. In Proceedings of the Fourth SIGHAN Workshop on Chinese Language Processing.

van Halteren, H. (Ed.). (1999). Syntactic Wordclass Tagging. Kluwer, Dordrecht.

Vintsyuk, T. K. (1968). Speech discrimination by dynamic programming. Cybernetics, 4(1), 52–57. Russian Kibernetika 4(1):81-88 (1968).

Voutilainen, A. (1995). Morphological disambiguation. In Karlsson, F., Voutilainen, A., Heikkilä, J., and Anttila, A. (Eds.), Constraint Grammar: A Language-Independent System for Parsing Unrestricted Text, pp. 165–284. Mouton de Gruyter, Berlin.

Voutilainen, A. (1999). Handcrafted rules. In van Halteren, H. (Ed.), Syntactic Wordclass Tagging, pp. 217–246. Kluwer, Dordrecht.

Wagner, R. A. and Fischer, M. J. (1974). The string-to-string correction problem. Journal of the Association for Computing Machinery, 21, 168–173.

Weischedel, R., Meteer, M., Schwartz, R., Ramshaw, L. A., and Palmucci, J. (1993). Coping with ambiguity and unknown

words through probabilistic models. Computational Linguistics, 19(2), 359–382.

Yarowsky, D. (1994). Decision lists for lexical ambiguity resolution: Application to accent restoration in Spanish and French. In Proceedings of the 32nd ACL, Las Cruces, NM, pp. 88–95. ACL.

6

HIDDEN MARKOV AND MAXIMUM ENTROPY MODELS

Numquam ponenda est pluralitas sine necessitat 'Plurality should never be proposed unless needed' William of Occam

Her sister was called Tatiana.

For the first time with such a name

the tender pages of a novel,

we'll whimsically grace.

Pushkin, Eugene Onegin, in the Nabokov translation

Alexander Pushkin's novel in verse, Eugene Onegin, serialized in the early 19th century, tells of the young dandy Onegin, his rejection of the love of young Tatiana, his duel with his friend Lenski, and his later regret for both mistakes. But the novel is mainly beloved for its style and structure rather than its plot. Among other interesting structural innovations, the novel is written in a form now known as the Onegin stanza, iambic tetrameter with an unusual rhyme scheme. These elements have caused complications and controversy in its translation into other languages. Many of the translations have been in verse, but Nabokov famously translated it strictly literally into English prose. The issue of its translation, and the tension between literal and verse translations, have inspired much commentary (see for example Hofstadter (1997)).

In 1913 A. A. Markov asked a less controversial question about Pushkin's text: could we use frequency counts from the text to help compute the probability that the next letter in sequence would be a vowel. In this chapter we introduce two important classes of statistical models for processing text and speech, both descendants of Markov's models. One of them is the Hidden Markov Model (HMM). The other, is the Maximum Entropy model (MaxEnt), and particularly a Markov-related variant of MaxEnt called the Maximum Entropy Markov Model (MEMM). All of these are machine learning models. We have already touched on some aspects of machine learning; indeed we briefly introduced the Hidden Markov Model in the previous chapter, and we have introduced the N-gram model in the chapter before. In this chapter we

give a more complete and formal introduction to these two important models.

HMMs and MEMMs are both sequence classifiers. A sequence classifier or sequence labeler is a model whose job is to assign some label or class to each unit in a sequence. The finite-state transducer we studied in Ch. 3 is a kind of non-probabilistic sequence classifier, for example transducing from sequences of words to sequences of morphemes. The HMM and MEMM extend this notion by being probabilistic sequence classifiers; given a sequence of units (words, letters, morphemes, sentences, whatever) their job is to compute a probability distribution over possible labels and choose the best label sequence.

We have already seen one important sequence classification task: part-of-speech tagging, where each word in a sequence has to be assigned a part-of-speech tag. Sequence labeling tasks come up throughout speech and language processing, a fact that isn't too surprising if we consider that language consists of sequences at many representational levels. Besides part-of-speech tagging, in this book we will see the application of these sequence models to tasks like speech recognition (Ch. 9), sentence segmentation and grapheme-to-phoneme conversion (Ch. 8), partial parsing/chunking (Ch. 13), and named entity recognition and information extraction (Ch. 22).

This chapter is roughly divided into two sections: Hidden Markov Models followed by Maximum Entropy Markov Models. Our discussion of the Hidden Markov Model extends what we said about HMM part-of-speech tagging. We begin in the next section by introducing the Markov Chain, then give a detailed overview of HMMs and the forward and Viterbi algorithms with more formalization, and finally introduce the important EM algorithm for unsupervised (or semi-supervised) learning of a Hidden Markov Model.

In the second half of the chapter, we introduce Maximum Entropy Markov Models gradually, beginning with techniques that may already be familiar to you from statistics: linear regression and logistic regression. We next introduce MaxEnt. MaxEnt by itself is not a sequence classifier; it is used to assign a class to a single element. The name Maximum Entropy comes from the idea that the classifier finds the probabilistic model which follows Occam's Razor in being the simplest (least constrained; has the maximum entropy) yet still consistent with some specific constraints. The Maximum Entropy Markov Model is the extension of MaxEnt to the sequence labeling task, adding components such as the Viterbi algorithm.

Although this chapter introduces MaxEnt, which is a classifier, we will not focus in general on non-sequential classification. Non-sequential classification will be addressed in later chapters with the introduction of classifiers like the Gaussian Mixture Model in (Ch. 9) and the Naive Bayes and decision list classifiers in (Ch. 20).

6.1 MARKOV CHAINS

The Hidden Markov Model is one of the most important machine learning models in speech and language processing. In order to define it properly, we need to first introduce the Markov chain, sometimes called the observed Markov model. Markov chains and Hidden Markov Models are both extensions of the finite automata of Ch. 2.

Recall that a finite automaton is defined by a set of states, and a set of transitions between states that are taken based on the input observations. A weighted finite-state automaton is a simple augmentation of the finite automaton in which each arc is associated with a probability, indicating how likely that path is to be taken. The probability on all the arcs leaving a node must sum to 1.

A Markov chain is a special case of a weighted automaton in which the input sequence uniquely determines which states the automaton will go through. Because it can't represent inherently ambiguous problems, a Markov chain is only useful for assigning probabilities to unambiguous sequences.

Fig. 6.1a shows a Markov chain for assigning a probability to a sequence of weather events, where the vocabulary consists of HOT, COLD, and RAINY. Fig. 6.1b shows another simple example of a Markov chain for assigning a probability to a sequence of words $ w_{1}...w_{n} $. This Markov chain should be familiar; in fact it represents a bigram language model. Given the two models in Figure 6.1 we can assign a probability to any sequence from our vocabulary. We'll go over how to do this shortly.

First, let's be more formal. We'll view a Markov chain as a kind of probabilistic graphical model; a way of representing probabilistic assumptions in a graph. A Markov chain is specified by the following components:

$$ \begin{aligned}&Q=q_{1}q_{2}\cdots q_{N}&&a set of N states&\\&A=a_{01}a_{02}\cdots a_{n1}\cdots a_{nn}&&a transition~probability~matrix~A,each~a_{ij}~representsenting~the~probability~of~moving~from~state~i&\\&&to~state~j,s.t.\quad\sum_{j=1}^{n}a_{ij}=1\quad\forall i&\\&q_{0},qF&&a~special~start~state~and~end~(final)state~which&\\&&&are~not~associated~with~observations.&\end{aligned} $$

Fig. 6.1 shows that we represent the states (including start and end states) as nodes in the graph, and the transitions as edges between nodes.

A Markov chain embodies an important assumption about these probabilities. In a first-order Markov chain, the probability of a particular state is dependent only on the

previous state:

Markov Assumption:

$$ P(q_{i}|q_{1}...q_{i-1})=P(q_{i}|q_{i-1}) $$

Note that because each $ a_{ij} $ expresses the probability $ p(q_j|q_i) $, the laws of probability require that the values of the outgoing arcs from a given state must sum to 1:

$$ \sum_{j=1}^{n}a_{ij}=1\quad\forall i $$

An alternate representation that is sometimes used for Markov chains doesn't rely on a start or end state, instead representing the distribution over initial states and accepting states explicitly:

$ \pi = \pi_1, \pi_2, ..., \pi_N $ an initial probability distribution over states. $ \pi_i $ is the probability that the Markov chain will start in state $ i $. Some states $ j $ may have $ \pi_j = 0 $, meaning that they cannot be initial states. Also, $ \sum_{i=1}^n \pi_i = 1 $

$$ Q A=\left\{q_{x},q_{y}...\right\}\quad\textrm{a set}Q A\subset Q\textrm{of legal}\textrm{a c c e p t i n g}\textrm{s t a t e s} $$

Thus the probability of state 1 being the first state can be represented either as $ a_{01} $ or as $ \pi_{1} $. Note that because each $ \pi_{i} $ expresses the probability $ p(q_{i}|\text{START}) $, all the $ \pi $ probabilities must sum to 1:

$$ \sum_{i=1}^{n}\pi_{i}=1 $$

Before you go on, use the sample probabilities in Fig. 6.2b to compute the probability of each of the following sequences:

(6.4) hot hot hot hot

(6.5) cold hot cold hot

What does the difference in these probabilities tell you about a real-world weather fact encoded in Fig. 6.2b?

6.2 THE HIDDEN MARKOV MODEL

A Markov chain is useful when we need to compute a probability for a sequence of events that we can observe in the world. In many cases, however, the events we are interested in may not be directly observable in the world. For example, in part-of-speech tagging (Ch. 5) we didn't observe part of speech tags in the world; we saw words, and had to infer the correct tags from the word sequence. We call the part-of-speech tags hidden because they are not observed. The same architecture will come up in speech recognition; in that case we'll see acoustic events in the world, and have to infer the presence of 'hidden' words that are the underlying causal source of the acoustics. A Hidden Markov Model (HMM) allows us to talk about both observed events (like words that we see in the input) and hidden events (like part-of-speech tags) that we think of as causal factors in our probabilistic model.

To exemplify these models, we'll use a task conceived of by Jason Eisner (2002). Imagine that you are a climatologist in the year 2799 studying the history of global warming. You cannot find any records of the weather in Baltimore, Maryland, for the summer of 2007, but you do find Jason Eisner's diary, which lists how many ice creams Jason ate every day that summer. Our goal is to use these observations to estimate the temperature every day. We'll simplify this weather task by assuming there are only two kinds of days: cold (C) and hot (H). So the Eisner task is as follows:

Given a sequence of observations $O$, each observation an integer corresponding to the number of ice creams eaten on a given day, figure out the correct ‘hidden’ sequence $Q$ of weather states (H or C) which caused Jason to eat the ice cream.

Let's begin with a formal definition of a Hidden Markov Model, focusing on how it differs from a Markov chain. An HMM is specified by the following components:

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

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

$$ a_{ij} $$

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

$ O = o_1o_2...o_T $ a sequence of $ T $ observations, each one drawn from a vocabulary $ V = v_1, v_2, ..., v_V $.

$ B = b_i(o_t) $ a sequence of observation likelihoods:, also called emission probabilities, each expressing the probability of an observation $ o_t $ being generated from a state i.

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

As we noted for Markov chains, an alternate representation that is sometimes used for HMMs doesn't rely on a start or end state, instead representing the distribution over initial and accepting states explicitly. We won't be using the $ \pi $ notation in this textbook, but you may see it in the literature:

$ \pi = \pi_1, \pi_2, ..., \pi_N $ an initial probability distribution over states. $ \pi_i $ is the probability that the Markov chain will start in state $ i $. Some states $ j $ may have $ \pi_j = 0 $, meaning that they cannot be initial states. Also, $ \sum_{i=1}^{n} \pi_i = 1 $

$$ Q A=\{q_{x},q_{y}...\}{}\quad\textrm{a set}Q A\subset Q\textrm{of}\textrm{legal}\textrm{accepting}\textrm{states} $$

A first-order Hidden Markov Model instantiated two simplifying assumptions. First, as with a first-order Markov chain, the probability of a particular state is dependent only on the previous state:

Markov Assumption:

$$ P(q_{i}|q_{1}...q_{i-1})=P(q_{i}|q_{i-1}) $$

Second, the probability of an output observation $ o_{i} $ is dependent only on the state that produced the observation $ q_{i} $, and not on any other states or any other observations:

$$ P(o_{i}|q_{1}\ldots q_{i},\ldots,q_{T},o_{1},\ldots,o_{i},\ldots,o_{T})=P(o_{i}|q_{i}) $$

Fig. 6.3 shows a sample HMM for the ice cream task. The two hidden states (H and C) correspond to hot and cold weather, while the observations (drawn from the alphabet $ O = \{1,2,3\} $) correspond to the number of ice creams eaten by Jason on a given day.

Notice that in the HMM in Fig. 6.3, there is a (non-zero) probability of transitioning between any two states. Such an HMM is called a fully-connected or ergodic HMM. Sometimes, however, we have HMMs in which many of the transitions between states have zero probability. For example, in left-to-right (also called Bakis) HMMs, the state transitions proceed from left to right, as shown in Fig. 6.4. In a Bakis HMM,

there are no transitions going from a higher-numbered state to a lower-numbered state (or, more accurately, any transitions from a higher-numbered state to a lower-numbered state have zero probability). Bakis HMMs are generally used to model temporal processes like speech; we will see more of them in Ch. 9.

Now that we have seen the structure of an HMM, we turn to algorithms for computing things with them. An influential tutorial by Rabiner (1989), based on tutorials by Jack Ferguson in the 1960s, introduced the idea that Hidden Markov Models should be characterized by three fundamental problems:

Problem 1 (Computing Likelihood): Given an HMM $ \lambda = (A, B) $ and an observation sequence $ O $, determine the likelihood $ P(O | \lambda) $.

Problem 2 (Decoding): Given an observation sequence $ O $ and an HMM $ \lambda = (A, B) $, discover the best hidden state sequence $ Q $.

Problem 3 (Learning): Given an observation sequence O and the set of states in the HMM, learn the HMM parameters A and B.

We already saw an example of problem (2) in Ch. 5. In the next three sections we introduce all three problems more formally.

6.3 COMPUTING LIKELIHOOD: THE FORWARD ALGORITHM

Our first problem is to compute the likelihood of a particular observation sequence. For example, given the HMM in Fig. 6.2b, what is the probability of the sequence 313? More formally:

Computing Likelihood: Given an HMM $ \lambda = (A, B) $ and an observation sequence $ O $, determine the likelihood $ P(O|\lambda) $.

For a Markov chain, where the surface observations are the same as the hidden events, we could compute the probability of 3/3 just by following the states labeled 3/3 and multiplying the probabilities along the arcs. For a Hidden Markov Model, things are not so simple. We want to determine the probability of an ice-cream observation sequence like 3/3, but we don't know what the hidden state sequence is!

Let's start with a slightly simpler situation. Suppose we already knew the weather, and wanted to predict how much ice cream Jason would eat. This is a useful part of many HMM tasks. For a given hidden state sequence (e.g. hot hot cold) we can easily compute the output likelihood of 313.

Let's see how. First, recall that for Hidden Markov Models, each hidden state produces only a single observation. Thus the sequence of hidden states and the sequence of observations have the same length. $ ^{1} $

Given this one-to-one mapping, and the Markov assumptions expressed in Eq. 6.6, for a particular hidden state sequence $ Q = q_0, q_1, q_2, ..., q_T $ and an observation sequence $ O = o_1, o_2, ..., o_T $, the likelihood of the observation sequence is:

$$ P(O|Q)=\prod_{i=1}^{T}P(o_{i}|q_{i}) $$

The computation of the forward probability for our ice-cream observation 3 1 3 from one possible hidden state sequence hot hot cold is as follows (Fig. 6.5 shows a graphic representation of this):

$$ P(3\ 1\ 3|\mathrm{hot\ hot\ cold})\ =P(3|\mathrm{hot})\times P(1|\mathrm{hot})\times P(3|\mathrm{cold}) $$

But of course, we don't actually know what the hidden state (weather) sequence was. We'll need to compute the probability of ice-cream events 3/3 instead by summing over all possible weather sequences, weighted by their probability. First, let's

compute the joint probability of being in a particular weather sequence Q and generating a particular sequence O of ice-cream events. In general, this is:

$$ P(O,Q)=P(O|Q)\times P(Q)=\prod_{i=1}^{n}P(o_{i}|q_{i})\times\prod_{i=1}^{n}P(q_{i}|q_{i-1}) $$

The computation of the joint probability of our ice-cream observation 3 1 3 and one possible hidden state sequence hot hot cold is as follows (Fig. 6.6 shows a graphic representation of this):

$$ \begin{aligned}P(3\ 1\ 3,hot\ hot\ cold)\ &=\ P(hot|start)\times P(hot|hot)\times P(cold|hot)\\&\quad\times P(3|hot)\times P(1|hot)\times P(3|cold)\end{aligned} $$

Now that we know how to compute the joint probability of the observations with a particular hidden state sequence, we can compute the total probability of the observations just by summing over all possible hidden state sequences:

$$ P(O)=\sum_{Q}P(O,Q)=\sum_{Q}P(O|Q)P(Q) $$

For our particular case, we would sum over the 8 three-event sequences cold cold cold, cold cold hot, i.e.:

$$ P(3\;1\;3)=P(3\;1\;3,\mathrm{c o l d}\;\mathrm{c o l d}\;\mathrm{c o l d})+P(3\;1\;3,\mathrm{c o l d}\;\mathrm{c o l d}\;\mathrm{h o t})+P(3\;1\;3,\mathrm{h o t}\;\mathrm{h o t}\;\mathrm{c o l d})+\ldots $$

For an HMM with $N$ hidden states and an observation sequence of $T$ observations, there are $N^{T}$ possible hidden sequences. For real tasks, where $N$ and $T$ are both large, $N^{T}$ is a very large number, and so we cannot compute the total observation likelihood by computing a separate observation likelihood for each hidden state sequence and then summing them up.

Instead of using such an extremely exponential algorithm, we use an efficient $ (O(N^{2}T)) $ algorithm called the forward algorithm. The forward algorithm is a kind of dynamic programming algorithm, i.e., an algorithm that uses a table to store intermediate values as it builds up the probability of the observation sequence. The forward algorithm computes the observation probability by summing over the probabilities of all possible hidden state paths that could generate the observation sequence, but it does so efficiently by implicitly folding each of these paths into a single forward trellis.

Fig. 6.7 shows an example of the forward trellis for computing the likelihood of 313 given the hidden state sequence hot hot cold.

Each cell of the forward algorithm trellis $ \alpha_t(j) $ represents the probability of being in state $ j $ after seeing the first $ t $ observations, given the automaton $ \lambda $. The value of each cell $ \alpha_t(j) $ is computed by summing over the probabilities of every path that could lead us to this cell. Formally, each cell expresses the following probability:

$$ \alpha_{t}(j)=P(o_{1},o_{2}\ldots o_{t},q_{t}=j|\lambda) $$

Here $q_t = j$ means “the probability that the $t$th state in the sequence of states is state $j$”. We compute this probability by summing over the extensions of all the paths that lead to the current cell. For a given state $q_j$ at time $t$, the value $\alpha_t(j)$ is computed as:

$$ \alpha_{t}(j)=\sum_{i=1}^{N}\alpha_{t-1}(i)a_{ij}b_{j}(o_{t}) $$

The three factors that are multiplied in Eq 6.15 in extending the previous paths to compute the forward probability at time t are:

$ \alpha_{t-1}(i) $ the previous forward path probability from the previous time step

$ a_{ij} $ the transition probability from previous state $ q_{i} $ to current state $ q_{j} $

$ b_{j}(o_{t}) $ the state observation likelihood of the observation symbol $ o_{t} $ given the current state j

Consider the computation in Fig. 6.7 of $\alpha_2(1)$, the forward probability of being at time step 2 in state 1 having generated the partial observation 3/1. This is computed by extending the $\alpha$ probabilities from time step 1, via two paths, each extension consisting of the three factors above: $\alpha_1(1) \times P(H|H) \times P(1|H)$ and $\alpha_1(2) \times P(H|C) \times P(1|H)$.

Fig. 6.8 shows another visualization of this induction step for computing the value in one new cell of the trellis.

We give two formal definitions of the forward algorithm; the pseudocode in Fig. 6.9 and a statement of the definitional recursion here:

1. Initialization:

$$ \alpha_{1}(j)\;=\;a_{0j}b_{j}(o_{1})\;1\leq j\leq N $$

2. Recursion (since states 0 and F are non-emitting):

$$ \alpha_{t}(j)=\sum_{i=1}^{N}\alpha_{t-1}(i)a_{ij}b_{j}(o_{t});\quad1\leq j\leq N,1

3. Termination:

$$ P(O|\lambda)=\alpha_{T}(q_{F})=\sum_{i=1}^{N}\alpha_{T}(i)a_{iF} $$

function FORWARD(observations of len T, state-graph of len N) returns forward-prob

create a probability matrix forward[N+2,T]

for each state s from 1 to N do

forward[s,1] ← $a_{0,s} * b_{s}(o_{1})$

for each time step t from 2 to T do

for each state s from 1 to N do

forward[s,t] ← $\sum_{s=1}^{N} \text{forward}[s',t-1] * a_{s',s} * b_{s}(o_{t})$

forward[qF,T] ← $\sum_{s=1}^{N} \text{forward}[s,T] * a_{s,qF}$

return forward[qF,T]

6.4 DECODING: THE VITERBI ALGORITHM

For any model, such as an HMM, that contains hidden variables, the task of determining which sequence of variables is the underlying source of some sequence of observations is called the decoding task. In the ice cream domain, given a sequence of ice cream observations 313 and an HMM, the task of the decoder is to find the best hidden

weather sequence $ (H\ H\ H) $. More formally,

Decoding: Given as input an HMM $ \lambda = (A, B) $ and a sequence of observations $ O = o_1, o_2, ..., o_T $, find the most probable sequence of states $ Q = q_1 q_2 q_3 \ldots q_T $.

We might propose to find the best sequence as follows: for each possible hidden state sequence (HHH, HHC, HCH, etc.), we could run the forward algorithm and compute the likelihood of the observation sequence given that hidden state sequence. Then we could choose the hidden state sequence with the max observation likelihood. It should be clear from the previous section that we cannot do this because there are an exponentially large number of state sequences!

Instead, the most common decoding algorithms for HMMs is the Viterbi algorithm. Like the forward algorithm, Viterbi is a kind of dynamic programming, and makes use of a dynamic programming trellis. Viterbi also strongly resembles another dynamic programming variant, the minimum edit distance algorithm of Ch. 3.

Fig. 6.10 shows an example of the Viterbi trellis for computing the best hidden state sequence for the observation sequence $ 3\,l\,3 $. The idea is to process the observation sequence left to right, filling out the trellis. Each cell of the Viterbi trellis, $ \nu_t(j) $ represents the probability that the HMM is in state $ j $ after seeing the first $ t $ observations and passing through the most probable state sequence $ q_0, q_1, ..., q_{t-1} $, given the automaton $ \lambda $. The value of each cell $ \nu_t(j) $ is computed by recursively taking the most probable path that could lead us to this cell. Formally, each cell expresses the following probability:

$$ v_{t}(j)=\max_{q_{0},q_{1},\ldots,q_{t-1}}P(q_{0},q_{1}\ldots q_{t-1},o_{1},o_{2}\ldots o_{t},q_{t}=j|\lambda) $$

Note that we represent the most probable path by taking the maximum over all possible previous state sequences $ \max_{q_{0}, q_{1}, \ldots, q_{t-1}} $. Like other dynamic programming algorithms, Viterbi fills each cell recursively. Given that we had already computed the probability of being in every state at time $ t-1 $, We compute the Viterbi probability by taking the most probable of the extensions of the paths that lead to the current cell. For a given state $ q_j $ at time $ t $, the value $ \nu_t(j) $ is computed as:

$$ v_{t}(j)=\max_{i=1}^{N}v_{t-1}(i)a_{ij}b_{j}(o_{t}) $$

The three factors that are multiplied in Eq. 6.20 for extending the previous paths to compute the Viterbi probability at time t are:

$ v_{t-1}(i) $ the previous Viterbi path probability from the previous time step $ a_{ij} $ the transition probability from previous state $ q_{i} $ to current state $ q_{j} $

$ b_{j}(o_{t}) $ the state observation likelihood of the observation symbol $ o_{t} $ given the current state j

Fig. 6.11 shows pseudocode for the Viterbi algorithm. Note that the Viterbi algorithm is identical to the forward algorithm except that it takes the $ \max $ over the previous path probabilities where the forward algorithm takes the $ \sum n $. Note also that the Viterbi algorithm has one component that the forward algorithm doesn't have: backpointers. This is because while the forward algorithm needs to produce an observation likelihood, the Viterbi algorithm must produce a probability and also the most likely state sequence. We compute this best state sequence by keeping track of the path of hidden states that led to each state, as suggested in Fig. 6.12, and then at the end tracing back the best path to the beginning (the Viterbi backtrace).

Finally, we can give a formal definition of the Viterbi recursion as follows:

1. Initialization:

$$ v_{1}(j)=a_{0j}b_{j}(o_{1})1\leq j\leq N $$

$$ bt_{1}(j)=0 $$

function VITERBI(observations of len T, state-graph of len N) returns best-path

create a path probability matrix viterbi[N+2,T]

for each state s from 1 to N do

viterbi[s,1]←a_{0,s} * b_{s}(o_{1})

backpointer[s,1]←0

for each time step t from 2 to T do

for each state s from 1 to N do

viterbi[s,t]←max_{t=1}^{N} viterbi[s',t-1] * a_{s',s} * b_{s}(o_{t})

backpointer[s,t]←argmax_{t=1}^{N} viterbi[s',t-1] * a_{s',s}

viterbi[q_{F},T]←max_{t=1}^{N} viterbi[s,T] * a_{s,q_{F}}

backpointer[q_{F},T]←argmax_{t=1}^{N} viterbi[s,T] * a_{s,q_{F}}

return the backtrace path by following backpointers to states back in time from backpointer[q_{F},T]

Figure 6.11 Viterbi algorithm for finding optimal sequence of hidden states. Given an observation sequence and an HMM $ \lambda = (A, B) $ the algorithm returns the state-path through

Figure 6.11 Viterbi algorithm for finding optimal sequence of hidden states. Given an observation sequence and an HMM $ \lambda = (A, B) $, the algorithm returns the state-path through the HMM which assigns maximum likelihood to the observation sequence. Note that states 0 and $ q_{F} $ are non-emitting.

2. Recursion (recall states 0 and $q_{F}$ are non-emitting):

$$ v_{t}(j)=\max_{i=1}^{N}v_{t-1}(i)a_{ij}b_{j}(o_{t});1\leq j\leq N,1

$$ \begin{array}{c} bt_{t}(j)\;=\;\underset{i=1}{\operatorname*{a r g m a x}}\nu_{t-1}(i)a_{i j}b_{j}(o_{t});\quad1\leq j\leq N,1

3. Termination:

$$ \begin{array}{c} The~best~score:\quad P*=v_{t}(q_{F})~=~\max\limits_{i=1}^{N}v_{T}(i)*a_{i,F}\end{array} $$

The start of backtrace: $ q_T^* = bt_T(q_F) = \underset{i=1}{argmax} v_T(i) * a_{i,F} $

6.5 TRAINING HMMs: THE FORWARD-BACKWARD ALGORITHM

We turn to the third problem for HMMs: learning the parameters of an HMM, i.e., the A and B matrices. Formally,

Learning: Given an observation sequence O and the set of possible states in the HMM, learn the HMM parameters A and B.

The input to such a learning algorithm would be an unlabeled sequence of observations O and a vocabulary of potential hidden states Q. Thus for the ice cream task,

we would start with a sequence of observations $ O = \{1,3,2,...,\} $, and the set of hidden states $ H $ and $ C $. For the part-of-speech tagging task we would start with a sequence of observations $ O = \{w_1,w_2,w_3...\} $ and a set of hidden states NN, NNS, VBD, IN,... and so on.

The standard algorithm for HMM training is the forward-backward or Baum-Welch algorithm (Baum, 1972), a special case of the Expectation-Maximization or EM algorithm (Dempster et al., 1977). The algorithm will let us train both the transition probabilities A and the emission probabilities B of the HMM.

Let us begin by considering the much simpler case of training a Markov chain rather than a Hidden Markov Model. Since the states in a Markov chain are observed, we can run the model on the observation sequence and directly see which path we took through the model, and which state generated each observation symbol. A Markov chain of course has no emission probabilities $B$ (alternatively we could view a Markov chain as a degenerate Hidden Markov Model where all the $b$ probabilities are 1.0 for the observed symbol and 0 for all other symbols.). Thus the only probabilities we need to train are the transition probability matrix $A$.

We get the maximum likelihood estimate of the probability $ a_{ij} $ of a particular transition between states i and j by counting the number of times the transition was taken.

which we could call $ C(i \to j) $, and then normalizing by the total count of all times we took any transition from state i:

$$ a_{ij}=\frac{C(i\rightarrow j)}{\sum_{q\in Q}C(i\rightarrow q)} $$

We can directly compute this probability in a Markov chain because we know which states we were in. For an HMM we cannot compute these counts directly from an observation sequence since we don't know which path of states was taken through the machine for a given input. The Baum-Welch algorithm uses two neat intuitions to solve this problem. The first idea is to iteratively estimate the counts. We will start with an estimate for the transition and observation probabilities, and then use these estimated probabilities to derive better and better probabilities. The second idea is that we get our estimated probabilities by computing the forward probability for an observation and then dividing that probability mass among all the different paths that contributed to this forward probability.

In order to understand the algorithm, we need to define a useful probability related to the forward probability, called the backward probability.

The backward probability $ \beta $ is the probability of seeing the observations from time $ t+1 $ to the end, given that we are in state i at time t (and of course given the automaton $ \lambda $):

$$ \boldsymbol{\beta}_{t}(i)=\boldsymbol{P}(o_{t+1},o_{t+2}\ldots o_{T}|\boldsymbol{q}_{t}=i,\boldsymbol{\lambda}) $$

It is computed inductively in a similar manner to the forward algorithm.

1. Initialization:

$$ \beta_{T}(i)~=~a_{i,F},~~1\leq i\leq N $$

2. Recursion (again since states 0 and $q_{F}$ are non-emitting):

$$ \beta_{t}(i)=\sum_{j=1}^{N}a_{ij}b_{j}(o_{t+1})\beta_{t+1}(j),\quad1\leq i\leq N,1\leq t

3. Termination:

$$ P(O|\lambda)=\alpha_{T}(q_{F})=\beta_{1}(0)=\sum_{j=1}^{N}a_{0j}b_{j}(o_{1})\beta_{1}(j) $$

Fig. 6.13 illustrates the backward induction step.

We are now ready to understand how the forward and backward probabilities can help us compute the transition probability $ a_{ij} $ and observation probability $ b_{i}(o_{t}) $ from an observation sequence, even though the actual path taken through the machine is hidden.

Let's begin by showing how to estimate $ \hat{a}_{ij} $ by a variant of (6.27):

$$ \hat{a}_{i j}=\frac{\mathrm{e x p e c t e d~n u m b e r~o f~t r a n s i t i o n s~f r o m~s t a t e~}i\mathrm{~t o~s t a t e~}j}{\mathrm{e x p e c t e d~n u m b e r~o f~t r a n s i t i o n s~f r o m~s t a t e~}i} $$

How do we compute the numerator? Here’s the intuition. Assume we had some estimate of the probability that a given transition $ i \to j $ was taken at a particular point in time t in the observation sequence. If we knew this probability for each particular time t, we could sum over all times t to estimate the total count for the transition $ i \to j $.

More formally, let's define the probability $ \xi_t $ as the probability of being in state $ i $ at time $ t $ and state $ j $ at time $ t+1 $, given the observation sequence and of course the model:

$$ \xi_{t}(i,j)=\boldsymbol{P}(q_{t}=i,q_{t+1}=j|\boldsymbol{O},\boldsymbol{\lambda}) $$

In order to compute $ \xi_t $, we first compute a probability which is similar to $ \xi_t $, but differs in including the probability of the observation; note the different conditioning of $ O $ from Equation (6.33):

$$ \mathrm{not-quite-}\xi_{t}(i,j)=P(q_{t}=i,q_{t+1}=j,O|\lambda) $$

Fig. 6.14 shows the various probabilities that go into computing not-quite- $ \xi_t $: the transition probability for the arc in question, the $ \alpha $ probability before the arc, the $ \beta $ probability after the arc, and the observation probability for the symbol just after the arc. These four are multiplied together to produce not-quite- $ \xi_t $ as follows:

$$ \mathrm{not-quite}-\xi_{t}(i,j)=\alpha_{t}(i)a_{ij}b_{j}(o_{t+1})\beta_{t+1}(j) $$

In order to compute $ \xi_t $ from not-quite- $ \xi_t $, the laws of probability instruct us to divide by $ P(O|\lambda) $, since:

$$ P(X|Y,Z)=\frac{P(X,Y|Z)}{P(Y|Z)} $$

The probability of the observation given the model is simply the forward probability of the whole utterance, (or alternatively the backward probability of the whole utterance!), which can thus be computed in a number of ways:

$$ P(O|\lambda)=\alpha_{T}(N)=\beta_{T}(1)=\sum_{j=1}^{N}\alpha_{t}(j)\beta_{t}(j) $$

So, the final equation for $ \xi_{t} $ is:

$$ \xi_{t}(i,j)=\frac{\alpha_{t}(i)a_{ij}b_{j}(o_{t+1})\beta_{t+1}(j)}{\alpha_{T}(N)} $$

The expected number of transitions from state $i$ to state $j$ is then the sum over all $t$ of $\xi$. For our estimate of $a_{ij}$ in (6.32), we just need one more thing: the total expected number of transitions from state $i$. We can get this by summing over all transitions out of state $i$. Here's the final formula for $\hat{a}_{ij}$:

$$ \hat{a}_{i j}=\frac{\sum_{t=1}^{T-1}\xi_{t}(i,j)}{\sum_{t=1}^{T-1}\sum_{j=1}^{N}\xi_{t}(i,j)} $$

We also need a formula for recomputing the observation probability. This is the probability of a given symbol $ \nu_{k} $ from the observation vocabulary V, given a state $ j $: $ \hat{b}_{j}(\nu_{k}) $. We will do this by trying to compute:

$$ \hat{b}_{j}(v_{k})=\frac{\mathrm{e x p e c t e d~n u m b e r~o f~t i m e s~i n~s t a t e~}j\mathrm{~a n d~o b s e r v i n g~s y m b o l~}v_{k}}{\mathrm{e x p e c t e d~n u m b e r~o f~t i m e s~i n~s t a t e~}j} $$

For this we will need to know the probability of being in state $j$ at time $t$, which we will call $\gamma_{t}(j)$:

$$ \Upsilon_{t}(j)=P(q_{t}=j|\boldsymbol{O},\lambda) $$

Once again, we will compute this by including the observation sequence in the probability:

$$ \gamma_{t}(j)=\frac{P(q_{t}=j,O|\lambda)}{P(O|\lambda)} $$

As Fig. 6.15 shows, the numerator of (6.42) is just the product of the forward probability and the backward probability:

$$ \gamma_{t}(j)=\frac{\alpha_{t}(j)\beta_{t}(j)}{P(O|\lambda)} $$

We are ready to compute $b$. For the numerator, we sum $\gamma_t(j)$ for all time steps $t$ in which the observation $o_t$ is the symbol $\nu_k$ that we are interested in. For the denominator, we sum $\gamma_t(j)$ over all time steps $t$. The result will be the percentage of the times that we were in state $j$ and we saw symbol $\nu_k$ (the notation $\sum_{t=1s,t,O_t=\nu_k}^T$ means “sum over all $t$ for which the observation at time $t$ was $\nu_k$”):

$$ \hat{b}_{j}(\nu_{k})=\frac{\sum_{t=1s.t.O_{t}=\nu_{k}}^{T}\gamma_{t}(j)}{\sum_{t=1}^{T}\gamma_{t}(j)} $$

We now have ways in (6.39) and (6.44) to re-estimate the transition A and observation B probabilities from an observation sequence O assuming that we already have a previous estimate of A and B.

These re-estimations form the core of the iterative forward-backward algorithm.

The forward-backward algorithm starts with some initial estimate of the HMM parameters $ \lambda = (A, B) $. We then iteratively run two steps. Like other cases of the EM (expectation-maximization) algorithm, the forward-backward algorithm has two steps: the expectation step, or E-step, and the maximization step, or M-step.

In the E-step, we compute the expected state occupancy count $ \gamma $ and the expected state transition count $ \xi $, from the earlier A and B probabilities. In the M-step, we use $ \gamma $ and $ \xi $ to recompute new A and B probabilities.

function FORWARD-BACKWARD( observations of len T, output vocabulary V, hidden state set Q) returns HMM=(A,B)

$$ \gamma_{t}(j)=\frac{\alpha_{t}(j)\beta_{t}(j)}{P(O|\lambda)}\forall t\text{and}j $$

$$ \xi_{t}(i,j)=\frac{\alpha_{t}(i)a_{ij}b_{j}(o_{t+1})\beta_{t+1}(j)}{\alpha_{T}(N)}\forall t,i,and j $$

M-step

$$ \hat{a}_{i j}=\frac{\displaystyle\sum_{t=1}^{T-1}\xi_{t}(i,j)}{\displaystyle\sum_{t=1}^{T-1}\sum_{j=1}^{N}\xi_{t}(i,j)} $$

$$ \hat{b}_{j}(\nu_{k})=\frac{\displaystyle\sum_{t=1s.t.O_{t}=\nu_{k}}^{T}\gamma_{t}(j)}{\displaystyle\sum_{t=1}^{T}\gamma_{t}(j)} $$

Although in principle the forward-backward algorithm can do completely unsupervised learning of the A and B parameters, in practice the initial conditions are very important. For this reason the algorithm is often given extra information. For example, for speech recognition, in practice the HMM structure is very often set by hand, and only the emission (B) and (non-zero) A transition probabilities are trained from a set of observation sequences O. Sec. ?? in Ch. 9 will also discuss how initial A and B estimates are derived in speech recognition. We will also see that for speech that the forward-backward algorithm can be extended to inputs which are non-discrete (“continuous observation densities”).

6.6 MAXIMUM ENTROPY MODELS: BACKGROUND

We turn now to a second probabilistic machine learning framework called Maximum Entropy modeling, MaxEnt for short. MaxEnt is more widely known as multinomial logistic regression.

Our goal in this chapter is to introduce the use of MaxEnt for sequence classification. Recall that the task of sequence classification or sequence labelling is to assign a label to each element in some sequence, such as assigning a part-of-speech tag to a word. The most common MaxEnt sequence classifier is the Maximum Entropy Markov Model or MEMM, to be introduced in Sec. 6.8. But before we see this use of MaxEnt as a sequence classifier, we need to introduce non-sequential classification.

The task of classification is to take a single observation, extract some useful features describing the observation, and then based on these features, to classify the observation into one of a set of discrete classes. A probabilistic classifier does slightly more than this; in addition to assigning a label or class, it gives the probability of the observation being in that class; indeed, for a given observation a probabilistic classifier gives a probability distribution over all classes.

Such non-sequential classification tasks occur throughout speech and language processing. For example, in text classification we might need to decide whether a particular email should be classified as spam or not. In sentiment analysis we have to determine whether a particular sentence or document expresses a positive or negative opinion. In many tasks, we'll need to know where the sentence boundaries are, and so we'll need to classify a period character ('·') as either a sentence boundary or not. We'll see more examples of the need for classification throughout this book.

MaxEnt belongs to the family of classifiers known as the exponential or log-linear classifiers. MaxEnt works by extracting some set of features from the input, combining them linearly (meaning that we multiply each by a weight and then add them up), and then, for reasons we will see below, using this sum as an exponent.

Let's flesh out this intuition just a bit more. Assume that we have some input x (perhaps it is a word that needs to be tagged, or a document that needs to be classified) from which we extract some features. A feature for tagging might be this word ends in -ing or the previous word was 'the'. For each such feature $ f_i $, we have some weight $ w_i $.

Given the features and weights, our goal is to choose a class (for example a part-of-speech tag) for the word. MaxEnt does this by choosing the most probable tag; the probability of a particular class c given the observation x is:

$$ p(c|x)~=~\frac{1}{Z}\mathrm{e x p}(\sum_{i}w_{i}f_{i}) $$

Here $Z$ is a normalizing factor, used to make the probabilities correctly sum to 1; and as usual $\exp(x) = e^{x}$. As we'll see later, this is a simplified equation in various ways; for example in the actual MaxEnt model the features $f$ and weights $w$ are both dependent on the class $c$ (i.e., we'll have different features and weights for different classes).

In order to explain the details of the MaxEnt classifier, including the definition

of the normalizing term Z and the intuition of the exponential function, we'll need to understand first linear regression, which lays the groundwork for prediction using features, and logistic regression, which is our introduction to exponential models. We cover these areas in the next two sections. Readers who have had a grounding in these kinds of regression may want to skip the next two sections. Then in Sec. 6.7 we introduce the details of the MaxEnt classifier. Finally in Sec. 6.8 we show how the MaxEnt classifier is used for sequence classification in the Maximum Entropy Markov Model or MEMM.