Unsupervised Discontinuous Constituency Parsing with Mildly Context-Sensitive Grammars (2023)

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 computational complexity of both parsing and parameter estimation, we restrict the grammar formalism to LCFRS-2 (i.e., binary LCFRS with fan-out two) and further discard rules that require O(l^6) time to parse, reducing inference to O(l^5) . We find that using a large number of nonterminals is beneficial and thus make use of tensor decomposition-based rank-space dynamic programming with an embedding-based parameterization of rule probabilities to scale up the number of nonterminals. Experiments on German and Dutch show that our approach is able to induce linguistically meaningful trees with continuous and discontinuous structures.

## introduction unsupervised parsing aims to induce hierarchical linguistic structures given only the strings in a language. a classic approach to unsupervised parsing is through probabilistic grammar induction @xcite , which learns a probabilistic grammar (i.e., a set of rewrite rules and their probabilities) from raw text. recent work has shown that neural parameterizations of probabilistic contextfree 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 @xcite @xcite @xcite . 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 . wh-movements. mildly context-sensitive grammars @xcite , which sit between context-free and context-sensitive grammars in the classic chomsky-schützenberger hierarchy @xcite ), foot_0 are powerful enough to model richer aspects of natural language including discontinuous and non-local phenomena. and despite their expressivity they enjoy polynomial-time inference algorithms, making them attractive both as cognitively plausible models of human language processing and as targets for unsupervised learning. there are several weakly equivalent formalisms for generating the mildly context-sensitive languages which might serve as potential targets for grammar induction: tree adjoining grammars @xcite , head grammars @xcite , combinatory categorial grammars @xcite , and linear indexed grammars @xcite . in this paper we work with linear context-free rewriting systems @xcite , which generalize the above formalisms and are weakly equivalent to multiple context-free grammars @xcite . derivation trees in an lcfrs directly correspond to discontinuous constituency trees where each node can dominate a non-contiguous sequence of words in the yield, as shown in fig. 1 . we focus on the lcfrs formalism as it has previously been successfully employed for supervised discontinuous constituency parsing @xcite @xcite . the complexity of parsing in a lcfrs is o(ℓ 3k |g|), where ℓ is the sentence length, k is the fan-out (the maximum number of contiguous blocks of text that can be dominated by a nonterminal), and |g| is the grammar size. while polynomial, this is too high to be practical for unsupervised learning on real-world data. we thus restrict ourselves to lcfrs-2, i.e., binary lcfrs with fan-out two, which has been shown to have high coverage on discontinuous treebanks @xcite . even with this restriction lcfrs-2 remains difficult to induce from raw text due to the o(ℓ 6 |g|) dynamic program for parsing and marginalization. however @xcite observe that a o(ℓ 5 |g|) variant of the grammar that discards certain rules can still recover 98% of real world treebank constituents. our approach uses with this restricted variant of lcfrs-2 (see sec 2.2). finally, following recent work which finds that that overparameterizing deep latent variable models is beneficial for unsupervised learning @xcite @xcite , we scale lcfrs-2 to a large number of nonterminals by adapting tensor-decomposition-based inference techniques-originally developed for pcfgs @xcite @xcite -to the lcfrs case. we conduct experiments german and dutchboth of which have frequent discontinuous and non-local language phenomena and have available discontinuous treebanks-and observe that our approach is able to induce grammars with nontrivial performance on discontinuous constituents. ## empirical study data. we conduct experiments with our tensor decomposition-based neural lcfrs (tn-lcfrs) on german and dutch, where discontinuous phenomena are more common (than in english). for german we concatenate tiger @xcite and negra @xcite as our training set, while for dutch we use the lassy small corpus treebank @xcite . the data split can be found in app. b.1. for processing we use disco-dop 5 @xcite and discard all punctuation marks. we further take the most frequent 10,000 words for each language as the vocabulary, similar to the standard setup in unsupervised constituency parsing on ptb @xcite @xcite . ## related work mildly context-sensitive grammars. given the evidence against the context-freeness of natural language @xcite , mildly context-sensitive grammars such as tree adjoining grammars were thought to be just flexible (but still constrained) enough to model natural language @xcite . prior work on inducing mildly context-sensitive grammars has generally focused on combinatory categorial grammars @xcite , and we are unaware of any work on in-ducing lcfrss from observed yields alone. our work is also related to the rich line of work on supervised discontinuous parsing @xcite @xcite @xcite @xcite , though we are unaware of any prior work on unsupervised discontinuous parsing. neural grammars. early work on probabilistic approaches to grammar induction was largely negative @xcite . however, recent work has shown that neural parameterizations of classic grammars can greatly improve structure induction. our work adds to the line of work on neural parameterizations of dependency models @xcite @xcite , context-free grammars @xcite @xcite , and synchronous grammars @xcite @xcite . neural parameterizations make it easy to share parameters and condition on additional side information (images/audio/video) which has shown to be particularly useful for multimodal grammar induction @xcite @xcite @xcite . scaling latent variable models. @xcite study the empirical benefits of overparameterization in learning latent variable models. other works have explored parameterizations of latent variable models that make it especially amenable to scaling @xcite @xcite . relatedly, @xcite and @xcite show the benefits of scaling probabilistic circuits @xcite . ## conclusion this work studied unsupervised discontinuous constituency parsing with mildly context-sensitive grammars, focusing on the formalism of linear context-free rewriting systems. by using a tensor decomposition-based neural parameterization of linear context-free rewriting systems, our approach was able to induce grammars that had nontrivial discontinuous parsing performance on german and dutch. whether even more expressive grammars will eventually lead to models learn linguistically meaningful structures and are at the same time competitive with pure neural language models (as a language model) remains an open question.