Quadratic-Time Dependency Parsing for Machine Translation

Efficiency is a prime concern in syntactic MT decoding, yet significant developments in statistical parsing with respect to asymptotic efficiency haven't yet been explored in MT. Recently, McDonald et al. (2005b) formalized dependency parsing as a maximum spanning tree (MST) problem, which can be solved in quadratic time relative to the length of the sentence. They show that MST parsing is almost as accurate as cubic-time dependency parsing in the case of English, and that it is more accurate with free word order languages. This paper applies MST parsing to MT, and describes how it can be integrated into a phrase-based decoder to compute dependency language model scores. Our results show that augmenting a state-of-the-art phrase-based system with this dependency language model leads to significant improvements in TER (0.92%) and BLEU (0.45%) scores on five NIST Chinese-English evaluation test sets.

• Publication year

  2009

• Venue

  Annual Meeting of the Association for Computational Linguistics

• Publication date

  2009-08-02

• Fields of study

  Linguistics, Computer Science

• Identifiers
  DOI 10.3115/1690219.1690255
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Non-Projective Dependency Parsing

  2010cited by this paper
• Lattice-based Minimum Error Rate Training for Statistical Machine Translation

  2008cited by this paper
• A New String-to-Dependency Machine Translation Algorithm with a Target Dependency Language Model

  2008cited by this paper
• Efficient Multi-Pass Decoding for Synchronous Context Free Grammars

  2008cited by this paper
• Optimizing Chinese Word Segmentation for Machine Translation Performance

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

  2008cited by this paper
• Chinese Syntactic Reordering for Statistical Machine Translation

  2007cited by this paper
• Large Language Models in Machine Translation

  2007cited by this paper
• CCG Supertags in Factored Statistical Machine Translation

  2007cited by this paper
• Moses: Open Source Toolkit for Statistical Machine Translation

  2007influential reference
• Adding Noun Phrase Structure to the Penn Treebank

  2007influential reference
• Forest Rescoring: Faster Decoding with Integrated Language Models

  2007cited by this paper
• Frustratingly Easy Domain Adaptation

  2007cited by this paper
• SPMT: Statistical Machine Translation with Syntactified Target Language Phrases

  2006cited by this paper
• A Study of Translation Edit Rate with Targeted Human Annotation

  2006influential reference
• A Hierarchical Phrase-Based Model for Statistical Machine Translation

  2005cited by this paper
• Non-Projective Dependency Parsing using Spanning Tree Algorithms

  2005influential reference
• Dependency Treelet Translation: Syntactically Informed Phrasal SMT

  2005cited by this paper
• Proceedings of the Ninth International Workshop on Parsing Technologies (IWPT), pages 65--73,

  2005cited by this paper
• Machine Translation Using Probabilistic Synchronous Dependency Insertion Grammars

  2005cited by this paper
• On Some Pitfalls in Automatic Evaluation and Significance Testing for MT

  2005cited by this paper
• Online Large-Margin Training of Dependency Parsers

  2005influential reference
• A STUDY OF TRANSLATION ERROR RATE WITH TARGETED HUMAN ANNOTATION

  2005cited by this paper
• The Alignment Template Approach to Statistical Machine Translation

  2004cited by this paper
• A Smorgasbord of Features for Statistical Machine Translation

  2004cited by this paper
• Minimum Error Rate Training in Statistical Machine Translation

  2003cited by this paper
• Arborescence optimization problems solvable by Edmonds' algorithm

  2003cited by this paper
• Ultraconservative Online Algorithms for Multiclass Problems

  2003cited by this paper
• Statistical Phrase-Based Translation

  2003cited by this paper
• Feature-Rich Part-of-Speech Tagging with a Cyclic Dependency Network

  2003cited by this paper
• Phrasal Cohesion and Statistical Machine Translation

  2002influential reference
• Bleu: a Method for Automatic Evaluation of Machine Translation

  2002influential reference
• SRILM - an extensible language modeling toolkit

  2002cited by this paper
• Efficient Parsing for Bilexical Context-Free Grammars and Head Automaton Grammars

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

  1999cited by this paper
• A Linear Observed Time Statistical Parser Based on Maximum Entropy Models

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

  1996cited by this paper
• Three New Probabilistic Models for Dependency Parsing: An Exploration

  1996influential reference
• Finding optimum branchings

  1977cited by this paper

• Machine Translation in the Era of Large Language Models:A Survey of Historical and Emerging Problems

  2025cites this paper
• Dependency Scoring Learning and Corpus Boosting for Translation-Based Cross-Lingual Dependency Parsing

  2025cites this paper
• A Truly Joint Neural Architecture for Segmentation and Parsing

  2024cites this paper
• Approach for Efficient Triple Pattern Extraction Information Retrieval in Ontology

  2022cites this paper
• Syntactic annotation in the i3rab dependency treebank

  2021cites this paper
• I3rab: A New Arabic Dependency Treebank Based on Arabic Grammatical Theory

  2020cites this paper
• Coarse-Grained vs. Fine-Grained Lithuanian Dependency Parsing

  2020cites this paper
• Tree Rotations for Dependency Trees: Converting the Head-Directionality of Noun Phrases

  2020cites this paper
• Improving Arabic dependency parsers by using dependency relations

  2020cites this paper
• Multi-Task Semantic Dependency Parsing with Policy Gradient for Learning Easy-First Strategies

  2019cites this paper
• A neural joint model for Vietnamese word segmentation, POS tagging and dependency parsing

  2018cites this paper
• An Improved Neural Network Model for Joint POS Tagging and Dependency Parsing

  2018cites this paper
• The mat sat on the cat: investigating structure in the evaluation of order in machine translation

  2017cites this paper
• UvA-DARE ( Digital Academic Repository ) Class-Based Language Modeling for Translating into Morphologically Rich Languages

  2014cites this paper
• Phrase Dependency Machine Translation with Quasi-Synchronous Tree-to-Tree Features

  2014cites this paper
• A Structured Language Model for Incremental Tree-to-String Translation

  2014cites this paper
• Class-Based Language Modeling for Translating into Morphologically Rich Languages

  2014cites this paper
• Triple Patterns Extraction for Accessing Data on Ontology

  2014cites this paper
• Semi-Supervised Learning and Domain Adaptation in Natural Language Processing

  2013cites this paper
• A Dependency-Constrained Hierarchical Model with Moses

  2013cites this paper
• An Empirical Study of Differences between Conversion Schemes and Annotation Guidelines

  2013cites this paper
• A Dynamic Confusion Score for Dependency Arc Labels

  2013cites this paper
• A Shift-Reduce Parsing Algorithm for Phrase-based String-to-Dependency Translation

  2013influential citation
• A unified approach for effectively integrating source-side syntactic reordering rules into phrase-based translation

  2013cites this paper
• Down-stream effects of tree-to-dependency conversions

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

  2012cites this paper
• Discriminative Feature-Rich Modeling for Syntax-Based Machine Translation

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

  2012cites this paper
• An incremental syntactic language model for statistical phrase-based machine translation

  2012cites this paper
• The Regression Model of Machine Translation

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

  2012cites this paper
• Bean soup translation: flexible, linguistically-motivated syntax for machine translation

  2012cites this paper
• A Class-Based Agreement Model for Generating Accurately Inflected Translations

  2012cites this paper
• Soft string-to-dependency hierarchical machine translation

  2011cites this paper
• Effects of Noun Phrase Bracketing in Dependency Parsing and Machine Translation

  2011cites this paper
• Quasi-Synchronous Phrase Dependency Grammars for Machine Translation

  2011cites this paper
• Reordering by Parsing

  2011cites this paper
• Parameterizing phrase based statistical machine translation models: an analytic study

  2011cites this paper
• L1 Regularized Regression for Reranking and System Combination in Machine Translation

  2010cites this paper
• On the Derivation Perplexity of Treebanks

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

  2010cites this paper
• 2D Trie for Fast Parsing

  2010cites this paper
• Fast and Accurate Arc Filtering for Dependency Parsing

  2010cites this paper
• Phrasal: A Statistical Machine Translation Toolkit for Exploring New Model Features

  2010cites this paper
• Phrasal: A Statistical Machine Translation Toolkit for Exploring New Model Features

  2010cites this paper
• Using a maximum entropy-based tagger to improve a very fast vine parser

  2009cites this paper