Quadratic-Time Dependency Parsing for Machine Translation

Proceedings of the 47th Annual Meeting of the ACL and the 4th IJCNLP of the AFNLP, pages 773–781, Suntec, Singapore, 2-7 August 2009. c⃝2009 ACL and AFNLP Quadratic-Time Dependency Parsing for Machine Translation Michel Galley Computer Science Department Stanford University Stanford, CA 94305-9020 mgalley@cs.stanford.edu Christopher D. Manning Computer Science Department Stanford University Stanford, CA 94305-9010 manning@cs.stanford.edu Abstract 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. 1 Introduction Hierarchical approaches to machine translation have proven increasingly successful in recent years (Chiang, 2005; Marcu et al., 2006; Shen et al., 2008), and often outperform phrase-based systems (Och and Ney, 2004; Koehn et al., 2003) on target-language fluency and adequacy. How- ever, their benefits generally come with high com- putational costs, particularly when chart parsing, such as CKY, is integrated with language models of high orders (Wu, 1996). Indeed, synchronous CFG parsing with m-grams runs in O(n3m) time, where n is the length of the sentence.1 Furthermore, synchronous CFG approaches of- ten only marginally outperform the most com- 1The algorithmic complexity of (Wu, 1996) is O(n3+4(m−1)), though Huang et al. (2005) present a more efficient factorization inspired by (Eisner and Satta, 1999) that yields an overall complexity of O(n3+3(m−1)), i.e., O(n3m). In comparison, phrase-based decoding can run in linear time if a distortion limit is imposed. Of course, this comparison holds only for approximate algorithms. Since exact MT decoding is NP complete (Knight, 1999), there is no exact search algorithm for either phrase-based or syntactic MT that runs in polynomial time (unless P = NP). petitive phrase-based systems in large-scale ex- periments such as NIST evaluations.2 This lack of significant difference may not be completely surprising. Indeed, researchers have shown that gigantic language models are key to state-of- the-art performance (Brants et al., 2007), and the ability of phrase-based decoders to handle large-size, high-order language models with no consequence on asymptotic running time during decoding presents a compelling advantage over CKY decoders, whose time complexity grows pro- hibitively large with higher-order language mod- els. While context-free decoding algorithms (CKY, Earley, etc.) may sometimes appear too computa- tionally expensive for high-end statistical machine translation, there are many alternative parsing al- gorithms that have seldom been explored …

Content truncated to 500 words