Elamur Research⌕
☰
home / papers / 2000 / Learning dependency translation models as collections of finite state head transducers

Learning dependency translation models as collections of finite state head transducers

Paper · 2000 · Hiyan Alsawi, Srinivas Bangalore and Shona Douglas

Summary

The paper addresses statistical machine translation without hand-written rules or semantic annotation, modelling translation as paired dependency structures. Its central device is the weighted head transducer. This finite-state machine begins at a chosen head symbol and reads input and writes output outward on both sides. That makes it strictly more expressive than conventional left-to-right transducers; for example, it can reverse strings of any length with a finite number of states. A dependency transduction model is a set of such transducers applied recursively, each mapping a source headword and its dependents to a target headword and its dependents. A dynamic programming search finds the lowest-cost derivation.

Training requires only unannotated sentence pairs:

  • correlation statistics guide a search for hierarchical alignments;
  • transducer transitions are extracted from those alignments;
  • weights are maximum-likelihood log probabilities.

The method was tested on spoken-language data for English-to-Spanish (ATIS) and English-to-Japanese (AT&T operator calls). The trained models clearly beat word-for-word baselines and decode faster than real time, which matters for speech translation.

Key points

  • Head transducers trained here use only input and output positions in {-1, 0, 1}. Unlike left-to-right FSTs, they allow unbounded movement with finitely many states.
  • English-to-Spanish (ATIS transcriptions) used 13,966 training bitexts of up to 20 words and 1,185 held-out test bitexts. The model e2s scored 73.3/75.0 (simple/translation accuracy, %) overall, against 45.2/46.9 for the sww baseline.
  • English-to-Japanese (customer–operator telephone utterances) used 12,226 training and 3,253 test bitexts, evaluated on Japanese characters. The model e2j scored 66.4/70.1 overall, against 37.2/42.8 for the jww baseline.
  • Vocabularies were only a few thousand words, and utterances averaged 7.3 words. The authors note that broader domains such as newspaper text remain untested.
  • On a 300MHz processor, decoding takes less time than speaking the utterance. The authors also claim better efficiency and more natural phrase decomposition than the IBM models (Brown et al.).

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

 Fields, topics and concepts

📚 Shelves 2The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 works

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

Cite

Cite as Hiyan Alsawi, Srinivas Bangalore and Shona Douglas. 2000. Learning dependency translation models as collections of finite state head transducers. Computational Linguistics.

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

@article{alsawi2000learning,
  title = {{Learning dependency translation models as collections of finite state head transducers}},
  author = {Hiyan Alsawi, Srinivas Bangalore and Shona Douglas},
  journal = {Computational Linguistics},
  year = {2000},
  url = {https://aclanthology.org/J00-1004/}
}

References

21 references, 4 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. 1972. find
  2. The Theory o/Parsing, Translation, and Compiling. Prentice-Hall, Englewood Cliffs, NJ. find
  3. Alshawi, H. 1996. Head automata for speech translation. In Proceedings of the International Conference on Spoken Language Processing, pages 2360-2364, Philadelphia, PA. find
  4. Alshawi, H., S. Bangalore, and S. Douglas. 1998. Learning phrase-based head transduction models for translation of spoken utterances. In Proceedings of the International Conference on Spoken Language Processing, pages 2767-2770, Sydney, Australia. find
  5. Alshawi, H. and S. Douglas. 2000. Learning dependency transduction models from unannotated examples. Philosophical Transactions of the Royal Society (Series A: Mathematical, Physical and Engineering Sciences). To appear. find
  6. Alshawi, Hiyan and Fei Xia. 1997. English-to-Mandarin speech translation with head transducers. In Proceedings of the Workshop on Spoken Language Translation, Madrid, Spain. find
  7. Brown, P. J., J. Cocke, S. A. Della Pietra, V. J. Della Pietra, J. Lafferty, R. L. Mercer, and P. Rossin. 1990. A statistical approach to machine translation. Computational Linguistics, 16(2):79-85.
  8. Brown, P. J., S. A. Della Pietra, V. J. Della Pietra, and R. L. Mercer. 1993. The mathematics of machine translation: Parameter estimation. Computational Linguistics, 16(2):263-312. find
  9. Dorr, B. J. 1994. Machine translation divergences: A formal description and proposed solution. Computational Linguistics, 20(4):597-634.
  10. Earley, J. 1970. An efficient context-free parsing algorithm. Communications of the ACM, 13(2):94-102. find
  11. Gale, W. A. and K. W. Church. 1991. Identifying word correspondences in parallel texts. In Proceedings of the Fourth DARPA Speech and Natural Language Processing Workshop, pages 152-157, Pacific Grove, CA.
  12. Hays, D. G. 1964. Dependency theory: A formalism and some observations. Language, 40:511-525. find
  13. Hudson, R. A. 1984. Word Grammar. Blackwell, Oxford. find
  14. Hutchins, W. J. and H. L. Somers. 1992. An Introduction to Machine Translation. find
  15. Lewis, P. M. and R. E. Stearns. 1968. Syntax-directed transduction. Journal of the Association for Computing Machinery, 15(3):465-488. find
  16. National Institute of Standards and Technology. 1997. Spoken Natural Language Processing Group Web page. http://www.itl.nist.gov/div894. ↗
  17. Tsukada, Hajime, Hiyan Alshawi, Shona Douglas, and Srinivas Bangalore. 1999. Evaluation of machine translation system based on a statistical method by using spontaneous speech transcription. In Proceedings of the Fall Meeting of the Acoustical Society of Japan, pages 115-116, September. find
  18. Vilar, J. M., V. M. Jim~nez, J. C. Amengual, A. Castellanos, D. Llorens, and E. Vidal. 1996. Text and speech translation by means of subsequential transducers. Natural Language Engineering, 2(4):351-354. find
  19. Watanabe, Hideo. 1995. A model of a bi-directional transfer mechanism using rule combination. Machine Translation, 10(4):269-291. find
  20. Wu, Dekai.1997. Stochastic inversion transduction grammars and bilingual parsing of parallel corpora. Computational Linguistics, 23(3):377-404.
  21. Younger, D. 1967. Recognition and Parsing of Context-Free Languages in Time n 3. Information and Control, 10:189-208. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/alsawi-2000-learning-dependency-translation-models-as/