Improving Transition-Based Dependency Parsing with Buffer Transitions

Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 308–319, Jeju Island, Korea, 12–14 July 2012. c⃝2012 Association for Computational Linguistics Improving Transition-Based Dependency Parsing with Buffer Transitions Daniel Fern´andez-Gonz´alez Departamento de Inform´atica Universidade de Vigo Campus As Lagoas, 32004 Ourense, Spain danifg@uvigo.es Carlos G´omez-Rodr´ıguez Departamento de Computaci´on Universidade da Coru˜na Campus de Elvi˜na, 15071 A Coru˜na, Spain carlos.gomez@udc.es Abstract In this paper, we show that significant im- provements in the accuracy of well-known transition-based parsers can be obtained, with- out sacrificing efficiency, by enriching the parsers with simple transitions that act on buffer nodes. First, we show how adding a specific tran- sition to create either a left or right arc of length one between the first two buffer nodes produces improvements in the accuracy of Nivre’s arc-eager projective parser on a num- ber of datasets from the CoNLL-X shared task. Then, we show that accuracy can also be improved by adding transitions involving the topmost stack node and the second buffer node (allowing a limited form of non-projectivity). None of these transitions has a negative im- pact on the computational complexity of the algorithm. Although the experiments in this paper use the arc-eager parser, the approach is generic enough to be applicable to any stack- based dependency parser. 1 Introduction Dependency parsing has become a very active re- search area in natural language processing in re- cent years. The dependency representation of syn- tax simplifies the syntactic parsing task, since no non-lexical nodes need to be postulated by the parsers; while being convenient in practice, since dependency representations directly show the head- modifier and head-complement relationships which form the basis of predicate-argument structure. This has led to the development of various data-driven dependency parsers, such as those by Yamada and Matsumoto (2003), Nivre et al. (2004), McDonald et al. (2005), Martins et al. (2009), Huang and Sagae (2010) or Tratz and Hovy (2011), which can be trained directly from annotated data and produce ac- curate analyses very efficiently. Most current data-driven dependency parsers can be classified into two families, commonly called graph-based and transition-based parsers (Mc- Donald and Nivre, 2011). Graph-based parsers (Eis- ner, 1996; McDonald et al., 2005) are based on global optimization of models that work by scoring subtrees. On the other hand, transition-based parsers (Yamada and Matsumoto, 2003; Nivre et al., 2004), which are the focus of this work, use local training to make greedy decisions that deterministically se- lect the next parser state. Among the advantages of transition-based parsers are the linear time complex- ity of many of them and the possibility of using rich feature models (Zhang and Nivre, 2011). In particular, many transition-based parsers (Nivre et al., 2004; Attardi, 2006; Sagae and Tsujii, 2008; Nivre, 2009; Huang and Sagae, 2010; G´omez- Rodr´ıguez and Nivre, 2010) are stack-based (Nivre, 2008), meaning that they keep a stack of partially processed tokens and an input buffer of unread to- kens. In this paper, we show …

Content truncated to 500 words