Online Large-Margin Training of Dependency Parsers

Proceedings of the 43rd Annual Meeting of the ACL, pages 91–98, Ann Arbor, June 2005. c⃝2005 Association for Computational Linguistics Online Large-Margin Training of Dependency Parsers Ryan McDonald Koby Crammer Fernando Pereira Department of Computer and Information Science University of Pennsylvania Philadelphia, PA {ryantm,crammer,pereira}@cis.upenn.edu Abstract We present an effective training al- gorithm for linearly-scored dependency parsers that implements online large- margin multi-class training (Crammer and Singer, 2003; Crammer et al., 2003) on top of efficient parsing techniques for de- pendency trees (Eisner, 1996). The trained parsers achieve a competitive dependency accuracy for both English and Czech with no language specific enhancements. 1 Introduction Research on training parsers from annotated data has for the most part focused on models and train- ing algorithms for phrase structure parsing. The best phrase-structure parsing models represent gen- eratively the joint probability P(x, y) of sentence x having the structure y (Collins, 1999; Charniak, 2000). Generative parsing models are very conve- nient because training consists of computing proba- bility estimates from counts of parsing events in the training set. However, generative models make com- plicated and poorly justified independence assump- tions and estimations, so we might expect better per- formance from discriminatively trained models, as has been shown for other tasks like document classi- fication (Joachims, 2002) and shallow parsing (Sha and Pereira, 2003). Ratnaparkhi’s conditional max- imum entropy model (Ratnaparkhi, 1999), trained to maximize conditional likelihood P(y|x) of the training data, performed nearly as well as generative models of the same vintage even though it scores parsing decisions in isolation and thus may suffer from the label bias problem (Lafferty et al., 2001). Discriminatively trained parsers that score entire trees for a given sentence have only recently been investigated (Riezler et al., 2002; Clark and Curran, 2004; Collins and Roark, 2004; Taskar et al., 2004). The most likely reason for this is that discrimina- tive training requires repeatedly reparsing the train- ing corpus with the current model to determine the parameter updates that will improve the training cri- terion. The reparsing cost is already quite high for simple context-free models with O(n3) parsing complexity, but it becomes prohibitive for lexical- ized grammars with O(n5) parsing complexity. Dependency trees are an alternative syntactic rep- resentation with a long history (Hudson, 1984). De- pendency trees capture important aspects of func- tional relationships between words and have been shown to be useful in many applications includ- ing relation extraction (Culotta and Sorensen, 2004), paraphrase acquisition (Shinyama et al., 2002) and machine translation (Ding and Palmer, 2005). Yet, they can be parsed in O(n3) time (Eisner, 1996). Therefore, dependency parsing is a potential “sweet spot” that deserves investigation. We focus here on projective dependency trees in which a word is the parent of all of its arguments, and dependencies are non-crossing with respect to word order (see Fig- ure 1). However, there are cases where crossing dependencies may occur, as is the case for Czech (Hajiˇc, 1998). Edges in a dependency tree may be typed (for instance to …

Content truncated to 500 words