Recent studies have shown the advantages of evaluating NLG systems using pairwise comparisons as opposed to direct assessment. Given k systems, a naive approach for identifying the top-ranked system would be to uniformly obtain pairwise comparisons from all (cid:0) k 2 (cid:1) pairs of systems. However, this can be very expensive as the number of human annotations required would grow quadratically with k . In this work, we introduce Active Evaluation , a framework to efficiently identify the top-ranked system by actively choosing system pairs for comparison using dueling bandit algorithms. We perform extensive experiments with 13 dueling bandits algorithms on 13 NLG evaluation datasets spanning 5 tasks and show that the number of human annotations can be reduced by 80%. To further reduce the number of human annotations, we propose model-based dueling bandit algorithms which combine automatic evaluation metrics with human evaluations. Specifically, we eliminate sub-optimal systems even before the human annotation process and perform human evaluations only on test examples where the automatic metric is highly uncertain. This reduces the number of human annotations required further by 89%. In effect, we show that identifying the top-ranked system requires only a few hundred human annotations, which grow linearly with k . Lastly, we provide practical recommendations and best practices to identify the top-ranked system efficiently. Our code has been made publicly available at https: //github.com/akashkm99/duelnlg 1 Introduction In the last few years, the field of NLG has made rapid progress with the advent of large-scale models trained on massive amounts of data (Vaswani et al., 2017; Xue et al., 2020; Liu et al., 2020; Brown et al., 2020). However, evaluation of NLG  * Work done at Indian Institute of Technology Madras systems continues to be a challenge. On the one hand, we have automatic evaluation metrics which are easy to compute but unreliable. In particular, many studies have shown that they do not correlate well with human judgments (Novikova et al., 2017; Elliott and Keller, 2014; Sai et al., 2019, 2020a,b). On the other hand, we have human evaluations, which are relatively more reliable but tedious, expensive, and time-consuming. Further, recent studies have highlighted some limitations of human evaluations that involve direct assessment on an absolute scale, e.g. , Likert scale. Specifically, human evaluations using direct assessment have been shown to suffer from annotator bias , high variance and sequence effects where the annotation of one item is influenced by preceding items (Kulikov et al., 2019; Sudoh et al., 2021; Liang et al., 2020; See et al., 2019; Mathur et al., 2017). In this work, we focus on reducing the cost and time required for human evaluations while not compromising on reliability. We take motivation from studies which show that selecting the better of two options is much easier for human annotators than providing an absolute score, which requires annotators to maintain a consistent standard across samples (Kendall, 1948; Simpson and Gurevych, 2018). In particular, recent works show that ranking NLG systems using pairwise comparisons is a more reliable alternative than using direct assessment (See et al., 2019; Li et al., 2019; Sedoc et al., 2019; Dhingra et al., 2019). While this is promising, a naive approach for identifying the top-ranked system from a set of k systems using uniform exploration is prohibitively expensive. Specifically, uniform exploration obtains an equal number of annotations for all the (cid:0) k 2 (cid:1) system pairs; as a result, the required human annotations grows as O ( k 2 ) . To reduce the number of pairwise annotations, we introduce Active Evaluation, a framework to efficiently identify the top-ranked NLG system. Our Active Evaluation framework consists of a 8761 learner that selects a pair of systems to compare at each time step. The learner, then, receives a feedback signal indicating the (human) preference between the selected systems on one input context, randomly sampled from the test dataset. The learner's objective is to reliably compute the top-ranked system with as few human annotations as possible. We adopt algorithms from the stochastic dueling bandits literature (Bengs et al., 2021) to decide which pair of NLG systems to compare at each time step. To check if existing dueling bandits algorithms can indeed provide reliable top-rank estimates with minimal annotations, we evaluate 13 such algorithms on 13 NLG evaluation datasets spanning five tasks viz. , machine translation, summarization, data-to-text generation, paraphrase generation, and grammatical error correction. We show that the best performing dueling bandit algorithm can reduce the number of human annotations by 80% when compared to uniform exploration. To further reduce human annotations, we leverage automatic evaluation metrics in our Active Evaluation framework. We utilize existing automatic metrics such as BLEU (Papineni et al., 2002), BertScore (Zhang et al., 2020), etc for pairwise evaluations by converting the direct evaluation scores into preference probabilities using pairwise probability models. We also develop trained pairwise metrics that directly predict the comparison outcome given pairs of generated texts and context or reference as input. To incorporate such evaluation metrics in our Active Evaluation framework, we propose three model-based dueling bandits algorithms, viz. , (i) Random Mixing: human annotations and evaluation metric predictions are randomly mixed, (ii) Uncertainty-aware selection: human annotations are obtained only when the predictions from the evaluation metric is highly uncertain, (iii) UCB Elimination: poorly performing NLG systems are eliminated using an Upper Confidence Bound (UCB) on the evaluation metric scores. Through our experiments, we show that the number of human annotations can be further reduced by 89% on average (this reduction is over and above the 80% reduction that we got earlier). In effect, we show that given k systems, we can find the top-ranked NLG system efficiently with just a few hundred comparisons that vary as O ( k ) . Lastly, we provide practical recommendations to efficiently identify the top-ranked NLG system based on our empirical study on various design choices and hyperparameters. We introduce the problem and our Active Evaluation setup in section 2.1. Later in section 2.2, we describe the different approaches to decide which pairs of NLG systems to compare at each time step. Finally, in section 2.3, we formalize the notion of top-ranked system. We consider the problem of finding the top-ranked NLG system from a given set of k systems, denoted by S = { 1 , 2 , . . . , k } . Our Active Evaluation framework consist of a learner which at each time step t , chooses a pair of systems s ( t ) 1 , s ( t ) 2  S for comparison. Then, we ask human annotators to compare the outputs of the chosen systems on a randomly sampled input context and provide the comparison outcome as feedback to the learner. Specifically, we first sample an input context X ( t ) from the test dataset and obtain the generated texts Y ( t ) 1 , Y ( t ) 2 from the chosen systems s ( t ) 1 , s ( t ) 2 . We then display the generated texts Y ( t ) 1 , Y ( t ) 2 along with the context X ( t ) to human annotators and obtain a comparison outcome w ( t ) = 1 , 0 , or 0 . 5 denoting whether Y ( t ) 1 is of better, worse, or equal (tie) quality as Y ( t ) 2 . Note that the feedback w ( t ) indicates the preference on only one input sample and not the entire test dataset. The overall framework is depicted in figure 1. The learner's objective is to find the top-ranked system with as few pairwise comparisons as possible. The learner should decide the pair of systems ( s ( t ) 1 , s ( t ) 2 ) to compare at each time step t . The naive approach is to uniformly explore all the (cid:0) k 2 (cid:1) system pairs. Specifically, the probability of selecting a pair ( i, j ) , i  = j at time t is given by P uniform (( s ( t ) 1 , s ( t ) 2 ) = ( i, j )) = 1 (cid:0) k 2 (cid:1) However, as we show in our experiments, the number of human annotations required to find the top-ranked system by this approach is very expensive and grows quadratically with the number of systems since we equally explore all (cid:0) k 2 (cid:1) pairs. To reduce the number of annotations, we use dueling bandit algorithms to actively choose pairs of systems to compare based on the history of previous 8762 Figure 1: Our Active Evaluation framework consisting of a learner that chooses a pair of systems to compare at each time step. observations. We provide an overview of 13 dueling bandits algorithms proposed in the literature in appendix B. We refer the readers to (Bengs et al., 2021) for a complete survey. We now formalize the notion of the top-ranked system. Let p ij denote the preference probability of system i over system j i.e. the probability that a generated text from system i is preferred over system j in the test dataset. We say that a system i "beats" system j if p ij > 12 . In other words, system i beats system j if the probability of winning in a pairwise comparison is larger for i than it is for j . We define the top-ranked system i  as the one that beats all other systems, i.e. p i  j > 12 ,  j  S  i  . Our Active Evaluation framework, which we described in the previous section, completely relied on human annotators to compare pairs of generated texts ( Y 1 , Y 2 ) to provide the preference feedback w . We can further reduce the number of required human annotations by estimating the human preference feedback using automatic evaluation metrics. However, most existing evaluation metrics are designed for direct assessment and not directly suitable for pairwise evaluations. In this section, we describe three pairwise probability models to convert direct evaluation scores into pairwise preference probabilities. Let f ( Y ) denote the score provided by a direct assessment metric f to a generated text Y (The dependence of f on the reference/context is omitted for brevity). The pairwise preference probability  p ( Y 1  Y 2 ) between any two hypotheses Y 1 and Y 2 can be modeled in 3 different ways:  Linear:  p ( Y 1  Y 2 ) = 1 2 + ( f ( Y 1 )  f ( Y 2 ))  Bradley-Terry-Luce (BTL) (Bradley and Terry, 1952; Luce, 1979):  p ( Y 1  Y 2 ) = f ( Y 1 ) f ( Y 1 ) + f ( Y 2 )  BTL-logistic: : As detailed in appendix C.2, we appropriately preprocess the scores f ( Y ) to ensure that preference probability lies between 0 and 1. We can now predict the comparison outcome w by thresholding the preference probability at two thresholds  1 and  2 (   1 ) to incorporate ties i.e. :  w =   1 , if  p ( Y 1  Y 2 ) >  2 0 , if  p ( Y 1  Y 2 ) <  1 0 . We choose  1 and  2 using grid search on the validation set. Refer appendix C.2 for more details. In the previous section, we discussed pairwise probability models to obtain the estimated preference probability  p ( Y 1  Y 2 ) and the comparison outcome  w using scores assigned by direct assessment metrics. We now propose three model-based dueling bandit algorithms wherein we combine such predictions from evaluation metrics with human annotations in the Active Evaluation framework. Here, we randomly provide either the real (human) or the evaluation metric predicted feedback to the learner. Specifically, at any time t , we use the predicted comparison outcome  w ( t ) as the feedback with probability p m and use human annotations w ( t ) as feedback with probability 1  p m . The hyperparameter p m controls the ratio of estimated and real feedback given to the learner. As with other hyperparameters, we tune p m on the validation set. In this algorithm, we estimate uncertainty in the evaluation metric predictions and decide to ask for human annotations only when the evaluation metric is highly uncertain. We specifically focus on trainable neural evaluation metrics such as Bleurt (Sellam et al., 2020) where we estimate the prediction uncertainty using recent advances in Bayesian deep learning. Let  p ( Y 1  Y 2 |  ) denote the preference probability modelled by a neural evaluation metric with parameters  . Given a training dataset D tr , Bayesian inference involves computing the posterior distribution p (  |D tr ) and marginalization over the parameters  :  p ( Y 1  Y 2 |D tr ) = (cid:90)   p ( Y 1  Y 2 |  ) p (  |D tr ) d However, computing the true posterior and averaging over all possible parameters is intractable in practice. Hence, several approximations have been proposed in variational inference such as finding a surrogate distribution q  (  ) for the true posterior. Gal and Ghahramani (2016) have shown that we can use the Dropout distribution (Srivastava et al., 2014) as the approximate posterior q  (  ) . Specifically, we can perform approximate Bayesian inference by applying Dropout during test time. Hence, the posterior can now be approximated with Monte-carlo samples as follows:  p ( Y 1  Y 2 |D tr )  1 LL (cid:88) l =1  p ( Y 1  Y 2 |  l ) where {  l } Ll =1 are L samples from the Dropout distribution q  (  ) (i.e. we apply Dropout L times independently during testing). We now discuss two different Bayesian uncertainty measures: BALD: The Bayesian Active Learning by Disagreement (BALD) (Houlsby et al., 2011) is defined as the mutual information between the model predictions and the model posterior. Let p l =  p ( Y 1  Y 2 |  l ) , where  l  q  (  ) , be the evaluation metric prediction using the l th sample  l from the Dropout distribution. Also, let  p = 1 L (cid:80) Ll =1 p l be the mean prediction. As shown in (Gal et al., 2017), we can approximate the BALD measure using samples from the Dropout distribution as:  I = H ( p )  1 LL (cid:88) l =1 H ( p l ) where H is the binary cross entropy function. The BALD uncertainty score is essentially the difference in entropy of the mean prediction  p and the average entropy of the individual predictions { p l } Ll =1 . Hence, the BALD uncertainty score is high when the metric's mean prediction is uncertain (high entropy) but the individual predictions are highly confident (low entropy), i.e. , when the metric produces disagreeing predictions with high confidence. STD: We also adopt the standard deviation of the preference probability taken over the posterior distribution as a measure of uncertainty:  = (cid:113) Var    p (  |D tr ) ( p ( Y 1  Y 2 |  )) Similar to BALD, we can approximate the above measure using the empirical standard deviation of samples drawn from the dropout distribution. Our proposed algorithm asks for human annotations only if the uncertainty measure (BALD or STD) is above a particular threshold. The key idea here is to eliminate a set of "poorly performing" NLG systems using the automatic metric and perform human evaluations with the remaining set of systems. To eliminate sub-optimal systems, we first need to quantify a performance measure for the systems. We use the Copeland score (Zoghi et al., 2015) which is defined as the normalized total number of pairwise wins for a system: C i = 1 k  1 (cid:80) j  = i 1 ( p ij > 12 ) . Copeland score is the highest for the top-ranked system with a value of 1 and it is less than 1 for all other systems. To estimate the Copeland score, we first predict the pairwise preference probability between any two systems i and j as follows:  p ij = 1 N (cid:88) Y 1 ,Y 2 D ij  p ( Y 1  Y 2 |  ) where D ij is the test dataset consisting of generated texts from systems i and j , N is the total number of test examples,  is the learned model parameters. We can now estimate the Copeland score  C i using the estimated preference  p ij and eliminate all systems with Copeland scores below a threshold. However, a major problem with this approach is that evaluation metrics are often inaccurate and we could wrongly eliminate the true top-ranked system without performing any human evaluations. For example, consider the example where i  is the 8764 top-ranked system with p i  j > 0 . 51 ,  j  S  i . If several of the predicted probabilities  p i  j are less than 0 . 5 , our top-ranked system i  will receive a low estimated Copeland score and will be incorrectly eliminated. To overcome this problem, we define an Upper Confidence Bound (UCB) on the preference probability using uncertainty estimates that we described in 4.2. Specifically, the upper confidence bound  u ij is given by  u ij =  p ij +    ij where  is a hyperparameter that controls the size of the confidence region and   2 ij is the estimated variance given by:   2 ij = 1 N 2 (cid:88) Y 1 ,Y 2 D ij Var   q  (  )  p ( Y 1  Y 2 |  ) where q  (  ) is the Dropout distribution. Using the upper confidence estimates  u ij , we now define the optimistic Copeland score for a system i as  C ui = 1 K  1 (cid:80) j  = i 1 ( u ij > 1 2 ) . Here, we consider a system i to beat another system j (  u ij > 0 . 5 ) if either the estimated preference is high (  p ij is high) or if there is an high uncertainty in the estimation (   ij is high). In UCB Elimination, we eliminate a system only if the optimistic Copeland score is below a threshold. In this section, we describe the (i) NLG tasks and datasets used in our experiments, (ii) automatic evaluation metrics used in our model-based algorithms, and (iii) annotation complexity measure used for comparing dueling bandit algorithms. We use a total of 13 datasets spanning 5 tasks in our experiments which are summarized in table 1. Machine Translation (MT): We use 7 human evaluation datasets collected from the WMT news translation tasks (Bojar et al., 2015, 2016) viz. fin  eng, rus  eng, deu  eng language pairs in WMT 2015 and tur  eng, ron  eng, cze  eng, deu  eng language pairs in WMT 2016. Grammatical Error Correction (GEC): We utilize two human evaluation datasets collected by (Napoles et al., 2019) where the source texts are from (i) student essays (FCE), and (ii) formal articles in Wikipedia (Wiki). We also use another GEC dataset collected by (Napoles et al., 2015a) from the CoNLL-2014 Shared Task (Ng et al., 2014). Paraphrase Generation: We use human evaluations of model generated English paraphrases released with the ParaBank dataset (Hu et al., 2019). Summarization: We make use of the human evaluations (Stiennon et al., 2020) of GPT3-like transformers on the TL;DR dataset (Vlske et al., 2017). We provide further details including preprocessing steps and downloadable links in appendix A.1. We can predict the comparison outcome w using two approaches. First, we can use pairwise probability models with existing direct assessment metrics as discussed in section 3. Alternatively, we can train evaluation metrics to directly predict the comparison outcome given pairs of generated texts and context/reference as input. We discuss both these approaches below: Direct Assessment Metrics: We experiment with a total of 10 direct assessment metrics viz. chrF (Popovic, 2015), BLEU-4 (Papineni et al., 2002), ROUGE-L (Lin, 2004), Embedding Average (Wi-eting et al., 2016), Vector Extrema (Forgues et al., 2014), Greedy Matching (Rus and Lintean, 2012), Laser (Artetxe and Schwenk, 2019), BertScore (Zhang et al., 2020), MoverScore (Zhao et al., 2019) and Bleurt (Sellam et al., 2020). We mention the implementation details in appendix A.2. Pairwise Evaluation Metrics: We finetune the pretrained Electra-base transformer model (Clark et al., 2020) to directly predict the comparison outcome w . We curate task-specific human evaluation datasets consisting of tuples of the form (con-text/reference, hypothesis 1, hypothesis 2, label) for finetuning. Due to space constraints, we mention 8765 Algorithm WMT 2016 WMT 2015 Grammarly CoNLL'14Task E2ENLG Para-Bank TL;DR tur-eng ron-eng cze-eng deu-eng fin-eng rus-eng deu-eng FCE Wiki Uniform 19479 24647 10262 3032 2837 12265 17795 8115 34443 61369 65739 825211 5893 SAVAGE 10289 18016 6639 2393 2675 12806 12115 5767 22959 39208 41493 255208 4733 DTS 10089 9214 8618 4654 4850 13317 16473 4355 11530 18199 19940 170467 1354 CCB 7017 11267 5389 2884 4092 11548 10905 4386 10020 21392 16960 87138 2518 Knockout 3415 7889 4723 3444 5104 5809 5956 3134 3777 8055 7708 17418 4953 RUCB 3125 5697 3329 1636 1655 4536 6222 2732 5617 19024 10924 41149 1647 RCS 2442 3924 3370 1537 2662 3867 5296 1816 4606 12678 7263 34709 1903 RMED 2028 5113 1612 864 1707 1929 4047 2093 5647 9364 3753 24132 1162 Table 2: Annotation complexity of the top 7 best performing dueling bandit algorithms along with the uniform exploration algorithm on 13 datasets spanning 5 NLG tasks details on the datasets and finetuning in appendix A.3 and A.4. For the summarization task alone, we couldn't find any pairwise human judgment dataset sufficient for finetuning the Electra model. To evaluate the performance of dueling bandit algorithms, we define annotation complexity as the minimum number of human annotations needed by an algorithm to identify the top-ranked NLG system with high confidence. Let i  be the actual top-ranked system, and  i  ( n ) denote the estimated winner by the algorithm after n human annotations, then annotation complexity is defined as: min n  :  n  n  , P (  i  ( n ) = i  ) > 1   acc where  acc is the allowable failure probability i.e. the learner can make a mistake with at most  acc probability. To compute the annotation complexity, we run each dueling bandit algorithm with 200 different random seeds and find the minimum number of human annotations after which the algorithm correctly returns the top-ranked NLG system in at least 190/200 runs (we set  acc = 0 . 05 ). We discuss the performance of dueling bandits algorithms in 6.1, automatic metrics in 6.2 and our proposed model-based algorithms in 6.3. Lastly in 6.4, we analyze the variation of annotation complexity with the number of NLG system. We report the annotation complexity of the top 7 dueling bandit algorithms along with uniform exploration on 13 datasets in table 2. We observe that the annotation complexity of uniform exploration is consistently high across all 13 datasets. In particular, the required human annotations become prohibitively expensive when the number of NLG 0 1000 2000 3000 4000 Number of Human Annotations 0 . systems is high, e.g. E2E NLG (16 systems) and ParaBank (28 systems) datasets. On the other hand, dueling bandit algorithms such as RUCB (Zoghi et al., 2014b), RCS (Zoghi et al., 2014a), RMED (Komiyama et al., 2015) are able to effectively identify the top-ranked system with much fewer annotations. In particular, RMED performs the best with a reduction of 80.01% in human annotations compared to uniform exploration. We also examine an alternative approach to assess the performance of dueling bandit algorithms. Here, we fix the number of human annotations (fixed annotation budget) and compute the accuracy in predicting the top-ranked system. As we show in figure 2, RMED achieves the highest top-rank prediction accuracy for any given number of human annotations. We provide the complete results in appendix F.2. Before we utilize automatic evaluation metrics using our proposed model-based algorithms, we analyze the effectiveness of these metrics for pairwise NLG evaluations. In table 3, we report the sentence-level accuracy in predicting the comparison outcome w using direct assessment metrics with the Linear probability model (as discussed in section 3) along with our trained Electra metric. Across the tasks, we observe that metrics that utilize con-8766 Metric WMT(Avg.) textualized word embeddings, such as BertScore, perform much better than n -gram and static word embedding-based metrics. In MT, we observe that Bleurt, specifically finetuned on WMT human judgment data, performs the best. In Data-to-Text and Paraphrase generation, our trained Electra metric finetuned on task-specific data significantly outperforms the existing metrics. Interestingly, on the summarization task, all the existing metrics perform much worse than random predictions i.e. they do not add any useful value in evaluation. Hence, we exclude the TLDR dataset from our analysis on model-based algorithms. Finally, as we show in appendix F.3, we observed that the performance is largely similar across all the three probability models: Linear, BTL, and BTL-logistic. We use our proposed model-based algorithms and incorporate the two best-performing evaluation metrics, viz. , Bleurt and Electra with the best performing dueling bandit algorithm, viz. , RMED. We compare the annotation complexity of various model-based algorithms in table 4. We observe that the Random Mixing algorithm with Bleurt and Electra reduces annotation complexity by 70.43% and 73.15%, respectively, when compared to the standard (model-free) RMED algorithm (row 1). Our Uncertainty-aware selection algorithm with the BALD measure further reduces the annotation complexity by around 37% (compared with Random Mixing). We notice that our UCB Elimination algorithm also provides significant improvements over standard RMED. Since UCB Elimination is complementary to Uncertainty-aware selection, we apply both these algorithms together and observe the lowest annotation complexity with a reduction of 89.54% using Electra and 84.00% using Bleurt over standard RMED. Lastly, in figure 3, we analyze the effect of using other evaluation metrics such as BLEU, BertScore, etc. , in Random Mixing. Interestingly, we notice that using metrics such as BLEU, which have low accuracy values, results in a higher annotation complexity than standard (model-free) RMED in some datasets. That is, we may even require a greater number of human annotations to over-compensate for the inaccurate predictions from metrics like BLEU. However, with Laser, MoverScore, and BertScore, we observe significant reductions in annotation complexity. Please refer appendix F.4 for further results. We analyze how annotation complexity varies with the number of NLG systems. Specifically, we chose a subset of k systems out of the total 28 systems in the ParaBank dataset and computed the annotation complexity among these k systems. As shown in figure 4, the annotation complexity of uniform ex-8767 Model-basedAlgorithm EvaluationMetric WMT 2016 WMT 2015 Grammarly CoNLL'14Task E2ENLG Para-Bank tur-eng ron-eng cze-eng deu-eng fin-eng rus-eng deu-eng FCE Wiki None (Model free) None 2028 5113 1612 864 1707 1929 4047 2093 5647 9364 3753 24132 Random Mixing Bleurt 237 1222 315 161 275 304 771 406 671 9584 1151 15874 Electra 728 3213 385 152 236 512 650 1529 237 3302 326 1044 Uncertainty-awareSelection(STD) Bleurt 103 1012 192 84 204 239 530 270 185 9356 1291 22876 Electra 978 7251 478 210 388 962 1259 477 234 4708 199 2137 Uncertainty-awareSelection(BALD) Bleurt 101 653 136 48 181 162 405 204 128 9356 1167 22619 Electra 737 1648 223 114 207 538 488 281 75 1557 67 858 UCB Eliminination Bleurt 711 2684 1131 573 419 843 3556 967 1115 8382 2005 14098 Electra 264 649 1131 414 294 1126 3556 3970 1115 2943 1112 9870 Uncertainty(BALD)+UCB Elim. ploration grows quadratically with k as it explores all system pairs equally. However, for (model-free) dueling bandit algorithms such as RMED, the annotation complexity is much lower and only varies as O ( k ) . As shown in appendix F.1, we observed similar trends with model-based algorithms. We summarize the key insights from this study and provide practical recommendations on efficiently identifying the top-ranked NLG system. 1. Use RMED dueling bandit algorithm to actively choose system pairs for comparison. 2. If human evaluation datasets are available, train a metric to predict the comparison outcome directly. Otherwise, use Bleurt with any of the Linear, BTL, BTL-logistic models. 3. Manually annotate a few examples from the test dataset and evaluate the sentence-level accuracy of the metric. If the performance is poor (e.g., accuracy near the random baseline), do not use model-based approaches, obtain feedback only from human annotators. 4. If the metric is reasonably accurate, use UCB Elimination with Uncertainty-aware Selection (BALD). Tune the hyperparameters of these algorithms, if possible. Otherwise, refer appendix D for best practices developed based on analyzing the sensitivity of model-based algorithms to hyperparameters. 5. We can reduce the annotation time if we use multiple annotators in parallel. We observed that dueling bandit algorithms, though originally proposed for sequential annotations, are robust to asynchronous feedback from multiple annotators (Refer appendix E for details). Several works (Bojar et al., 2014, 2015; Sakaguchi et al., 2014, 2016) in Machine translation and Grammatical Error Correction adopt the TrueSkill algorithm (Herbrich et al., 2006), originally used for ranking Xbox gamers, to efficiently rank NLG systems from pairwise annotations. A recent work (Sakaguchi and Durme, 2018) proposes an online algorithm to rank NLG systems when we receive pairwise preference feedback in the form of a continuous scalar with bounded support. The key difference in our work is that we focus on the problem of identifying the top-rank system instead of ranking all the systems. Experimental study of dueling bandit algorithms have been limited to synthetic simulations in a few works (Yue and Joachims, 2011; Urvoy et al., 2013). Most others (Zoghi et al., 2014b,a; Komiyama et al., 2015; Zoghi et al., 2015; Wu and Liu, 2016) focus on information retrieval applications that involve evaluating search retrieval algorithms (Radlinski et al., 2008). To the best of our knowledge, ours is the first work to extensively study the effectiveness of dueling bandit algorithms for NLG evaluation. In this work, we focused on the problem of identifying the top-ranked NLG system with few pairwise annotations. We formulated this problem in an Active Evaluation framework and showed that dueling bandit algorithms can reduce the number of human annotations by 80%. We then proposed model-based algorithms to combine automatic metrics with human evaluations and showed that human annotations can be reduced further by 89%; thereby requiring only a few hundred human annotations to identify the top-ranked system. In future work, we would like to extend our analysis to the general problem of finding the top-k ranked systems. Evaluating Natural Language Generation (NLG) models accurately and reliably with few human annotations is an important aspect of NLG research and its real-world applications. Our work shows that we can significantly reduce the number of human annotations required to find the top-ranked NLG system with high confidence. We envision that our work will benefit a wide range of applications such as translation systems, grammatical checkers, etc., where practitioners can find the best NLG model among a set of candidates more accurately and with fewer human annotations. Despite these improvements, there are still several challenges towards reliable NLG evaluation. For example, our model-based approaches, which use automatic metrics, may be subject to biases and other undesirable mistakes, depending on the metric and how they are trained in practice. Our approach may be used to evaluate models that generate fake news, toxic content, or other harmful applications, even though it is not specifically designed for such cases. We thank the Department of Computer Science and Engineering, IIT Madras, and the Robert Bosch Center for Data Science and Artificial Intelligence, IIT Madras (RBC-DSAI), for providing us resources required to carry out this research. We also wish to thank Google for providing access to TPUs through the TFRC program. We thank the anonymous reviewers for their constructive feedback in enhancing the work.
abstain abstain abstain method result objective method abstain result method other abstain method abstain abstain abstain abstain method abstain abstain abstain abstain method method abstain abstain method method abstain result method method objective objective abstain abstain abstain abstain result result method abstain method abstain method method method method method abstain abstain abstain abstain abstain other method abstain abstain abstain abstain abstain abstain method method method abstain method abstain method method abstain abstain abstain method method abstain abstain abstain method abstain abstain abstain abstain method method method abstain abstain abstain abstain abstain method abstain abstain abstain method abstain other method method abstain abstain abstain abstain method other method method abstain method method method abstain method method abstain abstain method method abstain method method method method method method method method method method other method abstain abstain result abstain abstain abstain abstain abstain abstain result result abstain abstain result abstain result result abstain abstain result abstain abstain abstain abstain result abstain result result abstain abstain result abstain result abstain abstain abstain other abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain other abstain method other other objective method result objective objective abstain result result abstain method method other other other