📄 Decoding complexity in word-replacement translation models

Summary

Kevin Knight examines how computationally hard decoding is in statistical machine translation built on the source-channel framework of Brown et al. (1993). In that setup, a bigram source model generates English, and a channel model turns it into French. Decoding means searching for the most probable English source of a given French sentence.

He first contrasts translation with part-of-speech tagging and letter-substitution ciphers, where dynamic programming gives efficient training and decoding. He then turns to IBM Model 1. Its training cost can be made polynomial with an algebraic rearrangement of the sum over alignments. Decoding, however, is a different matter. Knight states a decision version of Model 1 decoding (M1-DECIDE) and proves it NP-complete, using two separate polynomial reductions. One comes from the Hamilton Circuit Problem and captures the difficulty of choosing word order. The other comes from Minimum Set Cover and captures the difficulty of choosing a compact set of source words when dictionary entries overlap.

This worst-case result explains why MT systems rely on heuristic search such as beam search, or on restricted channel models.

Key points

• The paper compares several costs:
  • POS tagging decoding takes O(mv²) with dynamic programming, versus naive enumeration of O(v^m) tag sequences.
  • Model 1 EM training drops from naive O(ml^m) to O(lm) per sentence pair.
  • Naive Model 1 decoding, with English length capped at 2m, costs O(m²v^(2m)).
• M1-DECIDE asks whether some English string of length at most 2m reaches a score P(e)·P(f|e) above k. It belongs to NP because a guessed candidate can be checked in O(m²) time.
• The two proofs isolate distinct sources of hardness:
  • Word ordering arises from the source model and is related to the Traveling Salesman Problem.
  • Concise word selection arises from the channel model and is related to Minimum Set Cover.
• The intractability result carries over to fertility/distortion models (IBM Models 2–5). This follows by allowing only fertility 1 and making distortion tables uniform.
• Knight points to optimism from Traveling Salesman research, where heuristics often come within 2% of the optimal tour and the best possible route through more than 13,000 U.S. cities has been computed. He cautions that those results depend on symmetry and the triangle inequality, which word ordering lacks. He also notes that costly decoding suggests costly training from monolingual text.