On the Relation between Quality-Diversity Evaluation and Distribution-Fitting Goal in Text Generation

Text data is usually discrete, so we make the following notations. Assume the vocabulary size is $|V|$, and the maximum length is $L$, then the distribution of text data can be described by a categorical distribution with size $N=|V|^{L}$. We denote the real distribution and the generated model distribution as $P(x)=(P_{1},P_{2},\cdots,P_{N})$ and $Q(x)=(Q_{1},Q_{2},\cdots,Q_{N})$, respectively.

In general, the Quality of a text generation model measures how likely the generated text are to be realistic text in human’s view. Since the value of real probability $P(x)$ can be viewed as reflecting the realistic degree of a text $x$, the expectation of some function over $P(x)$ could be used to quantify quality. For example, in works of Yu et al. (2017) and Nie et al. (2018), Log-Likelihood (LL) is used as the quality metric, where $LL(Q;P)=\mathbb{E}_{x\sim Q}\log P(x)$. Following this idea, we propose a general form of quality, i.e., $U(Q;P)=\mathbb{E}_{x\sim Q}f_{u}[P(x)]$, where $f_{u}$ is a function over $P(x)$.

Similarly, the Diversity of a text generation model measures how much difference there are among generated texts. From the viewpoint of information, Shannon-Entropy (SE) of $Q(x)$ can be used as a natural diversity metric, where $SE(Q)=-\mathbb{E}_{x\sim Q}\log Q(x)$. From another understanding view, a text $x$ should be less likely to be generated again if the diversity is high. This idea has been adopted in biology to evaluate the diversity of biocoenosis, named as the Simpson’s Diversity Index (SDI), where $SDI(Q)=1-\mathbb{E}_{x\sim Q}Q(x)$. Summarizing these two different understandings, we obtain a general form of diversity, i.e. $V(Q)=-\mathbb{E}_{x\sim Q}f_{v}[Q(x)]$.

To this end, we propose a general form of quality and diversity metrics as follows:

where $f_{u}(x)$ is denoted as $f(x)$ and $-x\cdot f_{v}(x)$ as $g(x)$.

To guarantee $U$ and $V$ are rational quality and diversity metrics, we need to discuss about the conditions of $f$ and $g$. Without loss of generality, we first assume that $f$ is differentiable and $g$ is twice differentiable. Further, the following requirements are necessary for rational quality and diversity:

1. 1.

   Generating more samples with higher real probability yields higher overall quality;

2. 2.

   Distributing the probability more equally yields higher overall diversity.

Mathematically, these two requirements can be formalized as the following two properties:

1. If $P_{i}>P_{j}$, then for $Q^{\prime}=(Q_{1},\dots,Q_{i}+\epsilon,\dots,Q_{j}-\epsilon,\dots)$, there is $U(Q^{\prime})>U(Q)$ for any $\epsilon\in(0,Q_{j})$.

2. If $Q_{i}\geq Q_{j}$, then for $Q^{\prime}=(Q_{1},\dots,Q_{i}+\epsilon,\dots,Q_{j}-\epsilon,\dots)$, there is $V(Q^{\prime})<V(Q)$ for any $\epsilon\in(0,Q_{j})$.

Then we can obtain the conditions of $f$ and $g$ by the following theorem:

According to Theorem 1, it is necessary for $f(x)$ to be strictly monotonically increasing and $g(x)$ to be strictly concave for $x\in(0,\frac{1}{2})$. For simplicity, we only consider the cases where such properties hold for $x\in(0,1)$, thus get a sufficient condition:

1. 1.

   $f(x)$ is strictly monotonically increasing for $x\in(0,1)$;

2. 2.

   $g(x)$ is strictly concave for $x\in(0,1)$.

Under this condition, we can see that a model with highest quality will distribute all its density to text with highest real probability, and a model with highest diversity will be uniform, which are consistent with human understandings.

We consider the following MOP problem:

The goal is to maximize both quality and diversity, while keeping $Q$ a legal distribution. The optimal solutions of a MOP problem are called Pareto-optima, which means no other solution can beat them consistently over all objectives.

We give definitions of the terminologies of Pareto-optimality below:

Intuitively, a Pareto-optimum is a solution that there is no distribution can achieve both higher quality and higher diversity than it. And all the Pareto-optima constitutes the Pareto-frontier. The Pareto-frontier may collapse into one solution which leads to a global optimum, e.g. if $P$ is uniform, the unique optimal solution would be $Q^{*}=P$. However it is often the case where the objectives in MOP problem cannot reach their optima consistently, which results in a family of optimal solutions. Therefore, the structure of the Pareto-frontier under a non-uniform $P$ is what we care about.

We show the structure of the Pareto-frontier by giving the following theorem:

According to Theorem 2, different $w$s lead to different distributions, so we can change $w$ from $0$ to $B$ and get a family of optimal solutions with different quality and diversity. As such, for a non-uniform $P$, the Pareto-frontier is a family of distributions.

We can see quality and diversity act as a tradeoff if we want to maximize them at the same time. Since all distributions in the Pareto-frontier are Pareto-optima, trying to improve one metric for an optimum will lead to another optimum at most, thus inevitably causing another metric to drop. This result provides support for the quality-diversity tradeoff problem observed in previous works (Zhu et al., 2018; Caccia et al., 2018).

We show the result of Theorem 2 here on a special case. We pair Log-Likelihood (LL) with Shannon-Entropy (SE), the corresponding Pareto-optima can be written as

we have $w=-\beta$, and $b=1+\log Z$. These Pareto-optima are formerly used as quality-diversity tradeoff solutions by Li et al. (2019).

An illustration of the Pareto-frontier on a toy distribution is shown in Figure 1. We can see that quality and diversity are negatively correlated for solutions in the Pareto-frontier. Note that the ground truth distribution lies exactly on the frontier in this LL-SE case, which can be checked by setting $\beta=1$. We will then show this is the key to the relation between quality-diversity metrics and divergence metrics.

To bridge the gap between the distribution-fitting goal and quality-diversity evaluation, it is necessary for the optimal solutions from divergence minimization to be consistent with that from quality-diversity maximization. Since $Q=P$ is the optimal solution with minimum divergence and the above Pareto-frontier is the set of optimal solutions with maximal quality and diversity, we require $Q=P$ to be in the Pareto-frontier. Theoretical results are shown in the following Theorem:

We find that if quality and diversity metrics are carefully chosen, namely $g$ is the integral of an affine transformation of $f$, we can get a divergence metric by a linear combination of these two metrics.

The LL-SE case satisfies the condition in Theorem 3. Under this special case, there is $\Psi(Q)=\frac{1}{2}\mathrm{LL}(Q)+\frac{1}{2}\mathrm{SE}(Q)$, and

which is exactly the Reverse KL divergence if the constant $\frac{1}{2}$ is ignored. This linearly combined divergence metric can be viewed as a tangent line of the Pareto-frontier curve in Figure 1, and the real distribution is the tangent point.

Since such condition is also necessary, the real distribution is unlikely to be a Pareto-optima if we use casually chosen metrics. This means, there would be one distribution achieving both higher quality and higher diversity than the ground truth, which is implausible. Therefore, if the condition in Theorem 3 is not satisfied, it would be unlikely to measure the divergence using a combination of quality and diversity.

Now we can conclude that, it is sufficient to reflect the distribution-fitting goal by a hybrid of quality-diversity evaluation. However, specific metrics should be chosen carefully, in order to avoid the potential violation of such property. Suppose such property is violated severely, featured by a huge gap between the ground truth distribution and the Pareto-frontier, then a model which perfectly fits the real distribution would be significantly outperformed by another model over both quality and diversity, resulting in misleading conclusions.

Therefore in the next section, we will examine the existence of the gap for quality-diversity metrics used in practice, and provide suggestions on the choice of quality-diversity metrics.

BLEU (Papineni et al., 2002) and Self-BLEU (Zhu et al., 2018) are common metrics for quality and diversity evaluation, respectively. Intuitively, BLEU measures the $n$-gram overlap between a candidate set of generated text and a reference set of real text, while Self-BLEU is the average BLEU score of each generated text with other candidates as reference. High BLEU score means that $n$-grams in generated text are more likely to appear in real text, thus BLEU can be used as quality metric. Similarly, high Self-BLEU score means that generated text are similar to each other in terms of $n$-gram, thus Negative Self-BLEU (NSBLEU as abbreviation) can be used as diversity metric.

The expression of BLEU on a candidate set $C$ is:

where $BP$ is the Brevity Penalty which penalizes short sentences, and $M$ denotes the maximum $n$-gram order. $p_{n}$ is a precision term, which measures the proportion of grams in the candidate set that also appear in the reference set. BLEU is the geometric mean of $p_{n}$ for all $n\leq M$, multiplied by a penalty term.

The expression of BLEU does not seem to satisfy the general form of quality/diversity defined in Section 3.1. However on some special case, the general form is still satisfied, upon which we show some symptoms indicating the incompatibility of BLEU-NSBLEU. Assume the lengths of text are all $1$, so that $M=1$ and $BP\equiv 1$. In this case, BLEU contains only one term, i.e. $\mathrm{BLEU}=p_{1}$. Then for candidate set $C$ and reference set $R$, the expectation of BLEU and NSBLEU over generated distribution $Q$ and real distribution $P$ would be

Such expressions satisfy the general form with

The condition in Theorem 3 would be satisfied if and only if $|R|=1$ and $|C|=2$, which becomes $f(x)=x$ and $g(x)=-x^{2}$. However, the size of reference set $|R|$ is usually far more than $1$, under which cases the BLEU-NSBLEU metric pair would be divergence-incompatible.

Though above analysis is done on a special case, such results imply a potential incompatibility for general BLEU-NSBLEU metric pairs. We will confirm this incompatibility by an empirical approach in Section 6.

To avoid possible misleading conclusions in practice, we suggest to use diversity-compatible quality-diversity metric pair.

Since the real probability $P(x)$ is required in $U(Q;P)$ under the general form in Section 3.1, calculation of most quality metrics are intractable on real text data. The only exception is the case with $f(x)=x$, paired with $g(x)=-x^{2}$. The linearity of $f$ can avoid the explicit form of $P(x)$ by sampling from real data, i.e. $U(Q)=\mathbb{E}_{x\in P}\ Q(x)$. We name the corresponding quality metric as Coverage Rate (CR), and diversity metric as Negative Repetition Rate (NRR). Even so, we observe a large variance while estimating CR and NRR on real text data. This is mainly because of the extremely large space of text of $N=|V|^{L}$. Therefore, estimations of CR/NRR are highly inaccurate in the text space.

We thus suggest to calculate CR-NRR in $n$-gram space rather than in text space. Derive the $n$-gram distribution $Q_{g}$ and $P_{g}$ from text distribution $Q$ and $P$, so that

where $S_{n}$ denotes the set of all possible $n$-grams. In practice, $Q_{g}$ and $P_{g}$ can be estimated by the empirical distribution, i.e. count the number of target $n$-grams and divide by the total number. Note that if calculated by the longest $n$-gram with $n=L$, $\mathrm{CR}_{n}$ and $\mathrm{NRR}_{n}$ would exactly recover the original CR and NRR metric in text space, thus can be viewed as a generalized form. In the rest of this paper, we use CR-NRR as a default notation in the $n$-gram space unless explicitly stated.

In the $n$-grams space, calculation of metric pairs with other $f$/$g$ functions also becomes possible. However, metrics such as LL-SE suffer from another smoothing problem on real text data, i.e. their values go to infinity if some $n$-grams do not appear in candidate set or reference set. Therefore, we still suggest to use CR-NRR as a first choice.

Though there is a conversion from the text space to the $n$-gram space, CR/NRR can still reflect quality/diversity. The $\mathrm{CR}_{n}$ metric measures the average probability for an $n$-gram in candidate set to appear in the reference set, thus is an indicator of quality. Similarly, $\mathrm{NRR}_{n}$ measures the average probability for an $n$-gram to appear again in two consecutive sampling processes over the candidate set, thus is an indicator of diversity.

We then check the divergence-compatibility of CR-NRR evaluation. Firstly, CR-NRR is divergence-compatible w.r.t. distributions in the $n$-gram space, according to Theorem 3. We name the corresponding divergence metric as CR-NRR Divergence (CND), where

and

Secondly, CR-NRR is also divergence-compatible w.r.t. distributions in the text space. Assume $Q=P$ is dominated by $Q^{\prime}$ under CR-NRR evaluation, which means $Q_{g}=P_{g}$ would also be dominated by $Q^{\prime}_{g}$. This cause contradiction with the compatibility in $n$-gram space, so the compatibility in text space also holds.

In addition to the divergence-compatibility property, CR-NRR is also easy to acquire. It does not require the explicit value of $P(x)$ or $Q(x)$, thus can be applied on implicit models similarly to BLEU-NSBLEU. Moreover, the time complexity of CR-NRR algorithm is $O(m+n)$, which is much lower than BLEU-NSBLEU with $O(m\cdot(m+n))$, where $m$ and $n$ denote the size of candidate and reference set respectively. To conclude, we suggest to use CR-NRR in $n$-gram space for quality-diversity evaluation, instead of BLEU-NSBLEU.

We first run experiments on synthetic data rather than real text data, in order to get the precise values of all metrics. Under this setting, the information of generated distribution $Q$ and real distribution $P$ are explicitly given in advance, thus eliminates the possible variance from sampling. The synthetic data are texts with length $L$ using a pseudo vocabulary $V$. We construct the real distribution using an oracle LSTM model as in SeqGAN (Yu et al., 2017), whose weights are randomly sampled from a gaussian distribution with $\mu=0$. Different standard deviation $\sigma$s are applied to get several synthetic real distributions with different levels of entropy, i.e. distribution with smaller $\sigma$ is more flat and of higher entropy, and distribution with larger $\sigma$ is more sharp and of lower entropy.

Calculation of QDisc and DRate can be achieved by a simple binary-search algorithm if the exact form of Pareto-frontier is known. However for BLEU-NSBLEU metric pair, the frontier is unknown since Theorem 2 cannot be applied in this case. Consequently, we opt to used an optimization-based method for the estimation of QDisc. We try to solve the following optimization problem using stochastic gradient descent (SGD) with momentum:

where $\lambda$ is a penalty term to discourage the case where divergence is lower than real distribution $P$. We set $\lambda=2.0$ in our experiments. So that $\mathrm{QDisc}=U(Q^{*})-U(P)$, and the denominator in DRate is also calculated through such optimization-based method.

For BLEU metric with candidate set size $m$ and reference set size $n$, the expectation can be directly calculated by

The time complexity (number of terms) of such calculation is $O(|V|^{L\cdot(m+n)})$. This is intolerable for above optimization problem even in text space of normal size. As a result, we set $|V|=4,L=3,m=1,n=2$, and apply SGD under the Tensorflow framework¹¹1Slight increase of any parameter will consume intolerably more time, and is not necessary for the conclusions..

We use CN-n and BS-n as abbreviation for CR-NRR and BLEU-NSBLEU with $n$-gram, respectively. We report the QDisc and DRate of BLEU-NSBLEU in Table 1. Note that the reported QDisc values are corresponding lower bounds, since the optimization-based method does not guarantee a global optimum. These non-zero QDisc values provide a clear support for the incompatibility of BLEU-NSBLEU. We can also see that such discrepancy is significant on some cases, e.g. $\mathrm{QDisc}>0.02$ and $\mathrm{DRate}=9.41\%$ for BS-2 on data with $\sigma=0.5$. A QDisc value of 0.02 means that, we cannot surely claim that a model is better than another when the quality gap is below 0.02, which is already a clear gap for BLEU. We also run similar experiments for CR-NRR. However, no positive lower bound is observed, which is in accordance with our theory.

Significance of quality discrepancy varies on different cases, thus we care about the discrepancies on real text data. We use two public datasets, MSCOCO Image Caption dataset (Chen et al., 2015) and EMNLP2017 WMT News dataset²²2http://statmt.org/wmt17/translation-task.html. We use 50,000 sentences as candidate set and another 50,000 as reference set for each dataset ³³3See supplementary material for detailed configurations..

To provide an estimation of QDisc and DRate, we manually construct a family of strong models. We mix the empirical distribution $\tilde{P}$ with truncated uniform distribution $M$ under different proportions, i.e. $Q=(1-\epsilon)\cdot\tilde{P}+\epsilon\cdot M$. During text generation, a random text from reference set is sampled with probability $1-\epsilon$, otherwise a text with random tokens of length $L^{\prime}$ is constructed with probability $\epsilon$. We try both $L^{\prime}=5$ and $L^{\prime}=L$, and report the case with larger QDisc value.

We estimate QDisc by a linear interpolation between two closest points on the curve w.r.t. quality of real data. For the denominator of DRate in BLEU-NSBLEU, we use $1.0$ directly, since $\mathrm{BLEU}=1$ is reached for highest quality with $\epsilon=0.0$, and $\mathrm{BLEU}\approx 0$ for highest diversity with $\epsilon=1.0$. For CR-NRR, CR goes to $0$ when diversity is maximized with $\epsilon=1.0$. As for the maximal value of CR, we estimate it by using a single reference sentence as candidate and select the one with maximal CR value.

For a clearer view of the significance of quality discrepancy, we introduce two additional metrics: Self-Ratio and Ref-Ratio. Self-Ratio calculates the ratio between QDisc and the quality of candidate set. Ref-Ratio calculates the ratio between QDisc and the quality difference of $\epsilon=0.0$ and $\epsilon=0.2$. The evaluation results of BLEU-NSBLEU and CR-NRR with $3$-gram under $L^{\prime}=5$ are shown in Figure 2.

We can see that real data stays close to the CR-NRR curve, while a much larger gap is observed between real data and the BLEU-NSBLEU curve. We give the values of QDisc, DRate, Self-Ratio, and Ref-Ratio in Table 2. BLEU-NSBLEU shows a significant incompatibility, by QDisc values ranging from 0.032 to 0.211. Such huge discrepancy in BLEU is unbearable in real applications, e.g. we cannot claim a model is better than another even if it achieves higher NSBLEU and significantly higher BLEU. As a result, we suggest not to use BLEU-NSBLEU in order to avoid misleading conclusions. CR-NRR also shows a small positive discrepancy, this is due to the inevitable difference between the empirical distributions of candidate set and reference set. However, discrepancy caused by such distribution difference is generally much smaller than BLEU-NSBLEU. We also observe that DRate grows quickly as $n$-gram becomes longer for CR-NRR, thus we suggest to use CR-NRR with short $n$-gram such as CN-2 or CN-3.

Next we show how CR/NRR/CND behave on real text data. We apply temperature sweep on an RNN-based language model (RNNLM) pre-trained by maximum likelihood estimation, which is a quick way to get a family of models with quality-diversity tradeoff according to works of Caccia et al. (2018). The RNNLM consists of an embedding layer, an LSTM layer, and a fully-connected output layer. The embedding dimension and number of hidden nodes are all set to 128. We train the model using Adam (Kingma & Ba, 2014) optimizer with learning rate $0.001$ by 30 epochs. As temperature $t$ grows, the model becomes more close to uniform, so that quality decreases and diversity increases, and minimal divergence is taken near $t=1.0$. Results are shown in Figure 3, where we can see CR/NRR/CND are representative for quality/diversity/divergence respectively, which clearly fit our expectations. Therefore, we suggest to use CR-NRR for quality-diversity evaluation.