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

research-article

Free access

Translation as weighted deduction

Author:

Adam LopezAuthors Info & Claims

EACL '09: Proceedings of the 12th Conference of the European Chapter of the Association for Computational Linguistics

Pages 532 - 540

Published: 30 March 2009 Publication History

Abstract

We present a unified view of many translation algorithms that synthesizes work on deductive parsing, semiring parsing, and efficient approximate search algorithms. This gives rise to clean analyses and compact descriptions that can serve as the basis for modular implementations. We illustrate this with several examples, showing how to build search spaces for several disparate phrase-based search strategies, integrate non-local features, and devise novel models. Although the framework is drawn from parsing and applied to translation, it is applicable to many dynamic programming problems arising in natural language processing and other areas.

References

[1]

M. Auli, A. Lopez, P. Koehn, and H. Hoang. 2009. A systematic analysis of translation model search spaces. In Proc. of WMT, Mar.

Digital Library

[2]

P. Blunsom, T. Cohn, and M. Osborne. 2008. A discriminative latent variable model for statistical machine translation. In Proc. of ACL:HLT.

[3]

P. F. Brown, S. A. D. Pietra, V. J. D. Pietra, and R. L. Mercer. 1993. The mathematics of statistical machine translation: Parameter estimation. Computational Linguistics, 19(2):263--311, Jun.

Digital Library

[4]

E. Charniak, K. Knight, and K. Yamada. 2003. Syntax-based language models for statistical machine translation. In Proceedings of MT Summit, Sept.

[5]

D. Chiang. 2007. Hierarchical phrase-based translation. Computational Linguistics, 33(2):201--228.

Digital Library

[6]

K. Church and R. Patil. 1982. Coping with syntactic ambiguity or how to put the block in the box on the table. Computational Linguistics, 8(3--4):139--149, Jul.

Digital Library

[7]

S. B. Cohen, R. J. Simmons, and N. A. Smith. 2008. Dynamic programming algorithms as products of weighted logic programs. In Proc. of ICLP.

Digital Library

[8]

T. H. Cormen, C. D. Leiserson, R. L. Rivest, and C. Stein. 2001. Introduction to Algorithms. MIT Press, 2nd edition.

Digital Library

[9]

M. R. Costa-jussá and J. A. R. Fonollosa. 2006. Statistical machine reordering. In Proc. of EMNLP, pages 70--76, Jul.

Digital Library

[10]

C. J. Dyer, S. Muresan, and P. Resnik. 2008. Generalizing word lattice translation. In Proc. of ACL:HLT, pages 1012--1020.

[11]

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

Digital Library

[12]

J. Eisner and J. Blatz. 2006. Program transformations for optimization of parsing algorithms and other weighted logic programs. In Proc. of Formal Grammar, pages 45--85.

[13]

J. Eisner, E. Goldlust, and N. A. Smith. 2005. Compiling comp ling: Weighted dynamic programming and the Dyna language. In Proc. of HLT-EMNLP, pages 281--290.

Digital Library

[14]

J. Eisner. 2002. Parameter estimation for probabilistic finite-state transducers. In Proc. of ACL, pages 1--8, Jul.

Digital Library

[15]

G. Gallo, G. Longo, and S. Pallottino. 1993. Directed hypergraphs and applications. Discrete Applied Mathematics, 42(2), Apr.

Digital Library

[16]

K. Gimpel and N. A. Smith. 2009. Approximation semirings: Dynamic programming with non-local features. In Proc. of EACL, Mar.

[17]

J. Goodman. 1999. Semiring parsing. Computational Linguistics, 25(4):573--605, Dec.

Digital Library

[18]

L. Huang and D. Chiang. 2007. Forest rescoring: Faster decoding with integrated language models. In Proc. of ACL, pages 144--151, Jun.

[19]

M. Kay. 1986. Algorithm schemata and data structures in syntactic processing. In B. J. Grosz, K. S. Jones, and B. L. Webber, editors, Readings in Natural Language Processing, pages 35--70. Morgan Kaufmann.

Digital Library

[20]

D. Klein and C. Manning. 2001. Parsing and hypergraphs. In Proc. of IWPT.

[21]

P. Koehn, H. Hoang, A. Birch, C. Callison-Burch, M. Federico, N. Bertoldi, B. Cowan, W. Shen, C. Moran, R. Zens, C. Dyer, O. Bojar, A. Constantin, and E. Herbst. 2007. Moses: Open source toolkit for statistical machine translation. In Proc. of ACL Demo and Poster Sessions, pages 177--180, Jun.

Digital Library

[22]

S. Kumar and W. Byrne. 2005. Local phrase reordering models for statistical machine translation. In Proc. of HLT-EMNLP, pages 161--168.

Digital Library

[23]

P. Liang, A. Bouchard-Côté, B. Taskar, and D. Klein. 2006. An end-to-end discriminative approach to machine translation. In Proc. of ACL-COLLING, pages 761--768, Jul.

Digital Library

[24]

A. Lopez. 2008. Statistical machine translation. ACM Computing Surveys, 40(3), Aug.

[25]

J. B. Mariño, R. E. Banchs, J. M. Crego, A. de Gispert, P. Lambert, J. A. R. Fonollosa, and M. R. Costajussà. 2006. N-gram based statistical machine translation. Computational Linguistics, 32(4):527--549, Dec.

Digital Library

[26]

D. McAllester. 1999. On the complexity analysis of static analyses. In Proc. of Static Analysis Symposium, volume 1694/1999 of LNCS. Springer Verlag.

Digital Library

[27]

I. D. Melamed. 2004. Statistical machine translation by parsing. In Proc. of ACL, pages 654--661, Jul.

Digital Library

[28]

R. C. Moore and C. Quirk, 2007. Faster beam-search decoding for phrasal statistical machine translation. In Proc. of MT Summit.

[29]

M.-J. Nederhof. 2003. Weighted deductive parsing and Knuth's algorithm. Computational Linguistics, 29(1):135--143, Mar.

Digital Library

[30]

F. J. Och, D. Gildea, S. Khudanpur, A. Sarkar, K. Yamada, A. Fraser, S. Kumar, L. Shen, D. Smith, K. Eng, V. Jain, Z. Jin, and D. Radev. 2004. A smorgasbord of features for statistical machine translation. In Proc. of HLT-NAACL, pages 161--168, May.

[31]

F. C. N. Pereira and D. H. D. Warren. 1983. Parsing as deduction. In Proc. of ACL, pages 137--144.

Digital Library

[32]

S. M. Shieber, Y. Schabes, and F. C. N. Pereira. 1995. Principles and implementation of deductive parsing. Journal of Logic Programming, 24(1--2):3--36, Jul.

[33]

C. Tillman and H. Ney. 2003. Word reordering and a dynamic programming beam search algorithm for statistical machine translation. Computational Linguistics, 29(1):98--133, Mar.

Digital Library

[34]

A. Venugopal, A. Zollmann, and S. Vogel. 2007. An efficient two-pass approach to synchronous-CFG driven statistical MT. In Proc. of HLT-NAACL.

[35]

D. Wu. 1996. A polynomial-time algorithm for statistical machine translation. In Proc. of ACL, pages 152--158, Jun.

Digital Library

[36]

R. Zens and H. Ney. 2004. Improvements in phrase-based statistical machine translation. In Proc. of HLT-NAACL, pages 257--264, May.

Cited By

Roelleke TBonzanini MMartinez-Alvarez M(2013)On the modelling of ranking algorithms in probabilistic datalogProceedings of the 7th International Workshop on Ranking in Databases10.1145/2524828.2524832(1-6)Online publication date: 30-Aug-2013
https://dl.acm.org/doi/10.1145/2524828.2524832
Martinez-Alvarez MRoelleke T(2011)A descriptive approach to classificationProceedings of the Third international conference on Advances in information retrieval theory10.5555/2040317.2040354(297-308)Online publication date: 12-Sep-2011
https://dl.acm.org/doi/10.5555/2040317.2040354
Watanabe TSumita ELin D(2011)Machine translation system combination by confusion forestProceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies - Volume 110.5555/2002472.2002629(1249-1257)Online publication date: 19-Jun-2011
https://dl.acm.org/doi/10.5555/2002472.2002629
Show More Cited By

Index Terms

Translation as weighted deduction
1. Computing methodologies
2. Information systems
  1. Information retrieval
    1. Information retrieval query processing

Recommendations

Bean soup translation: flexible, linguistically-motivated syntax for machine translation
Dependency treelet translation: the convergence of statistical and example-based machine-translation?

We describe a novel approach to MT that combines the strengths of the two leading corpus-based approaches: Phrasal SMT and EBMT. We use a syntactically informed decoder and reordering model based on the source dependency tree, in combination with ...
A weighted finite state transducer translation template model for statistical machine translation

We present a Weighted Finite State Transducer Translation Template Model for statistical machine translation. This is a source-channel model of translation inspired by the Alignment Template translation model. The model attempts to overcome the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image DL Hosted proceedings

EACL '09: Proceedings of the 12th Conference of the European Chapter of the Association for Computational Linguistics

March 2009

905 pages

General Chair:
Alex Lascarides
University of Edinburgh (UK)
,
Program Chairs:
Claire Gardent
CNRS/LORIA Nancy (France)
,
Joakim Nivre
Uppsala University and Vaxjo University (Sweden)

Publisher

Association for Computational Linguistics

United States

Publication History

Published: 30 March 2009

Qualifiers

Research-article

Acceptance Rates

EACL '09 Paper Acceptance Rate 100 of 360 submissions, 28%;

Overall Acceptance Rate 100 of 360 submissions, 28%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
226
Total Downloads

Downloads (Last 12 months)34
Downloads (Last 6 weeks)7

Reflects downloads up to 20 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Roelleke TBonzanini MMartinez-Alvarez M(2013)On the modelling of ranking algorithms in probabilistic datalogProceedings of the 7th International Workshop on Ranking in Databases10.1145/2524828.2524832(1-6)Online publication date: 30-Aug-2013
https://dl.acm.org/doi/10.1145/2524828.2524832
Martinez-Alvarez MRoelleke T(2011)A descriptive approach to classificationProceedings of the Third international conference on Advances in information retrieval theory10.5555/2040317.2040354(297-308)Online publication date: 12-Sep-2011
https://dl.acm.org/doi/10.5555/2040317.2040354
Watanabe TSumita ELin D(2011)Machine translation system combination by confusion forestProceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies - Volume 110.5555/2002472.2002629(1249-1257)Online publication date: 19-Jun-2011
https://dl.acm.org/doi/10.5555/2002472.2002629
Wisniewski GAllauzen AYvon FLi HMàrquez L(2010)Assessing phrase-based translation models with oracle decodingProceedings of the 2010 Conference on Empirical Methods in Natural Language Processing10.5555/1870658.1870749(933-943)Online publication date: 9-Oct-2010
https://dl.acm.org/doi/10.5555/1870658.1870749
Dyer CWeese JSetiawan HLopez ATure FEidelman VGanitkevitch JBlunsom PResnik PKübler S(2010)cdecProceedings of the ACL 2010 System Demonstrations10.5555/1858933.1858935(7-12)Online publication date: 13-Jul-2010
https://dl.acm.org/doi/10.5555/1858933.1858935
Galron DPenkale SWay AMelamed IKoehn PMihalcea R(2009)Accuracy-based scoring for DOTProceedings of the 2009 Conference on Empirical Methods in Natural Language Processing: Volume 1 - Volume 110.5555/1699510.1699559(371-380)Online publication date: 6-Aug-2009
https://dl.acm.org/doi/10.5555/1699510.1699559
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
Li ZEisner JKoehn PMihalcea R(2009)First- and second-order expectation semirings with applications to minimum-risk training on translation forestsProceedings of the 2009 Conference on Empirical Methods in Natural Language Processing: Volume 1 - Volume 110.5555/1699510.1699517(40-51)Online publication date: 6-Aug-2009
https://dl.acm.org/doi/10.5555/1699510.1699517
Auli MLopez AHoang HKoehn PCallison-Burch CKoehn PMonz CSchroeder J(2009)A systematic analysis of translation model search spacesProceedings of the Fourth Workshop on Statistical Machine Translation10.5555/1626431.1626475(224-232)Online publication date: 30-Mar-2009
https://dl.acm.org/doi/10.5555/1626431.1626475

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 Publication

Media

Figures

Other

Tables

View Table of Contents