Elamur Research⌕
☰
home / papers / 2004 / Machine Translation with Inferred Stochastic Finite-State Transducers

Machine Translation with Inferred Stochastic Finite-State Transducers

Paper · 2004 · Francisco Casacuberta and Enrique Vidal

Summary

The paper tackles automatic learning of translation models for restricted-domain tasks where parallel sentence pairs are available. The authors use stochastic finite-state transducers because they are far cheaper to run than more expressive transduction models. Their inference method rests on a formal result: any (stochastic) rational translation is a homomorphic image of a (stochastic) regular language over a suitable extended alphabet. The method has three steps. First, statistical alignments turn each source–target pair into a single string of compound symbols. Next, an ordinary stochastic regular grammar, in practice an n-gram model with final states, is trained on these strings. Finally, each compound symbol is mapped back to its source/target components, which yields a transducer. Translation uses a Viterbi-style dynamic-programming approximation to the intractable exact search. The approach is tested in machine translation experiments within the EuTrans project. Its significance is that well-established grammar and n-gram learning tools can be reused directly to build translation transducers.

Key points

  • The method builds on Theorem 1 (Berstel 1979) and its stochastic extension, Theorem 2 (Casacuberta, Vidal, and Picó 2004). Together they guarantee that a transducer can be recovered from a regular language plus two morphisms, h_Σ and h_∆.
  • Labeling function L maps training pairs to strings over an extended alphabet Γ, and an inverse function Λ restores them. Statistical alignment (e.g., Och and Ney 2000) guides the labeling.
  • Exact search for the most probable translation is computationally hard (Casacuberta and de la Higuera 2000). Decoding instead maximizes the Viterbi score at a cost of O(|s|·|Q|·B), where B is the average branching factor.
  • A toy Italian→English example ("una camera doppia") shows the approximation can fail. The pair with joint probability 0.6 loses to one with probability 0.4, because their Viterbi scores are 0.3 and 0.4.
  • Experiments are framed within the EuTrans project. The extracted text omits the experimental section, so specific corpora statistics and error rates are not reported here.

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

🎓Universitat Politècnica de ValènciaValencia · Spain21 works · 3,275 citations

Also on the byline: Centro Tecnológico de Investigación, Desarrollo e Innovación en tecnologías de la Información y las Comunicaciones (TIC).

Fields, topics and concepts

📚 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 Francisco Casacuberta and Enrique Vidal. 2004. Machine Translation with Inferred Stochastic Finite-State Transducers. Computational Linguistics.

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

@article{casacuberta2004machine,
  title = {{Machine Translation with Inferred Stochastic Finite-State Transducers}},
  author = {Francisco Casacuberta and Enrique Vidal},
  journal = {Computational Linguistics},
  year = {2004},
  doi = {10.1162/089120104323093294},
  url = {https://doi.org/10.1162/089120104323093294}
}

References

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

  1. Al-Onaizan, Yaser, Jan Curin, Michael Jahr, Kevin Knight, John Lafferty, Dan Melamed, Franz-Josef Och, David Purdy, Noah A. Smith, and David Yarowsky. 1999. Statistical machine translation. Final Report, JHU Workshop, Johns Hopkins University, Baltimore. find
  2. Amengual, Juan-Carlos, Jose-Miguel Benedı́, Francisco Casacuberta, Asunción Casta no, Antonio Castellanos, Vı́ctor Jiménez, David Llorens, Andrés Marzal, Moisés Pastor, Federico Prat, Enrique Vidal, and Juan-Miguel Vilar. 2000. The EUTRANS-I speech translation system. Machine Translation Journal… find
  3. Bangalore, Srinivas and Giuseppe Ricardi. 2000a. Finite-state models for lexical reordering in spoken language translation. In Proceedings of the International Conference on Speech and Language Processing, Beijing, China, October. find
  4. Bangalore, Srinivas and Giuseppe Ricardi. 2000b. Stochastic finite-state models for spoken language machine translation. In Proceedings of the Workshop on Embedded Machine Translation Systems, North American Association for Computational Linguistics, pages 52–59, Seattle, May. find
  5. Bangalore, Srinivas and Giuseppe Ricardi. 2001. A finite-state approach to machine translation. In Proceedings of the Second Meeting of the North American Chapter of the Association for Computational Linguistics 2001, Pittsburgh, May. find
  6. Berstel, Jean. 1979. Transductions and context-free languages. B. G. Teubner, Stuttgart. find
  7. Brown, Peter F., Stephen A. Della Pietra, Vincent J. Della Pietra, and Robert L. find
  8. Mercer. 1993. The mathematics of statistical machine translation: Parameter estimation. Computational Linguistics, 19(2):263–310. find
  9. Casacuberta, Francisco. 1996. Maximum mutual information and conditional maximum likelihood estimation of stochastic regular syntax-directed translation schemes. In Grammatical Inference: Learning Syntax from Sentences (volume 1147 of Lecture Notes on Computer Science). Springer-Verlag, Berlin and H… find
  10. Casacuberta, Francisco. 2000. Inference of finite-state transducers by using regular grammars and morphisms. In Grammatical Inference: Algorithms and Applications (volume 1891 of Lecture Notes in Artificial Intelligence). Springer-Verlag, Berlin and Heidelberg, pages 1–14. find
  11. Casacuberta, Francisco and Colin de la Higuera. 2000. Computational complexity of problems on probabilistic grammars and transducers. In Grammatical Inference: Algorithms and Applications (volume 1891 of Lecture Notes in Artificial Intelligence). Springer-Verlag, Berlin and Heidelberg, pages 15–24. find
  12. Casacuberta, Francisco, David Llorens, Carlos Martı́nez, Sirko Molau, Francisco Nevado, Hermann Ney, Moiseés Pastor, David Picó, Alberto Sanchis, Enrique Vidal, and Juan-Miguel Vilar. 2001. Speech-to-speech translation based on finite-state transducers. In Proceedings of the IEEE International Con… find
  13. Casacuberta, Francisco, Enrique Vidal, and David Picó. 2004. Inference of finite-state transducers from regular languages. Pattern Recognition, forthcoming. find
  14. Clarkson, Philip and Ronald Rosenfeld. 1997. Statistical language modeling using the CMU-Cambridge toolkit. In Proceedings of EUROSPEECH, volume 5, pages 2707–2710, Rhodes, September. find
  15. Fu, King-Sun. 1982. Syntactic pattern recognition and applications. Prentice-Hall, Englewood Cliffs, NJ. find
  16. Garcı́a, Pedro, Enrique Vidal, and Francisco Casacuberta. 1987. Local languages, the successor method, and a step towards a general methodology for the inference of regular grammars. IEEE Transactions on Pattern Analysis and Machine Intelligence, 9(6):841–845. find
  17. González, Jorge, Ismael Salvador, Alejandro Toselli, Alfons Juan, Enrique Vidal, and Francisco Casacuberta. 2000. Offline recognition of syntax-constrained cursive handwritten text. In Advances in Pattern Recognition (volume 1876 of Lecture Notes in Computer Science). Springer-Verlag, Berlin and He… find
  18. Hazen, Timothy, I. Lee Hetherington, and Alex Park. 2001. FST-based recognition techniques for multi-lingual and multi-domain spontaneous speech. In Proceedings of EUROSPEECH2001, pages 1591–1594, Aalborg, Denmark, September. find
  19. ITI, FUB, RWTH Aachen, and ZERES. 2000. Example-based language translation systems: Final report. Technical Report D0.1c, Instituto Tecnológico de Informática, Fondazione Ugo Bordoni, Rheinisch Westfälische Technische Hochschule Aachen Lehrstuhl für Informatik V and Zeres GmbH Bochum. Informatio… find
  20. Knight, Kevin and Yaser Al-Onaizan. 1998. Translation with finite-state devices. In Proceedings of the Fourth. AMTA Conference (volume 1529 of Lecture Notes in Artificial Intelligence). Springer-Verlag, Berlin and Heidelberg, pages 421–437. find
  21. Llorens, David, Juna-Miguel Vilar, and Francisco Casacuberta. 2002. Finite state language models smoothed using n-grams. International Journal of Pattern Recognition and Artificial Intelligence, 16(3):275–289. find
  22. Mäkinen, Erkki. 1999. Inferring finite transducers. Technical Report A-1999-3, University of Tampere, Tampere, Finland. find
  23. Mohri, Mehryar. 1997. Finite-state transducers in language and speech processing. Computational Linguistics, 23(2):1–20.
  24. Mou, Xiaolong, Stephanie Seneff, and Victor Zue. 2001. Context-dependent probabilistic hierarchical sub-lexical modelling using finite-state transducers. In Proceedings of EUROSPEECH2001, pages 451–454, Aalborg, Denmark, September. find
  25. Ney, Hermann, Sven Martin, and Frank Wessel. 1997. Statistical language modeling using leaving-one-out. In S. Young and G. Bloothooft, editors, Corpus-Based Statiscal Methods in Speech and Language Processing. Kluwer Academic, Dordrecht, the Netherlands, pages 174–207. find
  26. Och, Franz-Josef and Hermann Ney. 2000. Improved statistical alignment models. In Proceedings of the 38th Annual Meeting of the Association for Computational Linguistics, pages 440–447, Hong Kong, October.
  27. Oncina, José, Pedro Garcı́a, and Enrique Vidal. 1993. Learning subsequential transducers for pattern recognition interpretation tasks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 15(5):448–458. find
  28. Papineni, Kishore, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2001. Bleu: A method for automatic evaluation of machine translation. Technical Report RC22176(W∅1∅9-∅22), IBM Research Division, Yorktown Heights, NY, September.
  29. Rosenfeld, Ronald. 1995. The CMU statistical language modeling toolkit and its use in the 1994 ARPA CSR evaluation. In Proceedings of the ARPA Spoken Language Technology Workshop, Princeton, NJ. Morgan Kaufmann, San Mateo, CA. find
  30. RWTH Aachen and ITI. 1999. Statistical modeling techniques and results and search techniques and results. Technical Report D3.1a and D3.2a, Rheinisch Westfälische Technische Hochschule Aachen Lehrstuhl für Informatik VI and Instituto Tecnológico de Informática. Information Technology. Long Term… find
  31. Segarra, Encarna, Marı́a-Isabel Galiano Emilio Sanchis, Fernando Garcı́a, and Luis Hurtado. 2001. Extracting semantic information through automatic learning techniques. In Proceedings of the Spanish Symposium on Pattern Recognition and Image Analysis, pages 177–182, Benicasim, Spain, May. find
  32. Seward, Alexander. 2001. Transducer optimizations for tight-coupled decoding. In Proceedings of EUROSPEECH2001, pages 1607–1610, Aalborg, Denmark, September. find
  33. Vidal, Enrique. 1997. Finite-state speech-to-speech translation. In Proceedings of the International Conference on Acoustic Speech and Signal Processing, Munich. IEEE Press, Piscataway, NJ, pages 111–114. find
  34. Vidal, Enrique, Francisco Casacuberta, and Pedro Garcı́a. 1995. Grammatical inference and automatic speech recognition. In A. Rubio, editor, New Advances and Trends in Speech Recognition and Coding (volume 147 of NATO-ASI Series F: Computer and Systems Sciences). Springer-Verlag, Berlin and Heidelbe… find
  35. Vidal, Enrique, Pedro Garcı́a, and Encarna Segarra. 1989. Inductive learning of finite-state transducers for the interpretation of unidimensional objects. In R. Mohr, T. Pavlidis, and A. Sanfeliu, editors, Structural Pattern Analysis. World Scientific, Singapore, pages 17–35. find
  36. Vilar, Juan-Miguel. 2000. Improve the learning of subsequential transducers by using alignments and dictionaries. In Grammatical Inference: Algorithms and Applications (volume 1891 of Lecture Notes in Artificial Intelligence). Springer-Verlag, Berlin and Heidelberg, pages 298–312. find
  37. Vilar, Juan-Miguel, Enrique Vidal, and Juan-Carlos Amengual. 1996. Learning extended finite state models for language translation. In András Kornai, editor, Proceedings of the Extended Finite State Models of Language Workshop, pages 92–96, Budapest, August. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/casacuberta-2004-machine-translation-inferred-stochastic-finite/