Paper: Constraints On Non-Projective Dependency Parsing

ACL ID E06-1010
Title Constraints On Non-Projective Dependency Parsing
Venue Annual Meeting of The European Chapter of The Association of Computational Linguistics
Session Main Conference
Year 2006
  • Joakim Nivre (Vaxjo University, Vaxjo Sweden; Uppsala University, Uppsala Sweden)

We investigate a series of graph-theoretic constraints on non-projective dependency parsing and their effect on expressivity, i.e. whether they allow naturally occurring syntactic constructions to be adequately represented, and efficiency, i.e. whether they reduce the search space for the parser. In particular, we define a new measure for the degree of non-projectivity in an acyclic dependency graph obeying the single-head constraint. The constraints are evaluated experimentally using data from the Prague Dependency Treebank and the Danish Dependency Treebank. Theresults indicate that, whereas complete linguistic coverage in principle requires unrestricted non-projective dependency graphs, limit- ing the degree of non-projectivity to at most 2 can reduce average running time from quadratic...