Hierarchical Permutation Complexity for Word Order Evaluation

Proceedings of COLING 2016, the 26th International Conference on Computational Linguistics: Technical Papers, pages 2164–2173, Osaka, Japan, December 11-17 2016. Hierarchical Permutation Complexity for Word Order Evaluation Miloˇs Stanojevi´c Khalil Sima’an Institute for Logic, Language and Computation (ILLC) University of Amsterdam {initial.last}@uva.nl Abstract Existing approaches for evaluating word order in machine translation work with metrics com- puted directly over a permutation of word positions in system output relative to a reference translation. However, every permutation factorizes into a permutation tree (PET) built of pri- mal permutations, i.e., atomic units that do not factorize any further. In this paper we explore the idea that permutations factorizing into (on average) shorter primal permutations should rep- resent simpler ordering as well. Consequently, we contribute Permutation Complexity, a class of metrics over PETs and their extension to forests, and define tight metrics, a sub-class of metrics implementing this idea. Subsequently we define example tight metrics and empirically test them in word order evaluation. Experiments on the WMT13 data sets for ten language pairs show that a tight metric is more often than not better than the baselines. 1 Introduction MT evaluation involves at least two factors, word order (syntactic) and adequacy (semantic). Conceiv- ably, MT system developers could use diagnostic tools based on metrics dedicated to each factor sepa- rately. Word order metrics are frequently used to evaluate pre-ordering components, e.g., (Herrmann et al., 2011; Bisazza and Federico, 2013), or for analyzing specific reordering phenomena, e.g., (Bisazza and Federico, 2013; Xiang et al., 2011; Braune et al., 2012). Other uses include, ordering component tuning, e.g., (Gao et al., 2011; Neubig et al., 2012; DeNero and Uszkoreit, 2011; Katz-Brown et al., 2011; Hall et al., 2011), measuring divergence between languages (Birch et al., 2008), and matching gene sequences in bioinformatics (Eres et al., 2004). For evaluating word order, a permutation is induced between a system output and the corresponding reference translation. Existing work uses metrics over permutations such as Kendall’s tau (Lapata, 2006; Birch and Osborne, 2011), Spearman (Isozaki et al., 2010), Hamming, Ulam (Birch et al., 2010) and Fuzzy Score (Talbot et al., 2011). Approximately, Kendall’s tau, Spearman and Hamming measure correct individual position or correct relative pairs, whereas Ulam and Fuzzy Score measure monotone units (contiguous or not). A word order metric measures how similar a permutation is to the monotone (or identity) permutation. Here we advocate the idea that a suitable metric must also assign similar values to similar permutations. Crucially, factorizing a permutation into a Permutation Tree (PET) reveals its atomic building blocks, called primal permutations (Albert and Atkinson, 2005; Gildea et al., 2006). In this view, permutations that factorize into similar PETs should be similar. Some previous work (Stanojevi´c and Sima’an, 2014a; Stanojevi´c and Sima’an, 2014b) has used PETs for evaluation, but without attempting to explain the effect of factorization. Next we motivate the idea that, all other things being equal, the more factorizable a permutation the simpler it is in terms of ordering. Informally, a PET for permutation π …

Content truncated to 500 words