Dynamic Programming in Rank Space: Scaling Structured Inference with Low-Rank HMMs and PCFGs (2022-05-01T00:00:00.000000Z)

TL;DR

This work uses tensor rank decomposition (aka. CPD) to decrease inference computational complexities for a subset of FGGs subsuming HMMs and PCFGs, and conducts experiments on HMM language modeling and unsupervised PCFG parsing, showing better performance.

Abstract

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 https://github.com/VPeterV/RankSpace-Models.

Authors

Kewei Tu

6 papers

Songlin Yang

3 papers

Wei Liu

1 papers

TL;DR

Abstract

Authors

References64 items

Modeling Label Correlations for Second-Order Semantic Dependency Parsing with Mean-Field Inference

Low-Rank Constraints for Fast Inference in Structured Models

Scaling Structured Inference with Randomization

Searching for More Efficient Dynamic Programs

Improved Latent Tree Induction with Distant Supervision via Span Constraints

Sequence-to-Sequence Learning with Latent Neural Grammars

Neural Bi-Lexicalized PCFG Induction

PCFGs Can Do Better: Inducing Probabilistic Context-Free Grammars with Many Symbols

Video-aided Unsupervised Grammar Induction

StructFormer: Joint Unsupervised Induction of Dependency and Constituency Structure from Masked Language Modeling

Scaling Hidden Markov Language Models

Unsupervised Parsing with S-DIORA: Single Tree Encoding for Deep Inside-Outside Recursive Autoencoders

Second-Order Unsupervised Neural Dependency Parsing

Factor Graph Grammars

Neuralizing Efficient Higher-order Belief Propagation

Unsupervised Parsing via Constituency Tests

Visually Grounded Compound PCFGs

The Return of Lexical Dependencies: Neural Lexicalized PCFGs

Einsum Networks: Fast and Scalable Learning of Tractable Probabilistic Circuits

Tensor Networks for Probabilistic Sequence Modeling

Torch-Struct: Deep Structured Prediction Library

Unsupervised Learning of PCFGs with Normalizing Flow

Enhancing Unsupervised Generative Dependency Parser with Contextual Information

Empirical Study of the Benefits of Overparameterization in Learning Latent Variable Models

Compound Probabilistic Context-Free Grammars for Grammar Induction

Learning higher-order sequential structure with cloned HMMs

Gradient Descent Provably Optimizes Over-parameterized Neural Networks

Benefits of over-parameterization with EM

Bridging HMMs and RNNs through Architectural Transformations

Unsupervised Learning of Syntactic Structure with Invertible Neural Projections

On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization

Introduction to Tensor Decompositions and their Applications in Machine Learning

Regularizing and Optimizing LSTM Language Models

Tensor Belief Propagation

An Algebraic Formalization of Forward and Forward-backward Algorithms

Inside-Outside and Forward-Backward Algorithms Are Just Backprop (tutorial paper)

Unsupervised Neural Dependency Parsing

Low-Rank Approximation of Weighted Tree Automata

A Multi-Teraflop Constituency Parser using GPUs

Approximate PCFG Parsing Using Tensor Decomposition

Tensor Decomposition for Fast Parsing with Latent-Variable PCFGs

Efficient Parallel CKY Parsing on GPUs

Reduced-Rank Hidden Markov Models

Advanced Dynamic Programming in Semiring and Hypergraph Frameworks

Minimum Risk Annealing for Training Log-Linear Models

Parsing and Hypergraphs

Handbook of Graph Grammars and Computing by Graph Transformations, Volume 1: Foundations

Hyperedge Replacement, Graph Grammars

Parsing Algorithms and Metrics

The Penn Treebank: Annotating Predicate Argument Structure

Directed Hypergraphs and Applications

Class-Based n-gram Models of Natural Language

Matrix Product States for Inference in Discrete Probabilistic Models

2021b) aim at scaling PCFG inference

2021) leverage tensor networks

2021b) is to transform Fig

2021) to shuffle sentences and lever

2021b) and use their code to preprocess dataset. This processing discards punctuation and lowercases all tokens with 10k most frequent words as the vocabulary. The splits of the dataset

2021) and use their code to preprocess dataset. We lowercase all words and substitutes OOV words with UNKs

2020) use tensor train

Fast and Accurate Neural CRF Constituency Parsing

An efﬁcient low-rank tensors representation for algorithms in complex probabilistic graphical models

Program transformations for optimization of parsing algorithms and other weighted logic programs

of the 2021 Conference of the North American Chapter of the Association for

Field of Study

Venue Information

Name

Type

URL

Alternate Names