2019/04/01 by Maximin Coavoux, Shay B. Cohen, Coavoux, Maximin +1
Computer Science · #Computation and Language (cs.CL) #FOS: Computer and information sciences #Machine Learning and Algorithms #Natural Language Processing Techniques #Network Packet Processing and Optimization #Topic Modeling
paper · pdf · doi:10.48550/arxiv.1904.00615
openalex publication_date 2019/04/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce a novel transition system for discontinuous constituency\nparsing. Instead of storing subtrees in a stack --i.e. a data structure with\nlinear-time sequential access-- the proposed system uses a set of parsing\nitems, with constant-time random access. This change makes it possible to\nconstruct any discontinuous constituency tree in exactly 4n - 2 transitions\nfor a sentence of length n. At each parsing step, the parser considers every\nitem in the set to be combined with a focus item and to construct a new\nconstituent in a bottom-up fashion. The parsing strategy is based on the\nassumption that most syntactic structures can be parsed incrementally and that\nthe set --the memory of the parser-- remains reasonably small on average.\nMoreover, we introduce a provably correct dynamic oracle for the new transition\nsystem, and present the first experiments in discontinuous constituency parsing\nusing a dynamic oracle. Our parser obtains state-of-the-art results on three\nEnglish and German discontinuous treebanks.\n