Transition-Based Syntactic Linearization with Lookahead Features

Ratish Puduppully, Yue Zhang, Manish Shrivastava

Abstract

Syntactic linearization—the process of ordering a bag of words into a grammatical sentence—is a core task in natural language generation. While transition-based models offer significant speed advantages, they have historically struggled with accuracy due to feature sparsity. This paper presents a novel transition-based framework that addresses this by deconstructing atomic shift actions and incorporating "lookahead" features from input syntactic constraints. The proposed model achieves a state-of-the-art 91.8 BLEU score on the Penn TreeBank benchmark, outperforming both previous transition-based models and computationally expensive best-first search methods while remaining over 30 times faster than the latter.

Introduction

The task of syntactic linearization involves generating a fluent sentence from an unordered set of words, often guided by syntactic information such as part-of-speech (POS) tags or dependency trees. Traditionally, researchers have chosen between two extremes: highly accurate but slow best-first search methods, and fast but less accurate transition-based models.

The authors argue that the accuracy gap in transition-based models is primarily a sparsity problem. Standard models use "atomic" shift actions that combine the action, word, and tag into a single label (e.g., SHIFT-John-NNP). This specificity prevents the model from generalizing to unseen words or effectively leveraging the rich syntactic "hints" provided in the input.

Methodology

To solve the sparsity issue, the authors propose two major modifications to the standard transition-based framework:

  1. Deconstructing SHIFT Actions: The model replaces specific shift labels with a generic SHIFT action. The specific word and POS tag are instead treated as configuration features. This allows the model to learn broader patterns of when to shift a word based on the current state, regardless of the specific word's frequency in the training data.
  2. Lookahead Features: Since the input often includes a dependency tree, the authors introduce "lookahead" features. When considering a word for a SHIFT action, the model examines that word’s future role in the sentence—such as its parent, children, or siblings in the dependency tree. Using these destinations as features helps the decoder make more informed ordering decisions.

Experimental Setup

The researchers evaluated their model using the Penn TreeBank (PTB), specifically Wall Street Journal sections 02-21 for training and section 23 for testing. Phrase-structure trees were converted into dependency trees using Penn2Malt, and base noun phrases were treated as single units to simplify the task.

Key Results

The proposed model achieved a significant performance breakthrough, particularly on the most challenging "labeled" syntactic linearization task.

Comparison of BLEU scores across different constraint levels, showing the proposed model achieving state-of-the-art results (91.8) on labeled data.

As shown in the results, the model reached 91.8 BLEU, a substantial improvement over the previous transition-based state-of-the-art of 82.9 and even surpassing the best-first search method (89.3). Qualitatively, the model produces sentences that are significantly more fluent and closer to the reference than previous transition-based baselines.

Qualitative comparison of generated sentences under full constraints, demonstrating the superior fluency of the proposed model over previous transition-based methods.

Efficiency and Generalization

  • Speed: Despite the added complexity of deconstructed actions, the model remains over 30 times faster than traditional best-first search methods, making it viable for real-time natural language generation.
  • Sparsity and Constraints: By treating syntactic constraints as features (lookahead) rather than just filters, the model effectively uses the input structure as a roadmap, reducing ambiguity during the generation process.

Conclusion

By addressing the fundamental problem of feature sparsity, this paper demonstrates that transition-based models can achieve state-of-the-art accuracy in syntactic linearization without sacrificing their inherent speed advantages. Future work will explore automated feature learning and scaling the approach to more diverse linguistic datasets.

Summary updated

BibTeX
@inproceedings{puduppully2016transition,
  author = {Ratish Puduppully and Yue Zhang and Manish Shrivastava},
  title = {{Transition-Based Syntactic Linearization with Lookahead Features}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2016},
  doi = {10.18653/v1/n16-1058},
}
Figure