Elamur Research⌕
☰
home / papers / 1996 / A Polynomial-Time Algorithm for Statistical Machine Translation

A Polynomial-Time Algorithm for Statistical Machine Translation

Paper · 1996 · Dekai Wu

Summary

Wu tackles the slowness of decoding in noisy-channel statistical MT for Chinese-to-English. In IBM-style systems, the alignment model lets any word land in any position, so the search space grows exponentially. These systems handle it with best-first A*-like "stack search," which can take hours per sentence. The paper replaces the word-alignment channel with a stochastic bracketing transduction grammar (SBTG) and keeps a bigram English language model. An SBTG is a special case of ITGs with a single nonterminal and two rule orientations: straight, where both languages keep the same child order, and inverted, where the English side is reversed. Because only these tree-shaped reorderings are allowed, the best translation can be found by a dynamic-programming search in polynomial time. The system was trained on the HKUST English-Chinese Parallel Bilingual Corpus of government transcripts. Under a coarse meaning-preservation judgment, its accuracy did not differ significantly from earlier A*-based systems, while decoding fell from hours to typically under a minute. This shows that structural constraints on reordering can make statistical MT practical.

Key points

  • Reordering limits: BTGs allow 22 of the 24 possible orderings of four constituents. Only "inside-out" permutations are excluded, and the author found none in the corpus.
  • Search-space reduction: The restriction shrinks the alignment space dramatically for longer strings. For length 16, about 3.9 billion BTG alignments are allowed, versus roughly 2.09×10¹³ unrestricted 1-1 matchings.
  • Training resources: The HKUST corpus was sentence-aligned statistically, and Chinese words and collocations were extracted. Translation pairs were then learned with EM. The resulting vocabularies were about 6,500 English and 5,500 Chinese words, with about 2.25 Chinese translations per English word. The lexicon's weighted precision was roughly 86%.
  • Evaluation: Testing used random Chinese sentences shorter than 20 words. Translations were judged on conveying the correct meaning, with attention to word order and no penalty for morphology or function words.
  • Speed: Earlier systems needed hours per sentence on Sun Sparc 10 machines. The new decoder took under a minute with unoptimized code. A simpler variant, which keeps the original channel model but restricts it to BTG shapes, admits an O(T⁷) algorithm.

Interesting ideas

  • I1. Constrain the hypothesis space structurally. Limiting reorderings to binary-tree-shaped swaps cuts the search space to something exactly searchable, instead of relying only on probabilities to suppress implausible orderings. The same move could suit other sequence-to-sequence problems where exhaustive permutation search is intractable.
  • I2. Use a minimal grammar. A BTG with one generic nonterminal needs no linguistic categories or treebank, yet still gives strong efficiency gains. This matters because search cost grows exponentially with grammar size, which makes the approach attractive for low-resource language pairs that lack parsers.
  • I3. Handle unmatched words with explicit rules. Rules that pair a word with an empty string on the other side let words go untranslated in either direction. This is a simple way to model insertions and deletions inside a synchronous grammar.
  • I4. Write general rules, search binary. A normal-form result lets the decoder assume binary rules without changing which tree shapes are explored. Probabilities can still be placed on n-ary rules, for example to favor long straight sequences. This separates convenient grammar writing from efficient search.
  • I5. Validate efficiency against a baseline. To justify a faster approximate method, the paper only shows that accuracy is not significantly worse than the slow baseline on a simple meaning-focused human check. This evaluation design is reusable when the contribution is efficiency rather than quality.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Hong Kong University of Science and TechnologyHong Kong · China58 works · 23,058 citations

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 9,085 worksArtificial Intelligence · 8,888 worksArts and Humanities · 9,296 worksLanguage and Linguistics · 9,206 works

🧭 Topics 1Research subjects and languages the work is about.Machine translation · 958 works

Cite

Cite as Dekai Wu. 1996. A Polynomial-Time Algorithm for Statistical Machine Translation. 34th Annual Meeting of the Association for Computational Linguistics.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.3115/981863.981884

@inproceedings{wu1996polynomial,
  title = {{A Polynomial-Time Algorithm for Statistical Machine Translation}},
  author = {Dekai Wu},
  booktitle = {34th Annual Meeting of the Association for Computational Linguistics},
  year = {1996},
  doi = {10.3115/981863.981884},
  url = {https://doi.org/10.3115/981863.981884}
}

References

17 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Barton, G. Edward, Robert C. Berwick, and Eric Sven Ristad. 1987. Computational Complexity and Natural Language. MIT Press, Cambridge, MA. find
  2. Brown, Peter F., John Cocke, Stephen A. DellaPietra, Vincent J. DellaPietra, Frederick Jelinek, John D. Lafferty, Robert L. Mercer, and Paul S. Roossin. 1990. A statistical approach to machine translation. Computational Linguistics, 16(2):29-85. find
  3. Brown, Peter F., Stephen A. DellaPietra, Vincent J. DellaPietra, and Robert L. Mercer. 1993. The mathematics of statisticM machine translation: Parameter estimation. Computational Linguistics, 19(2):263-311. find
  4. Dagan, Ido, Kenneth W. Church, and William A. Gale. 1993. Robust bilingual word alignment for machine aided translation. In Proceedings of the Workshop on Very Large Corpora, pages 1-8, Columbus, OH, June. find
  5. Earley, Jay. 1970. An efficient context-free parsing algorithm. Communications of the Association for Computing Machinery, 13(2):94-102. find
  6. Fung, Pascale and Dekai Wu. 1994. Statistical augmentation of a Chinese machine-readable dictionary. In Proceedings of the Second Annual Workshop on Very Large Corpora, pages 69-85, Kyoto, August. find
  7. Joshi, Aravind K. 1987. Word-order variation in natural language generation. In Proceedings of AAAI-87, Sixth National Conference on Artificial Intelligence, pages 550-555. find
  8. Shieber, Stuart M. 1984. Direct parsing of ID/LP grammars. Linguistics and Philosophy, 7:135-154. find
  9. Viterbi, Andrew J. 1967. Error bounds for convolutional codes and an asymptotically optimal decoding Mgorithm. IEEE Transactions on Information Theory, 13:260-269. find
  10. Wu, Dekai. 1994. Aligning a parallel English-Chinese corpus statistically with lexical criteria. In Proceedings of the 32nd Annual Conference of the Association for Computational Linguistics, pages 80-87, Las Cruces, New Mexico, June. find
  11. Wu, Dekai. 1995a. An algorithm for simultaneously bracketing parallel texts by aligning words. In Proceedings of the 33rd Annual Conference of the Association for Computational Linguistics, pages 244-251, Cambridge, Massachusetts, June. find
  12. Wu, Dekai. 1995b. Grammarless extraction of phrasal translation examples from parallel texts. In TMI-95, Proceedings of the Sixth International Conference on Theoretical and Methodological Issues in Machine Translation, volume 2, pages 354-372, Leuven, Belgium, July. find
  13. Wu, Dekai. 1995c. Stochastic inversion transduction grammars, with application to segmentation, bracketing, and alignment of parallel corpora. In Proceedings of IJCAL95, Fourteenth International Joint Conference on Artificial Intelligence, pages 1328-1334, Montreal, August. find
  14. Wu, Dekai. 1995d. Trainable coarse bilingual grammars for parMlel text bracketing. In Proceedings of the Third Annual Workshop on Very Large Corpora, pages 69-81, Cambridge, Massachusetts, June. find
  15. Wu, Dekai and Pascale Fung. 1994. Improving Chinese tokenization with linguistic filters on statistical lexicM acquisition. In Proceedings of the Fourth Conference on Applied Natural Language Processing, pages 180-181, Stuttgart, October. find
  16. Wu, Dekai and Cindy Ng. 1995. Using brackets to improve search for statistical machine translation. In PACLIC-IO, Pacific Asia Conference on Language, Information and Computation, pages 195-204, Hong Kong, December. find
  17. Wu, Dekai and Xuanyin Xia. 1995. Large-scale automatic extraction of an English-Chinese lexicon. Machine Translation, 9(3-4):285-313. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/wu-1996-polynomial-time-algorithm-statistical-machine/