Article Structure
Abstract
Finding a class of structures that is rich enough for adequate linguistic representation yet restricted enough for efficient computational processing is an important problem for dependency parsing.
Introduction
Dependency-based syntactic parsing has become a widely used technique in natural language processing, and many different parsing models have been proposed in recent years (Yamada and Matsumoto, 2003; Nivre et al., 2004; McDonald et al., 2005a; Titov and Henderson, 2007; Martins et al., 2009).
Preliminaries
2.1 Dependency Graphs
Determining Multiplanarity
Several constraints on non-projective dependency structures have been proposed recently that seek a good balance between parsing efficiency and coverage of non-projective phenomena present in natural language treebanks.
Parsing 1-Planar Structures
In this section, we present a deterministic linear-time parser for planar dependency structures.
Parsing 2-Planar Structures
The planar parser introduced in the previous section can be extended to parse all 2-planar dependency structures by adding a second stack to the system and making REDUCE and ARC transitions apply to only one of the stacks at a time.
Empirical Evaluation
In order to get a first estimate of the empirical accuracy that can be obtained with transition-based 2-planar parsing, we have evaluated the parser on four data sets from the CoNLL—X shared task (Buchholz and Marsi, 2006): Czech, Danish, German and Portuguese.
Conclusion
In this paper, we have presented an efficient algorithm for deciding whether a dependency graph is 2-planar and a transition-based parsing algorithm that is provably correct for 2-planar dependency forests, neither of which existed in the literature before.
Topics
treebanks
Appears in 15 sentences as: treebank (3) treebanks (12)
In A Transition-Based Parser for 2-Planar Dependency Structures
- In addition, we present an efficient method for determining whether an arbitrary tree is 2-planar and show that 99% or more of the trees in existing treebanks are 2-planar.
Page 1, “Abstract”
- Although these proposals seem to have a very good fit with linguistic data, in the sense that they often cover 99% or more of the structures found in existing treebanks , the development of efficient parsing algorithms for these classes has met with more limited success.
Page 1, “Introduction”
- First, we present a procedure for determining the minimal number m such that a dependency tree is m-planar and use it to show that the overwhelming majority of sentences in dependency treebanks have a tree that is at most 2-planar.
Page 1, “Introduction”
- According to the results by Kuhlmann and Nivre (2006), most non-projective structures in dependency treebanks are also non-planar, so being able to parse planar structures will only give us a modest improvement in coverage with respect to a projective parser.
Page 2, “Preliminaries”
- Several constraints on non-projective dependency structures have been proposed recently that seek a good balance between parsing efficiency and coverage of non-projective phenomena present in natural language treebanks .
Page 3, “Determining Multiplanarity”
- For example, Kuhlmann and Nivre (2006) and Havelka (2007) have shown that the vast majority of structures present in existing treebanks are well-nested and have a small gap degree (Bodirsky et al., 2005), leading to an interest in parsers for these kinds of structures (Gomez-Rodriguez et al., 2009).
Page 3, “Determining Multiplanarity”
- No similar analysis has been performed for m-planar structures, although Yli-Jyr'a (2003) provides evidence that all except two structures in the Danish dependency treebank are at most 3-planar.
Page 3, “Determining Multiplanarity”
- In this section, we provide a procedure for finding the minimal number m such that a dependency graph is m-planar and use it to show that the vast majority of sentences in dependency treebanks are
Page 3, “Determining Multiplanarity”
- However, we have found this not to be a problem when measuring multiplanarity in natural language treebanks , since the effective problem size can be reduced by noting that each connected component of the crossings graph can be treated separately, and that nodes that are not part of a cycle need not be considered.5 Given that non-projective sentences in natural language tend to have a small proportion of non-projective links (Nivre and Nilsson, 2005), the connected components of their crossings graphs are very small, and k-colourings for them can quickly be found by brute-force search.
Page 4, “Determining Multiplanarity”
- By applying these techniques to dependency treebanks of several languages, we obtain the data shown in Table 1.
Page 4, “Determining Multiplanarity”
- In most of the treebanks , well over 99% of the sentences are 2-planar, and 3-planarity has almost total coverage.
Page 4, “Determining Multiplanarity”
See all papers in Proc. ACL 2010 that mention treebanks.
See all papers in Proc. ACL that mention treebanks.
Back to top.
dependency trees
Appears in 9 sentences as: dependency tree (2) dependency trees (7)
In A Transition-Based Parser for 2-Planar Dependency Structures
- In this paper, we present a transition system for 2-planar dependency trees — trees that can be decomposed into at most two planar graphs — and show that it can be used to implement a classifier-based parser that runs in linear time and outperforms a state-of-the-art transition-based parser on four data sets from the CoNLL-X shared task.
Page 1, “Abstract”
- One of the unresolved issues in this area is the proper treatment of non-projective dependency trees , which seem to be required for an adequate representation of predicate-argument structure, but which undermine the efficiency of dependency parsing (Neuhaus and Broker, 1997; Buch-Kromann, 2006; McDonald and Satta, 2007).
Page 1, “Introduction”
- (2009) have shown how well-nested dependency trees with bounded gap degree can be parsed in polynomial time, the best time complexity for lexicalized parsing of this class remains a prohibitive 0(n7), which makes the practical usefulness questionable.
Page 1, “Introduction”
- In this paper, we explore another characterization of mildly non-projective dependency trees based on the notion of multiplanarity.
Page 1, “Introduction”
- First, we present a procedure for determining the minimal number m such that a dependency tree is m-planar and use it to show that the overwhelming majority of sentences in dependency treebanks have a tree that is at most 2-planar.
Page 1, “Introduction”
- Secondly, we present a transition-based parsing algorithm for 2-planar dependency trees , developed in two steps.
Page 1, “Introduction”
- Such a forest is called a dependency tree .
Page 2, “Preliminaries”
- Projective dependency trees correspond to the set of structures that can be induced from lexicalised context-free derivations (Kuhlmann, 2007; Gaif-man, 1965).
Page 2, “Preliminaries”
- Like context-free grammars, projective dependency trees are not sufficient to represent all the linguistic phenomena observed in natural languages, but they have the advantage of being efficiently parsable: their parsing problem can be solved in cubic time with chart parsing techniques (Eisner, 1996; Gomez-Rodriguez et al., 2008), while in the case of general non-projective dependency forests, it is only tractable under strong independence assumptions (McDonald et al., 2005b; McDonald and Satta, 2007).
Page 2, “Preliminaries”
See all papers in Proc. ACL 2010 that mention dependency trees.
See all papers in Proc. ACL that mention dependency trees.
Back to top.
dependency parsing
Appears in 7 sentences as: dependency parser (1) dependency parsers (1) dependency parsing (5)
In A Transition-Based Parser for 2-Planar Dependency Structures
- Finding a class of structures that is rich enough for adequate linguistic representation yet restricted enough for efficient computational processing is an important problem for dependency parsing .
Page 1, “Abstract”
- One of the unresolved issues in this area is the proper treatment of non-projective dependency trees, which seem to be required for an adequate representation of predicate-argument structure, but which undermine the efficiency of dependency parsing (Neuhaus and Broker, 1997; Buch-Kromann, 2006; McDonald and Satta, 2007).
Page 1, “Introduction”
- This was originally proposed by Yli-Jyr'a (2003) but has so far played a marginal role in the dependency parsing literature, because no algorithm was known for determining whether an arbitrary tree was m-planar, and no parsing algorithm existed for any constant value of m. The contribution of this paper is twofold.
Page 1, “Introduction”
- For reasons of computational efficiency, many dependency parsers are restricted to work with projective dependency structures, that is, forests in which the projection of each node corresponds to a contiguous substring of the input:
Page 2, “Preliminaries”
- The concept of planarity on its own does not seem to be very relevant as an extension of projectivity for practical dependency parsing .
Page 2, “Preliminaries”
- In the transition-based framework of Nivre (2008), a deterministic dependency parser is defined by a nondeterministic transition system, specifying a set of elementary operations that can be executed during the parsing process, and an oracle that deterministically selects a single transition at each choice point of the parsing process.
Page 4, “Parsing 1-Planar Structures”
- A transition system for dependency parsing is a quadruple S = (C, T, cs, Ct) where I.
Page 4, “Parsing 1-Planar Structures”
See all papers in Proc. ACL 2010 that mention dependency parsing.
See all papers in Proc. ACL that mention dependency parsing.
Back to top.
natural language
Appears in 4 sentences as: natural language (4) natural languages (1)
In A Transition-Based Parser for 2-Planar Dependency Structures
- Dependency-based syntactic parsing has become a widely used technique in natural language processing, and many different parsing models have been proposed in recent years (Yamada and Matsumoto, 2003; Nivre et al., 2004; McDonald et al., 2005a; Titov and Henderson, 2007; Martins et al., 2009).
Page 1, “Introduction”
- Like context-free grammars, projective dependency trees are not sufficient to represent all the linguistic phenomena observed in natural languages , but they have the advantage of being efficiently parsable: their parsing problem can be solved in cubic time with chart parsing techniques (Eisner, 1996; Gomez-Rodriguez et al., 2008), while in the case of general non-projective dependency forests, it is only tractable under strong independence assumptions (McDonald et al., 2005b; McDonald and Satta, 2007).
Page 2, “Preliminaries”
- Several constraints on non-projective dependency structures have been proposed recently that seek a good balance between parsing efficiency and coverage of non-projective phenomena present in natural language treebanks.
Page 3, “Determining Multiplanarity”
- However, we have found this not to be a problem when measuring multiplanarity in natural language treebanks, since the effective problem size can be reduced by noting that each connected component of the crossings graph can be treated separately, and that nodes that are not part of a cycle need not be considered.5 Given that non-projective sentences in natural language tend to have a small proportion of non-projective links (Nivre and Nilsson, 2005), the connected components of their crossings graphs are very small, and k-colourings for them can quickly be found by brute-force search.
Page 4, “Determining Multiplanarity”
See all papers in Proc. ACL 2010 that mention natural language.
See all papers in Proc. ACL that mention natural language.
Back to top.
parsing algorithm
Appears in 4 sentences as: parsing algorithm (3) parsing algorithms (1)
In A Transition-Based Parser for 2-Planar Dependency Structures
- Although these proposals seem to have a very good fit with linguistic data, in the sense that they often cover 99% or more of the structures found in existing treebanks, the development of efficient parsing algorithms for these classes has met with more limited success.
Page 1, “Introduction”
- This was originally proposed by Yli-Jyr'a (2003) but has so far played a marginal role in the dependency parsing literature, because no algorithm was known for determining whether an arbitrary tree was m-planar, and no parsing algorithm existed for any constant value of m. The contribution of this paper is twofold.
Page 1, “Introduction”
- Secondly, we present a transition-based parsing algorithm for 2-planar dependency trees, developed in two steps.
Page 1, “Introduction”
- In this paper, we have presented an efficient algorithm for deciding whether a dependency graph is 2-planar and a transition-based parsing algorithm that is provably correct for 2-planar dependency forests, neither of which existed in the literature before.
Page 8, “Conclusion”
See all papers in Proc. ACL 2010 that mention parsing algorithm.
See all papers in Proc. ACL that mention parsing algorithm.
Back to top.
shared task
Appears in 4 sentences as: shared task (4)
In A Transition-Based Parser for 2-Planar Dependency Structures
- In this paper, we present a transition system for 2-planar dependency trees — trees that can be decomposed into at most two planar graphs — and show that it can be used to implement a classifier-based parser that runs in linear time and outperforms a state-of-the-art transition-based parser on four data sets from the CoNLL-X shared task .
Page 1, “Abstract”
- Although the contributions of this paper are mainly theoretical, we also present an empirical evaluation of the 2-planar parser, showing that it outperforms the projective parser on four data sets from the CoNLL—X shared task (Buchholz and Marsi, 2006).
Page 1, “Introduction”
- In order to get a first estimate of the empirical accuracy that can be obtained with transition-based 2-planar parsing, we have evaluated the parser on four data sets from the CoNLL—X shared task (Buchholz and Marsi, 2006): Czech, Danish, German and Portuguese.
Page 8, “Empirical Evaluation”
- (2006b) in the original shared task , where the pseudo-projective version of MaltParser was one of the two top performing systems (Buchholz and Marsi, 2006).
Page 8, “Empirical Evaluation”
See all papers in Proc. ACL 2010 that mention shared task.
See all papers in Proc. ACL that mention shared task.
Back to top.