mlsanityData to 7 Oct 2026

Unsupervised Discontinuous Constituency Parsing with Mildly Context-Sensitive Grammars

arXiv 2212.09140 ↗First posted 18 Dec 2022cs.CLcited by 7

Not on the map. Why?

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

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

Builds on

31 of 85 references.

References · 31

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2020Einsum Networks: Fast and Scalable Learning of Tractable Probabilistic Circuitscited by 102
  3. 2018Ordered Neurons: Integrating Tree Structures into Recurrent Neural Networkscited by 101
  4. 2019Compound Probabilistic Context-Free Grammars for Grammar Inductioncited by 76
  5. 2017Neural Language Modeling by Jointly Learning Syntax and Lexiconcited by 57
  6. 2017Introduction to Tensor Decompositions and their Applications in Machine Learningcited by 45
  7. 2022Scaling Up Probabilistic Circuits by Latent Variable Distillationcited by 35
  8. 2020Visually Grounded Compound PCFGscited by 34
  9. 2021Sequence-to-Sequence Learning with Latent Neural Grammarscited by 30
  10. 2020Scaling Hidden Markov Language Modelscited by 22
  11. 2021VLGrammar: Grounded Grammar Induction of Vision and Languagecited by 22
  12. 2021PCFGs Can Do Better: Inducing Probabilistic Context-Free Grammars with Many Symbolscited by 22
19 more
  1. 2020The Return of Lexical Dependencies: Neural Lexicalized PCFGscited by 19
  2. 2020On the Role of Supervision in Unsupervised Constituency Parsingcited by 18
  3. 2021Neural Bi-Lexicalized PCFG Inductioncited by 18
  4. 2021Video-aided Unsupervised Grammar Inductioncited by 17
  5. 2022Finding Dataset Shortcuts with Grammar Inductioncited by 15
  6. 2018Unsupervised Learning of Syntactic Structure with Invertible Neural Projectionscited by 11
  7. 2020Span-based discontinuous constituency parsing: a family of exact chart-based algorithms with time complexities from O(n^6) down to O(n^3)cited by 11
  8. 2020Second-Order Unsupervised Neural Dependency Parsingcited by 10
  9. 2022Dynamic Programming in Rank Space: Scaling Structured Inference with Low-Rank HMMs and PCFGscited by 10
  10. 2020Discontinuous Constituent Parsing as Sequence Labelingcited by 9
  11. 2022Low-Rank Constraints for Fast Inference in Structured Modelscited by 8
  12. 2017Dependency Grammar Induction with Neural Lexicalization and Big Training Datacited by 7
  13. 2022Hierarchical Phrase-based Sequence-to-Sequence Learningcited by 7
  14. 2020Discontinuous Constituent Parsing with Pointer Networkscited by 6
  15. 2021Reducing Discontinuous to Continuous Parsing with Pointer Network Reorderingcited by 5
  16. 2020Factor Graph Grammarscited by 4
  17. 2021Discontinuous Grammar as a Foreign Languagecited by 4
  18. 2022Learning a Grammar Inducer from Massive Uncurated Instructional Videoscited by 3
  19. 2021Dependency Induction Through the Lens of Visual Perceptioncited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 3; 2024: 2; 2025: 1; 2026: 1.

7 papers.

  1. 2023A Theory of Emergent In-Context Learning as Implicit Structure Inductioncited by 86
  2. 2023Grammar Prompting for Domain-Specific Language Generation with Large Language Modelscited by 58
  3. 2024Analyzing The Language of Visual Tokenscited by 12
  4. 2023Simple Hardware-Efficient PCFGs with Independent Left and Right Productionscited by 3
  5. 2024Tree-Averaging Algorithms for Ensemble-Based Unsupervised Discontinuous Constituency Parsingcited by 0
  6. 2025Understanding Syntactic Generalization in Structure-inducing Language Modelscited by 0
  7. 2026Holographic Neural PCFG for Unsupervised Parsingcited by 0