Fast Generation of Translation Forest for Large-Scale SMT Discriminative Training

Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 880–888, Edinburgh, Scotland, UK, July 27–31, 2011. c⃝2011 Association for Computational Linguistics Fast Generation of Translation Forest for Large-Scale SMT Discriminative Training Xinyan Xiao, Yang Liu, Qun Liu, and Shouxun Lin Key Laboratory of Intelligent Information Processing Institute of Computing Technology Chinese Academy of Sciences {xiaoxinyan,yliu,liuqun,sxlin}@ict.ac.cn Abstract Although discriminative training guarantees to improve statistical machine translation by in- corporating a large amount of overlapping fea- tures, it is hard to scale up to large data due to decoding complexity. We propose a new al- gorithm to generate translation forest of train- ing data in linear time with the help of word alignment. Our algorithm also alleviates the oracle selection problem by ensuring that a forest always contains derivations that exactly yield the reference translation. With millions of features trained on 519K sentences in 0.03 second per sentence, our system achieves sig- nificant improvement by 0.84 BLEU over the baseline system on the NIST Chinese-English test sets. 1 Introduction Discriminative model (Och and Ney, 2002) can easily incorporate non-independent and overlapping features, and has been dominating the research field of statistical machine translation (SMT) in the last decade. Recent work have shown that SMT benefits a lot from exploiting large amount of features (Liang et al., 2006; Tillmann and Zhang, 2006; Watanabe et al., 2007; Blunsom et al., 2008; Chiang et al., 2009). However, the training of the large number of features was always restricted in fairly small data sets. Some systems limit the number of training ex- amples, while others use short sentences to maintain efficiency. Overfitting problem often comes when training many features on a small data (Watanabe et al., 2007; Chiang et al., 2009). Obviously, using much more data can alleviate such problem. Furthermore, large data also enables us to globally train millions of sparse lexical features which offer accurate clues for SMT. Despite these advantages, to the best of our knowledge, no previous discriminative training paradigms scale up to use a large amount of training data. The main obstacle comes from the complexity of packed forests or n-best lists generation which requires to search through all possible translations of each training example, which is computationally prohibitive in practice for SMT. To make normalization efficient, contrastive esti- mation (Smith and Eisner, 2005; Poon et al., 2009) introduce neighborhood for unsupervised log-linear model, and has presented positive results in various tasks. Motivated by these work, we use a translation forest (Section 3) which contains both “reference” derivations that potentially yield the reference trans- lation and also neighboring “non-reference” deriva- tions that fail to produce the reference translation.1 However, the complexity of generating this transla- tion forest is up to O(n6), because we still need bi- parsing to create the reference derivations. Consequently, we propose a method to fast gener- ate a subset of the forest. The key idea (Section 4) is to initialize a reference derivation tree with maxi- mum score by the help of word …

Content truncated to 500 words