Unsupervised Tree Induction for Tree-based Translation

Transactions of the Association for Computational Linguistics, 1 (2013) 243–254. Action Editor: Philipp Koehn. Submitted 12/2012; Revised 3/2013; Published 5/2013. c⃝2013 Association for Computational Linguistics. Unsupervised Tree Induction for Tree-based Translation Feifei Zhai, Jiajun Zhang, Yu Zhou and Chengqing Zong National Laboratory of Pattern Recognition, Institute of Automation, Chinese Academy of Sciences, Beijing, China {ffzhai,jjzhang,yzhou,cqzong}@nlpr.ia.ac.cn Abstract In current research, most tree-based translation models are built directly from parse trees. In this study, we go in another direction and build a translation model with an unsupervised tree structure derived from a novel non-parametric Bayesian model. In the model, we utilize synchronous tree substitution grammars (STSG) to capture the bilingual mapping between language pairs. To train the model efficiently, we develop a Gibbs sampler with three novel Gibbs operators. The sampler is capable of exploring the infinite space of tree structures by performing local changes on the tree nodes. Experimental results show that the string-to- tree translation system using our Bayesian tree structures significantly outperforms the strong baseline string-to-tree system using parse trees. 1 Introduction In recent years, tree-based translation models1 are drawing more and more attention in the community of statistical machine translation (SMT). Due to their remarkable ability to incorporate context structure information and long distance reordering into the translation process, tree-based translation models have shown promising progress in improving translation quality (Liu et al., 2006, 2009; Quirk et al., 2005; Galley et al., 2004, 2006; Marcu et al., 2006; Shen et al., 2008; Zhang et al., 2011b). However, tree-based translation models always suffer from two major challenges: 1) They are usually built directly from parse trees, which are generated by supervised linguistic parsers. 1 A tree-based translation model is defined as a model using tree structures on one side or both sides. However, for many language pairs, it is difficult to acquire such corresponding linguistic parsers due to the lack of Tree-bank resources for training. 2) Parse trees are actually only used to model and explain the monolingual structure, rather than the bilingual mapping between language pairs. This indicates that parse trees are usually not the optimal choice for training tree-based translation models (Wang et al., 2010). Based on the above analysis, we can conclude that the tree structure that is independent from Tree-bank resources and simultaneously considers the bilingual mapping inside the bilingual sentence pairs would be a good choice for building tree- based translation models. Therefore, complying with the above conditions, we propose an unsupervised tree structure for tree- based translation models in this study. In the structures, tree nodes are labeled by combining the word classes of their boundary words rather than by syntactic labels, such as NP, VP. Furthermore, using these node labels, we design a generative Bayesian model to infer the final tree structure based on synchronous tree substitution grammars (STSG) 2 . STSG is derived from the word alignments and thus can grasp the bilingual mapping effectively. Training the Bayesian model is difficult due to the exponential space of possible tree structures for …

Content truncated to 500 words