TL;DR
This paper introduces an efficient phrase-table representation for statistical machine translation (SMT) that significantly reduces memory requirements and enables real-time translation. By using a prefix tree structure for source phrases and on-demand loading, the system can handle massive phrase tables with minimal memory, leading to improved performance in both online and speech translation scenarios.
What Problem Does This Paper Address?
Statistical Machine Translation (SMT) systems, particularly phrase-based ones, rely on large "phrase tables" that store millions of source-target phrase pairs. These tables are crucial for translation quality but consume enormous amounts of memory, often making them impractical for real-time applications or devices with limited resources. A common workaround is to filter the phrase table for each new text to be translated, but this is a time-consuming process that needs to be repeated for every new input. Furthermore, in speech translation, matching phrases from an Automatic Speech Recognition (ASR) output (which is often a word graph of alternatives) to the phrase table becomes a computationally explosive problem due to the exponential growth of possible phrase combinations.
Methods
The paper proposes a novel phrase-table representation with two key properties:
- Prefix Tree Structure: Instead of a flat list, source phrases are organized into a prefix tree (trie). This structure exploits the redundancy among source phrases, as many share common prefixes. Each node in the tree represents a source phrase, and its children represent extensions of that phrase by one word. This allows for efficient searching of source phrases.
- On-Demand Loading: The entire phrase table is not loaded into memory at once. Instead, only the necessary parts of the prefix tree are loaded as needed for translating a specific sentence. This drastically reduces the memory footprint. The authors also employ a binary format for the phrase table, which acts as a memory map, and load coherent chunks of the tree to minimize disk access.
For speech translation, they introduce a phrase-matching algorithm that leverages the prefix tree structure. This algorithm efficiently finds matches between phrases in the input word graph and the phrase table, effectively solving the combinatorial problem that plagues naive approaches.
Datasets
- Chinese-English NIST Task: Used for evaluating the phrase-table representation. Corpus statistics are provided in Table 1.
- European Parliament Plenary Sessions (EPPS) Task: Used for evaluating the speech translation application. Corpus statistics are provided in Table 4.
Key Insights and Ideas
- Memory Reduction is Dramatic: The proposed representation reduces the phrase-table memory from gigabytes to tens of megabytes, making SMT feasible on resource-constrained devices.
- No Filtering Needed for Online MT: On-demand loading eliminates the need for pre-filtering the phrase table for new texts, enabling true online translation without a preprocessing step.
- Prefix Trees are Key for Speech Translation: The prefix tree structure is instrumental in developing an efficient algorithm to handle the combinatorial explosion of matching phrases in word graphs.
- Trade-off Between Phrase Length and Quality: The paper confirms that translation quality plateaus quickly with increasing source phrase length, suggesting that very long phrases don't necessarily improve performance.
Key Results
- Memory Savings: For the Chinese-English NIST task, the phrase-table memory was reduced to less than 20 MB, a reduction of about two orders of magnitude compared to storing the entire table (approx. 1.7 GB).
- Translation Quality: The new representation achieved no loss in translation quality compared to traditional methods.
- Speech Translation Efficiency: The phrase-matching algorithm effectively handles confusion networks (CNs), enabling the use of larger CNs and leading to improved translation quality. For the EPPS task, using full CNs resulted in a BLEU score of 38.9, compared to 37.6 for single-best input, with a manageable increase in decoding time (3.4x for full CNs vs. single-best).
- Speed: The on-demand loading approach was found to be no slower than traditional methods, attributed to the binary format and chunked loading.
Limitations and Future Work
- Lexicalized Distortion Models: The authors note that their assumption of source-phrase independence from context might be violated by lexicalized distortion models. In such cases, storing source phrases and probabilities alongside target phrases would be necessary.
- Language Model Memory: The paper suggests that similar techniques might be applicable to reducing the memory requirements of language models, which also pose a significant memory challenge.
- Finite-State Toolkit Integration: The authors propose that efficient on-demand loading for finite-state toolkits could enable the application of finite-state operations to large data tasks.
- Sorting Input Graph Edges: While the current algorithm is efficient, further optimization by sorting input graph edges during initialization is suggested as a potential area for future work.
Summary updated