A Three-Step Transition-Based System for Non-Projective Dependency Parsing

Proceedings of COLING 2014, the 25th International Conference on Computational Linguistics: Technical Papers, pages 224–232, Dublin, Ireland, August 23-29 2014. A Three-Step Transition-Based System for Non-Projective Dependency Parsing Oph´elie Lacroix and Denis B´echet LINA - University of Nantes 2 Rue de la Houssini`ere 44322 Nantes Cedex 3 {ophelie.lacroix,denis.bechet}@univ-nantes.fr Abstract This paper presents a non-projective dependency parsing system that is transition-based and op- erates in three steps. The three steps include one classical method for projective dependency parsing and two inverse methods predicting separately the right and left non-projective depen- dencies. Splitting the parsing allows to increase the scores on both projective and non-projective dependencies compared to state-of-the-art non-projective dependency parsing. Moreover, each step is performed in linear time. 1 Introduction Dependency parsing is a particularly studied task and could be a significant step in various natural lan- guage processes. That is why dependency parsers should tend to get speed and precision. In recent years, various methods for dependency parsing were proposed (K¨ubler et al., 2009). Among these methods, transition-based systems are particularly suitable. The first methods developed for transition-based parsers proposed to produce projective dependency structures (including no crossing dependencies). Then, extended methods were developed to handle the non-projective cases. The non-projective dependency structures admit non-projective dependencies (a dependency is non-projective if at least one word located between the head and the dependent of the dependency does not depend directly or inderectly on the head, see Figure 1 for example). Handling the non-projective cases has been the foundation of the first work concerning the dependency representa- tions (Tesni`ere, 1959; Melcuk, 1988). Moreover, it is important to successfully parse the non-projective sentences which can be very helpful in processes such as question-answering. The transition-based parsers achieve interesting overall results for both projective and non-projective analyses. But, in practice, the non-projective methods achieve far lower and variable scores on non- projective dependencies than on projective dependencies. Finding these dependencies is more difficult because the non-projective dependencies are often distant ones. It is then essential to achieve descent scores on non-projective dependencies as well as on projective ones because some languages contain a high rate of non-projective dependencies. Here we propose to predict separately the projective dependencies from the non-projective ones. Using a mixed dependency representation including both projective and non-projective dependency annotations in one representation, we aim at predicting the projective dependencies in a first step. Taking advantage of the good results of projective dependency parsing, we aim at predicting the non-projective dependencies in a second step. The formal dependency representation on which we base our work results from the formalism of cate- gorial dependency grammars (CDG) (Dekhtyar and Dikovsky, 2008). It allows to handle the discontinu- ities of the natural languages. The dependency representation induced is mixed: it associates projective and non-projective dependencies to represent complementary syntactic information in one dependency This work is licensed under a Creative Commons Attribution 4.0 International Licence. Page numbers and proceedings footer are added by the organisers. Licence details: http://creativecommons.org/licenses/by/4.0/ 224 pred obj det prepos-A …

Content truncated to 500 words