# Unsupervised Discontinuous Constituency Parsing with Mildly Context-Sensitive Grammars

arXiv: https://arxiv.org/abs/2212.09140 · HTML: https://mlsanity.com/paper/2212.09140/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 85 references that are in the map.
- First posted on arXiv 18 Dec 2022.

## Builds on (most cited first, 30 of 31)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Einsum Networks: Fast and Scalable Learning of Tractable Probabilistic Circuits](https://mlsanity.com/paper/2004.06231/) (2020)
- [Ordered Neurons: Integrating Tree Structures into Recurrent Neural Networks](https://mlsanity.com/paper/1810.09536/) (2018)
- [Compound Probabilistic Context-Free Grammars for Grammar Induction](https://mlsanity.com/paper/1906.10225/) (2019)
- [Neural Language Modeling by Jointly Learning Syntax and Lexicon](https://mlsanity.com/paper/1711.02013/) (2017)
- [Introduction to Tensor Decompositions and their Applications in Machine Learning](https://mlsanity.com/paper/1711.10781/) (2017)
- [Scaling Up Probabilistic Circuits by Latent Variable Distillation](https://mlsanity.com/paper/2210.04398/) (2022)
- [Visually Grounded Compound PCFGs](https://mlsanity.com/paper/2009.12404/) (2020)
- [Sequence-to-Sequence Learning with Latent Neural Grammars](https://mlsanity.com/paper/2109.01135/) (2021)
- [Scaling Hidden Markov Language Models](https://mlsanity.com/paper/2011.04640/) (2020)
- [VLGrammar: Grounded Grammar Induction of Vision and Language](https://mlsanity.com/paper/2103.12975/) (2021)
- [PCFGs Can Do Better: Inducing Probabilistic Context-Free Grammars with Many Symbols](https://mlsanity.com/paper/2104.13727/) (2021)
- [The Return of Lexical Dependencies: Neural Lexicalized PCFGs](https://mlsanity.com/paper/2007.15135/) (2020)
- [On the Role of Supervision in Unsupervised Constituency Parsing](https://mlsanity.com/paper/2010.02423/) (2020)
- [Neural Bi-Lexicalized PCFG Induction](https://mlsanity.com/paper/2105.15021/) (2021)
- [Video-aided Unsupervised Grammar Induction](https://mlsanity.com/paper/2104.04369/) (2021)
- [Finding Dataset Shortcuts with Grammar Induction](https://mlsanity.com/paper/2210.11560/) (2022)
- [Unsupervised Learning of Syntactic Structure with Invertible Neural Projections](https://mlsanity.com/paper/1808.09111/) (2018)
- [Span-based discontinuous constituency parsing: a family of exact chart-based algorithms with time complexities from O(n^6) down to O(n^3)](https://mlsanity.com/paper/2003.13785/) (2020)
- [Second-Order Unsupervised Neural Dependency Parsing](https://mlsanity.com/paper/2010.14720/) (2020)
- [Dynamic Programming in Rank Space: Scaling Structured Inference with Low-Rank HMMs and PCFGs](https://mlsanity.com/paper/2205.00484/) (2022)
- [Discontinuous Constituent Parsing as Sequence Labeling](https://mlsanity.com/paper/2010.00633/) (2020)
- [Low-Rank Constraints for Fast Inference in Structured Models](https://mlsanity.com/paper/2201.02715/) (2022)
- [Dependency Grammar Induction with Neural Lexicalization and Big Training Data](https://mlsanity.com/paper/1708.00801/) (2017)
- [Hierarchical Phrase-based Sequence-to-Sequence Learning](https://mlsanity.com/paper/2211.07906/) (2022)
- [Discontinuous Constituent Parsing with Pointer Networks](https://mlsanity.com/paper/2002.01824/) (2020)
- [Reducing Discontinuous to Continuous Parsing with Pointer Network Reordering](https://mlsanity.com/paper/2104.06239/) (2021)
- [Factor Graph Grammars](https://mlsanity.com/paper/2010.12048/) (2020)
- [Discontinuous Grammar as a Foreign Language](https://mlsanity.com/paper/2110.10431/) (2021)
- [Learning a Grammar Inducer from Massive Uncurated Instructional Videos](https://mlsanity.com/paper/2210.12309/) (2022)

## Built on by (most cited first, 7 of 7)

- [A Theory of Emergent In-Context Learning as Implicit Structure Induction](https://mlsanity.com/paper/2303.07971/) (2023)
- [Grammar Prompting for Domain-Specific Language Generation with Large Language Models](https://mlsanity.com/paper/2305.19234/) (2023)
- [Analyzing The Language of Visual Tokens](https://mlsanity.com/paper/2411.05001/) (2024)
- [Simple Hardware-Efficient PCFGs with Independent Left and Right Productions](https://mlsanity.com/paper/2310.14997/) (2023)
- [Tree-Averaging Algorithms for Ensemble-Based Unsupervised Discontinuous Constituency Parsing](https://mlsanity.com/paper/2403.00143/) (2024)
- [Understanding Syntactic Generalization in Structure-inducing Language Models](https://mlsanity.com/paper/2508.07969/) (2025)
- [Holographic Neural PCFG for Unsupervised Parsing](https://mlsanity.com/paper/2607.08063/) (2026)

## Abstract (arXiv)

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(n^6) time to parse, reducing inference to O(n^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