📄 CDER: Efficient MT Evaluation Using Block Movements

Summary

Automatic MT metrics such as BLEU, NIST and WER punish a translation heavily when whole groups of words appear in a different order, even though such variants are often still acceptable. PER, in contrast, ignores word order entirely and can be too lenient. The authors propose CDER, an edit-distance metric that adds block movement ("long jumps") as an operation with constant cost. Computing the exact block-move distance is NP-hard, so they relax one requirement. Every reference word must be covered exactly once, but candidate words may be used zero, one or several times. This makes CDER recall-oriented and lets it be computed exactly in O(I·L) time with a small change to the Levenshtein dynamic program. They also add word-dependent substitution costs, which work for WER and PER as well. They measured sentence-level correlation with human adequacy and fluency scores on Chinese–English and Arabic–English data. CDER beats BLEU, TER and WER, and a mix of 60% CDER and 40% PER does best. The result is a fast, exact, sentence-level metric that tolerates legitimate reordering.

Key points

• CDER builds on the CDCD distance of Lopresti and Tomkins (1997), which those authors solved in O(I²·L). This paper brings the cost down to O(I·L) by using the row minimum of the DP table as the starting point for long jumps. Exact long-jump distance became impractical beyond about 20-word sentences.
• Sentence-level correlation (r) on Chinese–English / Arabic–English:
  • BLEU: 0.615 / 0.603
  • TER: 0.548 / 0.582
  • WER: 0.559 / 0.589
  • CDER: 0.625 / 0.623
  • CDER with prefix substitution costs: 0.637 / 0.634
  • CDER + prefix costs + PER: 0.649 / 0.635
  • 95% confidence intervals: ±0.018 / ±0.028
• Word-dependent substitution costs come in two variants: one based on the length of the common prefix and one based on character-level Levenshtein distance. They raise WER correlation by about 2 points absolute and CDER correlation by just over 1 point.
• Reversing the coverage constraint (giving CDER precision-like behaviour) lowered correlation clearly. Taking the maximum of both directions also scored below the original CDER, though still slightly above BLEU and WER.
• Every length penalty tried lowered correlation, so CDER's bias toward overly long candidates remains an open problem.

Interesting ideas

• I1. Relaxing a constraint on one side only to make the problem tractable. Requiring exact coverage of the reference alone turns an NP-hard alignment into a quadratic DP. The same trick could make other alignment-based scores fast, for example comparing a lemmatized Ukrainian sentence to a gold reference.
• I2. Choosing which side to relax based on what must not be lost. The authors keep the reference strict because it holds all the needed information and contains no redundant repetitions. The direction of a relaxation is a design decision worth testing empirically, as they did by comparing directions.
• I3. Graded substitution costs from string similarity. Charging less for replacing a word with a similar form (shared prefix or small character edit distance) is cheap and helps several metrics. This seems especially promising for morphologically rich languages like Ukrainian, where wrong inflections of the right lemma are common.
• I4. Combining complementary metrics by linear interpolation. CDER rewards correct local order but favours long outputs, while PER ignores order but punishes extra length. Blending them (about 60/40, with weights tuned across seven corpora) beat either metric alone. Pairing measures whose weaknesses cancel out is a reusable evaluation pattern.
• I5. Judging a metric by sentence-level correlation with humans. Validating against per-sentence human adequacy and fluency scores, with confidence intervals, is a solid way to vet any new automatic metric before using it for system development.