Title: EXPLORING THE PARETO-OPTIMALITY BETWEEN QUALITY AND DIVERSITY IN TEXT GENERATION

Abstract: Quality and diversity are two essential aspects for performance evaluation of text generation models. Quality indicates how likely the generated samples are to be real samples, and diversity indicates how much differences there are between generated samples. Though quality and diversity metrics have been widely used for evaluation, it is still not clear what the relationship is between them. In this paper, we give theoretical analysis of a multi-objective programming problem where quality and diversity are both expected to be maximized. We prove that there exists a family of Pareto-optimal solutions, giving an explanation of the widely observed tradeoff behavior between quality and diversity in practice. We also give the structure of such solutions, and show that a linear combination of quality and diversity is sufficient to measure the divergence between the generated distribution and the real distribution. Further, we derive an efficient algorithm to reach the Pareto-optimal solutions in practice, enabling a controllable quality-diversity tradeoff.

1. INTRODUCTION:

Text generation is an essential task for many NLP applications, such as machine writing (Zhang et al., 2017) , machine translation (Bahdanau et al., 2014) , image captioning (Rennie et al., 2017) and dialogue system (Li et al., 2017) . Recently, lots of neural generation models have been proposed and gained increasing attentions (Yu et al., 2017; Fedus et al., 2018; Chen et al., 2018) . However, it is still an open problem which metrics are suitable to evaluate the performance of text generation models. Among the metrics used in practice, generation quality and diversity are two most widely considered aspects. High generation quality requires the model to generate realistic samples, i.e. generated samples are free of grammatical or logical errors. While high generation diversity requires the model to generate diverse samples, i.e. generated samples are less likely to be duplicate and contain diverse unique patterns. This work is motivated by three questions about quality and diversity: Q1: What is the relationship between quality and diversity? Besides being evaluation metrics, high generation quality and diversity have also been critical requirements in many applications (Li et al., 2015; Xu et al., 2018; Zhang et al., 2018b) . However, many researches find that quality and diversity show a tradeoff behavior among well-trained models (Lu et al., 2018; Gao et al., 2019; Hashimoto et al., 2019) . Though in accordance with intuition, such observations stay empirical and lack of theoretical support. Q2: Is there any gap between quality-diversity evaluation and the divergence objective? The original objective of training a text generation model is to approximate the probability distribution of real text data, which is equivalent to minimizing a divergence between model distribution and the real distribution (Mikolov et al., 2010) . Since divergence would be intractable if the text probabilities are not modeled explicitly, some researchers opt to use quality and diversity metrics instead as a remedy (Fedus et al., 2018; Chen et al., 2018) . However, it is not clear whether it is sufficient to approximate divergence by integration of quality and diversity. Q3: How to achieve optimal solutions in practice when quality and diversity are both required to be maximized? Quality or diversity may be focused more than another in some applica-tions. Though researchers have proposed different methods to tackle different application scenarios (Zhang et al., 2018a; Li et al., 2015; Zhang et al., 2018b) , it is still an open problem how to maximize one aspect while keeping another above some threshold, i.e. achieving a Pareto-optimal solution.

In this paper, we try to answer the above three question under the unconditional text generation setting. We first give a general definition of quality and diversity, and then study a Multi-Objective Programming(MOP) problem which maximizes quality and diversity simultaneously. Answers are given by performing theoretical analysis over this MOP problem:

A1: Quality and diversity truly act as a tradeoff. We prove there exists a family of Paretooptimal solutions for the MOP problem, which constitutes the Pareto-frontier. For each Pareto-optimal solution Q, there exists another Pareto-optimal solution Q , such that either quality or diversity of Q is higher than Q. This indicates that a quality-diversity tradeoff exists among all these optimal solutions, and non-optimal solutions have the potential to be improved over both metrics.

A2: Quality and diversity can be combined to be a divergence. We prove that a linear combination of some paired quality and diversity constitutes a divergence metric between the generated distribution and the real distribution, including some widely recognized quality and diversity metrics as special cases.

A3: Optimal solutions over both quality and diversity can be achieved by our proposed QDTC method. We prove that the optimal solutions of the MOP problem can be obtained by optimizing a designed objective function, and propose a QDTC algorithm which can be implemented efficiently like the widely used maximum likelihood estimation method. Experiments show that this algorithm achieves controllable quality and diversity tradeoff on both synthetic data and real MSCOCO dataset.

2. RELATED WORK:

To evaluate the performance of text generation models, many evaluation metrics are designed for different purposes. Early neural text generation models use Perplexity(PPL) to show how much a language model fit the training data (Mikolov et al., 2010) , and this metric is still adopted in recent works (Zhang et al., 2018a; Fedus et al., 2018) . PPL is correspondent to the Kullback-Leibler(KL) divergence, thus is a metric showing the difference between model distribution and the real distribution. However, Chen et al. (1998) show that PPL does not seem to correlate well with the task performance in real applications. Moreover, PPL cannot be calculated if text probabilities are not explicitly given. Therefore, the quality and diversity of generated text are further considered as complementary metrics.

For quality metrics, the evaluation is closely related to the ground truth distribution. Yu et al. (2017) propose to use Negative Log-Likelihood where the real distribution is known in advance, which measures the average log-probability of generated samples over the real distribution. If the real distribution is not explicitly given, BLEU (Papineni et al., 2002) and ROUGE (Lin & Och, 2004) are usually applied, which measure the n-gram overlap between generated samples and a set of reference ground truth samples. For diversity metrics, the evaluation is performed within the model itself. Li et al. (2015) proposed Distinct-n as diversity metric, which calculates the ratio of unique n-grams in generated samples. Zhu et al. (2018) proposed another metric called Self-BLEU, which is similar to BLEU score but use generated samples as reference set. In this work, we assume the real distribution P and the model distribution Q are explicitly given. To perform theoretical analysis, we propose a general form of quality and diversity, which is in accordance with above proposed metrics.

Although the tradeoff behavior between quality and diversity has not been well studied theoretically, there have been some works trying to control such tradeoff. The temperature-based method is the most widely used one (Hashimoto et al., 2019; Fan et al., 2018; Lau et al., 2017) . By dividing the probability vector by a temperature factor t before softmax operation, one can achieve higher quality with smaller t and higher diversity with larger t during the decoding stage. Another method to control the tradeoff during training is proposed by Li et al. (2019) . With different hyper-parameters in the objective function, the trained model can get higher quality at the expense of lower diversity.

Whether these methods can achieve optimal solutions under quality and diversity is still not clear, and the conclusions will be discussed in this paper.

3. DEFINITION OF QUALITY AND DIVERSITY:

Currently there is no unified definition for quality and diversity in text generation, which poses great challenges for further theoretical studies. In fact, it is not easy to define a general form of quality and diversity due to various understandings of these two aspects. In this paper, we try to give a general form of quality and diversity in a mathematical view, though it may not be comprehensive enough to cover all possible understandings.

3.1. A GENERAL FORM OF QUALITY AND DIVERSITY:

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 , • • • , P N ) and Q(x) = (Q 1 , Q 2 , • • • , 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 Yu et al. ( 2017) and Nie et al. (2018) , the Log-Likelihood(LL) is used as the quality metric, where LL(Q; P ) = E x∼Q log P (x). Following this idea, we propose a general form of quality, i.e., U (Q

; P ) = E x∼Q f u [P (x)],

where f u [P (x)] is a function over P (x).

Similarly, the Diversity of a text generation model measures how much difference there are among those generated texts. From the viewpoint of information, Shannon-Entropy(SE) of Q(x) can be used as a natural diversity metric, where

SE(Q) = -E x∼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 -E x∼Q Q(x). Summarizing these two different understandings, we obtain a general form of diversity, i.e.

V (Q) = -E x∼Q f v [Q(x)].

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

U (Q) = U (Q; P ) = E x∼Q f u [P (x)] = N i=1 Q i • f (P i ), V (Q) = -E x∼Q f v [Q(x)] = N i=1 g(Q i ),

where f u (x) is denoted as f (x) and -fv(x)

x is denoted as g(x).

3.2. THE RATIONALITY OF QUALITY AND DIVERSITY:

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. Generating more samples with higher real probability yields higher overall quality; 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 = (Q 1 , . . . , Q i + , . . . , Q j -, . . . ), U (Q ) > U (Q) for any ∈ (0, Q j ). 2. If Q i ≥ Q j , then for Q = (Q 1 , . . . , Q i + , . . . , Q j -, . . . ), V (Q ) < V (Q) for any ∈ (0, Q j ).

Then we can obtain the conditions of f and g by the following theorem: Theorem 1. The following conditions are both sufficient and necessary to satisfy the properties 1-2: For any x 1 , x 2 s.t. x 1 > x 2 > 0 and x 1 + x 2 ≤ 1, we have f (x 1 ) > f (x 2 ) and g (x 1 ) < g (x 2 ).

According to Theorem 1, it is necessary for f (x) to be strictly monotonically increasing and g(x) to be strictly concave for x ∈ (0, 1 2 ). For simplicity, we only consider the cases where such properties hold for x ∈ (0, 1), thus get a sufficient condition: i.e. f (x) is strictly monotonically increasing for x ∈ (0, 1), and g(x) is strictly concave for x ∈ (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 list some speical cases under this condition, which will be used as examples in the following analysis. For quality metrics, we use Log-Likelihood(LL) with f (x) = log x and Coverage-Rate(CR) with f (x) = x. For diversity metrics, we use Shannon-Entropy(SE) with g(x) = -x log x and Negative Repeat-Rate(NRR) with g(x) = -x 2 .

4 THE PARETO-OPTIMALITY

4.1. THE MOP PROBLEM:

To explore the relationship between quality and diversity, we consider the following Multi-Objective Programming(MOP): max

Q (U (Q),V (Q)) s.t. N i=1 Q i = 1 ∀i, -Q i ≤ 0

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: Definition 1. For two distributions Q and Q , if one of the following conditions are satisfied, we say that Q is dominated by Q .

1. U (Q ) > U (Q) and V (Q ) ≥ V (Q); 2. U (Q ) ≥ U (Q) and V (Q ) > V (Q).

A solution Q is called a Pareto-optimum if it is not dominated by any Q . The set containing all the Pareto-optima is called the Pareto-frontier.

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 Paretofrontier 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, thus there exists a family of optimal solutions. To verify the tradeoff behavior between quality and diversity, we need to prove the existence of such a family of optimal solutions, thus the structure of the Pareto-frontier under a non-uniform P is what we care about.

4.2. THE PARETO-FRONTIER:

We try to show what the Pareto-optima look like by giving the following theorems: Lemma 1. If Q is a Pareto-optimum, the following conditions are satisfied: if P i > P j , then

Q i ≥ Q j ; if P i = P j , then Q i = Q j .

Theorem 2. For a distribution Q, if P is not uniform, then:

(1) The following condition is both sufficient and necessary for Q to be a Pareto-optimum: there exist real value w ≤ 0 and b that for any i = 1, . . . , N , there is where (3) If we denote a Pareto-optimum Q as Q(w), then for any

EQUATION

EQUATION

w 1 < w 2 : if w 1 , w 2 ∈ [B, 0], there is Q(w 1 ) = Q(w 2 ) and U (Q(w 1 )) > U (Q(w 2 )), V (Q(w 1 )) < V (Q(w 2 )); if w 1 , w 2 ∈ (-∞, B], there is Q(w 1 ) = Q(w 2 ); where B = g ( 1 M )-g (0) f (Pm 1 )-f (Pm 2 )

, and

P m1 = max i P i , P m2 = max Pi =Pm 1 P i , M = #{i|P i = P m1 }, # denotes the size of a set.

Lemma 1 shows that the optimal distribution is order-preserving, and Theorem 2 further gives the structure of Pareto-optima. Since different ws lead to different distributions, 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. Now we can see that, if we want to maximize quality and diversity at the same time, these two metric acts as a tradeoff. 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.

We show the result of Theorem 2 here on the special cases used in Section 3.2. We pair LL with SE, and CR with NRR. For the LL-SE metrics, the Pareto-optima can be written as

Q i = P β i Z , Z = N i=1 P β i , β ≥ 0,

we have w = -β, and b = 1 + log Z. This is exactly the case used in Li et al. (2019) . For the CR-NRR metrics, the Pareto-optimum can be written as

Q i = max(P i + γ, 0) Z , Z = N i=1 max(P i + γ, 0), γ > -max i P i ,

we have w = -2 Z , and b = -2γ Z . An illustration of the Pareto-frontier on a toy dataset is shown in Figure 1 .

4.3. RELATIONSHIP WITH DIVERGENCE:

Besides quality and diversity, the direct difference between model distribution Q and real P is also considered in practice, which is usually evaluated by Divergence metrics such as the Kullback-Leibler divergence. Since calculation of divergence is usually intractable, quality and diversity are often used together as a remedy. However, it is still not clear whether combining quality and diversity is sufficient for divergence evaluation.

We show that a linear combination of quality and diversity constitute a divergence metric if function f and g are carefully chosen. Define a weighted sum of quality and diversity as

W (Q) = αU (Q) + (1 -α)V (Q), α ∈ [0, 1), then D(P ||Q) = W (P ) -W (Q)

would become a divergence metric as long as Q = P is a Pareto-optimum, as shown in the following Theorem: Theorem 3. The following condition is both sufficient and necessary for Q = P to be in the Paretofrontier for any P : there exist w 0 ≤ 0 and b 0 that

g(x) = w 0 f (x)dx + b 0 x.

(2)

If the above condition is satisfied, then Q = P corresponds to a Pareto-optimum with w = w 0 and b = b 0 , and it is the only distribution that maximize

W (Q) = αU (Q) + (1 -α)V (Q) with α = w0 w0-1 , and D(P ||Q) = W (P ) -W (Q) becomes a divergence metric.

We find that if quality and diversity metrics are carefully chosen, namely g is the integral of a affine transformation of f , we can get a divergence metric by a linear combination of these two metrics. 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. Illustration of such phenomenon with mismatched metrics is shown in Appendix A.7. 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.

The special cases listed in Section 3.2 would satisfy the condition in Theorem 3 if LL is paired with SE and CR with NRR. For the LL-SE metrics,

D(P ||Q) = 1 2 N i=1 Q i • log Qi Pi , which is exactly the Reverse KL divergence if the constant 1 2 is ignored. For the CR-NRR metrics, D(P ||Q) = 1 3 N i=1 (Q i -P i ) 2

, which measures the sum of squared difference among all probabilities.

5. OPTIMIZATION OF THE MOP PROBLEM:

Though the original goal is to recover real distribution for text generation models, higher quality or higher diversity may become the primary requirement in real applications. As a result, it is meaningful to achieve other Pareto-optima besides recovering the real distribution, leading to a controllable quality-diversity tradeoff.

One widely used method for quality-diversity tradeoff control is introducing a temperature factor to the decoding stage of neural decoders. However, such temperature-based method violates the order-preserving requirements in Lemma 1, thus cannot achieve general Pareto-optima due to the sequential nature of text(see Appendix A.8 for explanation). In fact, it is non-trivial to achieve general Pareto-optima through such post-editing methods, i.e. train a model with Q = P and then modify the decoding strategy.

As a result, we seek methods which can get the Pareto-optimal model immediately after training. In real applications, the real probability P (x) is never explicitly given, thus a unified objective such as W (Q) in Section 3.2 is not feasible for training a model. So we will give a method to achieve the Pareto-optima without knowing P .

5.1. TRAINING OBJECTIVE:

Borrowing the idea from the DDR methodLi et al. ( 2019), we also use a modified training objective while keeping the algorithm similar to the widely used maximum likelihood estimation method. For a Pareto-optimum

Q satisfying Q i = ĝ -1 [w • f (P i ) + b], the corresponding training objective is max Q E x∼P h[Q(x)], h(x) = c f -1 [ g (x)-b w ] dx, c > 0.

(3) Since f -1 has no definition outside of [f (0), f (1)], we use f -1 as an expansion, and the value outside of [f (0), f (1)] can be defined arbitrarily as long as f -1 is monotonically increasing and strictly positive. Theorem 4 gives the condition when such f -1 can be constructed and guarantees that we can get a Pareto-optimum by solving the above problem. In the following discussions, we further assume that f and g satisfy the conditions in Theorem 3 in order to get reasonable qualitydiversity metrics.

Theorem 4. There exists f -1 to make h concave, if and only if

lim x→0 + f (x) = -∞. If h(x)

is concave w.r.t x ∈ (0, 1), then with a objective defined as Equation 3, the optimal solution is a Pareto-optimum defined as Equation 1.

The parameter w and b in the expression of Pareto-optima provides a smooth way to control the quality-diversity tradeoff according to Theorem 2. Therefore, we can achieve higher quality or diversity by tuning w or b accordingly in Equation 3.

Since we do not know the value of both w and b for most of the time, such training objective cannot be applied directly to general cases. However, there are some cases which is still tractable. We observed that there is a free parameter c in the expression of h(x). Since changing c does not change the solution, so if w or b could be separated from h(x) and constitute a factor, we can get a feasible objective using another parameter. For example, if h(x, w, b, c

) = h 1 (x, w) • h 2 (w, b) • c, we can set c = h -1 2 (w, b) so that h(x, w, b, c) = h 1 (x, w).

In this way, b can be neglected and we only need to care about w. According to Theorem 5, if f is the logarithmic function or the power function, then b or w can be neglected respectively.

Theorem 5. If f -1 = f -1 , then the following condition is both sufficient and necessary for h(x, w, b, c) to be decomposed as h

(x, w, b, c) = h 1 (x, w) • h 2 (w, b) • c: there exist constant a and d such that f (x) = a • log x + d.

Also, the following condition is both sufficient and necessary for h(x, w, b, c) to be decomposed as

h(x, w, b, c) = h 3 (x, b) • h 4 (w, b) • c: there exist constant a and d such that f (x) = d • x a .

Theorem 5 provides a necessary condition for h to be used in practice, but we still need f to be monotonically increasing and h to be concave for a sufficient condition. Since an affine transformation of f is equivalent to f in terms of optimal solutions, we only consider the non-trivial cases in Theorem 5, including f (x) = log x and f (x) = x a . To simplify the conclusion, we assume g (x) = -f (x) which means w 0 = -1 and b 0 = 0 in Theorem 3.

For the case of logarithmic function f (x) = log x, we have h (x) = x 1 w • e b w • c. And for the case of power function f (x) = x a where a > 0, we have h

(x) = (x a + b) -1 a • (-w)

1 a • c. This case does not satisfy the concavity condition, thus should be discarded. However, the continuity holds for f (x) = -x a where a < 0, we have h

(x) = (x a -b) -1 a • (-w) 1 a • c.

As such, we can select an appropriate c to diminish the factor w or b. Thus in practice we can use

h (x) = x 1 w , or h (x) = (x a -b) -1 a , a < 0.

The derivative is sufficient for the gradient calculation, so it is not necessary to know the exact form of h(x).

5.2. ALGORITHM:

We show how to do the optimization using the expression of h . For a model Q θ parameterized by θ, denote the loss function as

L = -E x∼P h[Q θ (x)

]. The gradient w.r.t θ at current value θ = θ 0 would be Sample M examples {x i } M i=1 from D.

∇ θ L| θ=θ0 = -E x∼P h [Q θ (x)] • ∇ θ Q θ (x)| θ=θ0 = -E x∼P h [Q θ (x)] • Q θ (x) • ∇ θ log Q θ (x)| θ=θ0 = -∇ θ E x∼P h [Q θ0 (x)] • Q θ0 (x) • log Q θ (x)| θ=θ0 .

5::

θ 0 ← θ.

6::

Calculate T (x i ) for each i using Equation 4.

7:

θ ← θ + α • ∇ θ 1 M M i=1 T (x i ) • log Q θ (x i ) 8: until convergence Table 1: A summary of the two QDTC methods used in our experiments. Method f (x) g(x) h (x) U (Q) V (Q) QDTC-logarithm log x -x log x x 1 w N i=1 Q i log P i - N i=1 Q i log Q i QDTC-reciprocal -1 x log x 1 x -b - N i=1 Qi Pi N i=1 log Q i Let T (x) = h [Q θ0 (x)] • Q θ0 (x), (4) then ∇ θ L| θ=θ0 = -∇ θ E x∼P T (x) • log Q θ (x)| θ=θ0 .

(5) Now the model can be optimized using Equation 5. We summarized this Quality-Diversity Tradeoff Control(QDTC) algorithm as Algorithm 1:

Note that when we use h (x) = x 1 w and constrain w in (-∞, -1), QDTC method would be equivalent to the Differentiated Distribution Recovery(DDR) method used by Li et al. (2019) , thus DDR is a special case of our QDTC.

6. EXPERIMENTS:

In this section, we evaluate our proposed QDTC method on synthetic data as well as MSCOCO Image Caption dataset (Chen et al., 2015) , compared with the temperature-based method.

For the temperature-based method, we pre-train the model with Maximum Likelihood Estimation(MLE), and then tune the temperature t for different output during decoding.

For our QDTC method, we use two pairs of metrics: the logarithm ones where f (x) = log x, g(x) = -x log x; and the reciprocal ones where f (x) = -1

x , g(x) = log x. We summarize the details of these two cases in Table 1 . Although QDTC can be used without any pre-training, we find it would converge faster and more stably if we pre-train the model with MLE. As a result, we also use MLE pre-training for QDTC in all of our experiments.

6.1. EXPERIMENTS ON SYNTHETIC DATA:

In the synthetic data, the real probability P is explicitly given, so we can evaluate how close a generated model Q is to the Pareto-frontier. Specifically, we define a sequential data space with vocabulary size 10 and length 3. Thus the total number of feasible texts is N = 10 3 . The synthetic data are generated using a randomly initialized oracle model, whose parameters are known in advance. In our experiments, this model contains an embedding layer with dimension 32, an LSTM layer with 32 hidden nodes, and a fullyconnected(FC) output layer with 10 hidden nodes.

The text generation model share the same structure with the oracle model, but use learned parameters. To guarantee the consistency between training and test, we do not construct a dataset D in advance. Instead, we sample data from the oracle model directly whenever data are needed. The quality and diversity of the trained model are computed by the corresponding metrics in the logarithm case and the reciprocal case as shown in Table 1 .

As we can see from the results shown in Figure 2 , all methods show smooth curves from upper left to lower right under the evaluation of quality and diversity, indicating a tradeoff relation between the two metrics. The curves of our QDTC methods closely fit their corresponding ground truth curve, which means Pareto-optima are well obtained. The curve of temperature-based method gets close with ground truth at two points: the middle point where t = 1 and the leftmost point where t → ∞. This makes sense because temperature-based method can achieve Q = P with t = 1 and Q becomes uniform when t tends to +∞. However at other points, the discrepancies grow much larger, indicating a failure to achieve other Pareto-optima.

6.2. EXPERIMENTS ON MSCOCO DATASET:

To show the effectiveness of QDTC on real text data, we run experiments on the MSCOCO Image Caption dataset. Our empirical settings are exactly the same as Guo et al. (2017) , including the preprocessing and the data separation. Specifically, only the captions are used as text data, and sentences which contain words with frequency lower than 10 are removed. 80,000 unique sentences are sampled as training set, and another 5,000 unique sentences are used as test set. The final vocabulary size is 4,840 and maximum text length is 32.

The architectures of the text generation models are similar as that on synthetic data. The embedding dimension and number of LSTM hidden nodes are set to 128, and the number of FC hidden nodes is 4,840.

Since the ground truth distribution P is unknown under this setting, the calculations of our general defined quality and diversity metrics may become intractable. Fortunately, the CR-NRR metrics can be approximated by sampling due to the linearity of f : Therefore, the expectation over Q in NRR can be directly taken on generated samples, while the expectation over P in CR can be calculated by sampling from the test set.

CR(Q; P ) = N i=1 Q i • P i = E x∼P Q(x), N RR(Q) = - N i=1 Q 2 i = -E x∼Q Q(x).

Besides using CR and NRR as metrics, we also evaluate our results by the widely used quality and diversity metrics in application, i.e. BLEU-n (Papineni et al., 2002) and Distinct-n (Li et al., 2015) . BLEU-n measures the degree of n-gram overlap between generated text and a reference text set, i.e. the test set. Distinct-n calculates the ratio of unique n-grams over all n-grams in generated text.

Here we set n = 3. The experimental results are shown in Figure 3 .

From the results, we can see that with the change of w or b, our QDTC methods show smooth control of the quality-diversity tradeoff under CR-NRR and even BLEU-Distinct metrics. Therefore, QDTC can be applied in some real applications where quality or diversity is preferred while keeping another metric above a threshold. QDTC methods do not show consistent superiority over temperaturebased method in the figure, this is because the metrics used in the real data are different from the corresponding theoretical metrics in QDTC. Nevertheless, QDTC performs better than temperaturebased method in many cases.

7. CONCLUSION AND DISCUSSION:

In this paper, we mainly focus on the theoretical study of quality and diversity in text generation. We give a general definition of quality and diversity, and then study the MOP problem where quality and diversity are both required to be maximized. Three main conclusions are obtained by our study:

Firstly, quality and diversity show a clear tradeoff relation in theory. Therefore, we suggest using both metrics for evaluation in real application instead of focusing only one metric, to get a comprehensive understanding of a specific text generation model.

Secondly, a linear combination of some paired quality and diversity is equivalent to a divergence. This theoretical result indicates that quality and diversity metrics should be carefully chosen in practice, to avoid the mistake that ground-truth distribution is non-optimal.

Thirdly, an algorithm named QDTC is proposed to efficiently optimize both quality and diversity.

Experimental results show that QDTC achieves good approximation of the Pareto-optima on both synthetic data and real MSCOCO data. In applications where one metric is favored more than another, a good model should be able to achieve the required Pareto-optimal solution. We can see that our proposed QDTC gives a feasible example of how to achieve a controllable quality-diversity tradeoff in this direction.

In the future, we would like to study the relationship between quality and diversity under the conditional text generation settings. It is also anticipated to extend the conclusions to continuous data generation settings, such as image or video generation. 

A APPENDIX:

A.1 PRELIMINARIES Before starting the proofs, we first introduce some preliminaries on the constrained convex optimization problem. Assume f (x), c i (x), and h j (x) are continuous differentiable function define on R n , consider the constrained convex optimization problem defined as follows:

EQUATION

The optimal solutions for above problem are given by, as shown in the following theorem:

Theorem 6. Assume f (x) and c i (x) are convex, h j (x) are affine, and c i are strictly feasible (there exists one x satisfying c i (x) < 0 for all i). Define the Lagrange function as:

EQUATION

where α ≥ 0. Then the the following conditions are both sufficient and necessary for x to be a solution in problem 6.

EQUATION

The conditions in Equation 8 are called the Karush-Kuhn-Tucker(KKT) conditions.

A.2 PROOF OF THEOREM 1:

For property 1, from

U (Q ) -U (Q) = f (P i ) -f (P j ) = [f (P i ) -f (P j )] > 0, we get f (P i ) > f (P j ).

We then get the conclusion by setting x 1 = P i and x 2 = P j .

For property 2,

V (Q ) -V (Q) = [g(Q i + ) + g(Q j -)] -[g(Q i ) + g(Q j )] < 0 is true for any Q i > Q j . Denote C = Q i + Q j and r(x) = g(x) + g(C -x), then we have V (Q ) -V (Q) = r(Q i + ) -r(Q i ) < 0 for any Q i , . Since 0 < Q i < Q i + < 1, we need r (x) < 0 for x ∈ (0, 1).

Then, since r (x) = g (x) -g (C -x) < 0 is true for any 0 C -x < x < 1. Set x 1 = C -x and x 2 = x and we get g (x 1 ) < g (x 2 ) for any x 1 > x 2 > 0 and

x 1 + x 2 = Q i + Q j ≤ 1. A.3 PROOF OF LEMMA 1 If P i > P j , assume Q i < Q j , we can construct Q where Q k = Q k for all k = i, j and Q i = Q j , Q j = Q i . As such, V (Q ) = V (Q) but U (Q ) -U (Q) = (Q j -Q i )[f (P i ) -f (P j )] > 0. This means Q is dominated by Q , which conflicts with the fact that Q is a Pareto-optimum. So Q i ≥ Q j . If P i = P j , assume Q i = Q j ,

and we can further assume:

Q i > Q j . Again we construct Q where Q k = Q k for all k = i, j and Q i = Q j = Qi+Qj 2 . Surely we have U (Q ) = U (Q), and V (Q )-V (Q) = 2g( Qi+Qj 2 )-g(Q i )-g(Q j ). Since g is strictly concave, we have V (Q )-V (Q) > 0, which means Q is dominated by Q . This causes confliction, so Q i = Q j .

A.4 LEMMA 2 AND ITS PROOF:

This lemma is used to support the proof of Theorem 2 and Theorem 3.

Lemma 2. Assume α ∈ [0, 1) and W (Q) = αU (Q) + (1 -α)V (Q), then the distribution Q that maximize W (Q) satisfies Q i = ĝ -1 [w • f (P i ) + b], and w = α α-1 .

Define the optimization problem as follows:

min Q -α • U (Q) -(1 -α)V (Q) s.t. 1 - N i=1 Q i = 0 ∀i, -Q i ≤ 0

Again we first check that the prerequisites in KKT are all satisfied. -U (Q) is linear and -

V (Q) is convex w.r.t. Q ; 1 - N i=1 Q i is affine w.r.t. Q ; since all Q i can

be positive, so the inequalities are all strictly feasible. The Lagrange function is:

L(Q i , λ, ξ i ) = -α N i=1 Q i f (P i ) -(1 -α) N i=1 g(Q i ) + λ(1 - N i=1 Q i ) - N i=1 ξ i Q i , ξ ≥ 0

Apply KKT and we get the following conditions for a optimal solution: ∀i,

∂L ∂Q i = -αf (P i ) -(1 -α)g (Q i ) -λ -ξ i = 0, ∀i, -ξ i Q i = 0

For Q i = 0, there is ξ i = 0, so

Q i = g -1 [ α α -1 f (P i ) + λ α -1 ];

for

Q i = 0, there is ξ i > 0, so α α -1 f (P i ) + λ α -1 > g (0).

Denote w = α α-1 and b = λ α-1 and combine the two cases together, we get:

Q i = ĝ -1 [w • f (P i ) + b], w ≤ 0,

The above derivation is both sufficient and necessary, so we finished the proof.

A.5 PROOF OF THEOREM 2

We give the proofs for three conclusions individually.

A.5.1 CONCLUSION 1:

Here we only consider the case with U (Q) = max Q U (Q), and the case where U (Q) = max Q U (Q) will be incorporated into conclusion 3. We try to find a distribution Q with the highest diversity while quality is not lower than Q. Define a convex optimization problem as follows:

min Q -V (Q ) s.t. U (Q) -U (Q ) ≤ 0 1 - N i=1 Q i = 0 ∀i, -Q i ≤ 0

For Q to be a Pareto-optimum, it's both sufficient and necessary for Q to be a solution of above problem. Thus we try to solve this problem next.

We first check that the prerequisites in KKT are all satisfied.

-V (Q ) is convex w.r.t. Q ; 1 - N i=1 Q i is affine w.r.t. Q ; U (Q) -U (Q )

and -Q i are convex(linear) w.r.t Q ; since all Q i can be positive and U (Q) = max Q U (Q), so the inequalities are all strictly feasible. The Lagrange function is:

L(Q i , λ, η, ξ i ) = - N i=1 g(Q i ) + λ(1 - N i=1 Q i ) + η N i=1 (Q i -Q i )f (P i ) - N i=1 ξ i Q i , η, ξ ≥ 0

Apply KKT and we get the following conditions for a optimal solution: ∀i,

∂L ∂Q i = -g (Q i ) -λ -ηf (P i ) -ξ i = 0, η[U (Q) -U (Q )] = 0, ∀i, -ξ i Q i = 0

Since we need Q to be a solution, so ∀i, -g

(Q i ) -λ -ηf (P i ) -ξ i = 0, ∀i, -ξ i Q i = 0 For Q i = 0, there is ξ i = 0, so Q i = g -1 [-ηf (P i ) -λ]; for Q i = 0, there is ξ i > 0, so -ηf (P i ) -λ > g (0)

. Denote w = -η and b = -λ and combine the two cases together, we get:

Q i = ĝ -1 [w • f (P i ) + b], w ≤ 0,

where

ĝ -1 (x) = g -1 (x) if x < g (0), 0 if x ≥ g (0).

The above derivations are both sufficient and necessary, thus we finish the proof.

A.5.2 CONCLUSION 2:

For the second conclusion, we separate the proof into two parts: (1) b is correspondent to w;

(2) the monotonicity of b w.r.t. w.

(1) The sum of all Q i should be 1. Denote 

T (w, b) = N i=1 ĝ -1 [w • f (P i ) + b].

b = g (0) -w • f (max i P i ),

there is

w • f (P i ) + b ≥ w • f (max i P i ) + b = g (0), so T (w, b) = 0; when b = g ( 1 N ) -w • f (min i P i ), there is w • f (P i ) + b ≤ w • f (min i P i ) + b = g ( 1 N ), so T (w, b) ≥ 1.

From above analysis, the value of T can reach 0 or be greater than 1. So combining the monotonicity of T , there exists and only one b that satisfies T (w, b) = 1, leading to a rational distribution.

( 

(w) = - i∈S f (Pi) g {g -1 [w•f (Pi)+b(w)]} i∈S 1 g {g -1 [w•f (Pi)+b(w)]} .

Since g (x) < 0, so if f (x) < 0 for all x ∈ [0, 1], we can get b (w) > 0, thus b is strictly monotonically increasing w.r.t. w. Similarly, if f (x) > 0 for all x ∈ [0, 1], we can get b (w) < 0, thus b is strictly monotonically decreasing w.r.t. w.

A.5.3 CONCLUSION 3:

For the third conclusion, we also separate the proof into two parts: (1) the uniqueness of Q(w); (2) the monotonicity of U and V w.r.t. w.

(1) Since P is not uniform, so we can denote B, P m1 , P m2 as they are in the theorem. According to Lemma 1, since P m1 is the largest one, so the corresponding Q m1 is also the largest one, which means

Q m1 = ĝ -1 [w • f (P m1 ) + b] > 0. Thus we get w • f (P m1 ) + b < g (0)

. At the same time, because we can get Q i = Q m1 if P i = P m1 , so we can sum up all the largest Q i and get The requirement that Q = P in the Pareto-frontier is equivalent to the following condition: for any P , there exist w 0 ≤ 0 and b 0 that for any i, there is

M • Q m1 ≤ N i=1 Q i = 1,

P i = ĝ -1 [w 0 • f (P i ) + b 0 ].

This means, for any P i > 0, there is w 0 • f (P i ) + b 0 = g (P i ). Since f and g are both continuous, so

w 0 • f (0) + b 0 -g (0) = lim Pi→0 w 0 • f (P i ) + b 0 -g (P i ) = 0.

We can see w 0 • f (P i ) + b 0 = g (P i ) is also true for P i = 0. By solving this differential equation, we get

g(x) = w 0 f (x)dx + b 0 x.

Here b 0 can be any value because P i = g -1 [w 0 • f (P i ) + b 0 ] always lead to a plausible distribution P . Under this condition, we know that Q = P is the only distribution that maximize

W (Q) = αU (Q) + (1 -α)V (Q)

where α = w0 w0-1 according to Lemma 2. With the above conclusions, it is easy to check that D(P ||Q) = W (P ) -W (Q) ≥ 0 and D(P ||Q) = 0 if and only if Q = P , thus D(P ||Q) is a divergence metric.

A.7 ILLUSTRATION OF PARETO-FRONTIER WITH MISMATCHED METRICS:

We show in Figure 4 that the point Q = P is under the Pareto-frontier curve when quality and diversity metrics are not matched, i.e. the condition in Theorem 3 is not satisfied. We use the same toy dataset as in Figure 1 , but pair LL with NRR and CR with SE.

A.8 INSUFFICIENCY OF TEMPERATURE-BASED METHOD:

Temperature-based method for quality-diversity tradeoff is implemented through dividing the probability vector a by a temperature factor t before the softmax operation:

Q(x; t) = Sof tmax(a/t) = 1 Z (e a1/t , • • • , e a |v| /t ), Z = |V | i=1 e ai/t .

When the temperature is high (t → ∞), the distribution would be near uniform; and when the temperature is low (t → 0), the distribution would be sharp and assign Q(x) → 1 for x with largest P (x), and Q(x) → 0 for other x. However in text generation, this is applied for the conditional probability of each token given its prefix, i.e. P (x i |x 1:i-1 ), and is intractable to apply on the global probability P (x 1:L ).

We give an example showing that this method violates the requirements in Lemma 1, thus cannot be used to achieve general Pareto-optima. To be concrete, if the post-edited model distribution is Q, we construct a simple case that Q i > Q j while P i < P j for some i, j.

Assume the text length is 2, and the vocabulary is {a, b, c}. Then the real probability of a text sample x = (x 1 , x 2 ) would be P (x) = P (x 1 ) • P (x 2 |x 1 ). We assume P (x 1 ) = (0.5, 0.5, 0.0), P (x 2 |x 1 = a) = (0.4, 0.3, 0.3), P (x 2 |x 1 = b) = (0.5, 0.5, 0.0), then we have P (aa) = 0.2 < P (ba) = 0.25. However when the temperature t approaches 0, there would be Q(x 1 ) = (0.5, 0.5, 0.0), Q(x 2 |x 1 = a) = (1.0, 0.0, 0.0), Q(x 2 |x 1 = b) (0.5, 0.5, 0.0), so that Q(aa) = 0.5 > Q(ba) = 0.25.

This clearly violates the order-preserving nature of a Pareto-optimum, thus we can never get the full Pareto-frontier using the temperature-based method, no matter what f and g are.

A.9 PROOF OF THEOREM 4

We discuss the condition of f as conclusion 1 and the optimal solutions of the objective as conclusion 2.

A.9.1 CONCLUSION 1

Since g (x) is continuous and strictly monotonically decreasing w.r.t. x and w < 0, g (x)-b w is continuous and strictly monotonically increasing w.r.t. x. By changing the value of w and b, g (x)-b w can reach any finite real value. To make h concave, we need 1 f -1 (x) to be monotonically decreasing w.r.t. x ∈ (-∞, ∞).

We know that f is strictly monotonically increasing for x ∈ (0, 1), so f (0) = lim x→0 + f (x) is either a finite value or -∞.

Consider the case where f (0) is a finite value z. The domain of definition of f -1 would be (z, f (1)), and f -1 (z) = 0. Since f -1 in an expansion of f -1 , f -1 shares the same value in (z, f (1)), so f -1 (z) = 0. This will lead to lim x→z + 1 f -1 (x) = +∞. Thus 1 f -1 (x) is unable to be monotonically decreasing near x = z.

Then we consider the case where f (0) = -∞. The domain of definition of f -1 would be (-∞, f (1)], and f -1 (x) > 0 for any x ∈ (-∞, f (1)]. If f (1) = +∞, then we construct f -1 (x) = f -1 (x), so that f -1 (x) is strictly positive and monotonically increasing. As such, 1 f -1 (x) would be monotonically decreasing. If f (1) is a finite value, which means f -1 (f (1)) = 1, it is easy to define the value of f -1 (x) in x ∈ (f (1), +∞) to guarantee f -1 (x) is monotonically increasing and strictly positive. As such, 1 f -1 (x) would also be monotonically decreasing and strictly positive.

Based on above analysis, we can conclude that it is both sufficient and necessary for lim x→0 + f (x) = -∞.

A.9.2 CONCLUSION 2:

This problem is a convex optimization problem:

min Q - N i=1 P i •h(Q i ) s.t. 1 - N i=1 Q i = 0 ∀i, -Q i ≤ 0

The Lagrange function is:

L(Q, λ, ξ i ) = - N i=1 P i h(Q i ) + λ(1 - N i=1 Q i ) - N i=1 ξ i Q i , ξ ≥ 0. We then check if Q i = ĝ -1 [w • f (P i ) + b] is a solution of this problem. Since h (x) = c f -1 [ g (x)-b w ] , so ∂L ∂Q i = - c • P i f -1 [ g (Qi)-b w ] -λ -ξ i .

We show that this requirement is satisfied with

Q i = ĝ -1 [w • f (P i ) + b], λ = -c: if Q i > 0, then g (Q i ) = w • f (P i ) + b,

in which case ξ i = 0, and

∂L i = - c • P i P i -λ -ξ i = 0. If Q i = 0, then w • f (P i ) + b ≥ g (0), so 0 ≤ P i f -1 [ g (0)-b w ] ≤ 1.

We can set

ξ i = - c • P i f -1 [ g (0)-b w ] + c ≥ 0, so that ∂L ∂Q i = 0.

The above derivations are both sufficient and necessary, so

Q i = ĝ -1 [w • f (P i ) + b]

is the unique optimal solution.

A.10 PROOF OF THEOREM 5

We discuss the logarithm function case as conclusion 1 and the power function case as conclusion 2.

A.10.1 CONCLUSION 1

For sufficiency, when f (x) = a log x + d, there is f -1 (x) = exp{ x-d a }, so For necessity, we again pick any x 1 , x 2 ∈ (0, 1), and construct the function:

H(x, w, b) = h (x 1 , w, b, c) h (x 2 , w, b, c) = f -1 [ g (x2)-b w ] f -1 [ g (x1)-b w ]

.

If the decomposition can be found, this will require H(x, w, b) to exclude w in its expression, so there should be ∂H For simplicity, denote A(x, w, b) as t, then g (x)-b w = f (t), and

t • f (t) • 1 f (t) = a.

We get f (x) = d • x a by solving this differentiable equation, where a, d can be any constant.

:



Figures and Tables:

Figure 1: Illustration of the Pareto-frontier on a random toy categorical distribution with size 20. Left: The LL-SE case. Right: The CR-NRR case.

2) b is correspondent to w, i.e. b is fixed once w is fixed. If f (x) < 0 for all x ∈ [0, 1], then b is strictly monotonically increasing w.r.t. w. If f (x) > 0 for all x ∈ [0, 1], then b is strictly monotonically decreasing w.r.t. w.

The Quality-Diversity Tradeoff Control Algorithm Input: Dataset D = {x i } N i=1 , batch size M , learning rate α, model Q θ , function h . 1: Initialize Q θ with random weights. 2: Pre-train Q θ with Maximum Likelihood Estimation. (optional) 3: repeat 4:

Figure 2: Evaluation of quality and diversity on synthetic data. Vertical dashed lines show the boundary of maximum diversity. Left: The original metrics. Right: The quality discrepancy under the same diversity level compared with the Pareto-frontier.

Figure3: Evaluation of quality and diversity on MSCOCO dataset. We apply 7 hyper-parameters for each method, their corresponding values from left to right are: [1.3, 1.2, 1.1, 1.0, 0.9, 0.8, 0.7] for t in temperature-based method; [-0.85, -0.9, -0.95, -1.0, -1.1, -1.2, -1.3] for w in [1e9, 1e8, 1e7, 0,] for b in QDTC-reciprocal.

Since g (x) is strictly monotonically decreasing, so T (w, b) is monotonically non-increasing w.r.t. b. If T (w, b) > 0, there would be a term which is strictly monotonically decreasing w.r.t. b, under which condition T (w, b) is strictly monotonically decreasing w.r.t. b. Also, T (w, b) is continuous w.r.t. b since g -1 is continuous. When

Define T (w, b) = N i=1 ĝ -1 [w • f (P i ) + b(w)]as above. Since T (w, b) represents the total probability of a distribution, so there should be T (w, b) ≡ 1, thus dT dw = 0. dT dw = i∈S f (P i ) + b (w) g {g -1 [w • f (P i ) + b(w)]} , where S = {i|w • f (P i ) + b(w) < g (0)}. By the condition dT dw = 0, we get b

Figure 4: Illustration of the Pareto-frontier on a random toy categorical distribution with size 20. The diversity metrics are swaped, thus are mismatched. Left: Pair LL with NRR. Right: Pair CR with SE. Note that there is always a gap between the star and the curve, indicating that the real distribution lies on neither of the two Pareto-frontiers.

By setting h 1 (x, w) = exp{-g (x)-wd wa }dx and h 2 (w, b) = exp{ b wa }, we get h(x, w, b, c) = h (x, w, b, c)dx = h 1 (x, w) • h 2 (w, b) • c.For necessity, pick any x 1 , x 2 ∈ (0, 1), and construct a function:If the decomposition can be found, this will require H(x, w, b) to exclude b in its expression, so there should be ∂H(x, w, b) ∂b = 0.Denote A(x, w, b) = f -1 [ g (x)-b w ]. Then we have ∂H(x, w, b) ∂b = 1 A(x 2 , w, b) 2 • {-A(x 1 , w, b) wf [A(x 2 , w, b)] + A(x 2 , w, b) wf [A(x 1 , w, b)] } = 0. This lead to A(x 1 , w, b) • f [A(x 1 , w, b)] = A(x 2 , w, b) • f [A(x 2 , w, b)].This holds for any x 1 , x 2 , so both the left and right side should be a constant. Denote this constant as a, thenA(x, w, b) • f [A(x, w, b)] = a.For simplicity, denote A(x, w, b) as t, thent • f (t) = a.We get f (x) = a log x + d by solving this differentiable equation, where a, d can be any constant.A.10.2 CONCLUSION 2For sufficiency, whenf (x) = d • x a , there is f -1 (x) = ( (x) -b] -1 a • (wd) 1 a • c. By setting h 1 (x, b) = [g (x) -b] -1 a dxand h 2 (w, b) = (wd) 1 a , we get h(x, w, b, c) = h (x, w, b, c)dx = h 1 (x, b) • h 2 (w, b) • c.

Again denote A(x, w, b) = f -1 [ g (x)-b w ]. Then we have ∂H(x, w, b) ∂b = 1 A(x 2 , w, b) 2 • {-A(x 1 , w, b)[g (x 2 ) -b] w 2 f [A(x 2 , w, b)] + A(x 2 , w, b)[g (x 1 ) -b] w 2 f [A(x 1 , w, b)] } = 0.This lead toA(x 1 , w, b) • f [A(x 1 , w, b)] • w g (x 1 ) -b = A(x 2 , w, b) • f [A(x 2 , w, b)] • w g (x 2 ) -b .This holds for any x 1 , x 2 , so both the left and right side should be a constant. Denote this constant as a, thenA(x, w, b) • f [A(x, w, b)] • w g (x) -b = a.

Jingjing Xu, Xuancheng Ren, JunyangLin, and Xu Sun. Diversity-promoting  gan: A cross-entropy based generative adversarial network for diversified text generation. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 3940-3949, 2018. Lantao Yu, Weinan Zhang, Jun Wang, and Yong Yu. Seqgan: Sequence generative adversarial nets with policy gradient. In AAAI, pp. 2852-2858, 2017. Hainan Zhang, Yanyan Lan, Jiafeng Guo, Jun Xu, and Xueqi Cheng. Reinforcing coherence for sequence to sequence model in dialogue generation. In IJCAI, pp. 4567-4573, 2018a. Hainan Zhang, Yanyan Lan, Jiafeng Guo, Jun Xu, and Xueqi Cheng. Tailored sequence to sequence models to different conversation scenarios. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1479-1488, 2018b. Jiyuan Zhang, Yang Feng, Dong Wang, Yang Wang, Andrew Abel, Shiyue Zhang, and Andi Zhang. Flexible and creative chinese poetry generation using neural memory. arXiv preprint arXiv:1705.03773, 2017. Yaoming Zhu, Sidi Lu, Lei Zheng, Jiaxian Guo, Weinan Zhang, Jun Wang, and Yong Yu. Texygen: A benchmarking platform for text generation models. In The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval, pp. 1097-1100. ACM, 2018.

Table content: <table/>

Peer review (iclr2020):
Contributions: This paper studies an important problem, i.e., how to provide a theoretical framework to understand quality and diversity in text generation. To this end, the authors first provide a general definition of quality and diversity, and then study a MOP problem which tries to maximize both quality and diversity. By theoretical analysis, the authors concludes that: (i) there is truly a trade-off between quality and diversity; and (ii) quality and diversity can be combined to be a divergence metric. Further, the QDTC method is proposed for text generation. Strengths: (1) Novelty: I think this paper is novel. While most previous work on this topic are empirical, this work tries to formally define quality and diversity, and studies the Pareto-Optimality solutions. The authors also proposes a new QDTC algorithm for text generation. All these seem to be a quite novel perspective. (2) Writing: The paper is carefully written, and clearly presented. Weaknesses: (1) Experiments: My biggest concern of this paper lies in its experimental design. I understand that this paper is more like a theoretical paper, but proper experiments are still needed to justify your theory. Details are shown below. a) MSCOCO is a very simple dataset. The sentences inside are simple. I believe the use of MLE for training already provides good results. Therefore, I think only reporting results on simple MSCOCO dataset is not enough. It will be good to add experiments on other datasets as well, as what have been used in the literature. b) What are the generated text looking like? Do they show qualitative difference when compared with MLE baselines? c) Experiments are only compared with simple baselines. Also, only BLEU-3 and Disinct-3 are reported. Comparing with other related work will be appreciated, such as SeqGAN, LeakGAN, TextGAN, MaskGAN etc. d) Two variants of the QDTC algorithm are provided. In practice, which one performs better? e) Since this task is hard to evaluate by nature, it will be good to include human evaluation, and demonstrate how well your proposed quality and diversity measures align with humans* preference, and how well your proposed QDTC methods compare with baselines. (2) Clarity: a) I feel section 4 and 5.1 is a little bit challenging to follow, especially all the Lemma and Theorems. Though hard to follow, I still appreciate the authors a lot for all these derivations. Can the authors provide a concise summary on how these Theorems guide the algorithm design? b) The proposed method and theoretical analysis seem not restricted to text generation problems, and can be applied to image domain as well. Any comments on this? c) In Algorithm 1, it mentions that MLE pre-training is just an optional step. But in Section 6, it mentions that all the models are MLE pre-trained first. Can the authors show some results without MLE pre-training? Otherwise, it would be better to delete *(optional)* in Algorithm 1. Overall, I think this paper provides a novel perspective on quality and diversity for text generation. However, the experiments are not that satisfying, and could be much improved.