A Structured Language Model for Incremental Tree-to-String Translation

Proceedings of COLING 2014, the 25th International Conference on Computational Linguistics: Technical Papers, pages 1133–1143, Dublin, Ireland, August 23-29 2014. A Structured Language Model for Incremental Tree-to-String Translation Heng Yu1 1Institute of Computing Technology. CAS University of Chinese Academy of Sciences yuheng@ict.ac.cn Haitao Mi T.J. Watson Research Center IBM hmi@us.ibm.com Liang Huang Queens College & Grad. Center City University of New York huang@cs.qc.cuny.edu Qun Liu1,2 2Centre for Next Generation Localisation. Faculty of Engineering and Computing Dublin City University qliu@computing.dcu.ie Abstract Tree-to-string systems have gained significant popularity thanks to their simplicity and efficien- cy by exploring the source syntax information, but they lack in the target syntax to guarantee the grammaticality of the output. Instead of using complex tree-to-tree models, we integrate a structured language model, a left-to-right shift-reduce parser in specific, into an incremental tree-to-string model, and introduce an efficient grouping and pruning mechanism for this integra- tion. Large-scale experiments on various Chinese-English test sets show that with a reasonable speed our method gains an average improvement of 0.7 points in terms of (Ter-Bleu)/2 than a state-of-the-art tree-to-string system. 1 Introduction Tree-to-string models (Liu et al., 2006; Huang et al., 2006) have made promising progress and gained significant popularity in recent years, as they run faster than string-to-tree counterparts (e.g. (Galley et al., 2006)), and do not need binarized grammars. Especially, Huang and Mi (2010) make it much faster by proposing an incremental tree-to-string model, which generates the target translation exactly in a left- to-right manner. Although, tree-to-string models have made those progresses, they can not utilize the target syntax information to guarantee the grammaticality of the output, as they only generate strings on the target side. One direct approach to handle this problem is to extend tree-to-string models into complex tree-to-tree models (e.g. (Quirk et al., 2005; Liu et al., 2009; Mi and Liu, 2010)). However, tree-to-tree approaches still significantly under-perform than tree-to-string systems due to the poor rule coverage (Liu et al., 2009) and bi-parsing failures (Liu et al., 2009; Mi and Liu, 2010). Another potential solution is to use structured language models (Slm) (Chelba and Jelinek, 2000; Char- niak et al., 2003; Post and Gildea, 2008; Post and Gildea, 2009), as the monolingual Slmhas achieved better perplexity than the traditional n-gram word sequence model. More importantly, the Slmis inde- pendent of any translation model. Thus, integrating a Slminto a tree-to-string model will not face the problems that tree-to-tree models have. However, integration is not easy, as the following two questions arise. First, the search space grows significantly, as a partial translation has a lot of syntax structures. Second, hypotheses in the same bin may not be comparable, since their syntactic structures may not be comparable, and the future costs are hard to estimate. Hassan et al. (2009) skip those problems by only keeping the best parsing structure for each hypothesis. In this paper, we integrate a shift-reduce parser into an incremental tree-to-string model, and intro- duce an efficient grouping and pruning method to handle the growing search …

Content truncated to 500 words