BLEU Neighbors: A Reference-less Approach to Automatic Evaluation (2020)

Abstract: Evaluation is a bottleneck in the development of natural language generation (NLG) models. Automatic metrics such as BLEU rely on references, but for tasks such as open-ended generation, there are no references to draw upon. Although language diversity can be estimated using statistical measures such as perplexity, measuring language quality requires human evaluation. However, because human evaluation at scale is slow and expensive, it is used sparingly; it cannot be used to rapidly iterate on NLG models, in the way BLEU is used for machine translation. To this end, we propose BLEU Neighbors, a nearest neighbors model for estimating language quality by using the BLEU score as a kernel function. On existing datasets for chitchat dialogue and open-ended sentence generation, we find that – on average – the quality estimation from a BLEU Neighbors model has a lower mean squared error and higher Spearman correlation with the ground truth than individual human annotators. Despite its simplicity, BLEU Neighbors even outperforms state-of-the-art models on automatically grading essays, including models that have access to a gold-standard reference essay.

## introduction despite recent advances on many natural language generation (nlg) tasks -including open-ended generation, chitchat dialogue, and abstractive summarization -evaluation remains a challenge. automatic metrics such as bleu rely on references, but for many nlg tasks, there is no single correct answer. in dialogue, the space of acceptable responses to a given prompt is often very large, yet most datasets only provide a few gold-standard references @xcite . in open-ended generation, where text is generated freely by a language model, there are no references at all; statistical measures such as perplexity capture language diversity but not language quality @xcite . these limitations necessitate human evaluation. however, because human evaluation at scale is slow and expensive, it is used sparingly; it cannot be used to rapidly iterate on nlg models, in the way bleu is used for machine translation. prior work on automating reference-less evaluation has largely been limited in scope. heuristicbased evaluation was found to be effective for grammatical error correction, but the methods used were problem-specific and cannot be extended to other tasks @xcite @xcite . using the log-odds from a language model, @xcite made automatic judgments of sentence-level fluency that correlated moderately well with human judgment, but this captured only one facet of language quality. approaches that were broader in scope found less success: although adem, an rnn trained to score dialogue responses, was initially thought to correlate well with human judgment @xcite , it was later found to generalize poorly, placing outsized influence on factors such as response length @xcite . can we come up with a fast and simple method for reference-less evaluation of language quality, analogous to bleu for machine translation? note that our goal here is not to supplant human evaluation, but to complement it: as long as the method's predictions correlate moderately well with the ground-truth quality scores, it can be used to speed up nlg model development. our desiderata are then as follows: simplicity, speed, and a moderately strong correlation with the ground truth. to this end, we propose bleu neighbors, a new approach to reference-less automatic evaluation. our approach is a nearest neighbors model that predicts language quality by using bleu as a kernel function. we start with training examples s, where each sentence @xmath0. note that these examples are not references -we do not expect the nlg model being evaluated to generate any sentence in s. in fact, s contains sentences of varying quality, including incoherent sentences with low quality scores. given a test sentence x, we use the bleu score to identify its neighbors in the training data: {s | bleu * (x, s) > τ, @xmath1, where τ is a similarity threshold. then we simply take the mean of the neighbors' known quality scores to estimate q(x), the quality of x. consider the test sentence @xmath2. as seen in figure 1 , it overlaps with s 1 = 'the dog was quick.' and s 2 = 'it is the fox.' but not with s 3 = 'dogs are lazy.'. therefore, we estimate q(x) as the mean of q(s 1 ) and q(s 2 ) but not q(s 3 ). we test bleu neighbors on the datasets from huse @xcite , where each sentence's ground-truth quality score is the average over 20 human judgments. on the dialogue and open-ended generation datasets, we find that -on average -the bleu neighbors model has a lower mean squared error (mse) and higher spearman correlation with the ground truth than individual annotators. the premise of our method is that past approaches to reference-less evaluation fell short because they were too ambitious -if a given test sentence is not sufficiently similar to any training example, no prediction should be made at all. although we sacrifice some coverage in or-der to make more accurate estimates, this sacrifice is modest: bleu neighbors makes predictions for 41% to 99% of sentences from the huse datasets. our method is also data-efficient -none of huse datasets have over 400 training examples. our method is weakest on evaluating summaries; this is unsurprising, given that summary quality is conditioned on the source text, which the method ignores. in contrast, bleu neighbors is surprisingly effective at automatically grading essays, achieving a new state-of-the-art and even beating out models that have access to a gold-standard reference essay. these findings suggest that despite its simplicity, our approach has broad applicability. although bleu neighbors does not measure language diversity, it is sufficient for it to measure quality alone. the former is easier to estimate (e.g., perplexity) and can be combined with the bleu neighbors score in a hybrid metric @xcite . we conclude by providing some practical advice, such as how to prevent nlg models from explicitly optimizing for a high bleu neighbors score without generating high-quality output. ## bleu neighbors given a candidate sentence x, training examples s, and ground-truth quality scores {q(s) | @xmath3, we want to estimate q(x), the language quality of x. how can we do so in a fast and simple manner such that our predictions correlate well with the ground truth? we propose a nearest neighbors model that uses a variant of the bleu score called bleu * as the kernel function. once the neighbors of x have been identified, we take the mean of their known quality scores as q(x). definition 3.1. the non-unigram bleu-4 score is a variant of the bleu-4 score that ignores unigram precision. where definition 3.2. given a candidate sentence x, training examples s, and a similarity threshold τ ∈ [0, 1] , the bleu neighbors of x are to ensure that the quality estimate is stable, we require that n have a minimum size of @xmath4. conversely, a candidate sentence that overlaps with many training examples in s likely does so because it contains many common n-grams. this complicates evaluation: since bleu * does not weigh ngrams by their frequency, an abundance of common n-grams -such as "on the" or "it is", for examplecan exaggerate the similarity between the candidate and a training example. in this scenario, it is best that no prediction be made at all. since n ⊆ s, let @xmath5, 1] denote the largest fraction of s that n can contain. we express b as a fraction of the training set size |s| because if s is very large, it would not be uncommon for even sentences with rare n-grams to have matches in s. when n meets the aforementioned size constraints, the bleu neighbors estimate of x's quality is the average of its neighbors' quality scores: in other words, n ⊆ s comprises all the training examples that are sufficiently similar to the candidate with respect to bleu * . if there are fewer than a examples or more than b|s| examples in n , then no prediction is made; otherwise, the estimate q(x) is the average quality of the examples in n . although τ, a, b are parameters to be set, we find that τ = 0.08, @xmath6, @xmath7.66 are near-optimal for all tasks (see section 5.2). this universality allows bleu neighbors to be used out-of-the-box, without hyperparameter tuning. note that s should only be used to train the evaluator (i.e., bleu neighbors). the generator (i.e., the nlg model being evaluated) should not have access to s; otherwise, it could optimize for a high bleu neighbors score by including n-grams that only belong to examples with a high ground-truth quality, thus artificially inflating the quality estimates. definition 3.3. given a set of candidates x to be evaluated, the coverage of x is the proportion of candidates for which q(x) is defined. this is a key distinction between bleu neighbors and prior approaches to reference-less evaluation: our approach does not necessarily make a prediction for all candidates. this is by design -as mentioned earlier, we surmise that past approaches fell short because they were too ambitious, trying to score sentences that simply could not be scored. there is a trade-off between coverage and prediction error, with greater coverage generally coming at the cost of greater prediction error. each dataset contains a mixture of machine-and human-generated sentences, in roughly equal proportion. each sentence in the huse datasets was judged by 20 human annotators, who assigned it a label based on its typicality. these labels map to an integer score from 0 to 5. we divide the raw judgment by 5 to bound it in [0, 1] and then take the mean across all 20 annotators, which we treat as the ground-truth language quality q(s) for each sentence s. because these datasets are small, we use leave-one-out prediction. that is, given a candidate sentence from a particular huse dataset, we treat the remaining n -1 sentences as s. ## conclusion the absence of a reference-less evaluation metric for language quality has been an impediment to developing nlg models. to address this problem, we proposed bleu neighbors, a nearest neighbors model that leverages the bleu score as a kernel function in sentence space. our simple approach worked surprisingly well: it outperformed human annotators -on average -in predicting the quality of dialogue and open-ended generation data. we also found bleu neighbors to be state-of-the-art on automatically grading essays, even beating out models that had access to a gold-standard reference essay. moreover, our model is fast, data-efficient, and easy-to-use; it has only two hyperparameters and those have settings that work universally well, across various tasks. still, bleu neighbors is intended to complement, not supplant, human evaluation -its speed, simplicity, and ease of use makes it ideal for rapidly iterating on nlg models long before any human evaluation is done.