程序代写代做代考 scheme information theory Hidden Markov Mode algorithm Bayesian chain AI Speech and Language Processing. Daniel Jurafsky & James H. Martin. Copyright c© 2016. All

wi wi+1wi-1

ti-1ti-2

wi-1

Figure 10.12 An MEMM for part-of-speech tagging showing the ability to condition on
more features.

A basic MEMM part-of-speech tagger conditions on the observation word it-
self, neighboring words, and previous tags, and various combinations, using feature
templates like the following:templates

〈ti,wi−2〉,〈ti,wi−1〉,〈ti,wi〉,〈ti,wi+1〉,〈ti,wi+2〉
〈ti, ti−1〉,〈ti, ti−2, ti−1〉,

〈ti, ti−1,wi〉,〈ti,wi−1,wi〉〈ti,wi,wi+1〉, (10.28)

18 CHAPTER 10 • PART-OF-SPEECH TAGGING

Recall from Chapter 8 that feature templates are used to automatically populate
the set of features from every instance in the training and test set. Thus our exam-
ple Janet/NNP will/MD back/VB the/DT bill/NN, when wi is the word back, would
generate the following features:

ti = VB and wi−2 = Janet
ti = VB and wi−1 = will
ti = VB and wi = back
ti = VB and wi+1 = the
ti = VB and wi+2 = bill
ti = VB and ti−1 = MD
ti = VB and ti−1 = MD and ti−2 = NNP
ti = VB and wi = back and wi+1 = the

Also necessary are features to deal with unknown words, expressing properties
of the word’s spelling or shape:

wi contains a particular prefix (from all prefixes of length ≤ 4)
wi contains a particular suffix (from all suffixes of length ≤ 4)
wi contains a number
wi contains an upper-case letter
wi contains a hyphen
wi is all upper case
wi’s word shape
wi’s short word shape
wi is upper case and has a digit and a dash (like CFC-12)
wi is upper case and followed within 3 words by Co., Inc., etc.

Word shape features are used to represent the abstract letter pattern of the wordword shape
by mapping lower-case letters to ‘x’, upper-case to ‘X’, numbers to ’d’, and retaining
punctuation. Thus for example I.M.F would map to X.X.X. and DC10-30 would
map to XXdd-dd. A second class of shorter word shape features is also used. In these
features consecutive character types are removed, so DC10-30 would be mapped to
Xd-d but I.M.F would still map to X.X.X. For example the word well-dressed would
generate the following non-zero valued feature values:

prefix(wi) = w
prefix(wi) = we
prefix(wi) = wel
prefix(wi) = well
suffix(wi) = ssed
suffix(wi) = sed
suffix(wi) = ed
suffix(wi) = d
has-hyphen(wi)
word-shape(wi) = xxxx-xxxxxxx
short-word-shape(wi) = x-x

Features for known words, like the templates in Eq. 10.28, are computed for ev-
ery word seen in the training set. The unknown word features can also be computed
for all words in training, or only on rare training words whose frequency is below
some threshold.

The result of the known-word templates and word-signature features is a very
large set of features. Generally a feature cutoff is used in which features are thrown
out if they have count < 5 in the training set. 10.5 • MAXIMUM ENTROPY MARKOV MODELS 19 Given this large set of features, the most likely sequence of tags is then computed by a MaxEnt model that combines these features of the input word wi, its neighbors within l words wi+li−l , and the previous k tags t i−1 i−k as follows: T̂ = argmax T P(T |W ) = argmax T ∏ i P(ti|wi+li−l , t i−1 i−k ) = argmax T ∏ i exp (∑ i wi fi(ti,w i+l i−l , t i−1 i−k ) ) ∑ t ′∈tagset exp (∑ i wi fi(t ′,wi+li−l , t i−1 i−k ) ) (10.29) 10.5.2 Decoding and Training MEMMs We’re now ready to see how to use the MaxEnt classifier to solve the decoding problem by finding the most likely sequence of tags described in Eq. 10.29. The simplest way to turn the MaxEnt classifier into a sequence model is to build a local classifier that classifies each word left to right, making a hard classification of the first word in the sentence, then a hard decision on the the second word, and so on. This is called a greedy decoding algorithm, because we greedily choose thegreedy best tag for each word, as shown in Fig. 10.13. function GREEDY MEMM DECODING(words W, model P) returns tag sequence T for i = 1 to length(W) t̂i = argmax t ′∈ T P(t ′ | wi+li−l , t i−1 i−k ) Figure 10.13 In greedy decoding we make a hard decision to choose the best tag left to right. The problem with the greedy algorithm is that by making a hard decision on each word before moving on to the next word, the classifier cannot temper its decision with information from future decisions. Although greedy algorithm is very fast, and we do use it in some applications when it has sufficient accuracy, in general this hard decision causes sufficient drop in performance that we don’t use it. Instead we decode an MEMM with the Viterbi algorithm just as we did with theViterbi HMM, thus finding the sequence of part-of-speech tags that is optimal for the whole sentence. Let’s see an example. For pedagogical purposes, let’s assume for this example that our MEMM is only conditioning on the previous tag ti−1 and observed word wi. Concretely, this involves filling an N×T array with the appropriate values for P(ti|ti−1,wi), maintaining backpointers as we proceed. As with HMM Viterbi, when the table is filled, we simply follow pointers back from the maximum value in the final column to retrieve the desired set of labels. The requisite changes from the HMM-style application of Viterbi have to do only with how we fill each cell. Recall from Eq. ?? that the recursive step of the Viterbi equation computes the Viterbi value of time t for state j as 20 CHAPTER 10 • PART-OF-SPEECH TAGGING vt( j) = N max i=1 vt−1(i)ai j b j(ot); 1≤ j ≤ N,1 < t ≤ T (10.30) which is the HMM implementation of vt( j) = N max i=1 vt−1(i) P(s j|si) P(ot |s j) 1≤ j ≤ N,1 < t ≤ T (10.31) The MEMM requires only a slight change to this latter formula, replacing the a and b prior and likelihood probabilities with the direct posterior: vt( j) = N max i=1 vt−1(i) P(s j|si,ot) 1≤ j ≤ N,1 < t ≤ T (10.32) Figure 10.14 shows an example of the Viterbi trellis for an MEMM applied to the ice-cream task from Section ??. Recall that the task is figuring out the hidden weather (hot or cold) from observed numbers of ice creams eaten in Jason Eisner’s diary. Figure 10.14 shows the abstract Viterbi probability calculation, assuming that we have a MaxEnt model that computes P(si|si−1,oi) for us. start H C H C H C end P(C |st art ,3) P(H|H,1) P(C|C,1) P(C|H,1) P(H |C,1 ) P( H| st ar t,3 ) v1(2)=P(H|start,3) v1(1) = P(C|start,3) v2(2)= max( P(H|H,1)*P(H|start,3), P(H|C,1)*P(C|start,3) ) v2(1) = max( P(C|H,1)*P(H|start,3), P(C|C,1)*P(C|start,3) ) start start start t C H end end end end H C start qend q2 q1 q0 o1 o2 o3 3 1 1 Figure 10.14 Inference from ice-cream eating computed by an MEMM instead of an HMM. The Viterbi trellis for computing the best path through the hidden state space for the ice-cream eating events 3 1 3, modified from the HMM figure in Fig. ??. Learning in MEMMs relies on the same supervised learning algorithms we pre- sented for logistic regression. Given a sequence of observations, feature functions, and corresponding hidden states, we train the weights so as maximize the log- likelihood of the training corpus. As with logistic regression, regularization is im- portant, and all modern systems use L1 or L2 regularization. 10.6 • BIDIRECTIONALITY 21 10.6 Bidirectionality The one problem with the MEMM and HMM models as presented is that they are exclusively run left-to-right. While the Viterbi algorithm still allows present deci- sions to be influenced indirectly by future decisions, it would help even more if a decision about word wi could directly use information about future tags ti+1 and ti+2. Adding bidirectionality has another useful advantage. MEMMs have a theoret- ical weakness, referred to alternatively as the label bias or observation bias prob-label bias observation bias lem (Lafferty et al. 2001, Toutanova et al. 2003). These are names for situations when one source of information is ignored because it is explained away by another source. Consider an example from (Toutanova et al., 2003), the sequence will/NN to/TO fight/VB. The tag TO is often preceded by NN but rarely by modals (MD), and so that tendency should help predict the correct NN tag for will. But the previ- ous transition P(twill |〈s〉) prefers the modal, and because P(TO|to, twill) is so close to 1 regardless of twill the model cannot make use of the transition probability and incorrectly chooses MD. The strong information that to must have the tag TO has ex- plained away the presence of TO and so the model doesn’t learn the importance of the previous NN tag for predicting TO. Bidirectionality helps the model by making the link between TO available when tagging the NN. One way to implement bidirectionality is to switch to a much more powerful model called a Conditional Random Field or CRF, which we will introduce inCRF Chapter 20. But CRFs are much more expensive computationally than MEMMs and don’t work any better for tagging, and so are not generally used for this task. Instead, other ways are generally used to add bidirectionality. The Stanford tag- ger uses a bidirectional version of the MEMM called a cyclic dependency networkStanford tagger (Toutanova et al., 2003). Alternatively, any sequence model can be turned into a bidirectional model by using multiple passes. For example, the first pass would use only part-of-speech fea- tures from already-disambiguated words on the left. In the second pass, tags for all words, including those on the right, can be used. Alternately, the tagger can be run twice, once left-to-right and once right-to-left. In greedy decoding, for each word the classifier chooses the highest-scoring of the tag assigned by the left-to-right and right-to-left classifier. In Viterbi decdoing, the classifier chooses the higher scoring of the two sequences (left-to-right or right-to-left). Multiple-pass decoding is avail- able in publicly available toolkits like the SVMTool system (Giménez and Marquez,SVMTool 2004), a tagger that applies an SVM classifier instead of a MaxEnt classifier at each position, but similarly using Viterbi (or greedy) decoding to implement a sequence model. 10.7 Part-of-Speech Tagging for Other Languages The HMM and MEMM speech tagging algorithms have been applied to tagging in many languages besides English. For languages similar to English, the methods work well as is; tagger accuracies for German, for example, are close to those for English. Augmentations become necessary when dealing with highly inflected or agglutinative languages with rich morphology like Czech, Hungarian and Turkish. These productive word-formation processes result in a large vocabulary for these languages: a 250,000 word token corpus of Hungarian has more than twice as many 22 CHAPTER 10 • PART-OF-SPEECH TAGGING word types as a similarly sized corpus of English (Oravecz and Dienes, 2002), while a 10 million word token corpus of Turkish contains four times as many word types as a similarly sized English corpus (Hakkani-Tür et al., 2002). Large vocabular- ies mean many unknown words, and these unknown words cause significant per- formance degradations in a wide variety of languages (including Czech, Slovene, Estonian, and Romanian) (Hajič, 2000). Highly inflectional languages also have much more information than English coded in word morphology, like case (nominative, accusative, genitive) or gender (masculine, feminine). Because this information is important for tasks like pars- ing and coreference resolution, part-of-speech taggers for morphologically rich lan- guages need to label words with case and gender information. Tagsets for morpho- logically rich languages are therefore sequences of morphological tags rather than a single primitive tag. Here’s a Turkish example, in which the word izin has three pos- sible morphological/part-of-speech tags and meanings (Hakkani-Tür et al., 2002): 1. Yerdeki izin temizlenmesi gerek. iz + Noun+A3sg+Pnon+Gen The trace on the floor should be cleaned. 2. Üzerinde parmak izin kalmiş iz + Noun+A3sg+P2sg+Nom Your finger print is left on (it). 3. Içeri girmek için izin alman gerekiyor. izin + Noun+A3sg+Pnon+Nom You need a permission to enter. Using a morphological parse sequence like Noun+A3sg+Pnon+Gen as the part- of-speech tag greatly increases the number of parts-of-speech, and so tagsets can be 4 to 10 times larger than the 50–100 tags we have seen for English. With such large tagsets, each word needs to be morphologically analyzed (using a method from Chapter 3, or an extensive dictionary) to generate the list of possible morphological tag sequences (part-of-speech tags) for the word. The role of the tagger is then to disambiguate among these tags. This method also helps with unknown words since morphological parsers can accept unknown stems and still segment the affixes properly. Different problems occur with languages like Chinese in which words are not segmented in the writing system. For Chinese part-of-speech tagging word segmen- tation (Chapter 2) is therefore generally applied before tagging. It is also possible to build sequence models that do joint segmentation and tagging. Although Chinese words are on average very short (around 2.4 characters per unknown word com- pared with 7.7 for English) the problem of unknown words is still large, although while English unknown words tend to be proper nouns in Chinese the majority of unknown words are common nouns and verbs because of extensive compounding. Tagging models for Chinese use similar unknown word features to English, includ- ing character prefix and suffix features, as well as novel features like the radicals of each character in a word. One standard unknown feature for Chinese is to build a dictionary in which each character is listed with a vector of each part-of-speech tags that it occurred with in any word in the training set. The vectors of each of the characters in a word are then used as a feature in classification (Tseng et al., 2005). 10.8 Summary This chapter introduced the idea of parts-of-speech and part-of-speech tagging. The main ideas: BIBLIOGRAPHICAL AND HISTORICAL NOTES 23 • Languages generally have a relatively small set of closed class words that are often highly frequent, generally act as function words, and can be 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. • Two common approaches to sequence modeling are a generative approach, HMM tagging, and a discriminative approach, MEMM tagging. • The probabilities in HMM taggers are estimated, not using EM, but directly by maximum likelihood estimation on hand-labeled training corpora. The Viterbi algorithm is used to find the most likely tag sequence • Maximum entropy Markov model or MEMM taggers train logistic regres- sion models to pick the best tag given an observation word and its context and the previous tags, and then use Viterbi to choose the best sequence of tags for the sentence. More complex augmentions of the MEMM exist, like the Conditional Random Field (CRF) tagger. • Modern taggers are generally run bidirectionally. Bibliographical and Historical Notes What is probably the earliest part-of-speech tagger was part of the parser in Zellig Harris’s Transformations and Discourse Analysis Project (TDAP), implemented be- tween June 1958 and July 1959 at the University of Pennsylvania (Harris, 1962), although earlier systems had used part-of-speech information in dictionaries. TDAP used 14 hand-written rules for part-of-speech disambiguation; the use of part-of- speech tag sequences and the relative frequency of tags for a word prefigures all modern algorithms. The parser, whose implementation essentially corresponded a cascade of finite-state transducers, was reimplemented (Joshi and Hopely 1999; Karttunen 1999). The Computational Grammar Coder (CGC) of Klein and Simmons (1963) had three components: a lexicon, a morphological analyzer, and a context disambigua- tor. The small 1500-word lexicon listed only function words and other irregular words. The morphological analyzer used inflectional and derivational suffixes to as- sign part-of-speech classes. These were run over words to produce candidate parts- of-speech which were then disambiguated by a set of 500 context rules by relying on surrounding islands of unambiguous words. For example, one rule said that be- tween 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 a corpus of articles. The TAGGIT tagger (Greene and Rubin, 1971) was based on the Klein and Sim- mons (1963) system, using the same architecture but increasing the size of the dic- tionary and the size of the tagset to 87 tags. TAGGIT was applied to the Brown corpus and, according to Francis and Kučera (1982, p. 9), accurately tagged 77% of the corpus; the remainder of the Brown corpus was then tagged by hand. All these early algorithms were based on a two-stage architecture in which a dictionary was first used to assign each word a list of potential parts-of-speech and in the second stage large lists of hand-written disambiguation rules winnow down this list to a single part of speech for each word. 24 CHAPTER 10 • PART-OF-SPEECH TAGGING Soon afterwards the alternative probabilistic architectures began to be developed. Probabilities were used in tagging by Stolz et al. (1965) and a complete probabilis- tic tagger with Viterbi decoding was sketched by Bahl and Mercer (1976). The Lancaster-Oslo/Bergen (LOB) corpus, a British English equivalent of the Brown corpus, was tagging in the early 1980’s with the CLAWS tagger (Marshall 1983; Marshall 1987; Garside 1987), a probabilistic algorithm that can be viewed as a simplified approximation to the HMM tagging approach. The algorithm used tag bigram probabilities, but instead of storing the word likelihood of each tag, the algo- rithm marked tags either as rare (P(tag|word)< .01) infrequent (P(tag|word)< .10) or normally frequent (P(tag|word)> .10).

DeRose (1988) developed an algorithm that was almost the HMM approach, in-
cluding the use of dynamic programming, although computing a slightly different
probability: P(t|w)P(w) instead of P(w|t)P(w). The same year, the probabilistic
PARTS tagger of Church (1988), (1989) was probably the first implemented HMM
tagger, described correctly in Church (1989), although Church (1988) also described
the computation incorrectly as P(t|w)P(w) instead of P(w|t)P(w). Church (p.c.) ex-
plained that he had simplified for pedagogical purposes because using the probability
P(t|w) made the idea seem more understandable as “storing a lexicon in an almost
standard form”.

Later taggers explicitly introduced the use of the hidden Markov model (Ku-
piec 1992; Weischedel et al. 1993; Schütze and Singer 1994). Merialdo (1994)
showed that fully unsupervised EM didn’t work well for the tagging task and that
reliance on hand-labeled data was important. Charniak et al. (1993) showed the im-
portance of the most frequent tag baseline; the 92.3% number we give above was
from Abney et al. (1999). See Brants (2000) for many implementation details of a
state-of-the-art HMM tagger.

Ratnaparkhi (1996) introduced the MEMM tagger, called MXPOST, and the
modern formulation is very much based on his work.

The idea of using letter suffixes for unknown words is quite old; the early Klein
and Simmons (1963) system checked all final letter suffixes of lengths 1-5. The
probabilistic formulation we described for HMMs comes from Samuelsson (1993).
The unknown word features described on page 18 come mainly from (Ratnaparkhi,
1996), with augmentations from Toutanova et al. (2003) and Manning (2011).

State of the art taggers are based on a number of models developed just after the
turn of the last century, including (Collins, 2002) which used the the perceptron algo-
rithm, Toutanova et al. (2003) using a bidirectional log-linear model, and (Giménez
and Marquez, 2004) using SVMs. HMM (Brants 2000; Thede and Harper 1999)
and MEMM tagger accuracies are likely just a tad lower.

An alternative modern formalism, the English Constraint Grammar systems (Karls-
son et al. 1995; Voutilainen 1995; Voutilainen 1999), uses a two-stage formalism
much like the very early taggers from the 1950s and 1960s. A very large morpho-
logical analyzer with tens of thousands of English word stems entries is used to
return all possible parts-of-speech for a word, using a rich feature-based set of tags.
So the word occurred is tagged with the options 〈 V PCP2 SV 〉 and 〈 V PAST
VFIN SV 〉, meaning it can be a participle (PCP2) for an intransitive (SV) verb, or
a past (PAST) finite (VFIN) form of an intransitive (SV) verb. A large set of 3,744
constraints are then applied to the input sentence to rule out parts-of-speech that are
inconsistent with the context. For example here’s one rule for the ambiguous word
that, that eliminates all tags except the ADV (adverbial intensifier) sense (this is the
sense in the sentence it isn’t that odd):

EXERCISES 25

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 adjs as object complements */
then eliminate non-ADV tags
else eliminate ADV tag

The combination of the extensive morphological analyzer and carefully writ-
ten constraints leads to a very high accuracy for the constraint grammar algorithm
(Samuelsson and Voutilainen, 1997).

Manning (2011) investigates the remaining 2.7% of errors in a state-of-the-art
tagger, the bidirectional MEMM-style model described above (Toutanova et al.,
2003). He suggests that a third or half of these remaining errors are due to errors or
inconsistencies in the training data, a third might be solvable with richer linguistic
models, and for the remainder the task is underspecified or unclear.

The algorithms presented in the chapter rely heavily on in-domain training data
hand-labeled by experts. Much recent work in part-of-speech tagging focuses on
ways to relax this assumption. Unsupervised algorithms for part-of-speech tagging
cluster words into part-of-speech-like classes (Schütze 1995; Clark 2000; Gold-
water and Griffiths 2007; Berg-Kirkpatrick et al. 2010; Sirts et al. 2014) ; see
Christodoulopoulos et al. (2010) for a summary. Many algorithms focus on com-
bining labeled and unlabeled data, for example by co-training (Clark et al. 2003;
Søgaard 2010). Assigning tags to text from very different genres like Twitter textTwitter
can involve adding new tags for URLS (URL), username mentions (USR), retweets
(RT), and hashtags (HT), normalization of non-standard words, and bootstrapping
to employ unsupervised data (Derczynski et al., 2013).

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 ar-
ticle 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.

Exercises
10.1 Find one tagging error in each of the following sentences that are tagged with

the Penn Treebank tagset:

1. I/PRP need/VBP a/DT flight/NN from/IN Atlanta/NN
2. Does/VBZ this/DT flight/NN serve/VB dinner/NNS
3. I/PRP have/VB a/DT friend/NN living/VBG in/IN Denver/NNP
4. Can/VBP you/PRP list/VB the/DT nonstop/JJ afternoon/NN flights/NNS

10.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.

1. It is a nice night.
2. This crap game is over a garage in Fifty-second Street. . .
3. . . . Nobody ever takes the newspapers she sells . . .

26 CHAPTER 10 • PART-OF-SPEECH TAGGING

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

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

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

10.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?

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

10.5 Build a bigram HMM tagger. You will need a part-of-speech-tagged corpus.
First split the corpus into a training set and test set. From the labeled train-
ing set, train the transition and observation probabilities of the HMM tagger
directly on the hand-tagged data. Then implement the Viterbi algorithm from
this chapter and Chapter 9 so that you can label an arbitrary test sentence.
Now run your algorithm on the test set. Report its error rate and compare its
performance to the most frequent tag baseline.

10.6 Do an error analysis of your tagger. Build a confusion matrix and investigate
the most frequent errors. Propose some features for improving the perfor-
mance of your tagger on these errors.

Exercises 27

Abney, S. P., Schapire, R. E., and Singer, Y. (1999). Boosting
applied to tagging and PP attachment. In EMNLP/VLC-99,
College Park, MD, pp. 38–45.

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

Berg-Kirkpatrick, T., Bouchard-Côté, A., DeNero, J., and
Klein, D. (2010). Painless unsupervised learning with fea-
tures. In NAACL HLT 2010, pp. 582–590.

Brants, T. (2000). TnT: A statistical part-of-speech tagger.
In ANLP 2000, Seattle, WA, pp. 224–231.

Broschart, J. (1997). Why Tongan does it differently. Lin-
guistic 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.

Christodoulopoulos, C., Goldwater, S., and Steedman, M.
(2010). Two decades of unsupervised POS induction: How
far have we come?. In EMNLP-10.

Church, K. W. (1988). A stochastic parts program and noun
phrase parser for unrestricted text. In ANLP 1988, pp. 136–
143.

Church, K. W. (1989). A stochastic parts program and noun
phrase parser for unrestricted text. In ICASSP-89, pp. 695–
698.

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

Clark, S., Curran, J. R., and Osborne, M. (2003). Bootstrap-
ping pos taggers using unlabelled data. In CoNLL-03, pp.
49–55.

Collins, M. (2002). Discriminative training methods for hid-
den markov models: Theory and experiments with percep-
tron algorithms. In ACL-02, pp. 1–8.

Derczynski, L., Ritter, A., Clark, S., and Bontcheva, K.
(2013). Twitter part-of-speech tagging for all: Overcom-
ing sparse and noisy data. In RANLP 2013, pp. 198–206.

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

Evans, N. (2000). Word classes in the world’s languages. In
Booij, G., Lehmann, C., and Mugdan, J. (Eds.), Morphol-
ogy: A Handbook on Inflection and Word Formation, pp.
708–732. Mouton.

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

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

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

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

Giménez, J. and Marquez, L. (2004). SVMTool: A general
POS tagger generator based on Support Vector Machines.
In LREC-04.

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 grammat-
ical tagging of English. Department of Linguistics, Brown
University, Providence, Rhode Island.

Hajič, J. (2000). Morphological tagging: Data vs. dictionar-
ies. In NAACL 2000. Seattle.

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

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

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.

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 Hol-
land.

Joshi, A. K. and Hopely, P. (1999). A parser from antiq-
uity. 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. (Eds.). (1995). Constraint Grammar: A Language-
Independent System for Parsing Unrestricted Text. Mouton
de Gruyter.

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

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

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

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

Lafferty, J. D., McCallum, A., and Pereira, F. C. N. (2001).
Conditional random fields: Probabilistic models for seg-
menting and labeling sequence data. In ICML 2001, Stan-
ford, CA.

Manning, C. D. (2011). Part-of-speech tagging from 97% to
100%: Is it time for some linguistics?. In CICLing 2011,
pp. 171–189.

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 with-
out GLobal syntactic analysis: Tagging words in the LOB
corpus. Computers and the Humanities, 17, 139–150.

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

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

28 Chapter 10 • Part-of-Speech Tagging

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.

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.

Sampson, G. (1987). Alternative grammatical coding sys-
tems. In Garside, R., Leech, G., and Sampson, G.
(Eds.), The Computational Analysis of English, pp. 165–
183. Longman.

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

Samuelsson, C. and Voutilainen, A. (1997). Comparing a
linguistic and a stochastic tagger. In EACL-97, pp. 246–
253.

Schachter, P. (1985). Parts-of-speech systems. In Shopen, T.
(Ed.), Language Typology and Syntactic Description, Vol-
ume 1, 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 ACL-94, Las
Cruces, NM, pp. 181–187.

Sirts, K., Eisenstein, J., Elsner, M., and Goldwater, S.
(2014). Pos induction with distributional and morphologi-
cal information using a distance-dependent Chinese restau-
rant process. In ACL 2014.

Søgaard, A. (2010). Simple semi-supervised training of part-
of-speech taggers. In ACL 2010, pp. 205–208.

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 hid-
den 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.

Tseng, H., Jurafsky, D., and Manning, C. D. (2005). Mor-
phological features help POS tagging of unknown words
across language varieties. In Proceedings of the 4th
SIGHAN Workshop on Chinese Language Processing.

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.

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

Weischedel, R., Meteer, M., Schwartz, R., Ramshaw, L. A.,
and Palmucci, J. (1993). Coping with ambiguity and un-
known words through probabilistic models. Computational
Linguistics, 19(2), 359–382.

Part-of-Speech Tagging
(Mostly) English Word Classes
The Penn Treebank Part-of-Speech Tagset
Part-of-Speech Tagging
HMM Part-of-Speech Tagging
The basic equation of HMM Tagging
Estimating probabilities
Working through an example
Extending the HMM Algorithm to Trigrams
Unknown Words

Maximum Entropy Markov Models
Features in a MEMM
Decoding and Training MEMMs

Bidirectionality
Part-of-Speech Tagging for Other Languages
Summary
Bibliographical and Historical Notes
Exercises