Tagging and Sequences
Computational Linguistics
Course 1 Β· Chapter 7 Β· Tagging and Sequences
Chapter 6 needed to know that saw was a verb and telescope a noun, and it got that from a hand-written lexicon. This chapter asks how a program can assign such labels to running text, when the same word can carry different labels in different sentences. It is one of the oldest tasks in the field, and it shows the choice between hand-written rules and counted statistics in miniature.
Parts of Speech as Labels
Wikipedia's Part of speech article defines a part of speech as a category of words with similar grammatical properties, sharing syntactic behaviour and sometimes morphological and semantic behaviour. It separates open classes, which "commonly accept the addition of new words" (typically nouns, verbs, adjectives, adverbs, interjections), from closed classes that rarely gain members (typically prepositions, determiners, conjunctions, pronouns). It says "almost all languages have the word classes noun and verb" but that other classes vary: Japanese has more adjective classes than English, and some languages lack a clear adjective class. It also says many English words can belong to more than one part of speech, with neigh, break and telephone as verb-or-noun examples, a shift it calls conversion or zero derivation.
The Part-of-speech tagging article defines the task as marking each word in a corpus as a particular part of speech "based on both its definition and its context". Its points about the labels themselves:
- Tagsets are bigger than school grammar. Schools teach about 9 English parts of speech; computational tagging typically distinguishes "50 to 150 separate parts of speech for English".
- Different corpora, different tagsets. The article names the Brown and LOB tagsets, says the Penn tagset is the most popular for American English and is "much smaller", and says Petrov and colleagues proposed a universal tagset of 12 categories. It adds that smaller tagsets make automatic tagging easier.
- Why it is hard. Many word forms are ambiguous. Its example: dogs is usually a plural noun but is a verb in The sailor dogs the hatch.
To keep the code short, this chapter uses only seven labels: DET, NOUN, VERB, AUX, ADJ, PRON and ADP. They are my own simplification, not any published tagset.
A Tiny Corpus and a Baseline
The corpus below is mine: ten invented sentences, 48 tokens, tagged by hand. It is chosen so that light and watch are each both noun and verb, as in Chapter 3's lighthouse theme. Real taggers are trained on corpora such as the Brown Corpus (Chapter 3), thousands of times larger.
The simplest tagger gives every word its most frequent tag in the training data, and gives unseen words NOUN. I ran everything in this chapter with py -X utf8 and copied the output.
The baseline gets watch and light right in the second sentence and light wrong in the first (we light the lamp): it always says NOUN for light. The tagging article reports the same idea at full scale: giving each word its most common tag, and "proper noun" to unknown words, "will approach 90% accuracy" (it cites Charniak, 1997). So the baseline is strong, and the remaining errors are the ambiguous words.
Two Families of Tagger
The tagging article says algorithms fall into two groups, rule-based and stochastic. Its history gives the shape of the story:
| When | What the article says |
|---|---|
| Mid-1960s | The Brown Corpus, about 1,000,000 words, built by KuΔera and Francis; Greene and Rubin's first program was about 70% correct, and hand correction made it nearly perfect by the late 1970s |
| Mid-1980s | European researchers used hidden Markov models on the Lancaster-Oslo-Bergen Corpus; the CLAWS tagger enumerated all possibilities and reached "93-95%", at high cost |
| 1987 | DeRose and Church independently developed faster Viterbi-like dynamic-programming algorithms, both reporting over 95%; the field then treated tagging as separable from other levels of NLP |
| Later | Machine-learning methods (support vector machines, maximum entropy, perceptron, nearest-neighbour) reported above 95% (the article marks this claim "citation needed"); one 2014 result is given as 97.36% on a standard benchmark |
Rule-based: the Brill tagger
Wikipedia's Brill tagger article says Eric Brill described it in his 1993 PhD thesis, as an "error-driven transformation-based tagger". It first gives each known word its most frequent tag (and unknown words NOUN, which the article calls naive), then applies contextual rules that change tags by looking at small amounts of surrounding context, until a threshold is reached or no rule applies. Rules have the form tag1 β tag2 IF condition. Its example changes while from a preposition to a noun when the previous word is a determiner, as in all the while. It says rules are simple to implement as finite-state machines (compare Chapter 4) and typical taggers use "a few hundred rules", written by intuition or learned from a tagged corpus. The page does not describe rule templates in detail or list advantages, so I say nothing more about them.
Below is one rule of that style, written by me, applied after the baseline: change NOUN to VERB when the previous tag is PRON or AUX and the word has been seen as a verb.
Statistical: a hidden Markov model
The statistical alternative asks which whole tag sequence is most probable. A bigram HMM tagger scores a sequence by multiplying, for each word, the chance of the tag following the previous tag (Chapter 5's idea, applied to tags) by the chance of the tag producing the word. Trying every sequence would be slow; the Viterbi algorithm, named in the tagging article, finds the best one by dynamic programming. The code below is my own short version, with a small smoothing constant of 0.01 (Chapter 5) so unseen combinations do not score zero. I have not implemented CLAWS, Brill's learner or any named published tagger, and do not claim this equals them.
Both fix we light the lamp: after we (a pronoun), light becomes a verb, whether by my one rule or by the counted tag-to-tag chances. The Viterbi tagger also keeps watch a verb and light a noun in the longer sentence.
Scoring It, and Why Not to Trust This Score
I wrote five new sentences, tagged by hand, and counted correct tags (24 tokens in all): baseline 22 of 24, baseline plus the rule 24 of 24, Viterbi 24 of 24. This does not show the methods are equally good. The test sentences reuse the training words and patterns, there are only 24 tokens, and I wrote both the sets and the rule after seeing the errors. Chapter 9 returns to how to measure honestly.
Where neighbours still fail
One more run shows that context and statistics have limits when training data is tiny:
The Viterbi tagger calls the final light a preposition. I checked the counts: in the 48 training tokens, VERB is followed by a determiner 6 times, an adjective 2 times, a preposition once, and a noun never. So VERB followed directly by NOUN gets only the smoothing amount, and the tag ADP (seen only on the word on) can win. Which tag is "right" for this odd sentence is my judgement; the point is that the answer rests on the counts.
py -X utf8. I did not read the Hidden Markov model, Viterbi algorithm or Penn Treebank articles, so nothing is said about them beyond what the tagging article states. Machine-learning taggers are covered in NLP 7 (named entity recognition and part-of-speech tagging), which I have not re-read for this chapter.
Try It Yourself
Tag the keeper climbed the stairs with the baseline and with viterbi. Which words are unseen, and how does each tagger treat them? Then write a suffix rule (a word ending in -ed that is unseen becomes VERB) and apply it after the baseline.
Run brill and viterbi on the lamp will watch light. Explain why the two taggers disagree on the last word, and what you would add to the training data to fix it.
The chapter's own score is 24 of 24 for two taggers. List three reasons that score is weak evidence, and say what a better test would look like.
π View solutionChapter 7 Quick Reference
- Tagging: one label per token, chosen from a tagset (computational tagsets typically 50-150 tags for English)
- Baseline: most frequent tag per word; unknown words guessed as noun
- Brill: start from the baseline, then apply context rules "tag1 to tag2 IF condition"
- HMM + Viterbi: find the most probable whole tag sequence by dynamic programming
- Small test sets that overlap the training data prove very little