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

• I1. Use joint parses as a check on the reader's attachment noise (open problem 1). For each verse pair, find the best joint parse and count how often the straight and inverted choices agree with the two monolingual UD trees. A verse where they disagree is a candidate for a head patch.
• I2. Let a lexicon decide when a multiword unit (give a kiss to) is one meta token (open problem 2). Keep a merge only if the joint parse with it has fewer inverted productions and the residual bits of the reader and encoder go down.
• I3. Count the orientation of each head-child pair (straight or inverted) between the Hebrew MACULA trees and the aligned English order, per relation pair, in an ordered map. This is a count-based form of the Hebrew word-order normaliser (open problem 7): verb-subject to subject-verb is one orientation class.
• I4. Bracketing control: report bracket precision on a held-out set of verse pairs, and repeat it with a shuffled lexicon. If the shuffled run scores as well, the gate is not red and the test is too weak.

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.

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, 0 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
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

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/wu-1997-stochastic-inversion-transduction-grammars-bilingual/