Fast Decoding and Optimal Decoding for Machine Translation

A good decoding algorithm is critical to the success of any statistical machine translation system. The decoder's job is to find the translation that is most likely according to set of previously learned parameters (and a formula for combining them). Since the space of possible translations is extremely large, typical decoding algorithms are only able to examine a portion of it, thus risking to miss good solutions. In this paper, we compare the speed and output quality of a traditional stack-based decoding algorithm with two new decoders: a fast greedy decoder and a slow but optimal decoder that treats decoding as an integer-programming optimization problem.

• Publication year

  2001

• Venue

  Annual Meeting of the Association for Computational Linguistics

• Publication date

  2001-07-06

• Fields of study

  Computer Science

• Identifiers
  DOI 10.3115/1073012.1073042
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Determining computational complexity from characteristic ‘phase transitions’

  1999cited by this paper
• Decoding complexity in word-replacement translation models

  1999influential reference
• A DP-based Search Using Monotone Alignments in Statistical Translation

  1997cited by this paper
• Decoding Algorithm in Statistical Machine Translation

  1997cited by this paper
• A Polynomial-Time Algorithm for Statistical Machine Translation

  1996cited by this paper
• The Mathematics of Statistical Machine Translation: Parameter Estimation

  1993cited by this paper
• A New Method for Solving Hard Satisfiability Problems

  1992cited by this paper
• A New Method for Solving Hard Satis ability Problems

  1992cited by this paper
• Fast sequential decoding algorithm using a stack

  1969cited by this paper

• Watermark Robustness and Radioactivity May Be at Odds in Federated Learning

  2025cites this paper
• Reanalyzing the Most Probable Sentence Problem: A Case Study in Explicating the Role of Entropy in Algorithmic Complexity

  2021cites this paper
• Fast and Accurate Non-Projective Dependency Tree Linearization

  2020cites this paper
• Improving transliteration with precise alignment of phoneme chunks and using contextual features

  2020cites this paper
• Why Neural Machine Translation Prefers Empty Outputs

  2020cites this paper
• Improving transliteration with precise alignment of phoneme chunks and using contextual features

  2020cites this paper
• On the use of prior and external knowledge in neural sequence models

  2019cites this paper
• Knowing When to Stop: Evaluation and Verification of Conformity to Output-Size Specifications

  2019cites this paper
• Preference learning for machine translation

  2018cites this paper
• A Statistical Translation Approach by Network Model

  2018cites this paper
• Automatic Machine Translation for Arabic Tweets

  2018cites this paper
• A technical reading in statistical and neural machines translation (SMT & NMT)

  2017cites this paper
• A SYSTEMATIC READING IN STATISTICAL TRANSLATION : FROM THE STATISTICAL MACHINE TRANSLATION TO THE NEURAL TRANSLATION MODELS

  2017cites this paper
• Exploitation d'informations riches pour guider la traduction automatique statistique. (Complex Feature Guidance for Statistical Machine Translation)

  2016cites this paper
• Pipeline-tolerant decoder

  2016cites this paper
• Amélioration a posteriori de la traduction automatique par métaheuristique

  2016cites this paper
• Genetic-Based Decoder for Statistical Machine Translation

  2016cites this paper
• Aligning the foundations of hierarchical statistical machine translation

  2016cites this paper
• Refinements in hierarchical phrase-based translation systems

  2015cites this paper
• Exact and Approximate Methods for Machine Translation Decoding

  2015cites this paper
• A New Machine Translation Decoder Based on Artificial Immune System

  2015cites this paper
• Translating Negation: Induction, Search And Model Errors

  2015cites this paper
• Genuine Phrase-Based Statistical Machine Translation with Supervision

  2015cites this paper
• Statistical Machine Translation of the Arabic Language

  2015cites this paper
• Word Confidence Estimation and Its Applications in Statistical Machine Translation. (Les mesures de confiance au niveau des mots et leurs applications pour la traduction automatique statistique)

  2014cites this paper
• Lagrangian relaxation for natural language decoding

  2014cites this paper
• Exact Decoding for Phrase-Based Statistical Machine Translation

  2014cites this paper
• A Credit Assignment Compiler for Joint Prediction

  2014cites this paper
• (Comparison of Performance Factors in Probabilistic Korean Morpheme Restoring Model)

  2014cites this paper
• Confidence-based Rewriting of Machine Translation Output

  2014cites this paper
• EXACT SAMPLING AND OPTIMISATION IN STATISTICAL MACHINE TRANSLATION

  2014cites this paper
• UvA-DARE ( Digital Academic Repository ) Exact Decoding for Phrase-Based Statistical Machine Translation

  2014cites this paper
• Advances of Key Technology for Machine Translation and its Applications

  2014cites this paper
• Amélioration des systèmes de traduction par analyse linguistique et thématique : application à la traduction depuis l'arabe. (Improvements for Machine Translation Systems Using Linguistic and Thematic Analysis : an Application to the Translation from Arabic)

  2013influential citation
• Domain Adaptation for Statistical Machine Translation of Corporate and User-Generated Content

  2013cites this paper
• Learning to translate with products of novices: a suite of open-ended challenge problems for teaching MT

  2013cites this paper
• Oracle decoding as a new way to analyze phrase-based machine translation

  2013cites this paper
• A study in greedy oracle improvement of translation hypotheses

  2013cites this paper
• Optimal Beam Search for Machine Translation

  2013influential citation
• US 7 , 624 , 005 B 2 Page 2 OTHER PUBLICATIONS

  2013cites this paper
• Generating storylines from sensor data

  2013cites this paper
• depuis l'arabe

  2013cites this paper
• A Tutorial on Dual Decomposition and Lagrangian Relaxation for Inference in Natural Language Processing

  2012influential citation
• Discourse in Statistical Machine Translation

  2012cites this paper
• Discriminative Alignment Models For Statistical Machine Translation

  2012influential citation
• MODEL ADAPTATION TECHNIQUES IN MACHINE TRANSLATION

  2012cites this paper
• Prioritization and pruning : effic ient inference with weighted context-free grammars : a dissertaion

  2012cites this paper
• The Geometry of Constrained Structured Prediction: Applications to Inference and Learning of Natural Language Syntax

  2012cites this paper
• Efficient corpus selection for statistical machine translation

  2012cites this paper
• Efficient computational methods for understanding human behaviour from mobile phone data

  2012cites this paper
• Combined Use of Rule-Based and Corpus-Based Methods in Machine Translation

  2012cites this paper
• Predicting Structures in NLP: Constrained Conditional Models and Integer Linear Programming in NLP

  2012cites this paper
• Towards a Semantic Annotation of English Television News - Building and Evaluating a Constraint Grammar FrameNet

  2012cites this paper
• Towards a Semantic Annotation of English Television News - Building and Evaluating a Constraint Grammar FrameNet

  2012cites this paper
• Prioritization and pruning : efficient inference with weighted context-free grammars : a dissertaion

  2012cites this paper
• Exact Decoding of Phrase-Based Translation Models through Lagrangian Relaxation by

  2012cites this paper
• Phrase-Based Statistical Machine Translation

  2012cites this paper
• Prioritization and Pruning: Ecient Inference with Weighted Context-Free Grammars

  2012cites this paper
• Chunk-lattices for verb reordering in Arabic–English statistical machine translation

  2012cites this paper
• Building task-oriented machine translation systems

  2012cites this paper
• Document-Wide Decoding for Phrase-Based Statistical Machine Translation

  2012cites this paper
• Two Decades of Statistical Machine Translation

  2011cites this paper
• Deciphering Foreign Language

  2011cites this paper
• Reordering metrics for statistical machine translation

  2011cites this paper
• présentée à l'Université d'Avignon et des Pays de Vaucluse pour obtenir le diplôme de DOCTORAT

  2011cites this paper
• Online Learning via Dynamic Reranking for Computer Assisted Translation

  2011cites this paper
• Constructing efficient information extraction pipelines

  2011cites this paper
• Statistical approaches for natural language modelling and monotone statistical machine translation

  2011cites this paper
• Novel statistical approaches to text classification, machine translation and computer-assisted translation

  2011cites this paper
• Probabilistic inference for phrase-based machine translation : a sampling approach

  2011cites this paper
• Advances in fully-automatic and interactive phrase-based statistical machine translation

  2011cites this paper
• PARAPHRASE AND TEXTUAL ENTAILMENT RECOGNITION AND GENERATION

  2011cites this paper
• Fast and Robust Joint Models for Biomedical Event Extraction

  2011cites this paper
• Advances in Fully-Automatic and Interactive Phrase-Based Statistical Machine Translation

  2011cites this paper
• Probabilistic Word Alignment under the L_0-norm

  2011cites this paper
• Probabilistic Infrastructureless Positioning in the Pocket

  2011cites this paper
• Exact Decoding of Phrase-Based Translation Models through Lagrangian Relaxation

  2011cites this paper
• Exact Decoding of Syntactic Translation Models through Lagrangian Relaxation

  2011cites this paper
• Fast Generation of Translation Forest for Large-Scale SMT Discriminative Training

  2011cites this paper
• English-Indonesia Machine Translation Using Statistical Approach

  2011cites this paper
• Squibs: Does GIZA++ Make Search Errors?

  2010cites this paper
• Statistical machine translation

  2010cites this paper
• Approche mixte pour la traduction automatique statistique

  2010cites this paper
• Statistical Machine Translation from English to Malayalam

  2010cites this paper
• Monte Carlo techniques for phrase-based translation

  2010cites this paper
• ProbIN: Probabilistic inertial navigation

  2010cites this paper
• Robust machine translation for multi-domain tasks

  2010cites this paper
• Study and implementation on key techniques for an example based machine translation system

  2010cites this paper
• Computing Optimal Alignments for the IBM-3 Translation Model

  2010cites this paper
• L'alignement de graphes : applications en bioinformatique et vision par ordinateur

  2010cites this paper
• Syntax-based language models for statistical machine translation

  2010cites this paper
• Chunk-Based Verb Reordering in VSO Sentences for Arabic-English Statistical Machine Translation

  2010cites this paper
• Statistical machine translation using large-scale lexicon and deep syntactic structures

  2010cites this paper
• Weighted tree automata and transducers for syntactic natural language processing

  2010cites this paper
• Assessing Phrase-Based Translation Models with Oracle Decoding

  2010cites this paper
• Monte Carlo inference and maximization for phrase-based translation

  2009cites this paper
• METIS-II: Low-Resource MT for German to English

  2009cites this paper
• Resourcing machine translation with parallel treebanks

  2009cites this paper
• A prototype English-Turkish statistical machine translation system (İngilizce-Türkçe istatistiksel bilgisayarlı çeviri sistemi prototipi)

  2009cites this paper
• Semantic Roles for SMT: A Hybrid Two-Pass Model

  2009cites this paper