A Polynomial-Time Algorithm for Statistical Machine Translation

We introduce a polynomial-time algorithm for statistical machine translation. This algorithm can be used in place of the expensive, slow best-first search strategies in current statistical translation architectures. The approach employs the stochastic bracketing transduction grammar (SBTG) model we recently introduced to replace earlier word alignment channel models, while retaining a bigram language model. The new algorithm in our experience yields major speed improvement with no significant loss of accuracy.

• Publication year

  1996

• Venue

  Annual Meeting of the Association for Computational Linguistics

• Publication date

  1996-06-24

• Fields of study

  Computer Science

• Identifiers
  DOI 10.3115/981863.981884
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Stochastic Inversion Transduction Grammars, with Application to Segmentation, Bracketing, and Alignment of Parallel Corpora

  1995influential reference
• Using Brackets to Improve Search for Statistical Machine Translation

  1995cited by this paper
• An Algorithm for Simultaneously Bracketing Parallel Texts by Aligning Words

  1995influential reference
• Trainable Coarse Bilingual Grammars for Parallel Text Bracketing

  1995influential reference
• Grammarless Extraction of Phrasal Translation Examples from Parallel Texts

  1995influential reference
• Improving Chinese Tokenization With Linguistic Filters on Statistical Lexical Acquisition

  1994cited by this paper
• Aligning a Parallel English-Chinese Corpus Statistically With Lexical Criteria

  1994cited by this paper
• Statistical Augmentation of a Chinese Machine-Readable Dictionary

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

  1993cited by this paper
• A Statistical Approach to Machine Translation

  1990influential reference
• Computational complexity and natural language

  1987cited by this paper
• Word-Order Variation in Natural Language Generation

  1987cited by this paper
• Direct parsing of ID/LP grammars

  1984cited by this paper
• An efficient context-free parsing algorithm

  1970cited by this paper
• Error bounds for convolutional codes and an asymptotically optimum decoding algorithm

  1967cited by this paper

• Preference Grammars and Decoding Algorithms for Probabilistic Synchronous Context Free Grammar Based Translation

  2024cites this paper
• On Evaluating Multilingual Compositional Generalization with Translated Datasets

  2023cites this paper
• CHAPTER 10 Machine Translation andEncoder-Decoder Models

  2021cites this paper
• Formal Basis of a Language Universal

  2021influential citation
• Searching for More Efficient Dynamic Programs

  2021cites this paper
• 1 Language Divergences and Typology

  2020cites this paper
• Neural Machine Translation with Reordering Embeddings

  2019cites this paper
• Application of fuzzy neural network model in the evaluation of translation quality of scientific and technical documents

  2017cites this paper
• Automatic Generation of Morpheme Level Reordering Rules for Korean to English Machine Translation

  2017cites this paper
• Incorporating target language semantic roles into a string-to-tree translation model

  2017cites this paper
• Domain adaptation for statistical machine translation

  2017cites this paper
• Learning Better Classification-based Reordering Model for Phrase-based Translation

  2017cites this paper
• Book Review: Syntax-Based Statistical Machine Translation by Philip Williams, Rico Sennrich, Matt Post and Philipp Koehn

  2016cites this paper
• Learning to Rap Battle with Bilingual Recursive Neural Networks

  2015cites this paper
• Surveys: A Survey of Word Reordering in Statistical Machine Translation: Computational Models and Language Phenomena

  2015cites this paper
• A General Approach for Word Reordering in English-Vietnamese-English Statistical Machine Translation

  2015cites this paper
• A maximum entropy based reordering model for Mongolian-Chinese SMT with morphological information

  2014cites this paper
• Evaluating Improvised Hip Hop Lyrics - Challenges and Observations

  2014cites this paper
• Bimorphisms and synchronous grammars

  2014influential citation
• Modeling Hip Hop Challenge-Response Lyrics as Machine Translation

  2013cites this paper
• Flat vs. hierarchical phrase-based translation models for cross-language information retrieval

  2013cites this paper
• Backward and trigger-based language models for statistical machine translation

  2013cites this paper
• Improved Online Learning and Modeling for Feature-Rich Discriminative Machine Translation

  2013cites this paper
• The application of source language information in Chinese-English statistical machine translation

  2013cites this paper
• Learning to Freestyle: Hip Hop Challenge-Response Induction via Transduction Rule Segmentation

  2013cites this paper
• Freestyle: a challenge-response system for hip hop lyrics via unsupervised induction of stochastic transduction grammars

  2013cites this paper
• Unsupervised Tree Induction for Tree-based Translation

  2013cites this paper
• Hierarchical Alignment Trees : A Recursive Factorization of Reordering in Word Alignments with Empirical Results

  2013cites this paper
• NiuTrans: An Open Source Toolkit for Phrase-based and Syntax-based Machine Translation

  2012cites this paper
• Using Syntactic Head Information in Hierarchical Phrase-Based Translation

  2012cites this paper
• An overview of the phrase-based statistical machine translation techniques

  2012cites this paper
• The NiuTrans Machine Translation System for CWMT2011

  2011influential citation
• The NiuTrans Machine Translation System for NTCIR-9 PatentMT

  2011cites this paper
• Hierarchical Translation Equivalence over Word Alignments

  2011cites this paper
• Soft Dependency Constraints for Reordering in Hierarchical Phrase-Based Translation

  2011cites this paper
• Markov-based reordering model for English-Myanmar translation

  2011cites this paper
• Coarse-to-Fine Natural Language Processing

  2011cites this paper
• Principled Induction of Phrasal Bilexica

  2011cites this paper
• Word-Level Reordering Model for Phrase-Based SMT

  2011influential citation
• Advances in fully-automatic and interactive phrase-based statistical machine translation

  2011cites this paper
• Enhancing Language Models in Statistical Machine Translation with Backward N-grams and Mutual Information Triggers

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

  2011cites this paper
• Syntax-based Statistical Machine Translation Models and Approaches

  2011cites this paper
• Bitext Alignment

  2011cites this paper
• Automatic Reordering Rule Generation and Application of Reordering Rules in Stochastic Reordering Model for English-Myanmar Machine Translation

  2011cites this paper
• Two Decades of Statistical Machine Translation

  2011cites this paper
• Automatic Reordering Rule Generation Based On Parallel Tagged Aligned Corpus for Myanmar-English Machine Translation

  2011cites this paper
• Improved Models of Distortion Cost for Statistical Machine Translation

  2010cites this paper
• Head-modifier Relation based Non-lexical Reordering Model for Phrase-Based Translation

  2010cites this paper
• Towards a Pictorially Grounded Language for Machine-Aided Translation

  2010cites this paper
• New Statistical And Syntactic Models For Machine Translation

  2010cites this paper
• Dependency-Based Bracketing Transduction Grammar for Statistical Machine Translation

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

  2010cites this paper
• Beyond multi-class : structured learning for machine translation

  2010cites this paper
• Maximum Entropy Based Phrase Reordering for Hierarchical Phrase-Based Translation

  2010influential citation
• Syntax-based language models for statistical machine translation

  2010cites this paper
• Using linguistic knowledge in statistical machine translation

  2010cites this paper
• An Efficient Shift-Reduce Decoding Algorithm for Phrased-Based Machine Translation

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

  2010cites this paper
• Linguistically Annotated Reordering: Evaluation and Analysis

  2010cites this paper
• Extending the Hierarchical Phrase Based Model with Maximum Entropy Based BTG

  2010cites this paper
• Improving phrase-based SMT model with Flattened Bilingual Parse Tree

  2010cites this paper
• Binarization of Synchronous Context-Free Grammars

  2009cites this paper
• Quadratic-Time Dependency Parsing for Machine Translation

  2009cites this paper
• Learning Bilingual Linguistic Reordering Model for Statistical Machine Translation

  2009cites this paper
• Preference grammars and decoding algorithms for probabilistic synchronous context free grammar based translation

  2009cites this paper
• Efficient Beam Thresholding for Statistical Machine Translation

  2009influential citation
• Translation as Weighted Deduction

  2009cites this paper
• NEUTrans: a Phrase-Based SMT System for CWMT2009

  2009cites this paper
• Hierarchical Phrase-Based Translation with Weighted Finite State Transducers

  2009cites this paper
• State-of-the-Art Word Reordering Approaches in Statistical Machine Translation: A Survey

  2009influential citation
• A POS-Based Model for Long-Range Reorderings in SMT

  2009cites this paper
• CCG-based Models for Statistical Machine Translation

  2009cites this paper
• Improving Phrase-Based Translation via Word Alignments from Stochastic Inversion Transduction Grammars

  2009cites this paper
• USING SEMANTIC ROLE LABELS TO REORDER STATISTICAL MACHINE TRANSLATION OUTPUT

  2009cites this paper
• Phrase based statistical machine translation : models, search, training

  2008cites this paper
• A Reordering Model for Phrase-Based Machine Translation

  2008cites this paper
• Parsers as language models for statistical machine translation

  2008cites this paper
• Arabic Computational Linguistics: Current Implementations

  2008cites this paper
• Overcoming Vocabulary Sparsity in MT Using Lattices

  2008cites this paper
• Handling complexity of synchronous grammars for machine translation

  2008cites this paper
• Online Large-Margin Training of Syntactic and Structural Translation Features

  2008cites this paper
• A Search in the Forest : Efficient Algorithms for Parsing and Machine Translation based on Packed Forests A DISSERTATION PROPOSAL in Computer and Information Science

  2008cites this paper
• Linguistically Annotated BTG for Statistical Machine Translation

  2008influential citation
• Forest-based algorithms in natural language processing

  2008cites this paper
• Architecture and modeling for n-gram-based statistical machine translation

  2008cites this paper
• Coarse-to-Fine Syntactic Machine Translation using Language Projections

  2008cites this paper
• Reordering pPhrase-based machine translation over chunks

  2008cites this paper
• Machine Translation by Pattern Matching

  2008cites this paper
• Diversion of Hierarchical Phrases as Reordering Templates

  2008cites this paper
• Refinements in BTG-based Statistical Machine Translation

  2008cites this paper
• Computing multiple weighted reordering hypotheses for a phrase-based statistical machine translation system

  2008cites this paper
• On the application of different evolutionary algorithms to the alignment problem in statistical machine translation

  2008cites this paper
• 8 Statistical Machine Translation

  2008cites this paper
• Structured classification for multilingual natural language processing

  2007cites this paper
• Improving Statistical Machine Translation Using Word Sense Disambiguation

  2007cites this paper
• Binarization, Synchronous Binarization, and Target-side Binarization

  2007cites this paper
• On the Complexity of Non-Projective Data-Driven Dependency Parsing

  2007cites this paper
• Context-dependent phrasal translation lexicons for statistical machine translation

  2007cites this paper
• Phrase Reordering Model Integrating Syntactic Knowledge for SMT

  2007cites this paper