Evaluating Word Order Recursively over Permutation-Forests

Milos Stanojevic, Khalil Sima'anSSST @ EMNLP 2014 · DOI

TL;DR

This paper introduces a novel approach to evaluating the word order quality of machine translation (MT) outputs by leveraging hierarchical structures called Permutation Forests (PEFs). By moving beyond flat permutation metrics, PEFs capture long-distance reordering phenomena more effectively, leading to better correlation with human judgments across a wide range of language pairs.

What Problem Does This Paper Address?

Evaluating the quality of word order in machine translation (MT) is a crucial but challenging task. Traditional sentence-level evaluation metrics often rely on n-gram counts, which are sparse and struggle to capture subtle word order nuances. More recent approaches attempt to address this by assigning scores to permutations that represent how words in a system's output are reordered relative to a reference translation. However, these "flat" permutation metrics treat word positions as a linear sequence, failing to account for hierarchical structures or long-distance reordering phenomena. For instance, they might struggle to differentiate between a simple swap of two adjacent words and a complex rearrangement of entire phrases. This paper aims to bridge this gap by proposing a more sophisticated metric that considers the recursive, hierarchical nature of word order.

Methods

The core contribution of this paper is the introduction of Permutation Forests (PEFs) and a scoring mechanism based on them, called PEFscore.

  • Permutation Trees (PETs): The authors build upon the concept of PETs, which are tree-like decompositions of permutations. These trees represent how a permutation can be recursively factored into smaller, adjacent sub-permutations. Each node in a PET represents a block of words, and the structure captures hierarchical groupings.
  • Permutation Forests (PEFs): While PETs select a single "canonical" factorization, PEFs are introduced to compactly represent all possible valid factorizations of a permutation into PETs. This is achieved by packing multiple PETs into a hypergraph structure. The intuition is that different factorizations might correspond to different phrase segmentations, and considering all of them provides a more robust evaluation.
  • PEFscore: This is the proposed evaluation metric. It recursively computes a score by aggregating scores from child nodes and an "operator score" that reflects the reordering at each node. The operator score can be instantiated with existing metrics, but the paper proposes a simple score that rewards monotone (ordered) permutations. The PEFscore interpolates between the operator score and the scores of its children, allowing for a nuanced evaluation that considers both local and global reordering.

Datasets

The experiments were conducted using human rankings of translations from the WMT13 dataset. This dataset covers 10 language pairs and includes system translations, source sentences, and reference translations, with human evaluators ranking the system outputs.

Key Insights and Ideas

  • Hierarchy Matters: The paper strongly suggests that treating word order as a hierarchical, recursive structure (as captured by PETs and PEFs) is more effective than flat permutation metrics. This is because real-world reordering often involves phrases and longer segments, not just individual words.
  • All Factorizations are Better than One: Using Permutation Forests (PEFs), which consider all possible hierarchical factorizations, leads to more stable and often better results than using a single canonical Permutation Tree (PET). This implies that human judgment might not always align with a single "canonical" structural interpretation.
  • Long-Distance Reordering is Key: The PEF-based metrics show a particular advantage in handling long-distance reordering phenomena, which are notoriously difficult for simpler metrics.
  • English-Czech is an Outlier: The English-Czech language pair proved exceptionally difficult to evaluate for all metrics, including the proposed PEFscore. The authors attribute this to potentially lower annotator agreement in the WMT13 data for this pair, rather than an inherent flaw in their metric.

Key Results

  • The PEFscore metric demonstrated better correlation with human rankings than five known reordering metrics on the majority of the 10 language pairs tested on WMT13 data.
  • The PEFscore exhibited more stable performance across language pairs compared to other metrics, meaning its ranking didn't fluctuate as much.
  • While PETs also showed improved performance over flat metrics, PEFs consistently outperformed PETs, highlighting the benefit of considering all possible factorizations.
  • The paper found that distinguishing between inverted and non-binary operators did not significantly improve results, suggesting a simpler scoring for operators might suffice.

Limitations and Future Work

  • English-Czech Anomaly: The consistently poor performance on English-Czech is a notable limitation. The authors suggest that data quality or filtering might be a factor and that more robust data could yield better results.
  • Parameter Tuning: The PEFscore has interpolation parameters ($\alpha$ and $\beta$) that need to be tuned on a development set. While they found good general values, optimal tuning might be language-pair specific.
  • Lexical Component: The paper uses a simple unigram BLEU for the lexical component when combining reordering and lexical scores. The authors acknowledge that more sophisticated lexical scoring (e.g., using recall) could potentially improve overall performance.
  • Future Work: The authors suggest exploring more sophisticated operator scoring functions and investigating the metric's performance on other language pairs or with different MT systems. They also mention the availability of their metric as free software.

Summary updated

BibTeX
@inproceedings{stanojevic2014evaluating,
  author = {Milos Stanojevic and Khalil Sima'an},
  title = {{Evaluating Word Order Recursively over Permutation-Forests}},
  booktitle = {SSST @ EMNLP},
  year = {2014},
  doi = {10.3115/v1/w14-4017},
}
Figure