Abstract: John DeNero, Mohit Bansal, Adam Pauls, Dan Klein. Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics.
2009.
Introduction
In syntactic machine translation (MT), systems frequently employ tree-to-string transducers to capture structural transformations between languages. However, these grammars present significant computational challenges: they are typically flat (containing many adjacent non-terminals), highly lexicalized, and extremely large. Standard parsing algorithms like CKY require conversion to Chomsky Normal Form (CNF), which often results in an explosion of intermediate symbols, creating a major bottleneck in the translation pipeline.
This paper introduces a suite of optimization techniques—novel grammar normal forms, optimized binarization, and coarse-to-fine pruning—that collectively reduce parsing time by 81% while achieving a +1.3 BLEU improvement in translation quality.
Grammar Encodings and Anchoring
The authors propose Lexical Normal Form (LNF) to manage lexicalized rules. In LNF, rules containing words are restricted from containing sequences of non-terminals. This is further optimized into Anchored LNF (ALNF), where lexical rules must be "anchored" by words at both the beginning and end. This structural constraint allows the parser to perform "bound checks," efficiently skipping spans that do not match the required lexical items and delegating the primary workload to optimized binary non-lexical rules.
Optimized Binarization as Compression
Binarizing $n$-ary rules is not merely a formal requirement but an opportunity for grammar compression. The authors treat binarization as an optimization problem, seeking to minimize the total number of intermediate symbols by reusing them across different rules.
As shown in the figure above, naive left- or right-branching strategies result in thousands of symbols. A greedy binarization approach, which selects split points to maximize symbol reuse, drastically reduces this count to approximately 1,100—nearly matching the performance of an optimal Integer Linear Programming (ILP) solution while remaining computationally feasible.
Coarse-to-Fine (CTF) Search
To further accelerate parsing, the authors implement a two-pass coarse-to-fine strategy. Unlike standard monolingual parsing which clusters symbols (e.g., merging all noun phrases into a single category), the authors found that selecting a subset of the most frequent grammar symbols was more effective for MT. The first pass uses this "coarse" subset to prune the search space, allowing the second pass with the full grammar to focus only on high-probability regions of the chart.
Experimental Results
The methods were evaluated on an Arabic-English translation task using a massive bitext (220 million words) and the NIST05 test set. The combination of these techniques led to substantial improvements in both speed and quality.
The table above demonstrates that the efficiency gains allowed for a 100-fold increase in beam size during the language model reranking phase. This resulted in a significant jump of 1.3 BLEU points over the unoptimized baseline, while still maintaining a faster overall processing time.
Conclusion
The research demonstrates that the computational burden of large-scale transducer grammars can be mitigated through strategic grammar design. By viewing binarization as a symbol-sharing optimization and utilizing lexical anchoring and subset-based pruning, parsers can achieve the speed necessary for high-quality, multi-pass translation systems.
Summary updated