Efficient Top-Down BTG Parsing for Machine Translation Preordering

Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing, pages 208–218, Beijing, China, July 26-31, 2015. c⃝2015 Association for Computational Linguistics Efficient Top-Down BTG Parsing for Machine Translation Preordering Tetsuji Nakagawa Google Japan Inc. tnaka@google.com Abstract We present an efficient incremental top- down parsing method for preordering based on Bracketing Transduction Gram- mar (BTG). The BTG-based preordering framework (Neubig et al., 2012) can be applied to any language using only par- allel text, but has the problem of compu- tational efficiency. Our top-down parsing algorithm allows us to use the early up- date technique easily for the latent vari- able structured Perceptron algorithm with beam search, and solves the problem. Experimental results showed that the top- down method is more than 10 times faster than a method using the CYK algorithm. A phrase-based machine translation sys- tem with the top-down method had statis- tically significantly higher BLEU scores for 7 language pairs without relying on supervised syntactic parsers, compared to baseline systems using existing preorder- ing methods. 1 Introduction The difference of the word order between source and target languages is one of major problems in phrase-based statistical machine translation. In or- der to cope with the issue, many approaches have been studied. Distortion models consider word re- ordering in decoding time using such as distance (Koehn et al., 2003) and lexical information (Till- man, 2004). Another direction is to use more com- plex translation models such as hierarchical mod- els (Chiang, 2007). However, these approaches suffer from the long-distance reordering issue and computational complexity. Preordering (reordering-as-preprocessing) (Xia and McCord, 2004; Collins et al., 2005) is another approach for tackling the problem, which modifies the word order of an input sentence in a source lan- guage to have the word order in a target language (Figure 1(a)). Various methods for preordering have been studied, and a method based on Bracketing Trans- duction Grammar (BTG) was proposed by Neubig et al. (2012). It reorders source sentences by han- dling sentence structures as latent variables. The method can be applied to any language using only parallel text. However, the method has the prob- lem of computational efficiency. In this paper, we propose an efficient incremen- tal top-down BTG parsing method which can be applied to preordering. Model parameters can be learned using latent variable Perceptron with the early update technique (Collins and Roark, 2004), since the parsing method provides an easy way for checking the reachability of each parser state to valid final states. We also try to use forced-decoding instead of word alignment based on Expectation Maximization (EM) algorithms in order to create better training data for preorder- ing. In experiments, preordering using the top- down parsing algorithm was faster and gave higher BLEU scores than BTG-based preordering using the CYK algorithm. Compared to existing pre- ordering methods, our method had better or com- parable BLEU scores without using supervised parsers. 2 Previous Work 2.1 Preordering for Machine …

Content truncated to 500 words