Source-linked AI summary
Recurrent Neural Network Grammars
Chris Dyer, Adhiguna Kuncoro, Miguel Ballesteros, Noah A. Smith
TL;DR
Sequential RNNs perform well but do not explicitly represent the nested structures organizing natural-language relationships. This paper introduces recurrent neural network grammars, which combine recursive syntactic generation with recurrent conditioning and efficient inference for parsing and language modeling. RNNGs outperform prior single supervised generative parsers in English and state-of-the-art sequential language models, while corrected results establish strong English and Chinese benchmarks.
Problem
Sequential RNNs model language effectively but are a priori inappropriate for relationships organized through latent nested structures.
Method
RNNGs combine recursive phrase-structure generation, top-down transition-based parsing, recurrent representations, and importance sampling for generative inference.
Results
RNNGs outperform every previously published single supervised generative parser in English and the best single-sentence language models; corrected results report perplexities of 105.2 and 148.5 and parsing F1 of 93.3 and 86.9 on PTB and CTB.
Takeaways & Limitations
Explicit syntactic structure can support effective generative models for both parsing and language modeling, while the generative parser outperforms its discriminative counterpart in the reported experiments.
Takeaways & Limitations
The reported results were affected by an implementation error that discarded each constituent’s rightmost child and failed to propagate crucial information upward.
Abstract
from arXiv · showhide
We introduce recurrent neural network grammars, probabilistic models of sentences with explicit phrase structure. We explain efficient inference procedures that allow application to both parsing and language modeling. Experiments show that they provide better parsing in English than any single previously published supervised generative model and better language modeling than state-of-the-art sequential RNNs in English and Chinese.
1 Introduction
RNNGs model natural language with explicit nested phrase structure while retaining recurrent conditioning over syntactic derivation history. Their top-down transition-based algorithms support parsing, generation, and importance-sampling-based inference, with strong results in both parsing and language modeling.
- Sequential RNNs model surface order effectively, but natural-language relationships are largely organized through latent nested structures.
- RNNGs are probabilistic sentence models that explicitly represent nested hierarchical relationships among words and phrases.
- RNNG decisions condition on the entire syntactic derivation history, relaxing context-free independence assumptions.
- The model uses top-down transition-based parsing, incorporating root-to-terminal syntactic information while retaining transition-based algorithmic convenience.
- A discriminative parser supplies parse-tree samples for importance sampling, approximating generative-model marginal likelihoods and MAP trees.
- RNNGs achieve the best-known parsing results from a single supervised generative model and better language-model perplexities than state-of-the-art sequential LSTMs.
3 Top-down Parsing and Generation
RNNGs use top-down transition systems to parse sentences into trees and to jointly generate trees and words. Their transitions directly construct arbitrary phrase structures, with a unique depth-first, left-to-right transition sequence for each tree.
- Top-down parsing: The parser transforms words into parse trees using a stack, an input buffer, and classifier-selected NT, SHIFT, and REDUCE operations.The stack stores terminals, open nonterminals, and completed constituents; the buffer stores unprocessed terminals.
- Top-down parsing: NT opens a nonterminal, SHIFT moves the next terminal from the buffer to the stack, and REDUCE closes an open nonterminal around completed children.REDUCE can create constituents with an unbounded number of children.
- Top-down parsing: Transition constraints depend on the buffer, stack, and open-nonterminal count to ensure well-formed trees and limit excessive nesting.NT requires a nonempty buffer and fewer than 100 open nonterminals; other constraints restrict SHIFT and REDUCE.
- Generation: The generator replaces the input buffer with an output history and replaces SHIFT with GEN(x), stochastically producing terminals and tree structure until one completed constituent remains.Generator transitions are selected from the current stack and terminal history under modified validity constraints.
- Transition sequences and runtime: Each parse tree maps uniquely to a transition sequence through depth-first, left-to-right traversal, while runtime is linear in the number of generated tree nodes.The linear runtime assumes constant-time stack push and pop operations.
- Comparison to other models: RNNG transitions build rooted trees top down and directly generate arbitrary tree structures without requiring binarization.This distinguishes the generation algorithm from prior stack-based parsing and generation algorithms described in the paper.
4 Generative Model
The generative RNNG models joint distributions over trees and words by parameterizing transition decisions from continuous representations of generator state. Recurrent encodings and recursive composition represent unbounded structures and syntactic constituents.
- RNNGs define a joint distribution over syntax trees and word sequences as a transition sequence model parameterized by continuous embeddings of generator states.
- Each generator-state embedding combines representations of the output buffer, stack, and preceding action history.The output buffer, stack, and history are represented by embeddings ot, st, and ht, respectively.
- Recurrent networks encode unbounded output-buffer and action-history sequences, while stack LSTMs support stack push and pop operations.The stack contains open nonterminals, terminals, and complete trees, requiring specialized handling.
- 4.1 Syntactic Composition Function: During REDUCE, completed subtrees and tokens become children of the latest open nonterminal, and a bidirectional-LSTM composition function computes the new subtree embedding.The composition function reads the constituent label and child embeddings, then transforms the final forward and reverse states into a subtree embedding.
- 4.2 Word Generation: Word generation separates the GEN action from choosing the word and uses a class-factored softmax to reduce computational complexity.The class-factored softmax has complexity O(|C|) rather than O(|Σ|) for the full-vocabulary softmax.
- 4.1 Syntactic Composition Function: The composition function handles an unbounded number of children and uses nonterminal information, addressing limitations identified in prior syntactic composition functions.
5 Inference via Importance Sampling
Exact marginal-likelihood and MAP-tree inference are intractable because RNNG action sequences have unbounded dependencies. The paper therefore uses importance sampling with a discriminatively trained parser as an efficient proposal distribution.
- The generative model requires marginalizing over all trees for language modeling and finding the highest-probability tree for parsing.
- Unbounded dependencies across parsing actions make exact computation of both the marginal probability and MAP parse intractable.
- Importance sampling approximates these quantities using a conditional proposal distribution q(y | x).The proposal must cover every tree with positive joint probability, support efficient sampling, and provide known conditional probabilities.
- The discriminatively trained parser supplies the proposal because its action sequences can be sampled ancestrally and their conditional probabilities are available.
- Importance weights are defined as w(x, y) = p(x, y)/q(y | x), and Monte Carlo estimates use N samples drawn from q(y | x).
- The estimated MAP tree is the sampled tree with the highest probability under the joint model p(x, y).
6 Experiments
The experiments evaluate discriminative and generative parsing and generative language modeling in English and Chinese using established treebank datasets and held-out evaluation. The generative model shows strong parsing and language-modeling performance, while Chinese parsing follows the English pattern.
- The experiments evaluate discriminative and generative parsing, plus generative language modeling, in English and Chinese.
- English experiments train on Penn Treebank Sections 2–21, validate on Section 24, and evaluate on Section 23.
- Chinese experiments use Penn Chinese Treebank Version 5.1 with specified training, development, and evaluation sections.
- Data and Preprocessing: Preprocessing preserves orthographic case and uses parser-oriented normalization because the model serves both parsing and language modeling.
- Parsing Results: The parser comparison includes discriminative and generative RNNG models alongside representative published models on PTB Section 23.The generative model uses independent samples from a flattened discriminative-parser distribution and reranks them under the joint model.
- Chinese Parsing Results: Chinese parsing results show the same pattern as the English results.
- Language Model Results: Language-model evaluation reports held-out per-word perplexities for sequential and syntactic models, with log probabilities normalized by word count.
7 Discussion
The generative RNNG is effective for parsing and language modeling, likely because it relaxes independence assumptions while learning continuous syntactic representations. Its discriminative counterpart performs worse despite access to more information.
- RNNGs are effective as both parsers and language models.The proposed generative model performs well in both tasks.
- Relaxed independence assumptions and continuous symbol representations support the generative model’s effectiveness.The model combines non-linear syntactic relationships with learned continuous representations.
- The generative parser outperforms the discriminative parser despite conditioning on less information.The discriminative model uses the entire history, stack, and buffer, whereas the generative model accesses only history and stack.
8 Related Work
RNNGs combine recurrent language modeling with syntactic generation and use neural networks structured according to sentence syntax. Unlike prior syntactically structured neural models, they generate language while incorporating a context-free inductive bias.
- Modeling traditions: RNNGs combine recurrent representations of unbounded word history with syntactic language modeling.The model draws on both recurrent neural language models and models that jointly generate syntax and words.
- Syntactic generation: Prior syntactic generation work largely used bottom-up, shift-reduce-style tree construction, while RNNGs generate top-down.Related approaches include bottom-up generation and rooted branching processes that recursively rewrite nonterminals.
- Structured neural models: RNNGs are the first described syntactically structured neural models used to generate language rather than only discriminate.Earlier syntactically structured neural architectures were applied to parsing, sentiment analysis, and sentence representation.
- Inductive bias: The architecture incorporates a context-free inductive bias into a neural model.The model structure is organized around sentence syntax rather than relying only on sequential recurrence.
9 Outlook
The paper outlines extensions that broaden RNNGs beyond the demonstrated supervised setting, including efficient marginalization, conditional generation, sentence-processing models, and tree-free training.
- Efficient inference: A particle-filter scheme can marginalize RNNGs left to right in expected linear time for language-model applications.This provides an alternative to importance sampling based on a discriminative parser.
- Conditional generation: RNNGs could replace sequential architectures in neural transduction tasks that generate sentences conditioned on inputs.Prior conditional syntactic models have worked without computationally expensive decoding-time marginalization.
- Sentence processing: Their left-to-right structure could support sentence-processing models based on explicit grammars.The paper distinguishes this possibility from claiming that an RNNG itself is a processing model.
- Unsupervised training: Although experiments use supervised learning, RNNGs could be trained without trees using expectation maximization.This possibility follows from their status as joint models.
10 Conclusion
The paper introduces RNNGs as generative phrase-structure models usable for parsing and language modeling, alongside a discriminative parsing model. The generative model achieves strong English parsing and language-modeling results with minimal preprocessing and no feature engineering.
- RNNGs model phrase-structure trees probabilistically and support generative parsing and language modeling.A corresponding discriminative model can also be used as a parser.
- The approach requires no feature design or treebank transformations beyond out-of-vocabulary preprocessing.This describes the stated preprocessing and modeling requirements.
- The generative model outperforms every previously published single supervised generative parser in English.In Chinese, it performs slightly below the best-reported generative model.
- As language models, RNNGs outperform the best single-sentence language models.The conclusion summarizes their language-modeling advantage at that comparison level.
Corrigendum to Recurrent Neural Network Grammars
The corrigendum identifies an implementation bug in the RNNG recursive composition function and reports corrected results. The bug discarded each constituent’s rightmost child and replaced it with another copy of the nonterminal symbol.
- The original RNNG results used an implementation that did not match the presented model.The corrigendum reports results after correcting the recursive composition function.
- The buggy function replaced each constituent’s rightmost child with a second copy of its nonterminal symbol.For “NP the hungry cat,” it read “NP the hungry NP” instead of including “cat.”
- Because the error occurred for every constituent, crucial information was not properly propagated upward through the tree.
Results after Correction
After correction, the RNNG results improve across phrase-structure parsing and language modeling evaluations. The corrected generative model achieves the best reported parsing results on both listed datasets and remains competitive with sequential LSTM language modeling.
- Parsing: The corrected models achieve the best reported phrase-structure parsing results on both the English PTB §23 and Chinese CTB 5.1 datasets.Tables 5 and 6 summarize the corrected English and Chinese parsing results.
- Model scope: The discriminative RNNG is applicable only to parsing because it models p(y | x), whereas the generative model supports language modeling as well.
- Language modeling: The fixed generative RNNG still outperforms a highly optimized sequential LSTM baseline despite slightly higher language-modeling perplexity on PTB §23.