A Deductive Approach to Dependency Parsing

Proceedings of ACL-08: HLT, pages 968–976, Columbus, Ohio, USA, June 2008. c⃝2008 Association for Computational Linguistics A Deductive Approach to Dependency Parsing∗ Carlos G´omez-Rodr´ıguez Departamento de Computaci´on Universidade da Coru˜na, Spain cgomezr@udc.es John Carroll and David Weir Department of Informatics University of Sussex, United Kingdom {johnca,davidw}@sussex.ac.uk Abstract We define a new formalism, based on Sikkel’s parsing schemata for constituency parsers, that can be used to describe, analyze and com- pare dependency parsing algorithms. This abstraction allows us to establish clear rela- tions between several existing projective de- pendency parsers and prove their correctness. 1 Introduction Dependency parsing consists of finding the structure of a sentence as expressed by a set of directed links (dependencies) between words. This is an alterna- tive to constituency parsing, which tries to find a di- vision of the sentence into segments (constituents) which are then broken up into smaller constituents. Dependency structures directly show head-modifier and head-complement relationships which form the basis of predicate argument structure, but are not represented explicitly in constituency trees, while providing a representation in which no non-lexical nodes have to be postulated by the parser. In addi- tion to this, some dependency parsers are able to rep- resent non-projective structures, which is an impor- tant feature when parsing free word order languages in which discontinuous constituents are common. 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), es- tablish relations between them, derive new parsers from existing ones and obtain efficient implementa- tions automatically (G´omez-Rodr´ıguez et al., 2007). The formalism was initially defined for context-free grammars and later applied to other constituency- based formalisms, such as tree-adjoining grammars ∗Partially supported by Ministerio de Educaci´on y Ciencia and FEDER (TIN2004-07246-C03, HUM2007-66607-C04), Xunta de Galicia (PGIDIT07SIN005206PR, PGIDIT05PXIC- 10501PN, PGIDIT05PXIC30501PN, Rede Galega de Proc. da Linguaxe e RI) and Programa de Becas FPU. (Alonso et al., 1999). However, since parsing schemata are defined as deduction systems over sets of constituency trees, they cannot be used to de- scribe dependency parsers. In this paper, we define an analogous formalism that can be used to define, analyze and compare de- pendency parsers. We use this framework to provide uniform, high-level descriptions for a wide range of well-known algorithms described in the literature, and we show how they formally relate to each other and how we can use these relations and the formal- ism itself to prove their correctness. 1.1 Parsing schemata Parsing schemata (Sikkel, 1997) provide a formal, simple and uniform way to describe, analyze and compare different constituency-based parsers. The notion of a parsing schema comes from con- sidering parsing as a deduction process which gener- ates intermediate results called items. An initial set of items is directly obtained from the input sentence, and the parsing process consists of the application of inference rules (deduction steps) which produce new items from existing ones. Each item …

Content truncated to 500 words