Coarse-to-Fine Syntactic Machine Translation using Language Projections

Slav Petrov, Aria Haghighi, Dan KleinEMNLP 2008 · OpenReview

Abstract

Syntactic machine translation models often suffer from extreme computational complexity when integrated with n-gram language models (LMs). This paper presents a multipass, coarse-to-fine decoding approach that incrementally introduces language model complexity. By utilizing hierarchical word clusters—termed "language projections"—the decoder can efficiently prune the search space in early, abstract passes. Experimental results across multiple language pairs demonstrate speed-ups of up to 50 times over single-pass decoding while simultaneously improving BLEU scores.

Introduction: The Lexical Explosion Problem

In syntactic machine translation, translation is modeled as a parsing problem where a tree of the target language is constructed to correspond to the source language. While efficient on its own, producing natural-sounding output requires integration with an n-gram language model. This integration creates a massive computational bottleneck known as "lexical explosion."

To calculate phrase probabilities, the decoder must track boundary words for every hypothesis to ensure grammatical connectivity. This turns a manageable search space into a gargantuan one. Traditional solutions, such as bigram-to-trigram decoding, often fail to provide sufficient speed because even a bigram model with a full vocabulary remains too large for rapid processing.

Methodology: Language Projections

The core innovation of this work is a coarse-to-fine decoding strategy that operates along two orthogonal axes of abstraction: language model order and word bit-depth.

The two axes of refinement: increasing LM order and increasing bit-depth of word clusters.

Hierarchical Clustering

Instead of decoding with the full vocabulary immediately, the authors map words into hierarchical clusters represented as a binary tree. A "1-bit" encoding might split the entire language into just two broad categories (e.g., function words vs. content words), while a "10-bit" encoding provides 1,024 distinct clusters. This allows the decoder to work with a drastically reduced set of "words" in early passes.

Multi-pass Decoding and Posterior Pruning

The system performs a sequence of decoding passes. The initial pass uses a very coarse model (e.g., a 2-cluster bigram model), which is computationally inexpensive. Following each coarse pass, the algorithm calculates the posterior probability of each state. States that are highly unlikely in the coarse representation are pruned, ensuring they are never considered in the subsequent, more expensive fine-grained passes.

Key Results

The researchers evaluated the approach using the Europarl corpus for Spanish-to-English, French-to-English, and German-to-English translation.

BLEU score vs. total decoding time, showing the significant efficiency gains of the coarse-to-fine approach.

Performance and Efficiency

The coarse-to-fine approach achieved speedups of up to 50x compared to standard single-pass decoders. Remarkably, the entire multi-pass cascade was often faster than just the initial bigram pass of traditional two-pass decoders.

Beyond speed, the approach also yielded a surprising improvement in translation quality, with BLEU scores increasing by approximately 0.4 points. This suggests that by pruning the search space intelligently, the decoder can afford to maintain a wider "beam" of possibilities in the final pass than a single-pass decoder could manage within the same time constraints.

Conclusion

By focusing on vocabulary size as the primary driver of complexity, language projections provide a powerful mechanism for accelerating syntactic machine translation. The ability to prune the search space using abstract language representations allows for high-quality translation at a fraction of the traditional computational cost. Future work may explore the theoretical risks of pruning and the potential for these coarse models to act as beneficial secondary signals for translation quality.

Summary updated

Abstract

The intersection of tree transducer-based translation models with n-gram language models results in huge dynamic programs for machine translation decoding. We propose a multipass, coarse-to-fine approach in which the language model complexity is incrementally introduced. In contrast to previous order-based bigram-to-trigram approaches, we focus on encoding-based methods, which use a clustered encoding of the target language. Across various encoding schemes, and for multiple language pairs, we show speed-ups of up to 50 times over single-pass decoding while improving BLEU score. Moreover, our entire decoding cascade for trigram language models is faster than the corresponding bigram pass alone of a bigram-to-trigram decoder.
BibTeX
@inproceedings{petrov2008coarse,
  author = {Slav Petrov and Aria Haghighi and Dan Klein},
  title = {{Coarse-to-Fine Syntactic Machine Translation using Language Projections}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2008},
  url = {https://openreview.net/forum?id=r1ZH1fMObH},
}
Figure