Incremental Dependency Parsing Using Online Learning

Proceedings of the CoNLL Shared Task Session of EMNLP-CoNLL 2007, pp. 1134–1138, Prague, June 2007. c⃝2007 Association for Computational Linguistics Incremental Dependency Parsing Using Online Learning Richard Johansson and Pierre Nugues Department of Computer Science, Lund University, Sweden {richard, pierre}@cs.lth.se Abstract We describe an incremental parser that was trained to minimize cost over sen- tences rather than over individual parsing ac- tions. This is an attempt to use the advan- tages of the two top-scoring systems in the CoNLL-X shared task. In the evaluation, we present the perfor- mance of the parser in the Multilingual task, as well as an evaluation of the contribution of bidirectional parsing and beam search to the parsing performance. 1 Introduction The two best-performing systems in the CoNLL-X shared task (Buchholz and Marsi, 2006) can be clas- sified along two lines depending on the method they used to train the parsing models. Although the parsers are quite different, their creators could re- port near-tie scores. The approach of the top sys- tem (McDonald et al., 2006) was to fit the model to minimize cost over sentences, while the second- best system (Nivre et al., 2006) trained the model to maximize performance over individual decisions in an incremental algorithm. This difference is a nat- ural consequence of their respective parsing strate- gies: CKY-style maximization of link score and in- cremental parsing. In this paper, we describe an attempt to unify the two approaches: an incremental parsing strategy that is trained to maximize performance over sentences rather than over individual parsing actions. 2 Parsing Method 2.1 Nivre’s Parser We used Nivre’s algorithm (Nivre et al., 2006), which is a variant of the shift–reduce parser. Like the regular shift–reduce, it uses a stack S and a list of input words W, and builds the parse tree incre- mentally using a set of parsing actions (see Table 1). It can be shown that Nivre’s parser creates projec- tive and acyclic graphs and that every projective de- pendency graph can be produced by a sequence of parser actions. In addition, the worst-case number of actions is linear with respect to the number of words in the sentence. 2.2 Handling Nonprojective Parse Trees While the parsing algorithm produces projective trees only, nonprojective arcs can be handled using a preprocessing step before training the model and a postprocessing step after parsing the sentences. The projectivization algorithm (Nivre and Nils- son, 2005) iteratively moves each nonprojective arc upward in the tree until the whole tree is projective. To be able to recover the nonprojective arcs after parsing, the projectivization operation replaces the labels of the arcs it modifies with traces indicating which links should be moved and where attach to at- tach them (the “Head+Path” encoding). The model is trained with these new labels that makes it pos- sible to carry out the reverse operation and produce nonprojective structures. 2.3 Bidirectional Parsing Shift-reduce is by construction a directional parser, typically applied from left to right. To make bet- ter use of the training …

Content truncated to 500 words