tailieunhanh - Báo cáo khoa học: "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. 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 stateof-the-art transition-based parser on four data sets from the CoNLL-X shared task. . | A Transition-Based Parser for 2-Planar Dependency Structures Carlos Gomez-Rodriguez Departamento de Computacion Universidade da Coruna Spain Joakim Nivre Department of Linguistics and Philology Uppsala University Sweden 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. 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. 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. 1 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 . 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 . Caught between the Scylla of linguistically inadequate projective trees and the Charybdis of computationally intractable non-projective trees some researchers have sought a middle ground by exploring classes of mildly non-projective dependency structures that strike a better balance between expressivity and complexity Nivre 2006 Kuhlmann and Nivre 2006 Kuhlmann and Mohl 2007 Havelka 2007 . Although