Discontinuous Combinatory Constituency Parsing

Discontinuous Combinatory Constituency Parsing Zhousi Chen and Mamoru Komachi Faculty of Systems Design Tokyo Metropolitan University 6-6 Asahigaoka, Hino, Tokyo 191-0065, Japan {chen-zhousi@ed., komachi@}tmu.ac.jp Abstract We extend a pair of continuous combinator- based constituency parsers (one binary and one multi-branching) into a discontinuous pair. Our parsers iteratively compose con- stituent vectors from word embeddings with- out any grammar constraints. Their empirical complexities are subquadratic. Our extension includes 1) a swap action for the orientation- based binary model and 2) biaffine attention for the chunker-based multi-branching model. In tests conducted with the Discontinuous Penn Treebank and TIGER Treebank, we achieved state-of-the-art discontinuous accu- racy with a significant speed advantage. 1 Introduction Discontinuity is common in natural languages, as illustrated in Figure 1. Children from a discon- tinuous constituent are not necessarily consecu- tive because each can group with its syntactic cousins in the sentence rather than its two adja- cent neighbors. Although this relaxation makes discontinuous parsing more challenging than con- tinuous parsing, it becomes more valuable for studies and applications in non-configurational languages (Johnson, 1985), where word order does not determine grammatical function. With gradu- ally saturated continuous parsing accuracy (Zhou and Zhao, 2019; Kitaev and Klein, 2018, 2020; Xin et al., 2021), discontinuous parsing has started gaining more attention (Fern´andez-Gonz´alez and G´omez-Rodr´ıguez, 2020a, 2021; Corro, 2020). Typically, constituency parsers are divided into two genres (not including methods employing de- pendency parsing, e.g., Fern´andez-Gonz´alez and G´omez-Rodr´ıguez [2020b]): 1) Global parsers use a fixed chart to search through all parsing possi- bilities for a global optimum. 2) Local parsers rely on fewer local decisions, which leads to lower complexities. The global parser complexi- ties start at least from binary O(n3) (Kitaev and Klein, 2018) or m-ary O(n4) (Xin et al., 2021), resulting in low speeds for long parses. Global parsers introduce numerous hypotheses, whereas a local shift-reduce process or incremental parse ex- hibits more linguistic interests with fewer outputs (Yoshida et al., 2021; Kitaev et al., 2022). Neu- ral global parsers dominate both continuous and discontinuous parsing (Corro, 2020; Ruprecht and M¨orbitz, 2021) in terms of F1 score, but they do not exhibit a strong accuracy advantage over other parsers. Although local parsers may in some cases produce ill-formed trees, global parsers do not guarantee the selection of gold-standard answers from their charts. We propose extending a pair of local parsers to achieve high speed, accuracy, and convenient investigation for both binary and multi-branching parses. Chen et al. (2021) proposed a pair of continuous parsers employing bottom-up vector compositionality. We dub these as neural combi- natory constituency parsers (NCCP) with binary CB and multi-branching CM. To the best of our knowledge, they possess the top parsing speeds for continuous constituency. CB reflects a linguis- tic branching tendency, whereas CM represents unsupervised grammatical headedness through composition weight. CM is among the few parsers that do not require preprocessing binarization (Xin et al., 2021) but possess a high parsing speed. We dub our extension as DCCP with binary DB and multi-branching DM. The …

Content truncated to 500 words