A Bayesian Model for Generative Transition-based Dependency Parsing

Jan Buys, Phil Blunsom

Abstract

We propose a simple, scalable, fully generative model for transition-based dependency parsing with high accuracy. The model, parameterized by Hierarchical Pitman-Yor Processes, overcomes the limitations of previous generative models by allowing fast and accurate inference. We propose an efficient decoding algorithm based on particle filtering that can adapt the beam size to the uncertainty in the model while jointly predicting POS tags and parse trees. The UAS of the parser is on par with that of a greedy discriminative baseline. As a language model, it obtains better perplexity than a n-gram model by performing semi-supervised learning over a large unlabelled corpus. We show that the model is able to generate locally and syntactically coherent sentences, opening the door to further applications in language generation.

Introduction

In Natural Language Processing (NLP), dependency parsers are typically categorized as either discriminative or generative. Discriminative parsers, such as the MaltParser, are optimized for speed and accuracy in predicting tree structures for given sentences. However, they lack the ability to model the joint probability of words and structures, a feature essential for tasks like speech recognition, machine translation, and language generation.

Existing generative dependency parsers often face a trade-off: they are either too simplistic to achieve high accuracy or too computationally expensive for practical use. This paper introduces a fully generative, transition-based dependency parser that bridges this gap, maintaining the efficiency of modern transition-based systems while leveraging the probabilistic strengths of Bayesian modeling.

Methodology: Bayesian Transition-based Parsing

The proposed model is built upon three core components designed to balance structural complexity with computational efficiency:

  1. Transition-based Framework: The system utilizes an "arc-standard" strategy, constructing dependency trees through a sequence of shift, left-arc, and right-arc actions.
  2. Hierarchical Pitman-Yor Processes (HPYPs): To handle the power-law distribution of language, the authors employ HPYPs for robust smoothing. This Bayesian approach allows the model to effectively "back off" to simpler contexts when encountering rare word-tag-transition combinations.
  3. Particle Filtering for Decoding: Unlike standard beam search, which can struggle with generative paths of varying lengths, the authors implement a particle filter. By allocating a fixed number of particles ($K$) across derivations, the decoder dynamically adapts its search breadth based on model uncertainty. This approach ensures linear-time decoding and significant speed improvements.
Efficiency trade-offs: Parsing speed vs. accuracy as a function of particle count.

Experimental Results

The model was evaluated on the Wall Street Journal (WSJ) Penn Treebank and WMT English monolingual data. A key finding was that joint prediction of Part-of-Speech (POS) tags, words, and transitions improves parsing accuracy by approximately 1.1% UAS compared to using pre-tagged input. This suggests that syntactic structure provides valuable context for resolving tagging ambiguities.

Parsing Accuracy and Speed

The model achieved an Unlabeled Attachment Score (UAS) of 88.5% on the WSJ test set, making it highly competitive with the discriminative MaltParser (88.9%). Notably, the particle filter allows the parser to process up to 200 sentences per second, outperforming previous generative transition-based models by orders of magnitude.

Comparison of parsing performance (UAS/LAS) against MaltParser baselines.

Language Modeling and Generation

As a generative model, the system also functions as a syntax-aware language model. It achieved a perplexity of 145.54 on the WSJ dataset, surpassing a standard 5-gram HPYP model (147.22). Qualitative analysis of generated text demonstrated the model's ability to produce syntactically coherent sentences, such as: "mci communications said net dropped NUM % for an investor."

Conclusion

While the Bayesian back-off structure limits the inclusion of the millions of sparse features common in discriminative models, this generative approach offers unique advantages for semi-supervised learning and language generation. Future work may explore incorporating dependency labels into the conditioning context and implementing look-ahead mechanisms to further narrow the accuracy gap with state-of-the-art discriminative parsers.

Summary updated

Abstract

We propose a simple, scalable, fully generative model for transition-based dependency parsing with high accuracy. The model, parameterized by Hierarchical Pitman-Yor Processes, overcomes the limitations of previous generative models by allowing fast and accurate inference. We propose an efficient decoding algorithm based on particle filtering that can adapt the beam size to the uncertainty in the model while jointly predicting POS tags and parse trees. The UAS of the parser is on par with that of a greedy discriminative baseline. As a language model, it obtains better perplexity than a n-gram model by performing semi-supervised learning over a large unlabelled corpus. We show that the model is able to generate locally and syntactically coherent sentences, opening the door to further applications in language generation.
BibTeX
@inproceedings{buys2015bayesian,
  author = {Jan Buys and Phil Blunsom},
  title = {{A Bayesian Model for Generative Transition-based Dependency Parsing}},
  booktitle = {DepLing},
  year = {2015},
  url = {https://openreview.net/forum?id=8g9343F7xkS},
}
Figure