On LM Heuristics for the Cube Growing Algorithm

Proceedings of the 13th Annual Conference of the EAMT, pages 242–249, Barcelona, May 2009 On LM Heuristics for the Cube Growing Algorithm David Vilar and Hermann Ney Lehrstuhl f¨ur Informatik 6 RWTH Aachen University 52056 Aachen, Germany {vilar,ney}@informatik.rwth-aachen.de Abstract Current approaches to statistical machine translation try to incorporate more struc- ture into the translation process by includ- ing explicit syntactic information in form of a formal grammar (with a possible, but not necessary, correspondence to a linguis- tic motivated grammar). These more struc- tured models incur into an increased gener- ation cost, and efficient algorithms must be developed. In this paper we concentrate on the cube growing algorithm, a lazy version of the cube grow algorithm. The efficiency of this algorithm depends on a heuristic for language model computation, which is only scarcely discussed in the original pa- per. In this paper we investigate the effect of this heuristic on translation performance and efficiency and propose a new heuris- tic which efficiently decreases memory re- quirements and computation time, while maintaining translation performance. 1 Introduction In the last decade, the phrase-based approach to machine translation has been the de-facto standard for statistical machine translation (SMT) systems. The main reason was that it offered a great im- provement in translation quality over its predeces- sors, the single-word based models. The model itself is also relatively simple and allows for effi- cient generation algorithms like for example beam search (see e.g. (Koehn, 2004)). This allowed the approach to scale to bigger tasks and it is still one of the most widely used models nowadays. The current trend in SMT, however, is to bring more c⃝ 2009 European Association for Machine Translation. information in the form of grammatical structures. There are mainly two possibilities, in the form of linguistically motivated grammars (e.g. (Marcu et al., 2006)) or just formal grammars, which do not need to have a linguistic equivalent (e.g. (Chiang, 2005)). These more expressive models have associated a more difficult search problem, which normally involves a parsing process (usually a variation of the CYK algorithm) while incorporating the trans- lation information. The inclusion of language model (LM) information replicates nodes in the parsing tree, which increases the cost of the gen- eration process. And not to be underestimated, the number of rules the system has to deal with can be of one order of magnitude bigger than the standard phrase-based approach, depending on the model1. Therefore, new, efficient algorithms for trans- lation with these richer models had to be devel- oped. In this paper we will concentrate on the cube growing algorithm (Huang and Chiang, 2007), a lazy version of the cube pruning algorithm (Chi- ang, 2007). These algorithms represent the search space as an hypergraph and add language model scores as necessary. The most time-consuming operation in the translation process is the LM score computation, especially when huge LMs are used. The cube growing algorithm follows an on-demand com- putation strategy and tries to minimize the num- ber of LM scores …

Content truncated to 500 words