Squibs and Discussions Decoding Complexity in Word-Replacement Translation Models
Kevin K. Knight · 1999
Statistical machine translation is a relatively new approach to the long-standing problem of trans-lating human languages by computer. Current statistical techniques uncover translation rules from bilingual training texts and use those rules to translate new texts. The general architecture is the source-channel model: an English string is statistically generated (source), then statistically transformed into French (channel). In order to translate (or "decode") a French string, we look for the most likely English source. We show that for the simplest form of statistical models, this problem is NP-complete, i.e., probably exponential in the length of the observed sentence. We trace this complexity to factors not present in other decoding problems. 1.