TL;DR
This paper introduces a novel algorithmic framework for the decoding problem in Statistical Machine Translation (SMT). By decomposing the computationally hard decoding problem into two simpler, alternating subproblems, the authors develop efficient algorithms that can find high-quality translations significantly faster than previous methods.
What Problem Does This Paper Address?
Statistical Machine Translation (SMT) systems aim to find the most probable translation of a source sentence into a target language. This process involves three core components: the translation model, the language model, and the decoding problem. The decoding problem, in particular, is a computationally intensive combinatorial optimization task. Given a source sentence and the translation and language models, the goal is to find the target sentence that maximizes the joint probability. This problem is known to be NP-hard, meaning that finding an exact solution in polynomial time is highly unlikely. Consequently, much research has focused on developing efficient algorithms to find good suboptimal solutions. Existing approaches, like stack-based search and dynamic programming adaptations of algorithms like Held-Karp for the Traveling Salesman Problem, have faced significant computational challenges, especially for longer sentences. This paper addresses the need for faster and more practical decoding algorithms that can still produce high-quality translations.
Methods
The core contribution of this paper is a new algorithmic framework for decoding. The key idea is to model the decoding problem as an alternating search problem. This means breaking down the complex problem into two simpler, alternating subproblems:
- Fixed Alignment Decoding: Given a fixed alignment between source words and target positions, and a fixed target sentence length, find the best possible target sentence. The authors show this subproblem can be solved efficiently using dynamic programming in linear time (O(m), where m is the source sentence length) for IBM models.
- Viterbi Alignment: Given a source sentence and a candidate target sentence, find the best possible alignment between them. This is also shown to be solvable efficiently.
By iteratively alternating between solving these two subproblems, the framework refines both the alignment and the translation. The paper presents several algorithms derived from this framework:
- NaiveDecode: A simple, linear-time algorithm that solves the Fixed Alignment Decoding subproblem. It can be used to find suboptimal solutions quickly.
- NaiveOptimalDecode: An exponential-time algorithm that explores many possible alignments and target lengths, guaranteeing an optimal solution for the relaxed decoding problem but is computationally prohibitive.
- AlternatingSearch: A practical algorithm that leverages the alternating maximization paradigm. It iterates between NaiveDecode and Viterbi alignment, exploring a range of target sentence lengths. This algorithm achieves a complexity of O(m²) and is designed to balance speed and translation quality.
- A Linear Time Algorithm for FIXED ALIGNMENT DECODING: This section details the dynamic programming approach for the first subproblem, providing a crucial building block for the framework.
Datasets
The paper describes experiments conducted using:
- French-English translation model: Trained on the Hansard corpus (100K sentence pairs).
- English language model: Trained on approximately 800 million words.
- Test sentences: Divided into length classes (0-10, 11-20, 21-30, 31-40, 41-50, 51+ words). Each class contained 300 test French sentences.
The paper does not introduce new datasets but uses standard corpora for training and evaluation.
Key Insights and Ideas
- Decomposition is Key: The most significant insight is that the NP-hard decoding problem can be effectively tackled by breaking it into two simpler, complementary subproblems that can be solved efficiently.
- Alternating Maximization Power: Iteratively improving the translation given an alignment, and then improving the alignment given the translation, leads to a powerful search paradigm that converges to good solutions.
- Practicality of Suboptimal Solutions: The framework demonstrates that even linear-time algorithms (like NaiveDecode) can provide useful suboptimal solutions, and more complex algorithms derived from the framework can achieve near-optimal quality with significantly reduced computation.
- Flexibility in Target Length: Explicitly considering a range of target sentence lengths (e.g., m/2 to 2m) is crucial for finding better translations, as the optimal translation length may differ from the source sentence length.
Key Results
- Speed: The proposed algorithms are significantly faster than previous methods, including the Held-Karp adaptation. They can translate long sentences (50+ words) in a few seconds on standard hardware. Plot 1 shows algorithms based on the framework are an order of magnitude faster than the Held-Karp algorithm.
- Quality (Log Score): The log scores (optimization function values) achieved by the framework's algorithms are very close to those of the Held-Karp algorithm (Plot 3), indicating that they find solutions with high probability according to the models.
- Quality (NIST Score): While the log scores are comparable, the NIST scores (a measure of translation quality) for the framework's algorithms are slightly lower than the Held-Karp algorithm, though Algorithm 2.2 (AlternatingSearch) performs best among the proposed methods (Plot 2). This highlights a trade-off between speed and NIST score, with the framework prioritizing speed while maintaining good probabilistic scores.
Limitations and Future Work
- Complexity of AlternatingSearch: The paper notes that the complexity of AlternatingSearch is O(m²), and poses the question of whether it can be reduced to O(m).
- Exploring Alignments: The paper also asks if it's possible to explore "a bunch of alignments in one shot" rather than individually, which could lead to even faster algorithms.
- NIST Score vs. Log Score: While the algorithms optimize the log score, the NIST scores are slightly lower than the optimal Held-Karp approach. Future work could focus on bridging this gap.
- Parameter Tuning: The authors aimed for algorithms that give satisfactory results with minimal parameter tuning, and their experiments suggest this is achievable. However, further exploration of parameter sensitivity might be beneficial.
Summary updated