TL;DR
This paper introduces a novel two-pass decoding strategy for syntax-driven statistical machine translation. It tackles the computational cost of integrating n-gram language models (LMs) into synchronous context-free grammars (SCFGs) by first performing a fast, approximate parse and then using the LM to guide a more detailed search for better translations. This approach achieves comparable search error rates to state-of-the-art methods while offering a more efficient way to leverage powerful LMs.
What Problem Does This Paper Address?
Statistical Machine Translation (SMT) systems often aim to produce fluent and accurate translations by combining linguistic knowledge from grammars with the statistical power of language models. Syntax-driven SMT, using Probabilistic Synchronous Context-Free Grammars (PSCFGs), offers a way to model complex reordering constraints. However, integrating n-gram language models (LMs) directly into the decoding process of PSCFGs is computationally very expensive. This is because it requires an "online intersection" of the grammar and the LM, dramatically increasing the number of possible states (nonterminals) the decoder needs to manage.
Traditional approaches either resort to severe pruning, which can lead to significant search errors, or decode without the LM and then rescore the results, which also suffers from search errors. This paper addresses the challenge of efficiently integrating LMs into PSCFG decoding to reduce search errors without incurring prohibitive computational costs.
Methods
The paper proposes a two-pass decoding approach:
- First Pass: Approximate Parsing: This pass uses a modified CYK-style decoding algorithm. Instead of strictly enforcing LM context matching for chart item recombination (where multiple partial derivations are merged), it relaxes this criterion. Chart items are considered equivalent if they share the same nonterminal and span, even if their LM contexts differ. The LM probabilities are still computed, but only for the "first-best" approximation of the LM context. This significantly speeds up parsing by reducing the number of chart items. The output of this pass is a hypergraph of sentence-spanning derivations.
- Second Pass: Hypergraph Search (H.Search): This pass leverages the hypergraph generated in the first pass. It uses the n-gram LM to guide a heuristic search through this hypergraph, exploring alternative derivations. The core idea is to "unwind" partial derivations from the hypergraph and re-evaluate their scores using the LM. This allows the LM to actively drive the search for better translations, recovering from potential search errors made in the first pass. The algorithm prioritizes exploring partial derivations that are likely to lead to higher-scoring complete translations.
The paper also discusses Cube Pruning (CP) as a state-of-the-art single-pass baseline for comparison. CP is an optimization to the intersected LM parsing that aims to prune away poor-performing consequents early in the process.
Datasets
- Training and Development Data: The IWSLT 2006 Chinese to English translation task dataset, specifically the Full BTEC corpus of travel expressions (120K parallel sentences).
- Test Data: 500 sentences from the IWSLT 2006 test set.
- Grammars: Two grammars were used:
- A syntax-based grammar (3688 nonterminals, 0.3 million rules), derived from CCG categories.
- A purely hierarchical grammar (1 generic nonterminal, 0.05 million rules), similar to Chiang's (2005) work.
- Alignment and Parsing Tools: GIZA++ for initial phrase alignments and the Stanford Parser for syntactic parsing of target training sentences.
Key Insights and Ideas
- The Trade-off Between Speed and Accuracy: Directly integrating LMs into PSCFG decoding is powerful but slow. Severe pruning sacrifices accuracy, while post-hoc rescoring is also suboptimal. The two-pass approach offers a way to balance these.
- Approximate First Pass is Sufficient for Structure: The first pass, by relaxing LM context matching, efficiently builds a rich hypergraph of potential derivations. This structure is crucial for the second pass.
- LM-Driven Second Pass for Error Recovery: The second pass is where the LM truly shines. By using the LM to guide the exploration of the hypergraph, the system can find better translations that might have been missed in the first pass due to pruning.
- "Unwinding" Partial Derivations: The concept of partially unwinding derivations and re-evaluating their LM probabilities is key to the second pass's ability to explore alternatives effectively.
- Syntax-Based Grammars Offer Robustness: The syntax-based grammar yielded more consistent BLEU scores, suggesting that syntactic structure provides a beneficial inductive bias, making the system less sensitive to variations in LM exploration.
Key Results
- The proposed two-pass H.Search approach achieves search errors comparable to the state-of-the-art Cube Pruning (CP) method.
- For the IWSLT hierarchical grammar, both methods achieved a BLEU score of 19.1%.
- For the syntax-based grammar, both methods achieved a BLEU score of 20.7%.
- While H.Search achieved comparable accuracy, it often reached a given model cost "earlier" in terms of novel LM calls compared to CP.
- Decoding time plots showed similar results, with diminished relative improvement for H.Search. Profiling indicated that a significant portion of H.Search's time was spent on memory allocation/deallocation for partial derivations.
- The paper notes that H.Search makes significantly fewer (about half) total LM calls than CP to achieve each model cost.
Limitations and Future Work
- Decoding Time Overhead: While search errors are comparable, the H.Search method incurs overhead in memory allocation and deallocation for partial derivations, impacting decoding speed. The authors expect to reduce this overhead in future work.
- Admissibility of Heuristics: The search beam (Z) in H.Search is not an "admissible heuristic for error-free search." The authors suspect that simple methods to "underestimate" the score of remaining nonterminals in partial derivations could further bridge the gap in search error.
- Future Work:
- Investigate the impact of more powerful models (e.g., higher-order LMs, sentence-level syntactic features) during the search process.
- Address the question of how much search error is tolerable.
- Reduce the overhead associated with memory management for partial derivations.
- Explore methods to improve the admissibility of the search heuristic.
Summary updated