Paper: A Polynomial-Time Algorithm For Statistical Machine Translation

ACL ID P96-1021
Title A Polynomial-Time Algorithm For Statistical Machine Translation
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1996
  • Dekai Wu (University of Science and Technology, Clear Water Bay Hong Kong)

We introduce a polynomial-time algorithm for statistical machine translation. This algorithm can be used in place of the expensive, slow best-first search strate- gies in current statistical translation ar- chitectures. The approach employs the stochastic bracketing transduction gram- mar (SBTG) model we recently introduced to replace earlier word alignment channel models, while retaining a bigram language model. The new algorithm in our experi- ence yields major speed improvement with no significant loss of accuracy. 1 Motivation The statistical translation model introduced by IBM (Brown et al. , 1990) views translation as a noisy channel process. Assume, as we do throughout this paper, that the input language is Chinese and the task is to translate into English. The underlying generative...