Asynchronous Binarization for Synchronous Grammars

John DeNero, Adam Pauls, Dan KleinACL 2009 · OpenReview

TL;DR

This paper introduces "asynchronous binarization" for machine translation, a technique that decouples the binarization of grammar rules for the parsing and reranking stages. This allows for independent optimization of each stage, overcoming the limitations of traditional synchronous binarization which struggles with differing word orders between languages. The result is improved decoding accuracy and efficiency.

What Problem Does This Paper Address?

Modern machine translation systems often rely on synchronous grammars, which represent translation rules with both source and target language components. To make decoding efficient, these "n-ary" rules (rules with multiple non-terminals) are typically "binarized" – broken down into a series of binary rules. However, a major challenge arises because the word order in the target language often differs from the source language. This reordering makes it difficult, and sometimes impossible, to find a "synchronous binarization" that works for both languages simultaneously. This constraint can limit the grammar's expressiveness and the decoder's ability to find the best translation. The paper addresses this by proposing a way to binarize the grammar independently for the parsing and reranking stages, each using only one language's perspective.

Methods

The core innovation is asynchronous binarization, which is applied within a two-stage decoding framework.

  1. Source-Side Binarization (Parsing Stage): The grammar's source-side projection is binarized to enable efficient parsing. This stage aims to build a "derivation forest" (a compact representation of all possible parse trees) quickly. The paper mentions using techniques similar to DeNero et al. (2009) for efficient parsing, focusing on creating a cubic-time algorithm.
  2. Target-Side Binarization (Reranking Stage): After parsing, the resulting forest is reranked using an n-gram language model. Instead of using the same binarization as the parsing stage, the grammar's target-side projection is re-binarized specifically for this reranking process. This allows for optimizations tailored to language model scoring and the exploration of translation hypotheses. The paper uses a "cube growing" algorithm for reranking.

The key is that these two binarizations are independent. The source-side binarization doesn't need to consider target-side reordering, and the target-side binarization doesn't need to be constrained by the source-side parsing structure. This decoupling is achieved by transforming the parsed forest into an n-ary form and then applying a new binarization scheme for reranking. The paper also highlights the benefit of "reusing intermediate nodes" during target-side binarization, where common substructures across different rules can be shared, leading to cached computations and further efficiency gains.

Datasets

Not explicitly detailed in terms of specific training datasets for the grammar itself, but the evaluation was performed on:

  • 300 NIST 2005 Arabic sentences translated to English.
  • A large grammar learned from a 220 million word bitext.
  • A trigram language model trained on the English side of this bitext.

Key Insights and Ideas

  • Decoupling is Key: Synchronous binarization is an unnecessary constraint. By separating the binarization for parsing and reranking, we can optimize each stage independently.
  • Target-Side Binarization Matters for Reranking: Even simple target-side binarization schemes can significantly improve the accuracy of language model reranking compared to using an n-ary forest directly.
  • Circumventing Reordering Constraints: Asynchronous binarization elegantly sidesteps the problem of differing source and target word orders, which is a major hurdle for synchronous binarization.
  • Efficiency Gains through Sharing: Reusing intermediate nodes in the target-side binarized forest leads to significant speedups in reranking by caching language model evaluations.

Key Results

  • A modest increase in BLEU score (0.3 points) and model score (13 points) was observed when using left-branching target-side binarization for reranking, compared to an n-ary forest baseline. This demonstrates improved search accuracy by better exploring the translation space.
  • Binarization during reranking increased processing time by 25% due to more k-best list constructions.
  • However, reusing intermediate edges during reranking binarization reduced the overall binarized reranking time by 37%. This was attributed to intermediate nodes being used in an average of 4.5 different rules.

Limitations and Future Work

  • Limited Binarization Options: The paper acknowledges that the source-side binarization might be limited in ways that prevent minimizing intermediate symbols (as discussed in DeNero et al., 2009).
  • Maximizing Reuse: Future work will focus on evaluating a wider array of forest binarization strategies, particularly those that maximize the reuse of intermediate nodes for reranking efficiency.
  • Grammar Specificity: The paper notes that the optimal binarization strategy might vary depending on the specific grammar and language pair.

Summary updated

Abstract

Binarization of n-ary rules is critical for the efficiency of syntactic machine translation decoding. Because the target side of a rule will generally reorder the source side, it is complex (and sometimes impossible) to find synchronous rule binarizations. However, we show that synchronous binarizations are not necessary in a two-stage decoder. Instead, the grammar can be binarized one way for the parsing stage, then rebinarized in a different way for the reranking stage. Each individual binarization considers only one monolingual projection of the grammar, entirely avoiding the constraints of synchronous binarization and allowing binarizations that are separately optimized for each stage. Compared to n-ary forest reranking, even simple target-side binarization schemes improve overall decoding accuracy.
BibTeX
@inproceedings{denero2009asynchronous,
  author = {John DeNero and Adam Pauls and Dan Klein},
  title = {{Asynchronous Binarization for Synchronous Grammars}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2009},
  url = {https://openreview.net/forum?id=BJZL5hgOWH},
}
Figure