A Deductive Approach to Dependency Parsing
Article Structure
Abstract
We define a new formalism, based on Sikkel’s parsing schemata for constituency parsers, that can be used to describe, analyze and compare dependency parsing algorithms.
Introduction
Dependency parsing consists of finding the structure of a sentence as expressed by a set of directed links (dependencies) between words.
Dependency parsing schemata
Although parsing schemata were initially defined for context-free parsers, they can be adapted to different constituency-based grammar formalisms, by finding a suitable definition of Trees(G) for each particular formalism and a way to define deduction steps from its rules.
Topics
dependency parsing
Appears in 28 sentences as: dependency parser (2) dependency parsers (10) dependency parsers: (2) Dependency parsing (1) dependency parsing (14)
In A Deductive Approach to Dependency Parsing
- We define a new formalism, based on Sikkel’s parsing schemata for constituency parsers, that can be used to describe, analyze and compare dependency parsing algorithms.Page 1, “Abstract”
- This abstraction allows us to establish clear relations between several existing projective dependency parsers and prove their correctness.Page 1, “Abstract”
- Dependency parsing consists of finding the structure of a sentence as expressed by a set of directed links (dependencies) between words.Page 1, “Introduction”
- In addition to this, some dependency parsers are able to represent nonprojective structures, which is an important feature when parsing free word order languages in which discontinuous constituents are common.Page 1, “Introduction”
- However, since parsing schemata are defined as deduction systems over sets of constituency trees, they cannot be used to describe dependency parsers .Page 1, “Introduction”
- In this paper, we define an analogous formalism that can be used to define, analyze and compare dependency parsers .Page 1, “Introduction”
- However, parsing schemata are not directly applicable to dependency parsing , since their formal framework is based on constituency trees.Page 2, “Dependency parsing schemata”
- In spite of this problem, many of the dependency parsers described in the literature are constructive, in the sense that they proceed by combining smaller structures to form larger ones until they find a complete parse for the input sentence.Page 2, “Dependency parsing schemata”
- However, in order to define such a formalism we have to tackle some issues specific to dependency parsers:Page 2, “Dependency parsing schemata”
- Some dependency parsers are also grammar-Page 2, “Dependency parsing schemata”
- 0 The fundamental structures in dependency parsing are dependency graphs.Page 2, “Dependency parsing schemata”
See all papers in Proc. ACL 2008 that mention dependency parsing.
See all papers in Proc. ACL that mention dependency parsing.
Back to top.
dependency trees
Appears in 18 sentences as: dependency tree (8) dependency trees (11)
In A Deductive Approach to Dependency Parsing
- In order to make the formalism general enough to include these parsers, we define items in terms of sets of partial dependency trees as shown in Figure 1.Page 2, “Dependency parsing schemata”
- Such spans cannot be represented by a single dependency tree .Page 2, “Dependency parsing schemata”
- Therefore, our formalism allows items to be sets of forests of partial dependency trees , instead of sets of trees.Page 2, “Dependency parsing schemata”
- Partial dependency trees: We define the set of partial dependency trees (D-trees) as the set of finite trees where children of each node have a left-to-right ordering, each node is labelled with an element of EU (E x lN) , and the following conditions hold:Page 3, “Dependency parsing schemata”
- We denote the root node of a partial dependency tree 75 as root(t).Page 3, “Dependency parsing schemata”
- Relationship between trees and graphs: Let t E D-trees be a partial dependency tree ; g(t), its associated dependency graph, is a graph (V, E) 0 V ={wi E (E x N) | w, is the label ofa node in t}, o E ={(gi,wj) E (E x ]N)2 | C,D are nodes in t such that D is a daughter of C, wj the label of a daughter of C, y, the label of a daughter of D}.Page 3, “Dependency parsing schemata”
- Projectivity: A partial dependency tree 75 E D-trees is projective iff yield (75) cannot be written as...gi...gj...wherei2j.Page 3, “Dependency parsing schemata”
- Parse tree: A partial dependency tree 75 E D-trees is a parse tree for a given string wl .Page 3, “Dependency parsing schemata”
- Item set: Let 6 g D-trees be the set of dependency trees which are acceptable according to a given grammar G (which may be a grammar of D-rules or of CFG—like rules, as explained above).Page 3, “Dependency parsing schemata”
- This parser works with dependency trees which are linked to each other by creating links between their heads.Page 3, “Dependency parsing schemata”
- Its item set is defined as 100196 2 {[i,j,h] | 1 g i g h gj g n}, where an item [i, j, h] is defined as the set of forests containing a single projective dependency tree 75 such that t is grounded, yield(t) = y,- .Page 3, “Dependency parsing schemata”
See all papers in Proc. ACL 2008 that mention dependency trees.
See all papers in Proc. ACL that mention dependency trees.
Back to top.
parse tree
Appears in 13 sentences as: Parse tree (1) parse tree (6) Parse trees (1) parse trees (6)
In A Deductive Approach to Dependency Parsing
- Each item contains a piece of information about the sentence’s structure, and a successful parsing process will produce at least one final item containing a full parse tree for the sentence or guaranteeing its existence.Page 1, “Introduction”
- Items in parsing schemata are formally defined as sets of partial parse trees from a set denotedPage 1, “Introduction”
- Trees(G), which is the set of all the possible partial parse trees that do not violate the constraints imposed by a grammar G. More formally, an item set I is defined by Sikkel as a quotient set associated with an equivalence relation on Trees(G).1Page 1, “Introduction”
- Valid parses for a string are represented by items containing complete marked parse trees for that string.Page 1, “Introduction”
- (N, E, P, S), a marked parse tree for a string wl .Page 2, “Introduction”
- Parse tree: A partial dependency tree 75 E D-trees is a parse tree for a given string wl .Page 3, “Dependency parsing schemata”
- .Qn, we will say it is a projective parse tree for the string.Page 3, “Dependency parsing schemata”
- Final items in this formalism will be those containing some forest F containing a parse tree for some arbitrary string.Page 3, “Dependency parsing schemata”
- When defining projective parsers, correct final items will be those containing projective parse trees for wl .Page 3, “Dependency parsing schemata”
- The set of final items is {[1,n, h] | 1 g h g n}: these items trivially represent parse trees for the input sentence, where wh is the sentence’s head.Page 3, “Dependency parsing schemata”
- Deduction steps are shown in Figure 2, and the set of final items is {[0, n, ( Parse trees have we as their head, as in the previous algorithm).Page 5, “Dependency parsing schemata”
See all papers in Proc. ACL 2008 that mention parse tree.
See all papers in Proc. ACL that mention parse tree.
Back to top.
parsing algorithms
Appears in 7 sentences as: parsing algorithm (1) parsing algorithms (6)
In A Deductive Approach to Dependency Parsing
- We define a new formalism, based on Sikkel’s parsing schemata for constituency parsers, that can be used to describe, analyze and compare dependency parsing algorithms .Page 1, “Abstract”
- The formalism of parsing schemata (Sikkel, 1997) is a useful tool for the study of constituency parsers since it provides formal, high-level descriptions of parsing algorithms that can be used to prove their formal properties (such as correctness), establish relations between them, derive new parsers from existing ones and obtain efficient implementations automatically (Gomez-Rodriguez et al., 2007).Page 1, “Introduction”
- 0 Some of the most popular dependency parsing algorithms , like that of Eisner (1996), work by connecting spans which can represent disconnected dependency graphs.Page 2, “Dependency parsing schemata”
- 3 Some practical examples 3.1 C0196 (Collins, 96) One of the most straightforward projective dependency parsing strategies is the one described by Collins (1996), directly based on the CYK parsing algorithm .Page 3, “Dependency parsing schemata”
- We have defined a variant of Sikkel’s parsing schemata formalism which allows us to represent dependency parsing algorithms in a simple, declarative way7.Page 8, “Dependency parsing schemata”
- Parsing schemata are also a formal tool that can be used to prove the correctness of parsing algorithms .Page 8, “Dependency parsing schemata”
- 8Note that spanning tree parsing algorithms based on edge-factored models, such as the one by McDonald et al.Page 8, “Dependency parsing schemata”
See all papers in Proc. ACL 2008 that mention parsing algorithms.
See all papers in Proc. ACL that mention parsing algorithms.
Back to top.
constituency parsers
Appears in 6 sentences as: constituency parsers (4) constituency parsing (2)
In A Deductive Approach to Dependency Parsing
- We define a new formalism, based on Sikkel’s parsing schemata for constituency parsers , that can be used to describe, analyze and compare dependency parsing algorithms.Page 1, “Abstract”
- This is an alternative to constituency parsing , which tries to find a division of the sentence into segments (constituents) which are then broken up into smaller constituents.Page 1, “Introduction”
- The formalism of parsing schemata (Sikkel, 1997) is a useful tool for the study of constituency parsers since it provides formal, high-level descriptions of parsing algorithms that can be used to prove their formal properties (such as correctness), establish relations between them, derive new parsers from existing ones and obtain efficient implementations automatically (Gomez-Rodriguez et al., 2007).Page 1, “Introduction”
- Therefore, as items for constituency parsers are defined as sets of partial constituency trees, it is tempting to define items for dependency parsers as sets of partial dependency graphs.Page 2, “Dependency parsing schemata”
- Once we have this definition of an item set for dependency parsing, the remaining definitions are analogous to those in Sikkel’s theory of constituency parsing (Sikkel, 1997), so we will not include them here in full detail.Page 3, “Dependency parsing schemata”
- However, when executing this schema with a deductive engine, we can recover the parse forest by following back pointers in the same way as is done with constituency parsers (Billot and Lang, 1989).Page 4, “Dependency parsing schemata”
See all papers in Proc. ACL 2008 that mention constituency parsers.
See all papers in Proc. ACL that mention constituency parsers.
Back to top.
