TL;DR
This paper introduces ACME, a novel approach to combine multiple word alignment systems using Maximum Entropy (ME) models. By treating alignment combination as a link-level classification problem, ACME significantly improves alignment accuracy over individual systems and heuristic methods, leading to better machine translation performance.
What Problem Does This Paper Address?
Word alignment, the task of identifying corresponding words between translated sentences, is a crucial step in statistical machine translation (SMT) and has applications in other NLP tasks like lexicon construction and word sense disambiguation. While several word alignment systems exist, each has its strengths and weaknesses. Combining the outputs of these diverse systems to achieve a more accurate and robust alignment is a significant challenge. Previous attempts at combining alignments often operated at the sentence level or relied on simple intersection/union heuristics, which can be suboptimal. This paper aims to bridge this gap by developing a principled, link-level approach to leverage the complementary strengths of multiple alignment systems.
Methods
The core of ACME lies in its use of Maximum Entropy (ME) models. Instead of directly modeling the alignment probability, ACME frames the problem as deciding whether to include or exclude each potential alignment link. This decision is based on a set of feature functions extracted from:
- Linguistic Features: Part-of-speech (POS) tags of the current and neighboring words in both languages.
- Input Alignments: Whether a specific link exists in any of the input alignment systems.
- Neighboring Links: The presence and count of neighboring alignment links within a local window.
- Fertilities: The number of words a given word is aligned to in the input systems.
- Monotonicity: The absolute difference between the indices of the aligned words.
These features are used to train an ME model that learns the optimal weights (parameters) for each feature. The training process utilizes the YASMET toolkit, an efficient implementation of the Generalized Iterative Scaling (GIS) algorithm. A key aspect of their training strategy is to only consider alignment links that appear in at least one input alignment, mitigating issues with data sparsity and skewed results from including all possible word pairs. They also explore data partitioning based on POS tags to further improve performance.
Datasets
The experiments were conducted on three language pairs:
- English-Chinese (en-ch): 491 sentence pairs from NIST MTEval'02.
- English-Arabic (en-ar): 450 sentence pairs from NIST MTEval'03.
- English-Romanian (en-ro): 248 sentence pairs from the HLT Workshop'03.
For training the input alignment systems (GIZA++ and SAHMM), larger parallel corpora were used:
- English-Chinese: 107K sentence pairs (4.1M/3.3M words).
- English-Arabic: 44K sentence pairs (1.4M/1M words).
- English-Romanian: 48K sentence pairs (1M/1M words).
POS tags were generated using the MXPOST tagger, trained on the Penn Treebank for English and the Chinese Treebank for Chinese.
Key Insights and Ideas
- Link-level combination is powerful: Treating alignment combination as a binary classification problem for each individual link, rather than a global sentence-level decision, allows for more fine-grained and effective integration of evidence from multiple aligners.
- Linguistic features matter: POS tags, especially for the English side, significantly contribute to the accuracy of the combination model. Removing them leads to a noticeable increase in alignment error rate.
- Data partitioning improves robustness: Splitting the training data based on linguistic features (like POS tags) and learning separate models for each partition leads to substantial improvements, suggesting that different linguistic contexts benefit from tailored alignment combination strategies.
- More inputs are generally better: Increasing the number of input alignment systems (from 1 to 2 to 4) consistently reduces the alignment error rate, demonstrating the value of diverse sources of alignment information.
- ACME outperforms heuristics: The ME-based approach consistently achieves lower alignment error rates compared to simple intersection, union, and the grow-diag-final heuristic, especially when using more input alignments.
Key Results
- Significant AER Reduction: ACME[2] (using two input alignments) achieved a relative error reduction of 25.9% over GIZA++(gdf) and 28.0% over SAHMM(gdf) on English-Chinese.
- Partitioning Boost: Using POS tag partitioning, ACME[2] achieved AERs of 19.8% (GIZA++) and 18.0% (SAHMM) on English-Chinese, a significant improvement.
- ACME[4] Excellence: With four input alignments and partitioning, ACME[4] achieved an AER of 15.6% on English-Chinese, representing a substantial gain.
- MT Improvement: ACME-generated alignments led to statistically significant improvements in BLEU scores for a phrase-based MT system (Pharaoh) on both Chinese and Arabic data, with ACME[4] yielding the highest scores. For instance, on Arabic, ACME[4] achieved a BLEU score of 45.54%, a 1.6-1.7% absolute increase over the best heuristic.
- Language Pair Differences: The upper bounds for AER on English-Romanian were higher, indicating that the input alignments for this pair were inherently weaker, which may explain the comparatively lower improvements seen for ACME on this language pair.
Limitations and Future Work
- Supervised Learning: ACME is a supervised learning approach and requires manually aligned data for training. While the paper shows that significant improvements can be achieved with a small set of annotated data, the need for such data is a limitation.
- MT Improvement vs. AER Reduction: The authors note that while AER reductions are substantial, the improvements in MT BLEU scores are relatively smaller. Further research is needed to understand this discrepancy and why huge AER improvements don't always translate into proportionally larger MT gains.
- POS Tagger Dependency: The significant benefits of POS partitioning were observed primarily when using English POS tags. The impact of foreign-language POS tags was less pronounced, suggesting potential limitations in the availability or quality of FL POS taggers.
- Future Work: The paper suggests investigating why large AER improvements lead to smaller MT gains. Additionally, exploring other feature sets and applying ACME to other NLP tasks where word alignment is a component are natural extensions.
Summary updated