A Shift-Reduce Parsing Algorithm for Phrase-based String-to-Dependency Translation

Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, pages 1–10, Sofia, Bulgaria, August 4-9 2013. c⃝2013 Association for Computational Linguistics A Shift-Reduce Parsing Algorithm for Phrase-based String-to-Dependency Translation Yang Liu State Key Laboratory of Intelligent Technology and Systems Tsinghua National Laboratory for Information Science and Technology Department of Computer Science and Technology Tsinghua University, Beijing 100084, China liuyang2011@tsinghua.edu.cn Abstract We introduce a shift-reduce parsing algorithm for phrase-based string-to- dependency translation. As the algorithm generates dependency trees for partial translations left-to-right in decoding, it allows for efficient integration of both n-gram and dependency language mod- els. To resolve conflicts in shift-reduce parsing, we propose a maximum entropy model trained on the derivation graph of training data. As our approach combines the merits of phrase-based and string-to- dependency models, it achieves significant improvements over the two baselines on the NIST Chinese-English datasets. 1 Introduction Modern statistical machine translation approaches can be roughly divided into two broad categories: phrase-based and syntax-based. Phrase-based ap- proaches treat phrase, which is usually a sequence of consecutive words, as the basic unit of trans- lation (Koehn et al., 2003; Och and Ney, 2004). As phrases are capable of memorizing local con- text, phrase-based approaches excel at handling local word selection and reordering. In addition, it is straightforward to integrate n-gram language models into phrase-based decoders in which trans- lation always grows left-to-right. As a result, phrase-based decoders only need to maintain the boundary words on one end to calculate language model probabilities. However, as phrase-based de- coding usually casts translation as a string con- catenation problem and permits arbitrary permuta- tion, it proves to be NP-complete (Knight, 1999). Syntax-based approaches, on the other hand, model the hierarchical structure of natural lan- guages (Wu, 1997; Yamada and Knight, 2001; Chiang, 2005; Quirk et al., 2005; Galley et al., 2006; Liu et al., 2006; Huang et al., 2006; Shen et al., 2008; Mi and Huang, 2008; Zhang et al., 2008). As syntactic information can be exploited to provide linguistically-motivated re- ordering rules, predicting non-local permutation is computationally tractable in syntax-based ap- proaches. Unfortunately, as syntax-based de- coders often generate target-language words in a bottom-up way using the CKY algorithm, inte- grating n-gram language models becomes more expensive because they have to maintain target boundary words at both ends of a partial trans- lation (Chiang, 2007; Huang and Chiang, 2007). Moreover, syntax-based approaches often suffer from the rule coverage problem since syntac- tic constraints rule out a large portion of non- syntactic phrase pairs, which might help decoders generalize well to unseen data (Marcu et al., 2006). Furthermore, the introduction of non- terminals makes the grammar size significantly bigger than phrase tables and leads to higher mem- ory requirement (Chiang, 2007). As a result, incremental decoding with hierar- chical structures has attracted increasing attention in recent years. While some authors try to inte- grate syntax into phrase-based decoding (Galley and Manning, 2008; Galley and Manning, 2009; Feng et al., 2010), others develop incremental al- gorithms for …

Content truncated to 500 words