PCFGs Can Do Better: Inducing Probabilistic Context-Free Grammars with Many Symbols (2021-04-28T00:00:00.000000Z)

TL;DR

A new parameterization form of PCFGs based on tensor decomposition is presented, which has at most quadratic computational complexity in the symbol number and therefore allows us to use a much larger number of symbols.

Abstract

Probabilistic context-free grammars (PCFGs) with neural parameterization have been shown to be effective in unsupervised phrase-structure grammar induction. However, due to the cubic computational complexity of PCFG representation and parsing, previous approaches cannot scale up to a relatively large number of (nonterminal and preterminal) symbols. In this work, we present a new parameterization form of PCFGs based on tensor decomposition, which has at most quadratic computational complexity in the symbol number and therefore allows us to use a much larger number of symbols. We further use neural parameterization for the new form to improve unsupervised parsing performance. We evaluate our model across ten languages and empirically demonstrate the effectiveness of using more symbols.

Authors

Kewei Tu

6 papers

Songlin Yang

3 papers

Yanpeng Zhao

2 papers

TL;DR

Abstract

Authors

References47 items

An Empirical Study of Compound PCFGs

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

Scaling Hidden Markov Language Models

Second-Order Unsupervised Neural Dependency Parsing

Unsupervised Parsing via Constituency Tests

On the Role of Supervision in Unsupervised Constituency Parsing

Visually Grounded Compound PCFGs

The Return of Lexical Dependencies: Neural Lexicalized PCFGs

Torch-Struct: Deep Structured Prediction Library

Unsupervised Learning of PCFGs with Normalizing Flow

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

Compound Probabilistic Context-Free Grammars for Grammar Induction

Unsupervised Recurrent Neural Network Grammars

Unsupervised Latent Tree Induction with Deep Inside-Outside Recursive Auto-Encoders

Efficient Attention: Attention with Linear Complexities

Gradient Descent Provably Optimizes Over-parameterized Neural Networks

Benefits of over-parameterization with EM

Ordered Neurons: Integrating Tree Structures into Recurrent Neural Networks

Unsupervised Learning of Syntactic Structure with Invertible Neural Projections

Gaussian Mixture Latent Vector Grammars

On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization

Neural Language Modeling by Jointly Learning Syntax and Lexicon

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

Unsupervised Neural Dependency Parsing

Unsupervised Neural Hidden Markov Models

Variational Inference with Normalizing Flows

Adam: A Method for Stochastic Optimization

Introducing the SPMRL 2014 Shared Task on Parsing Morphologically-rich Languages

Recursive Deep Models for Semantic Compositionality Over a Sentiment Treebank

Approximate PCFG Parsing Using Tensor Decomposition

Spectral Learning of Latent-Variable PCFGs

The Infinite PCFG Using Hierarchical Dirichlet Processes

Learning Accurate, Compact, and Interpretable Tree Annotation

Minimum Risk Annealing for Training Log-Linear Models

Probabilistic CFG with Latent Annotations

The Penn Chinese TreeBank: Phrase structure annotation of a large corpus

Corpus-Based Induction of Syntactic Structure: Models of Dependency and Constituency

Parsing Algorithms and Metrics

The Penn Treebank: Annotating Predicate Argument Structure

Two Experiments on Learning Probabilistic Dependency Grammars from Corpora

Fast and Accurate Neural CRF Constituency Parsing

The estimation of stochastic context-free grammars using the Inside-Outside algorithm

Applications of stochastic context-free grammars using the Inside-Outside algorithm

of the First Joint Workshop on Statistical Parsing of Morphologically Rich Languages and Syntactic Analysis of Non-Canonical Languages

Language Technologies, Volume 1 (Long and Short Pa-pers)

Union Carbide Corp. / First Boston Corp. / Petrolane Inc. / British Petroleum Co. / Ford Motor Co. / Jaguar PLC / Jaguar shares / General Motors Corp. / Northern Trust Co

of the 3rd International Conference on Learning Representations

Field of Study

Journal Information

Name

Volume

Venue Information

Name

Type

URL

Alternate Names