We introduce a polynomial-time algorithm for statistical machine translation. This algorithm can be used in place of the expensive, slow best-first search strategies in current statistical translation architectures. The approach employs the stochastic bracketing transduction grammar (SBTG) model we recently introduced to replace earlier word alignment channel models, while retaining a bigram language model. The new algorithm in our experience yields major speed improvement with no significant loss of accuracy. 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 model, shown in Figure 1 , contains a stochastic English sentence generator whose output is "corrupted" by the translation channel to produce Chinese sentences. In the IBM system, the language model employs simple n-grams, while the translation model employs several sets of parameters as discussed below. Estimation of the parameters has been described elsewhere (Brown et al., 1993) . Translation is performed in the reverse direction from generation, as usual for recognition under generative models. For each Chinese sentence c that is to be translated, the system must attempt to find the English sentence e* such that: (1) e* = argmaxPr(elc ) e (2) = argmaxPr(cle ) Pr(e) e In the IBM model, the search for the optimal e* is performed using a best-first heuristic "stack search" similar to A* methods. One of the primary obstacles to making the statistical translation approach practical is slow speed of translation, as performed in A* fashion. This price is paid for the robustness that is obtained by using very flexible language and translation models. The language model allows sentences of arbitrary order and the translation model allows arbitrary word-order permutation. The models employ no structural constraints, relying instead on probability parameters to assign low probabilities to implausible sentences. This exhaustive space, together with massive number of parameters, permits greater modeling accuracy. But while accuracy is enhanced, translation efficiency suffers due to the lack of structure in the hypothesis space. The translation channel is characterized by two sets of parameters: translation and alignment probabilities3 The translation probabilities describe lexical substitution, while alignment probabilities describe word-order permutation. The key problem is that the formulation of alignment probabilities a(ilj, V, T) permits the Chinese word in position j of a length-T sentence to map to any position i of a length-V English sentence. So V T alignments are possible, yielding an exponential space with correspondingly slow search times. Note there are no explicit linguistic grammars in the IBM channel model. Useful methods do exist for incorporating constraints fed in from other preprocessing modules, and some of these modules do employ linguistic grammars. For instance, we previously reported a method for improving search times in channel translation models that exploits bracketing information (Wu and Ng, 1995) . If any brackets for the Chinese sentence can be supplied as additional input information, produced for example by a preprocessing stage, a modified version of the A*-based algorithm can follow the brackets to guide the search heuristically. This strategy appears to produces moderate improvements in search speed and slightly better translations. Such linguistic-preprocessing techniques could 1Various models have been constructed by the IBM team (Brown et al., 1993) . This description corresponds to one of the simplest ones, "Model 2"; search costs for the more complex models are correspondingly higher. 152
In REF the baseline ITG constraints were used for statistical machine translation.
A Polynomial-Time Algorithm For Statistical Machine Translation
Annual Meeting Of The Association For Computational Linguistics
Computer Science