Dependency Parsing with Undirected Graphs

Proceedings of the 13th Conference of the European Chapter of the Association for Computational Linguistics, pages 66–76, Avignon, France, April 23 - 27 2012. c⃝2012 Association for Computational Linguistics Dependency Parsing with Undirected Graphs 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 Daniel Fern´andez-Gonz´alez Departamento de Inform´atica Universidade de Vigo Campus As Lagoas, 32004 Ourense, Spain danifg@uvigo.es Abstract We introduce a new approach to transition- based dependency parsing in which the parser does not directly construct a depen- dency structure, but rather an undirected graph, which is then converted into a di- rected dependency tree in a post-processing step. This alleviates error propagation, since undirected parsers do not need to ob- serve the single-head constraint. Undirected parsers can be obtained by sim- plifying existing transition-based parsers satisfying certain conditions. We apply this approach to obtain undirected variants of the planar and 2-planar parsers and of Cov- ington’s non-projective parser. We perform experiments on several datasets from the CoNLL-X shared task, showing that these variants outperform the original directed al- gorithms in most of the cases. 1 Introduction Dependency parsing has proven to be very use- ful for natural language processing tasks. Data- driven dependency parsers such as those by Nivre et al. (2004), McDonald et al. (2005), Titov and Henderson (2007), Martins et al. (2009) or Huang and Sagae (2010) are accurate and efficient, they can be trained from annotated data without the need for a grammar, and they provide a simple representation of syntax that maps to predicate- argument structure in a straightforward way. In particular, transition-based dependency parsers (Nivre, 2008) are a type of dependency parsing algorithms which use a model that scores transitions between parser states. Greedy deter- ministic search can be used to select the transition to be taken at each state, thus achieving linear or quadratic time complexity. 0 1 2 3 Figure 1: An example dependency structure where transition-based parsers enforcing the single-head con- straint will incur in error propagation if they mistak- enly build a dependency link 1 → 2 instead of 2 → 1 (dependency links are represented as arrows going from head to dependent). It has been shown by McDonald and Nivre (2007) that such parsers suffer from error prop- agation: an early erroneous choice can place the parser in an incorrect state that will in turn lead to more errors. For instance, suppose that a sentence whose correct analysis is the dependency graph in Figure 1 is analyzed by any bottom-up or left- to-right transition-based parser that outputs de- pendency trees, therefore obeying the single-head constraint (only one incoming arc is allowed per node). If the parser chooses an erroneous transi- tion that leads it to build a dependency link from 1 to 2 instead of the correct link from 2 to 1, this will lead it to a state where the single-head con- straint makes it illegal to create the link from 3 to 2. Therefore, a single erroneous choice will …

Content truncated to 500 words