Discontinuous Constituency Parsing with a Stack-Free Transition System and a Dynamic Oracle

Maximin Coavoux, Shay Cohen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We introduce a novel transition system for discontinuous constituency parsing. Instead of storing subtrees in a stack –i.e. a data structure with linear-time sequential access– the proposed system uses a set of parsing items, with constant-time random access. This change makes it possible to construct any discontinuous constituency tree in exactly 4n − 2 transitions for a sentence of length n, whereas existing systems need a quadratic number of transitions to derive some structures. At each parsing step, the parser considers every item in the set to be combined with a focus item and to construct a new constituent in a  bottom-up fashion. The parsing strategy is based on the assumption that most syntactic structures can be parsed incrementally and that the set – the memory of the parser– remains reasonably small on average. Moreover, we introduce a dynamic oracle for the new transition system, and present the first experiments in discontinuous constituency parsing using a dynamic oracle. Our parser obtains state-of-the-art results on three English and German discontinuous treebanks.
Original languageEnglish
Title of host publicationProceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics
EditorsJill Burstein, Christy Doran, Thamar Solorio
Place of PublicationMinneapolis, Minnesota
PublisherAssociation for Computational Linguistics (ACL)
Pages204–217
Number of pages14
Volume1
DOIs
Publication statusPublished - 7 Jun 2019
Event2019 Annual Conference of the North American Chapter of the Association for Computational Linguistics - Minneapolis, United States
Duration: 2 Jun 20197 Jun 2019
https://naacl2019.org/

Conference

Conference2019 Annual Conference of the North American Chapter of the Association for Computational Linguistics
Abbreviated titleNAACL-HLT 2019
Country/TerritoryUnited States
CityMinneapolis
Period2/06/197/06/19
Internet address

Fingerprint

Dive into the research topics of 'Discontinuous Constituency Parsing with a Stack-Free Transition System and a Dynamic Oracle'. Together they form a unique fingerprint.

Cite this