Elamur Research
☰
home / papers / 1997 / Stochastic Inversion Transduction Grammars and Bilingual Parsing of Parallel Corpora

Stochastic Inversion Transduction Grammars and Bilingual Parsing of Parallel Corpora

What it is about

Wu introduces the inversion transduction grammar (ITG), a context-free grammar for sentence pairs. Each production emits its two children in the same order or in reversed order on the second side, which adds only a minimal amount of ordering freedom to simple transduction grammars. In its probabilistic form, the grammar gives a dynamic program that finds the maximum-likelihood joint parse of a sentence pair in polynomial time. The paper shows that a normal form exists and discusses which ordering shifts between languages (English and Chinese in the examples) the formalism can express. It then applies bilingual parsing to four tasks: segmentation by the translation lexicon, bracketing (about 2,000 English-Chinese pairs of up to 30 words), phrasal alignment, and constraints for monolingual parsing. No monolingual grammar is needed, only a translation lexicon.

Ideas

For Mova

The code that would use this is tools/translate (hebrew.rs for the order normaliser, meta.rs for merges) and tools/roundtrip for the monolingual trees. The paper's probabilistic parser is not neural, but its tables are not count-based in the Mova form; the orientation counts per relation pair are the idea to take over. Measure first the share of verse pairs where the best joint parse agrees with both monolingual parses, and run it twice to check the output is identical.

Library summary

The Research library's own summary of the paper, in our words — not the paper's text.

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" does not allow redistributing the text itself. Original — aclanthology.org/J97-3002.pdf

Summary

Wu tackles a core limitation of classical transduction grammars, especially finite-state ones: they force both languages into the same word order, which makes them poorly suited to modeling translated sentence pairs. The paper introduces the inversion transduction grammar (ITG) and its probabilistic variant (SITG). An ITG is a context-free formalism that generates two output streams at once. Each rule can combine its constituents in either the same order for both languages ("straight") or reversed order in the second language ("inverted"). The paper shows that a normal form exists and argues that this small amount of extra flexibility covers many cross-language reorderings while keeping parsing tractable. It also gives a maximum-likelihood bilingual parsing algorithm whose input is a sentence pair. The output is matched bracketings for both sentences, with word alignment as a by-product. Experiments on Chinese–English data demonstrate uses in segmentation, bracketing, phrasal alignment and parsing. The work matters because it supplies a principled, efficient way to extract structure from parallel corpora, which can help less-studied languages.

Key points

  • ITGs add only one extra degree of ordering freedom (inverted rule orientation) to simple transduction grammars, and they still fall within the broader class of context-free syntax-directed transduction grammars.
  • In word alignment experiments with the tree-structure constraint, accuracy reached 96.3% once two main error categories were excluded. Each category accounted for roughly half of the errors.
  • If an English parse tree is fixed in advance, the Chinese side is forced to conform to it, and parsing complexity drops to O(TV³). This enables transfer of grammatical knowledge from one language to the other.
  • Partial constraints can be imposed by marking illegal chart entries as impossible. Examples include bracketing from an external English bracketer and punctuation cues: colons and Chinese full stops act as reliable separators, while parentheses and quotation marks act as reliable delimiters.
  • An Earley-style active-chart parser handles unrestricted-form grammars at the same time complexity as the normal-form parser. The author also mentions ongoing work on EM-based training and on integrating SITGs into translation.

Topics: Machine translation

Cite

The paper itself, not this card. BibTeX from the library's record of the work.

@article{wu1997stochastic,
  title = {{Stochastic Inversion Transduction Grammars and Bilingual Parsing of Parallel Corpora}},
  author = {Wu, Dekai},
  journal = {Computational Linguistics},
  year = {1997},
  url = {https://aclanthology.org/J97-3002/}
}

References

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

  1. Aho, Alfred V. and Jeffrey D. Ullman. 1969a. Properties of syntax directed translations. Journal of Computer and System Sciences, 3(3):319-334. find
  2. Aho, Alfred V. and Jeffrey D. Ullman. 1969b. Syntax directed translations and the pushdown assembler. Journal of Computer and System Sciences, 3(1):37-56. find
  3. Aho, Alfred V. and Jeffrey D. Ullman. 1972. The Theory of Parsing, Translation, and Compiling. Prentice Hall, Englewood Cliffs, NJ. find
  4. Black, Ezra, Roger Garside, and Geoffrey Leech, editors. 1993. Statistically-Driven Computer Grammars of English: The IBM~Lancaster Approach. Editions Rodopi, Amsterdam. find
  5. 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
  6. Brown, Peter F., Stephen A. DellaPietra, Vincent J. DellaPietra, and Robert L. Mercer. 1993. The mathematics of statistical machine translation: Parameter estimation. Computational Linguistics, 19(2):263-311. find
  7. Brown, Peter F., Jennifer C. Lai, and Robert L. Mercer. 1991. Aligning sentences in parallel corpora. In Proceedings of the 29th Annual Meeting, pages 169-176, Berkeley, CA. Association for Computational Linguistics. find
  8. Catizone, Roberta, Graham Russell, and Susan Warwick. 1989. Deriving translation data from bilingual texts. In Proceedings of the First Lexical Acquisition Workshop, Detroit, MI. find
  9. Chang, Chao-Huang and Cheng-Der Chen. 1993. HMM-based part-or-speech tagging for Chinese corpora. In Proceedings of the Workshop on Very Large Corpora, pages 40-47, Columbus, OH, June. find
  10. Chen, Stanley F. 1993. Aligning sentences in bilingual corpora using lexical information. In Proceedings of the 31st Annual Meeting, pages 9-16, Columbus, OH. Association for Computational Linguistics. find
  11. Chiang, Tung-Hui, Jing-Shin Chang, Ming-Yu Lin, and Keh-Yih Su. 1992. Statistical models for word segmentation and unknown resolution. In Proceedings of ROCLING-92, pages 121-146. find
  12. Church, Kenneth W. 1993. Char-align: A program for aligning parallel texts at the character level. In Proceedings of the 31st Annual Meeting, pages 1-8, Columbus, OH. Association for Computational Linguistics. find
  13. Cranias, Lambros, Harris Papageorgiou, and Stelios Peperidis. 1994. A matching technique in example-based machine translation. In Proceedings of the Fifteen th International Conference on Computational Linguistics, pages 100-104, Kyoto. find
  14. Dagan, Ido and Kenneth W. Church. 1994. Termight: Identifying and translating technical terminology. In Proceedings of the Fourth Conference on Applied Natural Language Processing, pages 34-40, Stuttgart, October. find
  15. 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
  16. Earley, Jay. 1970. An efficient context-free parsing algorithm. Communications of the Association for Computing Machinery, 13(2):94-102. find
  17. Fung, Pascale and Kenneth W. Church. 1994. K-vec: A new approach for aligning parallel texts. In Proceedings of the Fifteenth International conference on Computational Linguistics, pages 1096-1102, Kyoto. find
  18. Fung, Pascale and Kathleen McKeown. 1994. Aligning noisy parallel corpora across language groups: Word pair feature matching by dynamic time warping. In AMTA-94, Association for Machine Translation in the Americas, pages 81-88, Columbia, MD, October. find
  19. 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
  20. Gale, William A. and Kenneth W. Church. 1991. A program for aligning sentences in bilingual corpora. In Proceedings of the 29th Annual Meeting, pages 177-184, Berkeley, CA. Association for Computational Linguistics. find our card
  21. Gale, William A., Kenneth W. Church, and David Yarowsky. 1992. Using bilingual materials to develop word sense disambiguation methods. In TMI-92, Proceedings of the Fourth International Conference on Theoretical and Methodological Issues in Machine Translation, pages 101-112, Montreal. find
  22. Gazdar, Gerald and Christopher S. Mellish. 1989. Natural Language Processing in LISP: An Introduction to Computational Linguistics. Addison-Wesley, Reading, MA. find
  23. Grishman, Ralph. 1994. Iterative alignment of syntactic structures for a bilingual corpus. In Proceedings of the Second Annual Workshop on Very Large Corpora, pages 57--68, Kyoto, August. find
  24. Kaji, Hiroyuki, Yuuko Kida, and Yasutsugu Morimoto. 1992. Learning translation templates from bilingual text. In Proceedings of the Fourteenth International Conference on Computational Linguistics, pages 672-678, Nantes. find
  25. Kaplan, Ronald M. and Martin Kay. 1994. Regular models of phonological rule systems. Computational Linguistics, 20(3):331-378. find
  26. Kasami, T. 1965. An efficient recognition and syntax analysis algorithm for context-free languages. Technical Report AFCRL-65-758, Air Force Cambridge Research Laboratory, Bedford, MA. find
  27. Kay, Martin and M. ROscheisen. 1988. Text-translation alignment. Technical Report P90-00143, Xerox Palo Alto Research Center. find
  28. Koskenniemi, Kimmo. 1983. Two-level morphology: A general computational model for word-form recognition and production. Technical Report 11, Department of General Linguistics, University of Helsinki. find
  29. Kupiec, Julian. 1993. An algorithm for finding noun phrase correspondences in bilingual corpora. In Proceedings of the 31st Annual Meeting, pages 17-22, Columbus, OH. Association for Computational Linguistics. find
  30. Laporte, Eric. 1996. Context-free parsing with finite-state transducers. In String Processing Colloquium, Recife, Brazil. find
  31. Lewis, P. M. and R. E. Stearns. 1968. Syntax-directed transduction. Journal of the Association for Computing Machinery, 15:465-488. find
  32. Lin, Yi-Chung, Tung-Hui Chiang, and Keh-Yih Su. 1992. discrimination oriented probabilistic tagging. In Proceedings of ROCLING-92, pages 85-96. find
  33. Lin, Ming-Yu, Tung-Hui Chiang, and Keh-Yih Su. 1993. A preliminary study on unknown word problem in chinese word segmentation. In Proceedings of ROCLING-93, pages 119-141. find
  34. Magerman, David M. and Mitchell P. Marcus. 1990. Parsing a natural language using mutual information statistics. In Proceedings of AAAI-90, Eighth National Conference on Artificial Intelligence, pages 984-989. find
  35. Matsumoto, Yuji, Hiroyuki Ishimoto, and Takehito Utsuro. 1993. Structural matching of parallel texts. In Proceedings of the 31st Annual Meeting, pages 23-30, Columbus, OH. Association for Computational Linguistics. find
  36. Nagao, Makoto. 1984. A framework of a mechanical translation between Japanese and English by analogy principle. In Alick Elithorn and Ranan Banerji, editors, Artifiical and Human Intelligence: Edited Review Papers Presented at the International NATO Symposium on Artificial and Human Intelligence. North-Holland, Amsterdam, pages 173-180. find
  37. Pereira, Fernando. 1991. Finite-state approximation of phrase structure grammars. In Proceedings of the 29th Annual Meeting, Berkeley, CA. Association for Computational Linguistics. find
  38. Pereira, Fernando and Yves Schabes. 1992. Inside-outside reestimation from partially bracketed corpora. In Proceedings of the 30th Annual Meeting, pages 128-135, Newark, DE. Association for Computational Linguistics. find
  39. Roche, Emmanuel. 1994. Two parsing algorithms by means of finite-state transducers. In Proceedings of the Fifteenth International Conference on Computational Linguistics, Kyoto. find
  40. Sadler, Victor and Ronald Vendelmans. 1990. Pilot implementation of a bilingual knowledge bank. In Proceedings of the Thirteenth International Conference on Computational Linguistics, pages 449-451, Helsinki. find
  41. Savitch, Walter J. 1982. Abstract Machines and Grammars. Little, Brown, Boston, MA. find
  42. Smadja, Frank A. 1992. How to compile a bilingual collocational lexicon automatically. In AAAI-92 Workshop on Statistically-Based NLP Techniques, pages 65-71, San Jose, CA, July. find
  43. Sproat, Richard, Chilin Shih, William Gale, and Nancy Chang. 1994. A stochastic word segmentation algorithm for a Mandarin text-to-speech system. In Proceedings of the 32nd Annual Meeting, pages 66-72, Las Cruces, NM, June. Association for Computational Linguistics. find
  44. Viterbi, Andrew J. 1967. Error bounds for convolutional codes and an asymptotically optimal decoding algorithm. IEEE Transactions on Information Theory, 13:260-269. find
  45. Wu, Dekai. 1994. Aligning a parallel English-Chinese corpus statistically with lexical criteria. In Proceedings of the 32nd Annual Meeting, pages 80-87, Las Cruces, NM, June. Association for Computational Linguistics. find
  46. Wu, Dekai. 1995. An algorithm for simultaneously bracketing parallel texts by aligning words. In Proceedings of the 33rd Annual Meeting, pages 244-251, Cambridge, MA, June. Association for Computational Linguistics. find
  47. Wu, Dekai and Pascale Fung. 1994. Improving Chinese tokenization with linguistic filters on statistical lexical acquisition. In Proceedings of the Fourth Conference on Applied Natural Language Processing, pages 180-181, Stuttgart, October. find
  48. Wu, Dekai and Xuanyin Xia. 1994. Learning an English-Chinese lexicon from a parallel corpus. In AMTA-94, Association for Machine Translation in the Americas, pages 206-213, Columbia, MD, October. find
  49. Wu, Zimin and Gwyneth Tseng. 1993. Chinese text segmentation for text retrieval: Achievements and problems. Journal of The American Society for Information Sciences, 44(9):532-542. find
  50. Younger, David H. 1967. Recognition and parsing of context-free languages in time n 3. Information and Control, 10(2):189-208. find