Quadratic-time dependency parsing for machine translation

Efficiency is a prime concern in syntactic MT de-coding, yet significant developments in statisti-cal 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) prob-lem, 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 depen-dency 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 de-scribes 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.