📄 Synchronous Binarization for Machine Translation

Summary

Syntax-based translation systems built on synchronous grammars or tree transducers can produce better output, but decoding gets expensive when rules contain many nonterminals. Reordering between the two languages forces the decoder to track the boundary words of every child, so the cost of n-gram language model integration grows exponentially with rule size. The authors propose synchronous binarization: each rule is split into binary pieces so that every intermediate (virtual) nonterminal covers a contiguous span in both the source and the target language. They give a linear-time algorithm that factors a rule's permutation where possible, and they extend it to tree-to-string rules that contain terminals. They tested it on over 50 million rules extracted from a large Chinese-English corpus with the method of Galley et al. (2004). Almost all of these rules turned out to be binarizable. Compared with ordinary monolingual binarization, the binarized grammar made decoding both faster and more accurate, and it outperformed an alignment-template system in BLEU. This makes large, syntactically rich rule sets practical to decode with an integrated language model.

Key points

• Standard left-to-right binarization of the source side leaves m-gram decoding at O(|w|^(3+2n(m−1))). Synchronous binarization makes this O(|w|^(3+4(m−1))), which no longer depends on rule size. Binary SCFG parsing is O(|w|^6), whereas general SCFG parsing is NP-hard.

• The rule set was built as follows:

  • GIZA++ alignments on a Chinese-English parallel corpus with 50M English words;
  • English parses from a variant of the Collins parser;
  • rules extracted with the algorithm of Galley et al. (2004). The result was 50,879,242 rules.

• 99.7% of the rules are binarizable, and no length bucket exceeds 25% non-binarizable rules. 86.8% of rules keep either identical or fully reversed order. Human inspection attributed most non-binarizable rules to alignment errors.

• Removing the 0.3% non-binarizable rules did not change BLEU in the baseline system.

• On 116 Chinese test sentences of at most 15 words, with a trigram LM, BLEU scores were:

  System	BLEU
  Monolingual binarization	36.25
  Synchronous binarization	38.44
  Alignment-template system (Och and Ney, 2004)	37.00

Interesting ideas

• I1. Judge a factorization by contiguity on both sides. A good decomposition is one where each intermediate piece covers an unbroken span in both languages. The same test could guide factoring in any setting that aligns two sequences, such as parallel treebanks or cross-lingual annotation projection.
• I2. Check binarizability with a stack. The algorithm merges adjacent spans whenever they form a consecutive range, in either straight or inverted order. This gives a cheap, linear-time way to test whether a permutation decomposes hierarchically, which could also serve as a reordering-complexity diagnostic for corpora.
• I3. Measure on real data, not theory. In theory almost no long permutations are binarizable, yet extracted rules are nearly all binarizable. Running a "spectrum analysis" on real data before accepting a worst-case argument is good practice in general.
• I4. Read leftover exceptions as noise signals. The few non-binarizable rules mostly came from alignment errors, so dropping them cost nothing. Rules that fail a structural check could therefore be used to spot word-alignment or extraction errors.
• I5. Name virtual nonterminals by their content. Naming intermediate symbols after their sub-alignment, much like Earley dotted rules, lets different rules share intermediate states without ambiguity. This is a reusable trick for compacting large extracted grammars.