More Web Proxy on the site http://driver.im/

article

Free access

Learning dependency translation models as collections of finite-state head transducers

Authors:

Srinivas BangaloreAuthors Info & Claims

Computational Linguistics, Volume 26, Issue 1

Pages 45 - 60

https://doi.org/10.1162/089120100561629

Published: 01 March 2000 Publication History

Abstract

The paper defines weighted head transducers, finite-state machines that perform middle-out string transduction. These transducers are strictly more expressive than the special case of standard left-to-right finite-state transducers. Dependency transduction models are then defined as collections of weighted head transducers that are applied hierarchically. A dynamic programming search algorithm is described for finding the optimal transduction of an input string with respect to a dependency transduction model. A method for automatically training a dependency transduction model from a set of input-output example strings is presented. The method first searches for hierarchical alignments of the training examples guided by correlation statistics, and then constructs the transitions of head transducers that are consistent with these alignments. Experimental results are given for applying the training method to translation from English to Spanish and Japanese.

References

[1]

Aho, Alfred V. and Jeffrey D. Ullman. 1972. The Theory of Parsing, Translation, and Compiling. Prentice-Hall, Englewood Cliffs, NJ.

Digital Library

[2]

Alshawi, H. 1996. Head automata for speech translation. In Proceedings of the International Conference on Spoken Language Processing, pages 2360--2364, Philadelphia, PA.

[3]

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.

[4]

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.

Digital Library

[5]

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.

[6]

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.

Digital Library

[7]

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.

Digital Library

[8]

Dorr, B. J. 1994. Machine translation divergences: A formal description and proposed solution. Computational Linguistics, 20(4):597--634.

Digital Library

[9]

Earley, J. 1970. An efficient context-free parsing algorithm. Communications of the ACM, 13(2):94--102.

Digital Library

[10]

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.

Digital Library

[11]

Hays, D. G. 1964. Dependency theory: A formalism and some observations. Language, 40:511--525.

[12]

Hudson, R. A. 1984. Word Grammar. Blackwell, Oxford.

[13]

Hutchins, W. J. and H. L. Somers. 1992. An Introduction to Machine Translation. Academic Press, New York.

[14]

Lewis, P. M. and R. E. Stearns. 1968. Syntax-directed transduction. Journal of the Association for Computing Machinery, 15(3):465--488.

Digital Library

[15]

National Institute of Standards and Technology. 1997. Spoken Natural Language Processing Group Web page. http://www.itl.nist.gov/div894.

[16]

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.

[17]

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.

Digital Library

[18]

Watanabe, Hideo. 1995. A model of a bi-directional transfer mechanism using rule combination. Machine Translation, 10(4):269--291.

[19]

Wu, Dekai.1997. Stochastic inversion transduction grammars and bilingual parsing of parallel corpora. Computational Linguistics, 23(3):377--404.

Digital Library

[20]

Younger, D. 1967. Recognition and Parsing of Context-Free Languages in Time n3. Information and Control, 10:189--208.

Cited By

Costa-Jussà MFarrús M(2014)Statistical machine translation enhancements through linguistic levelsACM Computing Surveys10.1145/251813046:3(1-28)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1145/2518130
Turchi MDe Bie TCristianini N(2012)An intelligent Web agent that autonomously learns how to translateWeb Intelligence and Agent Systems10.5555/2589968.258997110:2(165-178)Online publication date: 1-Apr-2012
https://dl.acm.org/doi/10.5555/2589968.2589971
Spitkovsky VAlshawi HJurafsky DTsujii JHenderson JPasca M(2012)Three dependency-and-boundary models for grammar inductionProceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning10.5555/2390948.2391024(688-698)Online publication date: 12-Jul-2012
https://dl.acm.org/doi/10.5555/2390948.2391024
Show More Cited By

Recommendations

From Two-Way to One-Way Finite State Transducers
LICS '13: Proceedings of the 2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science

Any two-way finite state automaton is equivalent to some one-way finite state automaton. This well-known result, shown by Rabin and Scott and independently by Shepherd son, states that two-way finite state automata (even non-deterministic) characterize ...
MSO definable string transductions and two-way finite-state transducers

We extend a classic result of Büchi, Elgot, and Trakhtenbrot: MSO definable string transductions i.e., string-to-string functions that are definable by an interpretation using monadic second-order (MSO) logic, are exactly those realized by deterministic ...
Iterated uniform finite-state transducers on unary languages
Abstract
An iterated uniform finite-state transducer executes the same length-preserving transduction in iterative sweeps. The first sweep occurs on the input string, while any subsequent sweep works on the output of the previous one. All sweeps always ...
Highlights
- We study Iterated Uniform Finite-State Transducers (IUFSTs) working on unary languages.
- We compare IUFSTs size with that of unary classical finite-state automata.
- We relate IUFSTs and one-way cellular automata recognition power.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computational Linguistics

Computational Linguistics Volume 26, Issue 1

Special issue on finite-state methods in NLP

March 2000

105 pages

ISSN:0891-2017

EISSN:1530-9312

Issue’s Table of Contents

Publisher

MIT Press

Cambridge, MA, United States

Publication History

Published: 01 March 2000

Published in COLI Volume 26, Issue 1

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

54
Total Citations
View Citations
433
Total Downloads

Downloads (Last 12 months)37
Downloads (Last 6 weeks)11

Reflects downloads up to 20 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Costa-Jussà MFarrús M(2014)Statistical machine translation enhancements through linguistic levelsACM Computing Surveys10.1145/251813046:3(1-28)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1145/2518130
Turchi MDe Bie TCristianini N(2012)An intelligent Web agent that autonomously learns how to translateWeb Intelligence and Agent Systems10.5555/2589968.258997110:2(165-178)Online publication date: 1-Apr-2012
https://dl.acm.org/doi/10.5555/2589968.2589971
Spitkovsky VAlshawi HJurafsky DTsujii JHenderson JPasca M(2012)Three dependency-and-boundary models for grammar inductionProceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning10.5555/2390948.2391024(688-698)Online publication date: 12-Jul-2012
https://dl.acm.org/doi/10.5555/2390948.2391024
Maletti A(2011)Survey: Weighted Extended Top-down Tree Transducers Part II—Application in Machine TranslationFundamenta Informaticae10.5555/2362176.2362184112:2-3(239-261)Online publication date: 1-Apr-2011
https://dl.acm.org/doi/10.5555/2362176.2362184
Spitkovsky VAlshawi HChang AJurafsky DMerlo PBarzilay RJohnson M(2011)Unsupervised dependency parsing without gold part-of-speech tagsProceedings of the Conference on Empirical Methods in Natural Language Processing10.5555/2145432.2145566(1281-1290)Online publication date: 27-Jul-2011
https://dl.acm.org/doi/10.5555/2145432.2145566
Maletti A(2011)Tree transformations and dependenciesProceedings of the 12th biennial conference on The mathematics of language10.5555/2050185.2050186(1-20)Online publication date: 6-Sep-2011
https://dl.acm.org/doi/10.5555/2050185.2050186
Attardi GChanev AMiceli Barone AWU DAPIDIANAKI MCARPUAT MSPECIA L(2011)A dependency based statistical translation modelProceedings of the Fifth Workshop on Syntax, Semantics and Structure in Statistical Translation10.5555/2024261.2024270(79-87)Online publication date: 23-Jun-2011
https://dl.acm.org/doi/10.5555/2024261.2024270
Gimpel KSmith NKoehn PMihalcea R(2009)Feature-rich translation by quasi-synchronous lattice parsingProceedings of the 2009 Conference on Empirical Methods in Natural Language Processing: Volume 1 - Volume 110.5555/1699510.1699539(219-228)Online publication date: 6-Aug-2009
https://dl.acm.org/doi/10.5555/1699510.1699539
Ganchev KGillenwater JTaskar BSu K(2009)Dependency grammar induction via bitext projection constraintsProceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP: Volume 1 - Volume 110.5555/1687878.1687931(369-377)Online publication date: 2-Aug-2009
https://dl.acm.org/doi/10.5555/1687878.1687931
Cohn TLapata M(2009)Sentence compression as tree transductionJournal of Artificial Intelligence Research10.5555/1622716.162273334:1(637-674)Online publication date: 1-Apr-2009
https://dl.acm.org/doi/10.5555/1622716.1622733
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents