Discriminative Phrase-based Lexicalized Reordering Models using Weighted Reordering Graphs

Wang Ling, João Graça, David Martins de Matos, Isabel Trancoso, Alan W. BlackIjcnlp 2011

TL;DR

This paper introduces a novel approach to improve machine translation by enhancing how word order reordering is handled. They propose "weighted reordering graphs" that assign different importance to phrase pairs based on their alignment quality and proximity, leading to more accurate translation predictions. This method achieves state-of-the-art results on Chinese-English translation tasks.

What Problem Does This Paper Address?

Machine translation (MT) systems, especially phrase-based ones, struggle with reordering words and phrases to match the target language's grammatical structure. Early models penalized words that moved too far from their original positions, which is insufficient for languages with significantly different word orders like Chinese and English. While more advanced models use "reordering graphs" to consider multiple phrase pairs, these graphs treat all phrase relationships equally. This paper addresses the limitation of these existing reordering graph models by introducing a weighting mechanism that discriminates between phrase pairs based on their alignment quality and distance, aiming for more nuanced and accurate reordering predictions.

Methods

The core contribution is the development of weighted reordering graphs. This builds upon existing phrase-based reordering models and reordering graphs.

  • Weighted Alignment Matrices: The paper leverages weighted alignment matrices (introduced in Liu et al., 2009) which provide a probability distribution over possible word alignments, rather than relying on a single "best" alignment. This allows for a more robust estimation of phrase pair quality.
  • Weighted Reordering Graphs: The authors extend the reordering graph concept by introducing weights for both phrase pairs (vertices) and the edges connecting them.
  • Vertex Weights ($W_v(p)$): These weights are derived from the phrase pair scoring algorithm based on weighted alignment matrices. Phrase pairs with higher alignment probabilities and consistency receive higher weights, indicating better quality.
  • Edge Weights ($W_e(e)$): These weights are defined using a distance metric. They penalize edges connecting phrase pairs that are further apart in the target sentence, reflecting that closer phrases are more likely to maintain their relative order. A parameter $\lambda$ controls the penalty for increased distance.
  • Discriminative Estimation: The weighted reordering graph allows for a discriminative estimation of reordering orientations. By weighting paths through the graph, the model can prioritize more probable and higher-quality reordering sequences. The probability of a given orientation $P_c(p, o)$ is calculated by summing weighted path probabilities from a start node to an end node, considering both vertex and edge weights.

Datasets

The experiments were conducted on two parallel corpora:

  • BTEC (French-English): Used for experiments with the French-English language pair.
  • DIALOG (Chinese-English): Used for experiments with the Chinese-English language pair.

Specific subsets and evaluation sets from IWSLT (International Workshop on Spoken Language Translation) were utilized for development and testing, including IWSLT04, IWSLT06, and IWSLT08.

Key Insights and Ideas

  • Quality Matters: Not all phrase alignments are created equal. By weighting phrase pairs based on the quality of their underlying word alignments (from weighted alignment matrices), we can significantly improve reordering estimates.
  • Proximity is Predictive: The distance between phrase pairs in the target sentence is a strong indicator of their reordering likelihood. Penalizing distant connections helps the model focus on more probable reordering patterns.
  • Combining Strengths: The proposed weighted reordering graph effectively combines the benefits of weighted alignment matrices (for phrase quality) and distance-based penalties (for reordering likelihood), leading to superior performance.
  • Beyond Single Alignments: Relying on a single "best" alignment is a bottleneck. Using weighted alignment matrices provides a richer signal for reordering.

Key Results

The paper reports significant improvements in BLEU scores, particularly for the Chinese-English language pair, which is known for its complex reordering challenges.

  • Chinese-English: The proposed weighted reordering graph approach achieved improvements of 0.38 (2%) and 0.94 (3.7%) BLEU points over state-of-the-art methods using weighted alignment matrices on the IWSLT 2010 evaluation dataset.
  • BTEC (French-English): While phrase-based models showed less improvement compared to word-based models on this corpus, the weighted approach still yielded gains, particularly when using weighted phrase extraction.
  • General Trend: Across various configurations and datasets (BTEC, IWSLT06, IWSLT08), the weighted reordering graph models (especially the combined $W_vW_e$) consistently outperformed their unweighted counterparts and simpler reordering models.

Limitations and Future Work

  • Parameter Optimization: The paper mentions that the parameter $\lambda$ for the distance penalty function was set empirically (to 0.5) and suggests that optimizing this parameter is a direction for future work.
  • Corpus Size: The authors note that for smaller training corpora (like the BTEC dataset), phrase-based models might not perform as well, potentially due to a lower probability of finding long matching sequences. They suggest that larger training corpora would likely yield greater improvements.
  • Scorer Combination: Future work includes experimenting with different types of phrase pair and edge scorers, and exploring methods to combine and optimize multiple scorers within the weighted reordering graph framework.
  • Larger Corpora Evaluation: Evaluating the algorithm on larger corpora is planned to better assess its impact and potential for finding longer translation units.
  • Prior Knowledge: The authors suggest incorporating prior knowledge about phrase pair probabilities based on their size could further improve translation quality.

Summary updated

BibTeX
@inproceedings{ling2011discriminative,
  author = {Wang Ling and João Graça and David Martins de Matos and Isabel Trancoso and Alan W. Black},
  title = {{Discriminative Phrase-based Lexicalized Reordering Models using Weighted Reordering Graphs}},
  booktitle = {Ijcnlp},
  year = {2011},
}
Figure