Abstract
Jan Buys, Phil Blunsom. Proceedings of the Third International Conference on Dependency Linguistics (Depling 2015).
2015.
Introduction
In the field of dependency parsing, discriminative models have long been the standard due to their speed and high accuracy. These models focus on predicting parse trees given an input sentence. However, generative models—which model the joint probability of the parse tree and the sentence—offer significant theoretical advantages. They are naturally suited for semi-supervised learning, unsupervised learning, and text generation tasks.
Despite these benefits, existing generative dependency parsers often face a difficult trade-off: they are either too simplistic to achieve high accuracy or computationally prohibitive, sometimes requiring days to train or parsing only a single sentence per second. This paper introduces a generative transition-based parser designed to be both expressive and efficient enough for practical, real-world applications.
Methodology: Generative Parsing with HPYPs
The proposed model incrementally predicts words, Part-of-Speech (POS) tags, and parser transitions (shift, left-arc, right-arc) in a left-to-right fashion. To achieve high accuracy and efficiency, the authors introduce two primary innovations: Hierarchical Pitman-Yor Processes (HPYPs) and a Particle Filtering Decoder.
Hierarchical Pitman-Yor Processes
The probability distributions for predicting words, tags, and transitions are smoothed using HPYP priors. HPYPs are particularly effective for natural language processing because they naturally model the power-law distribution of words. This allows the model to condition on large, complex contexts—such as the top words on the stack and their children—by gracefully backing off to smaller contexts when data is sparse.
The impact of these context elements is significant. As shown in the ablation study, incrementally adding context features like stack elements ($\sigma$) and their children ($rc, lc$) leads to substantial gains in both Unlabeled Attachment Score (UAS) and Labeled Attachment Score (LAS).
Particle Filtering Decoder
Standard beam search often struggles with generative transition-based parsing because it is difficult to compare partial derivations that have shifted different numbers of words. To address this, the authors employ a linear-time decoder inspired by sequential Monte Carlo methods (particle filtering). Instead of a fixed beam size, a fixed number of "particles" is distributed among candidate derivations. This allows the effective beam size to dynamically adapt to the model's uncertainty at each step, focusing computational resources where they are most needed.
Evaluation and Results
The model was evaluated on the standard English Penn Treebank (WSJ sections), with trees converted to dependencies using Yamada and Matsumoto (YM) and Stanford Dependencies (SD) rules.
Parsing Accuracy and Speed
The generative model achieved 88.47% UAS and 86.13% LAS on the WSJ test set. This performance is highly competitive, closely trailing the discriminative MaltParser baseline. Notably, joint prediction of POS tags alongside transitions and words improved UAS by over 1%, demonstrating that syntactic structure and POS tagging mutually inform each other within a generative framework.
In terms of speed, the parser is remarkably efficient. Using 1,000 particles and pre-tagged POS, it parses 108 sentences per second. When POS tags are jointly predicted, the speed is 27 sentences per second, while maintaining high accuracy.
Language Modeling
Beyond parsing, the model serves as a highly coherent syntactic language model. It outperformed a 5-gram HPYP baseline in perplexity on the WSJ corpus. When leveraging semi-supervised learning on a larger 1-million sentence subset of WMT data, the performance gap widened, proving the model's ability to generalize effectively to unannotated data.
Discussion and Future Work
While the model is a significant step forward for generative parsing, its accuracy still lags behind state-of-the-art discriminative parsers that utilize rich look-ahead features. The HPYP back-off structure can struggle with sparsity in very large contexts, and the particle filter decoder's aggressive pruning prevents the easy incorporation of look-ahead features.
However, the model's strength as a syntactic language model suggests promising future applications in downstream natural language generation. Integrating this generative parser into machine translation pipelines, for instance, could significantly enhance the syntactic fluency and global coherence of translated text.
Summary updated