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(l6) time to parse, reducing inference to O(l5). 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
Most unsupervised parsers—models that attempt to learn the underlying grammar of a language from raw text—rely on Probabilistic Context-Free Grammars (PCFGs). While PCFGs are efficient, they assume that phrases are always contiguous blocks of words. However, in many languages like German and Dutch, phrases are frequently interrupted by other words, creating "discontinuous" structures.
As shown in Figure 1, the German sentence "Im Oktober wurde Passent in Berlin operiert" contains a discontinuous structure that standard PCFGs cannot naturally represent. While Mildly Context-Sensitive Grammars (MCSGs) like Linear Context-Free Rewriting Systems (LCFRS) can handle these patterns, they are notoriously difficult to use for unsupervised learning due to their massive computational complexity ($O(\ell^6)$ for sentence length $\ell$) and high parameter requirements.
Methodology: TN-LCFRS
This paper introduces TN-LCFRS (Tensor-decomposition-based Neural LCFRS), the first unsupervised parser capable of inducing discontinuous constituency trees. The approach makes discontinuous parsing tractable through three primary engineering choices:
- Restricted Formalism: The model uses a binary LCFRS with a "fan-out" of two, meaning a phrase can consist of at most two separate blocks. By discarding specific rare rule types, the authors reduce parsing complexity from $O(\ell^6)$ to $O(\ell^5)$.
- Tensor Decomposition: Typically, the number of rules in these grammars grows cubically with the number of nonterminal symbols ($m^3$). By applying Canonical-Polyadic Decomposition (CPD), the massive rule probability tensor is factorized into smaller matrices, making the complexity linear in $m$ and allowing the model to scale to thousands of nonterminals.
- Neural Parameterization: Instead of learning a static table of probabilities, a neural network generates rule weights based on shared embeddings for the grammar symbols, allowing the model to share knowledge between similar phrase types.
For inference, the model employs Minimal Bayes Risk (MBR) decoding, which identifies the tree that maximizes the expected number of correct constituents rather than just the single most likely tree.
Experimental Results
The researchers evaluated TN-LCFRS on languages known for frequent word-order displacement, specifically German (TIGER and NEGRA treebanks) and Dutch (LASSY Small Corpus).
The Impact of Scaling
A key insight from the experiments is that overparameterization is a feature: using a very large number of nonterminals (up to 4,500) was crucial for success. Even if the underlying "rank" of the grammar is low, a high-dimensional space helps the model explore and find better linguistic structures during learning.
As illustrated in Figure 4, the TN-LCFRS₄₅₀₀ variant significantly outperformed smaller models and standard neural PCFGs. On the German NEGRA dataset, it achieved an overall F1 of 46.1, compared to 40.8 for a standard PCFG. More importantly, it achieved a Discontinuous F1 (DF1) of 8.0 on NEGRA and 8.9 on Dutch LASSY, whereas standard PCFGs score zero by definition.
Conclusion and Limitations
TN-LCFRS demonstrates that correctly modeling discontinuous phenomena can actually improve accuracy on standard continuous spans as well. However, the model remains computationally heavy and sensitive to initialization. It also struggled with English, where the signal for discontinuity is too sparse (~1.8% of constituents) for the model to pick up without supervision. Future work will focus on reducing computational costs and finding ways to "nudge" the model toward these structures in languages where they are rare.
Summary updated