Article

Free access

A DP based search using monotone alignments in statistical translation

Authors:

C. Tillmann,

S. Vogel,

H. Ney,

A. ZubiagaAuthors Info & Claims

ACL '98/EACL '98: Proceedings of the 35th Annual Meeting of the Association for Computational Linguistics and Eighth Conference of the European Chapter of the Association for Computational Linguistics

Pages 289 - 296

https://doi.org/10.3115/976909.979654

Published: 07 July 1997 Publication History

PDF eReader

Abstract

In this paper, we describe a Dynamic Programming (DP) based search algorithm for statistical translation and present experimental results. The statistical translation uses two sources of information: a translation model and a language model. The language model used is a standard bigram model. For the translation model, the alignment probabilities are made dependent on the differences in the alignment positions rather than on the absolute positions. Thus, the approach amounts to a first-order Hidden Markov model (HMM) as they are used successfully in speech recognition for the time alignment problem. Under the assumption that the alignment is monotone with respect to the word order in both languages, an efficient search strategy for translation can be formulated. The details of the search algorithm are described. Experiments on the EuTrans corpus produced a word error rate of 5.1%.

References

[1]

A. L. Berger. P. F. Brown. S. A. Della Pietra. V. J. Della Pietra. J. R. Gillett. J. D. Lafferty. R. L. Mercer. H. Printz. and L. Ures. 1994. "The Candide System for Machine Translation". In Proc. of ARPA Human Language Technology Workshop. pp. 152--157. Plainsboro. NJ. Morgan Kaufmann Publishers. San Mateo. CA. March.

Digital Library

Google Scholar

[2]

P. F. Brown, V. J. Della Pietra. S. A. Della Pietra. and R. L. Mercer. 1993. "The Mathematics of Statistical Machine Translation: Parameter Estimation". Computational Linguistics. Vol. 19. No. 2. pp. 263--311.

Digital Library

Google Scholar

[3]

I. Dagan. K. W. Church. and W. A. Gale. 1993. "Robust Bilingual Word Alignment for Machine Aided Translation". In Proc. of the Workshop on very Large Corpora. pp. 1--8. Columbus, OH.

Digital Library

Google Scholar

[4]

P. Fung. and K. W. Church. 1994. "K-vec: A New Approach for Aligning Parallel Texts". In Proc. of the 15th Int. Conf. on Computational Linguistics, pp. 1096--1102. Kyoto.

Digital Library

Google Scholar

[5]

F. Jelinek. 1976. "Speech Recognition by Statistical Methods". Proc. of the IEEE. Vol. 64. pp. 532--556. April.

Google Scholar

[6]

M. Kay. and M. Röscheisen. 1993. "Text-Translation Alignment". Computational Linguistics. Vol. 19. No. 2. pp. 121--142.

Digital Library

Google Scholar

[7]

H. Ney, D. Mergel, A. Noll, A. Paeseler. 1992. "Data Driven Search Organization for Continuous Speech Recognition". IEEE Trans. on Signal Processing, Vol. SP-40. No. 2. pp. 272--281. February.

Google Scholar

[8]

E. Vidal. 1996. "Final report of Esprit Research Project 20268 (EuTrans): Example-Based Understanding and Translation Systems". Universidad Politécnica de Valencia. Instituto Tecnológio de Informática, October.

Google Scholar

[9]

E. Vidal. 1997. "Finite-State Speech-to-Speech Translation". In Proc. of the Int. Conf. on Acoustics, Speech and Signal Processing. Munich. April.

Digital Library

Google Scholar

[10]

S. Vogel, H. Ney, and C. Tillmann. 1996. "HMM Based Word Alignment in Statistical Translation". In Proc. of the 16th Int. Conf. on Computational Linguistics. pp. 836--841. Copenhagen. August.

Digital Library

Google Scholar

[11]

D. Wu. 1996. "A Polynomial-Time Algorithm for Statistical Machine Translation". In Proc. of the 34th Annual Conf. of the Association for Computational Linguistics, pp. 152--158. Santa Cruz, CA. June.

Digital Library

Google Scholar

Cited By

View all

Hardmeier CNivre JTiedemann JTsujii JHenderson JPasca M(2012)Document-wide decoding for phrase-based statistical machine translationProceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning10.5555/2390948.2391081(1179-1190)Online publication date: 12-Jul-2012
https://dl.acm.org/doi/10.5555/2390948.2391081
Na SNg HMa WNie JBaeza-Yates RChua TCroft W(2011)Enriching document representation via translation for improved monolingual information retrievalProceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval10.1145/2009916.2010030(853-862)Online publication date: 24-Jul-2011
https://dl.acm.org/doi/10.1145/2009916.2010030
Contractor DFaruquie TSubramaniam LJoshi AHuang CJurafsky D(2010)Unsupervised cleansing of noisy textProceedings of the 23rd International Conference on Computational Linguistics: Posters10.5555/1944566.1944588(189-196)Online publication date: 23-Aug-2010
https://dl.acm.org/doi/10.5555/1944566.1944588
Show More Cited By

A DP based search using monotone alignments in statistical translation
1. Computing methodologies
  1. Artificial intelligence
    1. Natural language processing
2. Hardware
  1. Power and energy
    1. Power estimation and optimization

Recommendations

Word re-ordering and DP-based search in statistical machine translation
COLING '00: Proceedings of the 18th conference on Computational linguistics - Volume 2

In this paper, we describe a search procedure for statistical machine translation (MT) based on dynamic programming (DP). Starting from a DP-based solution to the traveling salesman problem, we present a novel technique to restrict the possible word ...
A syntax-based statistical translation model
N-gram-based statistical machine translation versus syntax augmented machine translation: comparison and system combination
EACL '09: Proceedings of the 12th Conference of the European Chapter of the Association for Computational Linguistics

In this paper we compare and contrast two approaches to Machine Translation (MT): the CMU-UKA Syntax Augmented Machine Translation system (SAMT) and UPC-TALP N-gram-based Statistical Machine Translation (SMT). SAMT is a hierarchical syntax-driven ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

July 1997

543 pages

Program Chairs:
Philip R. Cohen
Oregon Graduate Institute
,
Wolfgang Wahlster
DFKI Saarbrücken, Germany

Publisher

Association for Computational Linguistics

United States

Publication History

Published: 07 July 1997

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 85 of 443 submissions, 19%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
488
Total Downloads

Downloads (Last 12 months)41
Downloads (Last 6 weeks)10

Reflects downloads up to 22 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Hardmeier CNivre JTiedemann JTsujii JHenderson JPasca M(2012)Document-wide decoding for phrase-based statistical machine translationProceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning10.5555/2390948.2391081(1179-1190)Online publication date: 12-Jul-2012
https://dl.acm.org/doi/10.5555/2390948.2391081
Na SNg HMa WNie JBaeza-Yates RChua TCroft W(2011)Enriching document representation via translation for improved monolingual information retrievalProceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval10.1145/2009916.2010030(853-862)Online publication date: 24-Jul-2011
https://dl.acm.org/doi/10.1145/2009916.2010030
Contractor DFaruquie TSubramaniam LJoshi AHuang CJurafsky D(2010)Unsupervised cleansing of noisy textProceedings of the 23rd International Conference on Computational Linguistics: Posters10.5555/1944566.1944588(189-196)Online publication date: 23-Aug-2010
https://dl.acm.org/doi/10.5555/1944566.1944588
Tillmann C(2009)A beam-search extraction algorithm for comparable dataProceedings of the ACL-IJCNLP 2009 Conference Short Papers10.5555/1667583.1667653(225-228)Online publication date: 4-Aug-2009
https://dl.acm.org/doi/10.5555/1667583.1667653
Lopez A(2008)Statistical machine translationACM Computing Surveys10.1145/1380584.138058640:3(1-49)Online publication date: 13-Aug-2008
https://dl.acm.org/doi/10.1145/1380584.1380586
Zhang YZens RNey H(2007)Chunk-level reordering of source language sentences with automatically learned rules for statistical machine translationProceedings of the NAACL-HLT 2007/AMTA Workshop on Syntax and Structure in Statistical Translation10.5555/1626281.1626282(1-8)Online publication date: 26-Apr-2007
https://dl.acm.org/doi/10.5555/1626281.1626282
Elming JHabash NSidner CSchultz TStone MZhai C(2007)Combination of statistical word alignments based on multiple preprocessing schemesHuman Language Technologies 2007: The Conference of the North American Chapter of the Association for Computational Linguistics; Companion Volume, Short Papers10.5555/1614108.1614115(25-28)Online publication date: 22-Apr-2007
https://dl.acm.org/doi/10.5555/1614108.1614115
Tillmann CMcDonald RSutton CDaumé HMcCallum APereira FBilmes J(2006)Efficient dynamic programming search algorithms for phrase-based SMTProceedings of the Workshop on Computationally Hard Problems and Joint Inference in Speech and Language Processing10.5555/1631828.1631830(9-16)Online publication date: 9-Jun-2006
https://dl.acm.org/doi/10.5555/1631828.1631830
Al-Onaizan YPapineni K(2006)Distortion models for statistical machine translationProceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics10.3115/1220175.1220242(529-536)Online publication date: 17-Jul-2006
https://dl.acm.org/doi/10.3115/1220175.1220242
Fattah MRen FKuroiwa S(2006)Stemming to improve translation lexicon creation form bitextsInformation Processing and Management: an International Journal10.1016/j.ipm.2005.07.00242:4(1003-1016)Online publication date: 1-Jul-2006
https://dl.acm.org/doi/10.1016/j.ipm.2005.07.002
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

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

Cited By

Recommendations

Word re-ordering and DP-based search in statistical machine translation

A syntax-based statistical translation model

N-gram-based statistical machine translation versus syntax augmented machine translation: comparison and system combination