mlsanityData to 7 Oct 2026

Dynamic Programming in Rank Space: Scaling Structured Inference with Low-Rank HMMs and PCFGs

arXiv 2205.00484 ↗First posted 1 May 2022cs.CL cs.LGcited by 10

Not on the map. Why?

Abstract (arXiv)

Hidden Markov Models (HMMs) and Probabilistic Context-Free Grammars (PCFGs) are widely used structured models, both of which can be represented as factor graph grammars (FGGs), a powerful formalism capable of describing a wide range of models. Recent research found it beneficial to use large state spaces for HMMs and PCFGs. However, inference with large state spaces is computationally demanding, especially for PCFGs. To tackle this challenge, we leverage tensor rank decomposition (aka. CPD) to decrease inference computational complexities for a subset of FGGs subsuming HMMs and PCFGs. We apply CPD on the factors of an FGG and then construct a new FGG defined in the rank space. Inference with the new FGG produces the same result but has a lower time complexity when the rank size is smaller than the state size. We conduct experiments on HMM language modeling and unsupervised PCFG parsing, showing better performance than previous work. Our code is publicly available at urlhttps://github.com/VPeterV/RankSpace-Models.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Builds on 30 of its 64 references that are in the map. First posted on arXiv 1 May 2022.

Builds on

30 of 64 references.

References · 30

  1. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  2. 2018On the Optimization of Deep Networks: Implicit Acceleration by Overparameterizationcited by 280
  3. 2017Regularizing and Optimizing LSTM Language Modelscited by 205
  4. 2020Einsum Networks: Fast and Scalable Learning of Tractable Probabilistic Circuitscited by 102
  5. 2019Compound Probabilistic Context-Free Grammars for Grammar Inductioncited by 76
  6. 2020Fast and Accurate Neural CRF Constituency Parsingcited by 50
  7. 2017Introduction to Tensor Decompositions and their Applications in Machine Learningcited by 45
  8. 2020Torch-Struct: Deep Structured Prediction Librarycited by 40
  9. 2020Visually Grounded Compound PCFGscited by 34
  10. 2020StructFormer: Joint Unsupervised Induction of Dependency and Constituency Structure from Masked Language Modelingcited by 33
  11. 2021Sequence-to-Sequence Learning with Latent Neural Grammarscited by 30
  12. 2020Unsupervised Parsing via Constituency Testscited by 23
18 more
  1. 2020Scaling Hidden Markov Language Modelscited by 22
  2. 2021PCFGs Can Do Better: Inducing Probabilistic Context-Free Grammars with Many Symbolscited by 22
  3. 2020The Return of Lexical Dependencies: Neural Lexicalized PCFGscited by 19
  4. 2021Neural Bi-Lexicalized PCFG Inductioncited by 18
  5. 2021Video-aided Unsupervised Grammar Inductioncited by 17
  6. 2018Unsupervised Learning of Syntactic Structure with Invertible Neural Projectionscited by 11
  7. 2018Benefits of over-parameterization with EMcited by 10
  8. 2019Learning higher-order sequential structure with cloned HMMscited by 10
  9. 2020Second-Order Unsupervised Neural Dependency Parsingcited by 10
  10. 2022Low-Rank Constraints for Fast Inference in Structured Modelscited by 8
  11. 2021Improved Latent Tree Induction with Distant Supervision via Span Constraintscited by 6
  12. 2020Neuralizing Efficient Higher-order Belief Propagationcited by 5
  13. 2020Factor Graph Grammarscited by 4
  14. 2021Scaling Structured Inference with Randomizationcited by 2
  15. 2015Low-Rank Approximation of Weighted Tree Automatacited by 1
  16. 2017An Algebraic Formalization of Forward and Forward-backward Algorithmscited by 1
  17. 2021Searching for More Efficient Dynamic Programscited by 1
  18. 2022Modeling Label Correlations for Second-Order Semantic Dependency Parsing with Mean-Field Inferencecited by 1

Built on by

Cited by year (2026 to 7 Oct)

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

10 papers.

  1. 2022Unsupervised Discontinuous Constituency Parsing with Mildly Context-Sensitive Grammarscited by 7
  2. 2023Augmenting Transformers with Recursively Composed Multi-grained Representationscited by 5
  3. 2023Simple Hardware-Efficient PCFGs with Independent Left and Right Productionscited by 3
  4. 2023SynJax: Structured Probability Distributions for JAXcited by 2
  5. 2023Improving Grammar-based Sequence-to-Sequence Modeling with Decomposition and Constraintscited by 1
  6. 2024Structural Optimization Ambiguity and Simplicity Bias in Unsupervised Neural Grammar Inductioncited by 1
  7. 2024Unsupervised Morphological Tree Tokenizercited by 0
  8. 2024On Eliciting Syntax from Language Models via Hashingcited by 0
  9. 2025Probability Distribution Collapse: A Critical Bottleneck to Compact Unsupervised Neural Grammar Inductioncited by 0
  10. 2026Holographic Neural PCFG for Unsupervised Parsingcited by 0