Unsupervised Discontinuous Constituency Parsing with Mildly Context-Sensitive Grammars

Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics Volume 1: Long Papers, pages 5747–5766 July 9-14, 2023 ©2023 Association for Computational Linguistics Unsupervised Discontinuous Constituency Parsing with Mildly Context-Sensitive Grammars Songlin Yang ShanghaiTech University yangsl66@mit.edu Roger P. Levy MIT BCS rplevy@mit.edu Yoon Kim MIT CSAIL yoonkim@mit.edu Abstract We study grammar induction with mildly context-sensitive grammars for unsupervised discontinuous parsing. Using the probabilistic linear context-free rewriting system (LCFRS) formalism, our approach fixes the rule structure in advance and focuses on parameter learning with maximum likelihood. To reduce the com- putational complexity of both parsing and pa- rameter estimation, we restrict the grammar for- malism to binary LCFRS with fan-out two and further discard rules that require O(ℓ6) time to parse, reducing inference to O(ℓ5). We find that using a large number of nontermi- nals is beneficial and thus make use of tensor decomposition-based rank-space dynamic pro- gramming with an embedding-based parame- terization of rule probabilities to scale up the number of nonterminals. Experiments on Ger- man and Dutch show that our approach is able to induce linguistically meaningful trees with continuous and discontinuous structures. 1 Introduction Unsupervised parsing aims to induce hierarchical linguistic structures given only the strings in a lan- guage. A classic approach to unsupervised parsing is through probabilistic grammar induction (Lari and Young, 1990), which learns a probabilistic grammar (i.e., a set of rewrite rules and their proba- bilities) from raw text. Recent work has shown that neural parameterizations of probabilistic context- free grammars (PCFG), wherein the grammar’s rule probabilities are given by a neural network over shared symbol embeddings, can achieve promising results on unsupervised constituency parsing (Kim et al., 2019; Jin et al., 2019, 2021; Yang et al., 2021b, 2022). However, context-free rules are not natural for modeling discontinuous language phenomena such as extrapositions, cross-serial dependencies, and Code: https://github.com/sustcsonglin/TN-LCFRS. S(1) VP(2) PP(1) PP(1) APPR NN VAFIN NE APPR NE VVPP Im Oktober wurde Passent in Berlin operiert In Octobor surgery Passent in Berlin underwent Figure 1: An example of a discontinuous parse tree in German. Each non-leaf node’s fan-out is marked in brackets. wh-movements. Mildly context-sensitive grammars (Joshi, 1985), which sit between context-free and context-sensitive grammars in the classic Chom- sky–Schützenberger hierarchy (Chomsky, 1959; Chomsky and Schützenberger, 1963),1 are pow- erful enough to model richer aspects of natural language including discontinuous and non-local phenomena. And despite their expressivity they en- joy polynomial-time inference algorithms, making them attractive both as cognitively plausible mod- els of human language processing and as targets for unsupervised learning. There are several weakly equivalent formalisms for generating the mildly context-sensitive lan- guages which might serve as potential targets for grammar induction: tree adjoining grammars (Joshi, 1975), head grammars (Pollard, 1985), com- binatory categorial grammars (Steedman, 1987), and linear indexed grammars (Gazdar, 1988). In this paper we work with linear context-free rewrit- ing systems (LCFGS, Vijay-Shanker et al., 1987), 1This hierarchy does not necessarily extend to proba- bilistic grammars. For example Icard (2020) show that in a particular probabilistic …

Content truncated to 500 words