Neural Syntactic Generative Models with Exact Marginalization

Jan Buys, Phil BlunsomNAACL 2018 · OpenReview

Neural Syntactic Generative Models with Exact Marginalization

This paper introduces a neural generative model that incorporates syntactic structure (dependency trees) as a latent variable while maintaining exact marginalization. By using dynamic programming over shift-reduce parsing transitions, the authors calculate word probabilities without the need for the expensive sampling or approximations required by previous models like RNNGs, achieving state-of-the-art results for generative dependency parsing.

The Challenge of Latent Syntax

Recurrent Neural Networks (RNNs) are the workhorses of language modeling, but they often struggle to capture long-distance syntactic dependencies, such as subject-verb agreement in complex sentences. To fix this, researchers have proposed "syntactic" models that explicitly represent sentence structure. However, most existing models face a difficult choice:

  1. Use "soft" structure: Easier to train but doesn't truly model discrete syntax.
  2. Use latent discrete structure: Models like the Recurrent Neural Network Grammar (RNNG) are highly expressive but require approximate inference (like importance sampling) because summing over all possible parse trees is mathematically daunting.

The authors ask: Is it possible to build a neural generative model where we can sum over all possible syntactic structures exactly and efficiently?

Methodology

The authors combine transition-based dependency parsing with neural sequence modeling.

Figure 1: A dependency tree illustrating syntactic relations (e.g., nsubj, nmod, obj) for the sentence "The girls from school play football".

Transition Systems and Generative Story

They utilize the arc-hybrid and arc-eager systems. These are "shift-reduce" parsers that process a sentence from left to right, using a stack to manage words and an "arc" action to create dependencies. Unlike a standard parser that just predicts the best tree, this model defines a joint probability $p(w, t)$ for words $w$ and transitions $t$. To find the probability of a sentence $p(w)$, the model must marginalize (sum) over all possible transition sequences that could produce that sentence.

Dynamic Programming

To make this summation tractable, they employ an $O(n^3)$ dynamic programming algorithm. The key constraint to keep this efficient is using a minimal feature set: the RNN only looks at a small number of encoder vectors (like the top of the stack and the current buffer word) rather than the entire history of the parse. They compare two formulations: stack-next (predicting the word currently being pushed onto the stack) and buffer-next (predicting the next word waiting in the buffer).

Experimental Results

The models were evaluated on the standard benchmark for English dependency parsing: the Penn Treebank (PTB) Wall Street Journal corpus. They tested on both Stanford Dependencies (SD) and Yamada and Matsumoto (YM) representations.

Figure 5: Performance comparison (UAS/LAS) of the proposed Arc-eager and Arc-hybrid models against prior work on SD and YM datasets.

Key Findings

  • Generative Parsing: Their supervised arc-hybrid model achieved 91.01% Unlabeled Attachment Score (UAS) on PTB, a state-of-the-art result for generative dependency parsers.
  • Efficiency: Thanks to a GPU-optimized implementation of the DP algorithm, their model is significantly faster than previous generative parsers, parsing roughly 7.4 sentences per second.
  • Language Modeling: The model achieved a perplexity of 107.61 on the PTB test set. While this outperformed unbatched LSTMs and older syntactic models, it was slightly behind the best-tuned vanilla LSTMs (100.67) and the more expressive RNNG (101.2).

Insights and Limitations

  • The Expressivity Trade-off: To achieve exact marginalization via DP, the model's recurrence cannot be "syntax-dependent" (i.e., the RNN state can't change based on the specific tree structure being built). While this makes the model less expressive than RNNG, the gain in inference speed and exactness is a significant practical advantage.
  • Parsing vs. Perplexity: A surprising finding was that better parsing accuracy does not necessarily lead to lower language modeling perplexity. The stack-next model was a better language model, while the buffer-next model was a better parser.
  • Label Bias: The authors show that exact decoding is only marginally better than "greedy" decoding for these models, suggesting their locally-normalized transition model is robust against label bias.
  • Unsupervised Limitations: When trained without gold-standard trees, the model failed to learn non-trivial syntactic structures, defaulting to simple adjacency strategies. This suggests that pure language modeling objectives are insufficient to induce human-like syntax without additional inductive biases.

Summary updated

BibTeX
@inproceedings{buys2018neural,
  author = {Jan Buys and Phil Blunsom},
  title = {{Neural Syntactic Generative Models with Exact Marginalization}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2018},
  url = {https://openreview.net/forum?id=SyWTiGWOZB},
}
Figure