Abstract: Jamie Brunning, Adrià de Gispert, William Byrne. Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics. 2009.
Introduction
In Statistical Machine Translation (SMT), the "alignment" process is critical: it identifies which words in a source sentence correspond to which words in a target sentence. Traditionally, foundational models like IBM Model 1 and Hidden Markov Models (HMMs) have been context-independent. They operate under the simplifying assumption that the probability of a word $f$ translating to word $e$ remains constant, regardless of the surrounding linguistic environment.
Linguistically, this assumption is flawed. A word like "bank" carries vastly different translation probabilities depending on whether its neighbors are "river" and "water" or "investment" and "shares." However, incorporating context into these models traditionally leads to a "combinatorial explosion" of parameters. Attempting to track every possible combination of surrounding words results in severe "data sparsity," where the model lacks sufficient training examples for specific, rare contexts.
Methodology: Decision Tree Clustering
To address the data sparsity problem while capturing contextual nuances, the researchers developed an extension to Model 1 and HMMs that incorporates arbitrary context information, such as Part-of-Speech (POS) tags. They borrowed a technique from Automatic Speech Recognition (ASR)—decision tree clustering—to manage model complexity.
The implementation follows a structured optimization process:
- Contextual Questions: The model evaluates binary questions about a source word's environment (e.g., "Is the preceding word a preposition?" or "Is the following word a noun?").
- EM Optimization: The tree grows by selecting splits that maximize the Expectation-Maximization (EM) auxiliary function, ensuring that splits directly improve the likelihood of the training data.
- Clustering: Contexts resulting in similar translation distributions are grouped into "classes." This allows the model to share data across similar linguistic environments, providing reliable estimates even for rare contexts.
- Thresholding: Two controls, $T_{imp}$ (minimum likelihood improvement) and $T_{occ}$ (minimum occurrences), prevent the tree from over-splitting and overfitting the training data.
Experimental Setup
The models were evaluated on two major language pairs:
- Arabic-English: Trained on ~300k parallel sentence pairs from NIST 08 data, using the MADA toolkit for morphological decomposition.
- Chinese-English: Trained on 600k random parallel sentences from the LDC collection.
Alignment quality was measured using Alignment Error Rate (AER) against a manually-aligned gold standard, while end-to-end translation quality was assessed via BLEU scores.
Key Results and Insights
The researchers found that context-dependent (CD) models consistently outperformed their context-independent (CI) counterparts. Analysis of the decision trees revealed a surprising insight: the POS tags of the previous and next words were often more predictive of a translation than the POS tag of the word itself.
As shown in the performance metrics, the CD approach achieved significant gains:
- Alignment Accuracy: CD models reached lower AER across both Model 1 and HMM architectures. However, as seen in Figure 5, if the improvement threshold is too low, the model can begin to overfit, causing AER to rise in later iterations.
- Translation Quality: These alignment improvements translated to significant BLEU score increases: +0.3 to +0.6 for Arabic-English and +0.5 to +0.8 for Chinese-English.
- Efficiency: The clustering approach allowed for a modest increase in parameters while remaining computationally tractable for large-scale datasets.
Conclusion and Future Work
By applying ASR-inspired decision tree clustering to SMT, the authors successfully mitigated the data sparsity issues inherent in context-dependent modeling. While the study focused on immediate neighbors and POS tags, future work could explore longer-range dependencies or the inclusion of actual word identities. Furthermore, extending these techniques to more complex models like IBM Models 4 or 5 remains a promising avenue for further improving statistical translation systems.
Summary updated