Introduction
Evaluating word order in Machine Translation (MT) remains a significant challenge. Traditional metrics like Kendall’s tau, Spearman’s rho, or Hamming distance treat word reorderings as "flat" sequences. However, human language is inherently hierarchical; a complex-looking reordering might actually be a simple movement of a single syntactic block. This paper introduces Permutation Complexity, a framework that evaluates word order by decomposing permutations into recursive hierarchical structures called Permutation Trees (PETs). By treating reorderings as "blocks" rather than flat sequences, the authors demonstrate that metrics favoring "factorizable" (simpler) reorderings correlate more closely with human judgments.
Methodology: Factorization and Permutation Trees
The core of this approach is the realization that every permutation can be factored into atomic units, similar to how integers are factored into primes.
The Factorization Process
The authors propose a multi-step process to represent permutations hierarchically:
- Factorization: Permutations are broken down into "primal permutations"—irreducible units that cannot be further decomposed.
- Permutation Trees (PETs): A PET represents a permutation as a tree where each internal node is a primal permutation. A permutation that can be broken into many small, simple pieces (like monotone or inverted operations) is considered highly factorizable and thus "simpler."
- Permutation Forests (PEFs): Since some permutations allow multiple hierarchical interpretations, the authors use "forests" to efficiently capture all possible PETs.
Proposed Metrics
The authors define "tight metrics" which assign lower complexity scores to permutations that factorize into shorter, more frequent primal units. Key metrics include:
- $|PET|(\pi)$: The ratio of nodes in a PET; more nodes indicate smaller, simpler building blocks.
- $\#PETs(\pi)$: A measure of "bracketing freedom," or the number of ways a permutation can be represented as a tree.
- $MAX_{|Op|}(\pi)$: The size of the largest irreducible block in the tree.
Experimental Setup and Results
The metrics were evaluated using the WMT13 dataset, which includes human rankings of translation quality across ten language pairs (English to/from Czech, Russian, French, Spanish, and German). This selection covers both rigid and free word-order languages.
Key Findings
The hierarchical metrics, particularly $|PET|$, significantly outperformed traditional statistical baselines like Kendall’s tau in 7 out of 10 language pairs. The improvement was most pronounced in languages with freer word order, such as Russian and Czech, where MT systems often struggle with non-linear reordering.
Insights and Future Directions
The central insight is that simplicity equals human-likeness. A permutation that is easily "compressed" into a small set of simple hierarchical rules is perceived as a more natural translation than one requiring a single, massive, complex rule.
While the current metrics are relatively simple, they lay the groundwork for more sophisticated versions that could weight different types of primal permutations based on their linguistic frequency. Beyond MT, this framework of hierarchical complexity could be applied to fields like bioinformatics for gene sequence matching or general linguistic divergence studies.
Summary updated