Feature-Rich Part-of-Speech Tagging with a Cyclic Dependency Network

Feature-Rich Part-of-Speech Tagging with a Cyclic Dependency Network Kristina Toutanova Dan Klein Computer Science Dept. Computer Science Dept. Stanford University Stanford University Stanford, CA 94305-9040 Stanford, CA 94305-9040 kristina@cs.stanford.edu klein@cs.stanford.edu Christopher D. Manning Yoram Singer Computer Science Dept. School of Computer Science Stanford University The Hebrew University Stanford, CA 94305-9040 Jerusalem 91904, Israel manning@stanford.edu singer@cs.huji.ac.il Abstract We present a new part-of-speech tagger that demonstrates the following ideas: (i) explicit use of both preceding and following tag con- texts via a dependency network representa- tion, (ii) broad use of lexical features, includ- ing jointly conditioning on multiple consecu- tive words, (iii) effective use of priors in con- ditional loglinear models, and (iv) fine-grained modeling of unknown word features. Using these ideas together, the resulting tagger gives a 97.24% accuracy on the Penn Treebank WSJ, an error reduction of 4.4% on the best previous single automatically learned tagging result. 1 Introduction Almost all approaches to sequence problems such as part- of-speech tagging take a unidirectional approach to con- ditioning inference along the sequence. Regardless of whether one is using HMMs, maximum entropy condi- tional sequence models, or other techniques like decision trees, most systems work in one direction through the sequence (normally left to right, but occasionally right to left, e.g., Church (1988)). There are a few excep- tions, such as Brill’s transformation-based learning (Brill, 1995), but most of the best known and most successful approaches of recent years have been unidirectional. Most sequence models can be seen as chaining to- gether the scores or decisions from successive local mod- els to form a global model for an entire sequence. Clearly the identity of a tag is correlated with both past and future tags’ identities. However, in the unidirectional (causal) case, only one direction of influence is explicitly consid- ered at each local point. For example, in a left-to-right first-order HMM, the current tag t0 is predicted based on the previous tag t−1 (and the current word).1 The back- ward interaction between t0 and the next tag t+1 shows up implicitly later, when t+1 is generated in turn. While unidirectional models are therefore able to capture both directions of influence, there are good reasons for sus- pecting that it would be advantageous to make informa- tion from both directions explicitly available for condi- tioning at each local point in the model: (i) because of smoothing and interactions with other modeled features, terms like P(t0|t+1, . . .) might give a sharp estimate of t0 even when terms like P(t+1|t0, . . .) do not, and (ii) jointly considering the left and right context together might be especially revealing. In this paper we exploit this idea, using dependency networks, with a series of local con- ditional loglinear (aka maximum entropy or multiclass logistic regression) models as one way of providing ef- ficient bidirectional inference. Secondly, while all taggers use lexical information, and, indeed, it is well-known that lexical probabilities are much more revealing than tag sequence probabilities (Charniak et al., 1993), most taggers …

Content truncated to 500 words