📄 Parallel Implementations of Word Alignment Tool

Summary

GIZA++ is the standard tool for training IBM and HMM word alignment models for phrase-based SMT. It runs as a single process on a single thread, and word alignment accounts for most of an SMT system's training time. Gao and Vogel use the structure of EM to fix this. In the E-step, every sentence pair can be aligned independently, because parameters change only in the M-step. They build two parallel versions on this basis. PGIZA++ splits the corpus across separate processes, possibly on cluster nodes, and a master process merges their count files and normalizes them. MGIZA++ runs threads in shared memory and uses locks to synchronize access to the count tables. On 4 CPUs, MGIZA++ finished in about 41% of the single-thread time, and its Viterbi alignments were almost identical to the reference. PGIZA++ gained little on a small corpus because of file I/O and normalization costs, but it scales past a single machine. While parallelizing, the authors also found and fixed an HMM initialization bug in GIZA++. The work matters because it makes alignment training on large parallel corpora practical.

Key points

• Model sequence: both tools parallelize the usual training pipeline of Model 1, then HMM, then Model 3 and Model 4. Each iteration consists of parallel alignment and count collection, followed by a central merge-and-normalize step.
• Pruning count tables: in a 10-million-sentence-pair experiment, pruning shrank each child's lexicon (TTable) count file from about 1.27 GB to between 494 MB (Model 1) and 129 MB (Model 4). Pruning slightly changes the results.
• Speed on a small corpus (total time):
  • MGIZA++ on 1 CPU: 14,913 s, the same speed as the original GIZA++.
  • MGIZA++ on 4 CPUs: 6,140 s.
  • PGIZA++ on 4 nodes: 12,963 s. Its Model 1 stage was actually slower than single-thread MGIZA++.
• Agreement with bug-fixed GIZA++ (share of sentences with different Viterbi alignments):
  • Original GIZA++: 10.19%, mostly due to the HMM bug, which arose when the target sentence has one word.
  • MGIZA++: 0.019%.
  • PGIZA++: 1.86%.
  • Score residuals were 0.6503, 0.0017 and 0.0371, respectively.
• Job control: PGIZA++ can launch child processes via ssh, Condor or Maui. Children report completion by creating signal files on a shared network file system.

Interesting ideas

• I1. Parallelize the E-step. Any EM-style learner whose parameters are fixed during the E-step can be split into independent data shards with summed counts. This applies, for example, to training topic models or HMM taggers on large Ukrainian corpora.
• I2. Prune counts before writing them. Dropping low-probability counts before writing them to disk greatly cuts network and disk I/O. The small loss in fidelity may be acceptable, and this trade-off is worth measuring in any distributed counting pipeline.
• I3. Measure fidelity, not just speed. Comparing outputs against a reference implementation by counting changed outputs and computing a normalized score residual is a cheap regression test. It could be reused when refactoring or porting any NLP tool.
• I4. Use shared files as a barrier. Workers creating marker files in a shared folder, watched by a master script, gives scheduler-independent synchronization with no messaging infrastructure. It is handy for simple cluster workflows.
• I5. Choose by corpus size and network speed. Shared-memory threads win on moderate data, while multi-process clusters pay off only at large scale. The authors suggest combining both, along with dynamic assignment of work and binary model formats (about 1/3 the size of text for the TTable).