Evaluating Natural Language Generation via Unbalanced Optimal Transport

1 Introduction

Natural language generation (NLG) has become a hot topic in the area of natural language processing, with a wide range of applications in many tasks, such as image captioning [Xu et al., 2015], machine translation [Bahdanau et al., 2014] and dialogue generation [Li et al., 2016]. To evaluate the performance of NLG methods, qualitative evaluation measures such as BLEU [Papineni et al., 2002], ROUGE [Lin, 2004] and METEOR [Banerjee and Lavie, 2005], are widely used to replace the costly human judgements. However, these measures fail to correlate well with human judgements due to their limitations in considering the semantic meanings of words or phrases, as shown in [Novikova et al., 2017].

∗Work done during the internship at ICT, CAS.

†Corresponding author.

Recently, embedding-based evaluation measures have been proposed to tackle with this problem. Typical examples include BERTScore [Zhang et al., 2020], YiSi-1 [Lo, 2019], WMD [Kusner et al., 2015], WMDo [Chow et al., 2019] and MoverScore [Zhao et al., 2019]. They first compute the semantic similarity between word representations, produced by word embedding models such as word2vec [Mikolov et al., 2013] or contextual embedding models such as BERT [Devlin et al., 2018]. The final score is then given by different intrinsic metrics, such as generalized precision, recall and F-score used in BERTScore, and the earth mover's distance (EMD) used in WMD, WMDo and MoverScore.

This paper focus on study the intrinsic metrics. The motivation comes from both empirical and theoretical perspectives. Empirically, it is unclear which intrinsic metric is the best. For example, previous studies have shown that the three different BERTScore versions perform differently on different data sets [Zhang et al., 2020]. Theoretically, existing work on the relations of these intrinsic metrics are superficial. For example, Zhao et al. [2019] classifies existing measures to two categories, where EMD is classified as the optimal matching (soft alignment), and generalized precision and recall are classified as the greedy matching (hard alignment). Generalized precision and recall are then transformed to a quasi (non-optimized) EMD form. To the best of our knowledge, an in-depth theoretical study on the relations of these intrinsic metrics is missing.

Inspired by the fact that EMD is a special optimal transport distance [Peyr´e et al., 2019], we conduct our study from the perspective of optimal transport theory. We theoretically prove that generalized precision and recall correspond to the optimal transport problem with unilateral hard marginal constraint, respectively; while EMD corresponds to the optimal transport problem with bilateral hard marginal constraints. Further considering the fact that F-score is the combination of precision and recall, the relation of different intrinsic metrics is clear. That is, they are the optimal transport problem with different hard marginal constraints. However, these hard constraints may cause serious problems in the NLG evaluation. When the candidate and reference sentences contain paraphrases of different length, only part of the paraphrasing words may be matched under the hard constraints, named incomplete matching problem. Besides, some words may be matched to less related ones, instead of their semantically close neighbors, named noisy matching problem.

To tackle these problems, we propose a family of new intrinsic metrics named Lazy Earth Mover's Distances (Lazy-EMDλc,λr ), induced by the more general unbalanced optimal transport problem with parameters λc, λr. Existing intrinsic metrics can be viewed as special extreme cases in our framework. Specifically, general precision, recall and EMD corresponds to Lazy-EMD∞,0 , Lazy-EMD0,∞ and Lazy-EMD∞,∞, respectively. Furthermore, we prove that Lazy-EMD has the ability to significantly alleviate the incomplete and noisy matching problem, by replacing the hard marginal constraints to the soft ones. We conduct extensive experiments on the large scale metric evaluation datasets provided by WMT18 and WMT19 [Ma et al., 2018; Ma et al., 2019]. Experimental results show that our proposed metrics produce more consistent results with human judgements, as compared with existing embedding-based evaluation measures.

Our contributions are summarised as follows:

• We theoretically prove the relations of different intrinsic metrics, i.e., the optimal transport problemwith different hard marginal constraints.
• We propose a family of new intrinsic metrics based on the more general unbalanced optimal transport problem, which significantly alleviate the incomplete and noisy matching problems of the existing measures.
• Extensive experiments on WMT18 and WMT19 show that our metric outperforms previous ones by producing more consistent results with human judgements.

2 Background

In this section, we introduce some details of the existing embedding-based evaluation measures for natural language generation. Since both BERTScore and YiSi-1 use generalized precision, recall and F-score as the intrinsic metrics, while WMD, WMDo and MoverScore all use earth mover's distance as the intrinsic metric, this section is separated into two subsections according to different intrinsic metrics.

First we give some notations. Suppose a sentence is represented as a triple (X,X,w), where X = (x1, · · · , xk) is a sequence of tokens, X = (x1, · · · , xk) is a sequence of token vectors, w = (w1, · · · ,wk) is a normalized vector with wi represents the weight assigned to xi.

2.1 Generalized Precision and Recall

Generalized precision and recall between a candidate sentence ( ˆX, ˆX, ˆw) and a reference sentence (X,X,w) are defined as follows. They measure the similarity of the two sentences.

Definition 1 (Generalized Precision and Recall).

where S(ˆxi, xj) measures the similarity of ˆxi and xj . In BERTScore [Zhang et al., 2020], the vector representation X is generated by the pre-trained model BERT [Devlin et al., 2018]. S is defined as the cosine similarity. The weight vector wi for each token is either uniform or defined by its inverse document frequency (IDF) computed using the reference sentences. Using generalized precision and recall as the internal metrics, we get two versions of BERTScore, denoted as PBERT and RBERT. FBERT is defined as their harmonic mean.

YiSi-1 is one typical configuration of YiSi [Lo, 2019]. The up-to-date version of YiSi-1 also uses BERT to generate X for X. The weight wi is defined by IDF computed using the reference sentences, with a plus-one smoothing in the logarithm. S is defined as the cosine similarity. The final score is defined as a weighted harmonic mean of generalized precision and recall. That is,

where α is usually set to 0.7 in machine translation evaluation.

2.2 EarthMover's Distance

The earth mover's distance between the candidate sentence( ˆX, ˆX, ˆw) and the reference sentence (X,X,w) is defined as follows, which measures the dissimilarity of the two sentences.

Definition 2 (Earth Mover's Distance).

where C ∈ R| ˆX|×|X| , with Ci,j stands for the dissimilarity of ˆxi and xj. This definition is deduced from the general form of EMD in [Rubner et al., 1998] under the condition ∑i ˆwi = ∑j wj = 1.

Word Mover's Distance (WMD) [Kusner et al., 2015] is a typical EMD on two documents, where X is the sequence of content words in the document and X is the sequence of their word2vec embeddings. w is a normalized bag-of-words vector. The dissimilarity between two word vectors is measured by the Euclidean distance.

WMDo [Chow et al., 2019] is an extension of WMD that further incorporates word order. Different fromWMD, X is a sequence of both content and stopping words in the sentence, and the dissimilarity is defined based on the cosine similarity. The final score combines WMD with an additional penalty of word order.

MoverScore [Zhao et al., 2019] employs contextual embeddings to replace the word2vec embeddings. Specifically, X and X are generated by the pre-trained model BERT, and w is a normalized vector of the IDF weights. Furthermore, the EMD used in MoverScore is an extension of the original one from single words to n-grams.

2.3 Comparisons of Different Metrics

By incorporating embeddings into consideration, these measures have shown promising improvement with human correlation as compared with traditional measures such as BLEU, ROUGE, and METEOR, shown in [Kilickaya et al., 2016; Zhang et al., 2020; Ma et al., 2019]. However, it is not clear which intrinsic metric is the best. For example, previous empirical studies have shown that the three different BERTScore versions perform differently, and alternate as the best on different evaluation datasets [Zhang et al., 2020]. Besides, existing empirical studies on generalized F-score and EMD conducted by BERTScore and MoverScore generate different conclusions on WMT17.

In this case, a thorough theoretical analysis is crucial. However, most existing theoretical results are superficial. In [Zhao et al., 2019], different metrics are related by transforming generalized precision and recall to a quasi non-optimized form of EMD, without further understanding. Some work attempts to separate these metrics to different categories. In [Zhang et al., 2020], the generalized precision and recall, EMD are classified to the greedy and optimal matching, respectively. While in [Zhao et al., 2019], generalized precision and recall, and EMD are viewed as hard and soft alignments, respectively. Though different categories indeed show some connections and differences [Rus and Lintean, 2012], there lacks an in-depth theoretical study on the relations of these metrics. That is exactly the motivation of this paper.

3 Theoretical Analysis on the Relations

Now we show our main theoretical results of the relations between these intrinsic metrics, i.e., they are proven to be the optimal transport problem with different hard marginal constraints. The idea of relating different metrics via optimal transport theory comes from the fact that EMD is an instance of the standard optimal transport distance [Peyr´e et al., 2019].

3.1 Optimal Transport Problem

Generally, optimal transport problem is to find a transport plan that meets the transport requirements with a minimum cost. Suppose we have two discrete distributions PX and PY supported on X = (x1, · · · , xn) and Y = (y1, · · · , ym), respectively. The amount of mass on these points is given by µ ∈ Rn and ν ∈ Rm. Suppose the cost matrix is C, where Ci,j denotes the cost of transporting a unit of mass from point xi to yj . We define a coupling matrix P ∈ Rn×m + , where Pi,j stands for the amount of mass flowing from the mass at xi toward yj. Then the optimal coupling P∗ is the solution of the following standard optimal transport problem.

Definition 3 (Standard Optimal Transport).

From the definition, we can see that a feasible coupling matrix satisfies two hard constraints on the boundaries. Intuitively, if we view µ as the source and ν as the target, then P1m = µ means that all the mass µi on the point xi must be fully transported to Y , and PT 1n = ν means the total mass transported to yj must meet its capacity νj .

3.2 Relations as Different Constraints

By varying the constraints of Eq. (7), the optimal transport problem bridges generalized precision, recall and EMD.

Firstly, it is straightforward that EMD in Definition 2 corresponds to the optimal transport problem with constraints Eq. (7), by setting µ = ˆw, ν = w, and C to be the dissimilarity matrix as in Def. 2. That is to say, EMD could be represented as:

In fact, generalized precision and recall correspond to the optimal transport problems with each hard marginal constraint in Eq. (7), respectively. Theorem 1 demonstrates how to relate generalized precision to the corresponding optimal transport problem, defined as follows.

Theorem 1. Let µ = ˆw, C = 1-S, where Si,j = S(ˆxi, xj) as defined in Def. 1. Suppose that the solution of the corresponding optimal transport problem (8) is denoted as P∗p , then generalized precision defined in Eq. (1) can be represented as

Proof. As we discussed in 3.1, the constraint P1m = µ means all the mass µi on the point xi must be fully transported to Y , while with the constraint PT 1n = ν removed, there is no requirement on Y . As a result, the optimal plan is transporting all the mass µi on the point xi to the point yj with the lowest cost Ci,j. Therefore, the optimal coupling matrix of problem (8) can be written as:

To prove it, suppose that there exists k, l such that (P ∗ p )k,l > 0, and l ̸= k∗ := argminj Ck,j. Let P′ = P∗p , except that P ′k,l = 0, P ′k,k∗ = (P ∗ p )k,l + (P ∗ p )k,k∗. Then P′ satisfies the constraint, but we have 〈C,P′ 〉 < 〈C,P∗p 〉, which is a contradiction.

As argminj Ci,j = argmaxj Si,j , µ = ˆw, we have

The inner product of S and P∗p becomes

With Si,j = S(ˆxi, xj), the above formula exactly equals to that of Eq. (1), i.e., generalized precision.

Similarly, we can prove that generalized recall corresponds to the optimal transport problem with another unilateral hard constraint, i.e., PT 1n = ν, where ν = w. Let the corresponding optimal coupling matrix denoted as P∗r , generalized recall can be written as R = 〈S, P∗r 〉.

To conclude, we have proven that generalized precision, recall and EMD correspond to the optimal transport problem with different hard marginal constraints.

3.3 Problems of Hard Constraints

However, these hard constraints may cause some problems in the evaluation process. Consider the coupling value Pij: it can be viewed as an assignment of weights on ˆxi and xj, which are lexical tokens in the candidate and reference sentences, respectively. When the value is non-zero, we say the corresponding tokens are matched. In this paper, our theoretical analysis shows that the hard constraints may cause incomplete and noisy matching problems.

The incomplete matching problem means that only part of the paraphrasing words are matched, which usually happens when the candidate and reference sentences contain paraphrases of different length. Now we show why the hard constraints result in this phenomenon.

First consider generalized precision, suppose that word ˆx1 in the candidate sentence is a paraphrase of words x1 and x2 in the reference sentence. By the explicit form of P∗p in Eq. (10), ˆx1 will only be matched with one of x1 and x2, unless S(ˆx1, x1) equals exactly as S(ˆx1, x2), which is very rare even though x1 and x2 are similar. Similarly, when candidate sentences contain longer paraphrase, the incomplete matching problem will happen for generalized recall.

Table 1 shows two examples of the incomplete matching problem, corresponding to the generalized precision and recall, respectively. In both examples, 'boy' is matched with 'man', instead of 'young man'. Evaluation results given by generalized precision and recall are both contradicted by human judgements. As the harmonic mean of them, F-score sometimes fixes their bias as in Example 2. However in Example 1, F-score still shows inconsistency. We also show the results of our proposed new metric Lazy-EMD, of which the dissimilarity evaluations agree with human judgements.

For EMD, the bilateral hard constraints further limit the capacity of semantic units. As a result, the matching is dependent on the value of ˆw1, ˆw2 and w1. If w1 > min( ˆw1, ˆw2), both ˆx1 and ˆx2 will be matched with x1. However if w1 ≤ min( ˆw1, ˆw2), since the optimal P∗ must satisfies ∑i P ∗ i,1 = w1, x1 will be only matched with the nearest one between ˆx1 and ˆx2. That is the incomplete matching problem.

Noisy matching problem means that words are matched with some less relevant tokens, instead of their semantic neighbors. We still consider the above example, with further assumption that the rest of the words in the reference sentence are less relevant with either ˆx1 or ˆx2 semantically. For EMD, when w1 = ˆw1, C1,1 < C2,1, coupling P ∗ 1,1 = ˆw1. By the constraint on PT 1n, ∑i P ∗ i,1 = ˆw1, then we have P ∗ 2,1 = 0. Since the constraint requires ∑j P ∗ 2,j = ˆw2, there exists some k s.t. P ∗ 2,k > 0. In other words, instead of x1, ˆx2 will be matched to some unrelated words. That is exactly the noisy matching problem.

4 Lazy EarthMover's Distances

To tackle the above problems, we propose a family of new intrinsic metrics, namely Lazy Earth Mover's Distances, induced from the more general unbalanced optimal transport problem. Unbalanced optimal transport problem [Peyr´e et al., 2019] relaxes the hard marginal constraints in standard optimal transport, by incorporating them into the optimization objective as penalties.

Definition 4 (Unbalanced Optimal Transport).

In the definition, parameters λc and λr control how much the corresponding marginal deviation are penalized, measured by K-L divergence [Kullback and Leibler, 1951].

Let µ = ˆw, ν = w, and C be the dissimilarity matrix as in Thm. 1. Denote P∗ λc,λr as the corresponding optimal coupling matrix of the unbalanced optimal problem with penalty parameters λc, λr . The Lazy Earth Mover's Distance between sentences is then defined as follows.

The word 'lazy' is to emphasize the fact that the final transport plan may not meet its original requirement. The transport behavior will be further explained in Section 4.1.

From the above definitions, we can see that standard optimal transport problem is a special case of unbalanced optimal transport problem, with λc = ∞, λr = ∞. Furthermore, P∗p and P∗r are the solutions of the unbalanced transport problem with λc = ∞, λr = 0, and λc = 0, λr = ∞, respectively. Therefore, the intrinsic metrics generalized precision, recall, and EMD can be viewed as special Lazy-EMDs:

4.1 Optimal Transport Plan of Lazy-EMD

Intuitively, by replacing hard marginal constraints with soft ones, Lazy-EMDs have the ability to alleviate the incomplete and noisy matching problems. Now we theoretically prove the above claim, by investigating the optimal transport plan of the unbalanced optimal transport problem.

Suppose that the candidate sentence is mapped to ˆX = (ˆx1, · · · , ˆxn), with a weight vector ˆw = ( ˆw1, · · · , ˆwn) representing the mass on each token. For simplicity, we consider the case where the reference sentence contains only one word X = (xr), with a unit of mass on it. Let the transport cost from xr to ˆxi be ci > 0, ∀i, and the transport plan be a vector P = (p1, · · · , pn)T . Then the optimal transport plan can be obtained with closed form shown in the following theorem.

Theorem 2. The optimal transport plan P∗λc,λr of the unbalanced transport problem with penalty parameters 0 < λc, λr < ∞ satisfies

From the results, we can see that the optimal transport plan is obtained by reweighting the mass vector ˆw. Specifically, the coefficient exp(- ci λc - λr λc A) is a decreasing function of ci. If the incomplete matching problem happens for ˆxi, ˆxi must be semantically close with xr, i.e., Si,r is large. Therefore, ci = 1 - Si,r is small, and the reweighting coefficient of p∗i will be large. In this way, the incomplete matching problem will be significantly alleviated. Similarly, the noisy matching problem usually happens for less relevant tokens with large costs. Therefore, the reweighting coefficients in the optimal transport plan on these tokens will be small. In this way, the noisy matching problem will be alleviated.

We further analyze the impact of penalty parameters λc and λr on the optimal coupling P∗ . It is clear that p∗i increases with λc and λr. So the unilateral and bilateral upper bounds are achieved by the optimal coupling correspondent to generalized precision, recall and EMD. That is,

5 Experiments

This section demonstrates our experimental results on WMT18 [Ma et al., 2018] and WMT19 [Ma et al., 2019]. We evaluate six different intrinsic metrics, i.e. generalized precision, recall, F1, Fα, WMD and Lazy-EMD, by their segmentlevel correlations with human judgments.

5.1 Datasets

Our experiments are conducted on WMT18 and WMT19, two widely used machine translation datasets for evaluating NLG measures. Specifically, WMT18 contains predictions of 149 translation systems across 14 language pairs, while WMT19 contains predictions of 193 translation systems across 15 language pairs. We follow the WMT18 and WMT19 standard practice and use Kendall rank correlation to evaluate metric quality on the segment-level human judgements, where WMT18 contains the relative ranking result of 327k sentence pairs and WMT19 contains 531k sentence pairs.

5.2 Implementation Details

For a fair comparison, we fix the embeddings and focus on comparing different intrinsic metrics. According to previous studies [Peters et al., 2018; Devlin et al., 2018], the contextual embeddings produced by BERT is usually better than word2vec-based word embeddings for various downstream NLP tasks. So we apply the default setting of BERTScore to other measures in our comparison. The implementation is based on BERTScore v0.2.2.

For EMD computation, the built-in function ot.emd in python package POT is used [Flamary and Courty, 2017]. Lazy-EMD is computed with the generalized Sinkhorn scaling algorithm. 1 The regularization parameter in the Sinkhornscaling algorithm is set as 0.009. The penalty parameters are set to be different for three data categories, based on the target language of the translation, i.e., English, Chinese and others. For English, the parameter is set to (0.23, 0.31), which is tuned on et-en in WMT18. For Chinese, the parameter is set as (0.018, 0.97), which is tuned on en-zh in WMT19. For other languages, the parameter is set as (0.009, 0.95), which is tuned on en-cs in WMT19.

1 Code is available at https://github.com/Beastlyprime/lazy emd

We compare Lazy-EMD with generalized precision, recall, F1 and EMD. Further considering that Lazy-EMD is a soft EMD which involves additional parameters, we also compare with Fα, where the parameter α is used to balance the effect of precision and recall. Fα can be viewed as an extension of F1 used in YiSi-1 (α = 0.7). In our experiments, α is tuned in the same way as we do for Lazy-EMD. Specifically, α is set to 0.48, 0.9, and 0.96 for English, Chinese and other target languages, respectively.

5.3 Experimental Results

Table 2 and Table 3 show our main experimental results. From the results, we can see that all the embedding-based measures outperform the n-gram based evaluation measure sentBLEU [Ma et al., 2018]. However, since WMT18 is relatively not large, all the embedding-based metrics perform comparably. For the larger dataset WMT19, Lazy-EMD outperforms all baselines in all translation scenarios, even better than Fα. Specifically, Lazy-EMD achieves the best correlation on 12 of 15 language pairs, which validates the advantage of replacing hard marginal constraints with soft ones.

Since the results in Table 2 and Table 3 are under parameters specifically tuned for different target languages, we show the performances of Lazy-EMD under the three different parameters on WMT19, to further study the influence of different penalty parameters. The results are demonstrated in Table 4. We can see that optimal parameter choices do differ between languages. However, the bottom two lines show the performance of Lazy-EMD is insensitive to slight variation on the parameters, which is another benefit of the proposed metric. The analysis of the origin of the difference in optimal parameters will be an interesting topic for future research.

6 Conclusions

This paper focuses on studying different intrinsic metrics of existing embedding-based evaluation measures, i.e., generalized precision, recall, F-score and EMD. We theoretically prove that these intrinsic metrics correspond to the optimal transport problem with different hard marginal constraints. To tackle the incomplete and noisy matching problems of these intrinsic metrics, we propose a family of new metrics, namely Lazy-EMD, based on the more general unbalanced optimal transport problem. Extensive experiments on WMT18 and WMT19 show that Lazy-EMD outperform traditional embedding-based measures in terms of consistency with segment-level human judgements.

To the best of our knowledge, this is the first in-depth theoretical study on the relations of different embedding-based NLG evaluation measures. The main novelty lies in the viewpoint of optimal transport theory. In the future, we plan to extend Lazy-EMD to evaluate distance between documents by incorporating document structure into the unbalanced optimal transport problem.

Acknowledgments

This work was supported by Beijing Academy of Artificial Intelligence (BAAI) under Grants No. BAAI2019ZD0306, and BAAI2020ZJ0303, the National Natural Science Foundation of China (NSFC) under Grants No. 61722211, 61773362, 61872338, 61902381, and 61906180, the Youth Innovation Promotion Association CAS under Grants No. 20144310, and 2016102, the National Key RD Program of China under Grants No. 2016QY02D0405, the Lenovo-CAS Joint Lab Youth Scientist Project, and Tencent AI Lab RhinoBird Focused Research Program (No. JR202033).