TL;DR
This paper tackles the challenge of efficiently storing and retrieving translation rules for hierarchical phrase-based machine translation (HPBMT) systems, which are significantly larger than traditional phrase-based systems. The authors introduce novel lookup algorithms that leverage suffix arrays and prefix trees, drastically reducing the time required to find relevant rules on-the-fly, making HPBMT more practical.
What Problem Does This Paper Address?
Statistical machine translation (SMT) systems rely on vast "rule sets" extracted from parallel text data. For standard phrase-based models, efficient storage and retrieval of these rules is crucial, and suffix arrays have emerged as a promising solution for fast lookups. However, hierarchical phrase-based translation (HPBMT) introduces a new complexity: rules can involve "gaps" (discontiguous phrases). This makes traditional suffix array lookup algorithms, designed for contiguous substrings, insufficient. Existing methods for handling these gaps are either too slow (taking minutes per sentence) or require significant tradeoffs, rendering them impractical for large-scale use. The core problem is finding an efficient way to query these larger, more complex HPBMT rule sets in real-time during the translation process.
Methods
The paper builds upon the idea of using suffix arrays to store the entire training data in memory for fast rule lookups. For contiguous phrases, standard suffix array binary search is efficient. The main innovation lies in addressing the "collocation problem" for discontiguous phrases (those with gaps).
The authors propose a series of algorithms:
- Baseline Approach: They first analyze the problem of finding discontiguous patterns (e.g.,
aXbXc) using suffix arrays. This involves adapting approximate pattern matching algorithms, but they find existing ones too slow. - Hashing with Sentence IDs: To improve efficiency, they use the sentence ID of subpattern occurrences as a hash key. This groups potential collocations within the same sentence, reducing the search space.
- Prefix Trees with Suffix Links: A key data structure is a prefix tree augmented with suffix links. This tree efficiently represents patterns and their relationships, allowing for faster traversal and identification of potential rule matches. It also serves as a cache for successful lookups.
- Optimized Collocation Algorithms: They introduce several strategies for combining frequent and rare patterns:
- Precomputation: For the most frequent patterns, collocations are precomputed at decoder startup.
- Double Binary Search: For frequent and rare pattern pairs, a "double binary search" algorithm efficiently finds intersections of sorted sets.
- Merge Algorithm: For pairs of rare patterns, a simpler merge algorithm is used.
- Efficient Enumeration: They also propose methods to intelligently enumerate phrases to look up, avoiding redundant computations and enabling caching strategies.
Datasets
The experiments were conducted on a large Chinese-English parallel corpus from news domains, consisting of over 1 million sentences. This corpus is described as being similar in scale to those used in previous large-scale HPBMT experiments. Alignments were generated using GIZA++ and symmetrized with the grow-diag-final heuristic. The test set used for timing measurements was the first 50 sentences of the NIST Chinese-English 2003 test set.
Key Insights and Ideas
- HPBMT rule sets are orders of magnitude larger: The hierarchical nature of HPBMT rules (allowing gaps) leads to a significantly larger rule set compared to standard phrase-based models, making efficient indexing paramount.
- Contiguous vs. Discontiguous lookup is fundamentally different: Standard suffix array binary search works well for contiguous substrings but fails for discontiguous ones, requiring entirely new algorithmic approaches.
- Frequent patterns are the bottleneck: The most expensive computations for finding collocations involve one or more very frequent subpatterns. This Zipfian distribution of pattern frequencies allows for targeted optimization.
- Prefix trees are powerful for representing hierarchical patterns: The prefix tree structure, combined with suffix links, provides an effective way to manage and search for complex, gapped patterns and cache results.
- A multi-pronged approach is necessary: No single algorithm suffices. The authors combine precomputation, specialized search algorithms (double binary search, merge), and efficient data structures (prefix trees) to achieve significant speedups.
Key Results
The paper demonstrates a dramatic reduction in computation time for hierarchical phrase lookup.
- Speedup: The proposed algorithms reduce the empirical computation time by nearly two orders of magnitude. The baseline algorithm took an average of 2241.25 seconds (about 37 minutes) per sentence for collocations, while the optimized system with full caching achieved 30.70 seconds per sentence.
- Feasibility: This speedup makes on-the-fly lookup for hierarchical phrase-based translation feasible, a significant improvement over previous methods.
- Memory Usage: The memory requirements for the system, including precomputed collocations, are estimated to be around 2GB for a large corpus and trigram model.
Limitations and Future Work
- Current speed is still relatively slow: While significantly improved, the optimized system's per-sentence processing time (around 30 seconds) is still slower than the decoding time (around 10 seconds).
- Python implementation overhead: The authors note that their implementation is in Python, an interpreted language, and a more efficient C implementation could yield further speedups.
- Startup time: Loading data structures into memory at startup can take several minutes, though this can be amortized over many sentences or potentially addressed with memory-mapped files.
- Future Applications: The authors suggest that these techniques could be applied to other areas requiring approximate pattern matching, such as bioinformatics. They also envision a future where machine translation is treated more like searching in a protein database, using training sentences as a form of indirect feature representation for discriminative learning.
Summary updated