Parallel Implementations of Word Alignment Tool

Software Engineering, Testing, and Quality Assurance for Natural Language Processing, pages 49–57, Columbus, Ohio, USA, June 2008. c⃝2008 Association for Computational Linguistics Parallel Implementations of Word Alignment Tool Qin Gao and Stephan Vogel Language Technology Institution School of Computer Science Carnegie Mellon University Pittsburgh, PA, 15213, USA {qing, stephan.vogel}@cs.cmu.edu Abstract Training word alignment models on large cor- pora is a very time-consuming processes. This paper describes two parallel implementations of GIZA++ that accelerate this word align- ment process. One of the implementations runs on computer clusters, the other runs on multi-processor system using multi-threading technology. Results show a near-linear speed- up according to the number of CPUs used, and alignment quality is preserved. 1 Introduction Training state-of-the-art phrase-based statistical ma- chine translation (SMT) systems requires several steps. First, word alignment models are trained on the bilingual parallel training corpora. The most widely used tool to perform this training step is the well-known GIZA++(Och and Ney, 2003). The re- sulting word alignment is then used to extract phrase pairs and perhaps other information to be used in translation systems, such as block reordering mod- els. Among the procedures, more than 2/3 of the time is consumed by word alignment (Koehn et al., 2007). Speeding up the word alignment step can dramatically reduces the overall training time, and in turn accelerates the development of SMT systems. With the rapid development of computing hard- ware, multi-processor servers and clusters become widely available. With parallel computing, process- ing time (wall time) can often be cut down by one or two orders of magnitude. Tasks, which require several weeks on a single CPU machine may take only a few hours on a cluster. However, GIZA++ was designed to be single-process and single-thread. To make more efficient use of available computing resources and thereby speed up the training of our SMT system, we decided to modify GIZA++ so that it can run in parallel on multiple CPUs. The word alignment models implemented in GIZA++, the so-called IBM (Brown et al., 1993) and HMM alignment models (Vogel et al., 1996) are typ- ical implementation of the EM algorithm (Dempster et al., 1977). That is to say that each of these mod- els run for a number of iterations. In each iteration it first calculates the best word alignment for each sentence pairs in the corpus, accumulating various counts, and then normalizes the counts to generate the model parameters for the next iteration. The word alignment stage is the most time-consuming part, especially when the size of training corpus is large. During the aligning stage, all sentences can be aligned independently of each other, as model parameters are only updated after all sentence pairs have been aligned. Making use of this property, the alignment procedure can be parallelized. The basic idea is to have multiple processes or threads aligning portions of corpus independently and then merge the counts and perform normalization. The paper implements two parallelization meth- ods. The PGIZA++ implementation, which is based on (Lin et al, …

Content truncated to 500 words