Discontinuous Constituent Parsing as Sequence Labeling

Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, pages 2771–2785, November 16–20, 2020. c⃝2020 Association for Computational Linguistics 2771 Discontinuous Constituent Parsing as Sequence Labeling David Vilares and Carlos G´omez-Rodr´ıguez Universidade da Coru˜na, CITIC Departamento de Ciencias de la Computaci´on y Tecnolog´ıas de la Informaci´on Campus de Elvi˜na s/n, 15071 A Coru˜na, Spain {david.vilares,carlos.gomez}@udc.es Abstract This paper reduces discontinuous parsing to sequence labeling. It first shows that exist- ing reductions for constituent parsing as label- ing do not support discontinuities. Second, it fills this gap and proposes to encode tree dis- continuities as nearly ordered permutations of the input sequence. Third, it studies whether such discontinuous representations are learn- able. The experiments show that despite the architectural simplicity, under the right repre- sentation, the models are fast and accurate.1 1 Introduction Discontinuous constituent parsing studies how to generate phrase-structure trees of sentences com- ing from non-configurational languages (John- son, 1985), where non-consecutive tokens can be part of the same grammatical function (e.g. non- consecutive terms belonging to the same verb phrase). Figure 1 shows a German sentence exhibit- ing this phenomenon. Discontinuities happen in languages that exhibit free word order such as Ger- man or Guugu Yimidhirr (Haviland, 1979; Johnson, 1985), but also in those with high rigidity, e.g. En- glish, whose grammar allows certain discontinuous expressions, such as wh-movement or extraposition (Evang and Kallmeyer, 2011). This makes discon- tinuous parsing a core computational linguistics problem that affects a wide spectrum of languages. There are different paradigms for discontinu- ous phrase-structure parsing, such as chart-based parsers (Maier, 2010; Corro, 2020), transition- based algorithms (Coavoux and Crabb´e, 2017; Coavoux and Cohen, 2019) or reductions to a prob- lem of a different nature, such as dependency pars- ing (Hall and Nivre, 2008; Fern´andez-Gonz´alez and Martins, 2015). However, many of these ap- proaches come either at a high complexity or low 1https://github.com/aghie/disco2labels Noch nie habe ich so viel gewählt . SROOT VP AVP ADV ADV VAFIN PPER ADV ADV VVPP $. AVP (Yet) (never) (have) (I) (so) (much) (chosen) . Figure 1: An example of a German sentence exhibiting discontinuous structures, extracted from the NEGRA treebank (Skut et al., 1997). A valid English translation is: ‘Never before I have chosen so much.’ speed, while others give up significant performance to achieve an acceptable latency (Maier, 2015). Related to these research aspects, this work ex- plores the feasibility of discontinuous parsing un- der the sequence labeling paradigm, inspired by G´omez-Rodr´ıguez and Vilares (2018)’s work on fast and simple continuous constituent parsing. We will focus on tackling the limitations of their en- coding functions when it comes to analyzing dis- continuous structures, and include an empirical comparison against existing parsers. Contribution (i) The first contribution is theoret- ical: to reduce constituent parsing of free word or- der languages to a sequence labeling problem. This is done by encoding the order of the sentence as (nearly ordered) permutations. We present various ways of doing so, which can be naturally combined with the …

Content truncated to 500 words