Supertagging-based Parsing with Linear Context-free Rewriting Systems

Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 2923–2935 June 6–11, 2021. ©2021 Association for Computational Linguistics 2923 Supertagging-based Parsing with Linear Context-free Rewriting Systems Thomas Ruprecht and Richard M¨orbitz Faculty of Computer Science Technische Universit¨at Dresden 01062 Dresden, Germany {thomas.ruprecht,richard.moerbitz}@tu-dresden.de Abstract We present the first supertagging-based parser for linear context-free rewriting systems (LCFRS). It utilizes neural classifiers and out- performs previous LCFRS-based parsers in both accuracy and parsing speed by a wide margin. Our results keep up with the best (gen- eral) discontinuous parsers, particularly the scores for discontinuous constituents establish a new state of the art. The heart of our ap- proach is an efficient lexicalization procedure which induces a lexical LCFRS from any dis- continuous treebank. We describe a modifica- tion to usual chart-based LCFRS parsing that accounts for supertagging and introduce a pro- cedure that transforms lexical LCFRS deriva- tions into equivalent parse trees of the origi- nal treebank. Our approach is evaluated on the English Discontinuous Penn Treebank and the German treebanks Negra and Tiger. 1 Introduction In NLP, constituency parsing is a task that assigns – usually tree-shaped – syntactic structures to sen- tences. Formalisms such as context-free grammars (CFG) are used in this setting because they are conceptually simple, interpretable, and parsing is tractable (cubic in sentence length). Discontinuous constituents span non-contigu- ous sets of positions in a sentence. The result- ing phrase structures do not take the shape of a tree anymore, as they contain crossing branches (cf. the left of Fig. 1), and cannot be modeled by CFG. As a countermeasure, many treebanks, e.g. the Penn Treebank (PTB; Marcus et al., 1994), de- note these phrase structures as trees nevertheless and introduce designated notations for discontinu- ity, which is then often ignored in parsing. How- ever, discontinuity occurs in about 20 % of the sentences in the PTB and to an even larger ex- tent in German treebanks such as Negra and Tiger. For parsing discontinuous constituents, so-called mildly context-sensitive grammar formalisms have been investigated, e.g. tree-adjoining grammars (TAG; Joshi et al., 1975) and linear context-free rewriting systems (LCFRS; Vijay-Shanker et al., 1987). An LCFRS derivation of a discontinuous phrase is shown in the right of Fig. 1. The in- creased expressiveness of these formalisms comes at the cost of a higher parsing complexity: given a sentence of length n, parsing is in O(n6) for TAG and O(n3·fo(G)) for a binary LCFRS G. The grammar-specific fanout fo(G) indicates that G can parse constituents spanning up to n non-contiguous sets of positions. TAG have the same expressive- ness as LCFRS with fanout 2 (Seki et al., 1991), which accounts for 96.67 % of the sentences in Ne- gra and 96.83 % of the sentences in Tiger (Maier and Søgaard, 2008). Previous publications have established mildly context-sensitive formalisms in the field of statistical constituent parsing, and found methods to tame the high parsing complex- ity (Evang and Kallmeyer, 2011; Kallmeyer and …

Content truncated to 500 words