Paper: Quadratic-Time Dependency Parsing for Machine Translation

ACL ID P09-1087
Title Quadratic-Time Dependency Parsing for Machine Translation
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2009

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. Ourresultsshowthataugmentingastate-of- the-art phrase-based system with this dependency language model leads...