On the Evaluation of Machine Translation n-best Lists (2020)

Abstract: The standard machine translation evaluation framework measures the single-best output of machine translation systems. There are, however, many situations where n-best lists are needed, yet there is no established way of evaluating them. This paper establishes a framework for addressing n-best evaluation by outlining three different questions one could consider when determining how one would define a ‘good’ n-best list and proposing evaluation measures for each question. The first and principal contribution is an evaluation measure that characterizes the translation quality of an entire n-best list by asking whether many of the valid translations are placed near the top of the list. The second is a measure that uses gold translations with preference annotations to ask to what degree systems can produce ranked lists in preference order. The third is a measure that rewards partial matches, evaluating the closeness of the many items in an n-best list to a set of many valid references. These three perspectives make clear that having access to many references can be useful when n-best evaluation is the goal.

## introduction machine translation evaluation has traditionally focused on one-best translation results because many common use cases (translating a user manual, reading a news article, etc.) require only a single translation. there are, however, many scenarios in which n-best translation can be useful; examples include cross-language information retrieval, where query terms may not match in the single-best output, or language learning, where a learner is interested in whether their translation is acceptable. optimizing translation systems for such applications might benefit from evaluation measures that focus on choosing among systems based on which produces the best list of translated sentences, what we refer to here for brevity as an n-best list. often in these n-best scenarios, researchers first select 'good' mt systems (i.e., by bleu) in the hope that these good systems will also produce good results beyond the top translation candidate. in this paper we test that hypothesis, using a newly available dataset to measure the quality of n-best lists directly. to look at the problem in this way we must first decide what properties of an n-best list we would consider 'good'. in this paper we explore three questions: we introduce measures for each of the three questions, using a ranking quality measure already widely used in information retrieval for question 1, correlation measures to address question 2, and variants of bleu for question 3. in this latter study, we particularly note that n-best evaluation done in this way contrasts with a current standard used for both n-best and 1-best mt evaluation, 1-best single-reference bleu. however, our purpose is not to argue for a single n-best evaluation measure, but rather to highlight that different measures produce different system rankings, and therefore it is crucial that researchers carefully consider what questions to ask when evaluating systems. the measures we propose are illustrative as answers to our research questions, but are not the only solutions; many others might work. we aim to provide groundwork and encourage future work on the topic. our investigation is made possible by the recent availability of annotations created for the duolingo simultaneous translation and paraphrase for language education (staple) shared task, which contains an extensive (although not necessarily exhaustive) set of valid translations for each of several thousand "input prompt" sentences @xcite . ## the staple shared task the duolingo staple dataset consists of thousands of english prompts, with large sets of valid translations of each, often numbering in the hundreds, each labeled with the relative frequency with which each valid translation was selected by language learners. in the 2020 staple task, participating systems were asked to produce all and only the valid translations. doing well at this task, which was evaluated using a variant of the f 1 measure, requires both ranking translations well and deciding where to truncate the n-best list (i.e., the choice of n). our focus in this paper is on ranking quality, leaving the question of how best to evaluate truncation to other work. we compare systems from @xcite 's submission to the 2020 duolingo sta-ple shared task. they were built using the data described in all were variations of the following standard training procedure. we used transformer architectures @xcite trained with fairseq @xcite . models included 6 encoder and decoder layers, a model size of 512, a feed forward layer size of 2048, and 8 attention heads. models were trained with the adam optimizer (kingma and ba, 2015) with a dropout size of 0.1 and an effective batch size of 200k tokens. model training was terminated when validation perplexity failed to increase for 10 consecutive epoch-level checkpoints. our systems varied in the following experimental parameters: ## head-weighted precision we begin with our first question: how well does a system produce valid translations and rank them above invalid translations? a task that might be more aligned with such a question would be one that necessitates a strict, binary score for validity and is agnostic to where a truncation of the list might occur. for example, a language learner hoping to learn several valid possible ways to express a sentence in a target language may want to peruse many translation outputs, starting at the top of the list. it would be unknown where the user would stop, and it would be important that the translations are fully valid. of course the space of valid translations in this framework could be enormous, so it is important to consider the effect of incompleteness in the set of valid references. we consider that in section 3.2, but first we introduce a measure for head-weighted precision with a simplifying assumption that the set of valid references is complete. assuming we have this, we say for the purpose of question 1 that a good n-best list would have a lot of valid translations, and that it would place them near the head (i.e., the top) of the ranked list. we refer to this framework then as head-weighted precision. ## preference correlation our second question for n-best evaluation is how well models can rank translations in preference order. since we have model scores from the trans-2 spearman's ρ = 0.956. lation model and relative prevalence from the sta-ple dataset, one type of easily computed measure of quality for the model scores would be their degree of correlation with the staple score for each translation (which indicates which of the translations are more commonly used; i.e., their relative prevalence). one interesting aspect of this type of measure is that it relies on having frequency (or some other preference score) annotation information for each reference translation. certain tasks may be better imagined to take advantage of such data. for example, a task in which models need to generate diverse translations may want to sample from valid outputs in a way that more closely reflects natural human variance. that is, it should sample a frequent translation more often than an infrequent one. correlating a model's scores for translations with gold frequency scores may then be useful for such a case. we consider how these preference correlation scores could be used for system rankings. we calculate both spearman's ρ and pearson's r on all of our models in japanese and portuguese. 3 we then construct a scatterplot of the preference correlation and map scores for each system, as shown in figure 3 . from the near-zero slope of a linear fit and the near-zero r 2 values, it is clear that both spearman's ρ and pearson's r are measuring something very different from map. that is not to say that they are not good measures; rather, it says that they are measuring something different. map measures how reliably systems can place valid translations early in a ranked list; correlation to the gold standard preference order measures how reliably systems can place preferred translations ahead of less preferred translations. both of these measures have additional limitations, which discourage their usage. first is the requirement for more nuanced gold data. while map only requires access to several valid translations, these measures require either a preference order or preference scores for those translations, which may be difficult to obtain. a second limitation is the handling of missing data. both measures compare scores or rankings of translations between two sets. if the intersection between these two sets is very small, it limits the usefulness of the measures. though we have many frequency scores and relative rankings in the gold translations, if the nbest lists we use to compare do not contain many of those translations, the measures could be less reliable. ## unweighted partial match finally, our third question is how close the translations are to the reference translations. a task that may benefit from such a measure would be cross-language information retrieval (clir). in such a task, the machine translation sys-tem would serve as an upstream component of the pipeline. it is less likely for translations to need to be fully valid to be useful as compared to some other mt tasks. clir could benefit from combining the terms from several translation outputs regardless of if each entire sentence is perfectly valid. in this way, a measure that can assign partial credit to translations by matching n-grams as well as weighting all translations equally may be appropriate. for this, we turn to bleu @xcite , which computes n-gram overlap between a system's translations and the available references. this raises the question of how many references we should use when we have very many available, and which of the system translations we should be using in this computation. the staple dataset provides an opportunity to explore this question. in this section, we compute bleu measures with different numbers of references, to different depths in the n-best list. we find that at deep depths with many references bleu ranks systems similarly to map, but that with fewer references its behavior is quite different. in order to set up various configurations for our n-best bleu measures, we perform a grid search over {1,5,10,100,1000}-best {1,5,10,100,all 4 }reference bleu. in what we call x-best y-reference bleu, x refers to how many top hypotheses from the system output are used, and y refers to how many references are used. when working with multiple hypotheses in an n-best list, we simply treat them as independent translations in a larger pseudo-corpus, pairing each with the relevant reference(s) for evaluation with bleu. after obtaining system scores under each of the bleu configurations, we calculate the spearman's ρ and pearson rank correlation coefficients between system rankings from bleu compared to those from map. we find similar patterns for both languages and both correlation metrics, so we show spearman's correlation for japanese in figure 4 . an important observation is our finding that 1best, 1-reference bleu does not correlate well with map. from this we conclude that when placing many valid translations near the top of the n-best list is important, as is the case in some applications, optimizing for 1-best 1-reference bleu may be suboptimal. this situation is not improved by adding hypotheses to the pseudo-corpus, so long as only a single reference is used. however, increasing the number of references does bring the correlation to moderate strength even when still only evaluating at 1-best. once the evaluation has access to several references, evaluating deeper in the n-best list further improves the correlation with map, and correlations at moderately deep depths are quite substantial (e.g., ρ = 0.86 for 100-best 100-reference). in figure 5 , we zoom in on two of these bleu configurations. we choose 1-best 1-reference, which represents a standard bleu evaluation framework, and also 100-best 100-reference, since it showed nearly the highest correlation with map (increasing the depth to 1000 and the references to 1000 yields only slightly stronger correlation). as the slope and r 2 of the linear fit indicate, 1-best 1-reference bleu has little value for predicting map, whereas 100-best 100-reference bleu has substantial preditive power. moreover, this relationship is strongest for higher values of map; this is important, because when seeking to choose the best system for some task, a system builder would choose from among the best-performing ones. to help explain this difference, we also performed a qualitative analysis. this revealed that systems with high 1-best 1-reference bleu scores but low map produced valid translations at the top of the n-best list, but very poor translations (e.g., latin characters in japanese) deeper in the list. systems with both higher map and 100-best 100-reference bleu scores were better at producing reasonable sentences throughout the entire list. this makes sense as a system with a great translation at rank 1 but terrible translations between ranks 2 and 100, for example, will have a great 1best 1-reference bleu but will be heavily punished by map. ## discussion access to frequency scores in staple's gold data has provided a unique chance to use correlation between those scores and model scores as a way to evaluate systems. however, we see that these measures behave quite differently from map, and thus we would recommend use of preference correlation ( §4) only in cases in which fine-grained distinctions between preference scores are important for the intended application. we also looked into using bleu for n-best evaluation. map and bleu seem like quite different ways of evaluating in terms of how they approach the problem. map relies on binary scores, gives no partial credit, and weighs translations at the top of the list higher. bleu on the other hand looks at closeness, allowing for partial credit, and treats all sentences equally, no matter where they appear in the n-best list. it could be expected then that these measures would differ, as we see when comparing map to 1-best 1-reference bleu. however, as we increase depth and number of references for bleu, the correlation of the resulting system rankings increases substantially and ultimately they yield quite similar system rankings. from this we can conclude that, at least for the systems we have experimented with, and for the language learning task that the staple dataset models, systems that find many good translations also tend to rank those translations well. thus, with enough references the choice between map and bleu might be made based on efficiency. we suspect that the ability of many-best many-reference to work with partial matches might give it advantages over map when the number of available references is more limited than in staple, but we leave ablation studies to test that hypothesis to future work. of course, the requirement for large numbers of references, which are generally expensive to obtain, is a limitation. however, this is a separate consideration; in the duolingo dataset that was the center of our study, they were produced organically within that task; in other settings, if evaluation of n-best lists were to be important enough, the requisite investments to create the required resources could in some cases be made. in such a setting, techniques such as crowdsourcing or monolingual paraphrase generation might possibly be leveraged to reduce costs. moreover, our ablation study indicates that the ground truth need not be completely comprehensive to be useful. a second limitation is that our experiments were conducted on the relatively simple sentences used for the duolingo staple shared task. as with any study, it remains to be seen how well it generalizes to other settings, including other datasets. but this does not detract from our findings on the staple dataset, which was after all motivated by a real language learning task that benefits large number of of people. perhaps our most salient general observation is that it seems that having access to more references and evaluating deeper in the list makes for better evaluation of n-best lists. of course, this benefit must be balanced against the cost of generating the requisite number of references. ## conclusion we have shown how different metrics can be used to characterize n-best list quality. in particular, we have introduced map as a measure for n-best list quality for machine translation systems. map rewards systems that place good translations near the top of the list. bleu, computed over a pseudocorpus built from n-best lists, and against large reference sets, ranks systems similarly to map. in both cases, the key distinguishing feature from typical mt system evaluation is the use of large reference sets, which yields insights unavailable with shallower evaluations using only a single reference. map is but one measure among many that have been used to characterize the quality of ranked lists in other settings. as future work, we would be interested in exploring the use of measures such as inferred average precision (infap) that are designed to be particularly robust to missing data in the gold standard @xcite , and measures such as normalized discounted cumulative gain (ndcg) @xcite that represent multiple degrees of utility (thus requiring more nuanced ground truth, as what we have in staple).