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:
- Use "soft" structure: Easier to train but doesn't truly model discrete syntax.
- 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.
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.
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-nextmodel was a better language model, while thebuffer-nextmodel 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