SparseGAN: Sparse Generative Adversarial Network for Text Generation

During adversarial training, the generator takes a random variable $z$ as input, and outputs the latent representation of generated sentence $H_{g}\in\mathbb{R}^{T\times d}$ using a multi-layer Long Short-Term Memory (LSTM) decoder Schmidhuber and Hochreiter (1997):

where $T$ denotes the sentence length and $d$ the dimensionality of hidden states.

Specifically, the random variable $z$ has a standard normal distribution $z\sim\mathcal{N}(0,1)$ that is taken as the initial value of the LSTM decoder’s hidden state. Then, at each time stamp $t$, the LSTM decoder outputs the hidden state $h_{t}\in\mathbb{R}^{d}$ given previous state $h_{t-1}\in\mathbb{R}^{d}$ and previous word $v_{t-1}\in\mathbb{R}^{d}$ predicted by the model:

where $\mathcal{H}(\cdot,\cdot)$ is the standard forward process of a LSTM decoder. Once the whole sequence is generated, the sentence representation $H_{g}$, is derived as the concatenation of all hidden states:

where $[\cdot,\cdot]$ denotes the concatenation operation of multiple vectors.

The purpose of introducing a pretrained denoising auto-encoder (DAE) Vincent et al. (2008) into the GAN-based text generation model is to force the generator to mimic the reconstructed latent representations $H_{r}\in\mathbb{R}^{T\times d}$ of real sentences instead of the conventional embedding representations Haidar et al. (2019). The DAE consists of two parts: a multi-layer bi-LSTM encoder to encode the input real sentence $r$ into intermediate representation, and a multi-layer LSTM decoder to decode the reconstructed hidden state $h^{{}^{\prime}}_{t}\in\mathbb{R}^{d}$ at each time stamp. Similar to the generator, these hidden states $h^{{}^{\prime}}_{t}$ are concatenated jointly to form the latent representation $H_{r}\in\mathbb{R}^{T\times d}$ of the real sentence $r$.

The role of the sparse encoder is to provide a sparse version of the sentence representation including the generated sentence’s representation $H_{g}$ output by generator and the real sentence’s representation $H_{r}$ output by DAE:

where $S_{g},S_{r}\in\mathbb{R}^{T\times d}$, and $\mathcal{F}_{sparse}(\cdot)$ denotes the sparse representation learning algorithm (See Section 4).

A commonly used discriminator for text generation is a Convolutional neural network (CNN) classifier which employs a convolutional layer with multiple filters of different sizes to capture relations of various word lengths, followed by a fully-connected layer. The CNN-based discriminator takes the sparse representation $S\in\mathbb{R}^{k\times b}$ output by the sparse encoder as input , and output a score to determine whether the sentences are natural or generated ones. Formally, the scoring function is defined as follows:

where $*$ denotes the convolution operator; $f(\cdot)$ denotes a non-linear function and $W,b,\omega$ are model parameters.

Inspired by Wasserstein GAN (WGAN) Gulrajani et al. (2017), the game between the generator $G_{\theta}$ and the discriminator $D_{\phi}$ is the minimax objective:

where $\mathbb{P}_{r}$ is the data distribution, $\mathbb{P}_{g}$ is the distribution of the generator’s input and $S_{g},S_{r}$ are defined in Equation 4. The gradient penalty term Gulrajani et al. (2017) in the objective function enforces the discriminator to be a 1-Lipschitz function, where $\mathbb{P}_{\hat{x}}$ is the distribution sampling uniformly along straight lines between pairs of points sampled from the $\mathbb{P}_{r}$ and $\mathbb{P}_{g}$, while $S_{\hat{x}}$ is the sparse representation of $\hat{x}$ output by the sparse encoder. The importance of this gradient penalty term is controlled by a hyperparameter $\lambda$.

Sparse representation learning is to search for the most compact representation of a vector via the linear combination of elements in an overcomplete dictionary Mallat and Zhang (1993). Given an overcomplete dictionary $D\in\mathbb{R}^{N\times d}$ with elements in its rows, and a target vector $y\in\mathbb{R}^{d}$, the problem of sparse representation is to find the sparsest coefficient vector of the linear combination $x^{*}\in\mathbb{R}^{N}$ satisfying $y=D^{T}x^{*}$:

where $||x||_{0}$ is $\ell_{0}$-norm of $x$, namely the number of non-zero coordinates of $x$. However, the equality constraint is too strict to be satisfied, and it can be relaxed by minimize the Euclidean distance between $y$ and $D^{T}x$. The original problem is then translated into the following problem:

The objective is to reduce the reconstruction error while using the elements as few as possible. Once the problem solved, $D^{T}x^{*}$ can be used as the final sparse representation of $y$.

Inspired by the sparse representation principle, the sparse encoder takes the vocabulary embedding matrix $E\in\mathbb{R}^{N\times d}$ as the overcomplete dictionary and approximates $h_{t}$ as the sparse linear combination of word embeddings in $E$, which can be derived as:

where $c$ is the coefficient vector of the linear combination. The embedding matrix $E\in\mathbb{R}^{N\times d}$ can be used as the overcomplete dictionary since in text generation tasks, the embedding matrix is always overcomplete with tens of thousands of words, and the condition of $N>>d$ is satisfied in most cases.

As shown in Figure 2, the constructed sparse representation confines the inputs of the discriminators to the feature space spanned by the word embeddings. Since the generator and DAE share the same embedding matrix, it will be easier for the discriminator to minimize distance between distributions of real sentences and generated ones. To solve the above optimization problem, we apply the Matching Pursuit (MP) algorithm Mallat and Zhang (1993).

The MP algorithm calculates the sparse representation $s_{t}\in\mathbb{R}^{d}$ of $h_{t}$ in an iterative way. As illustrated in Algorithm 1, there is a residual vector $r_{t}\in\mathbb{R}^{d}$ to record the remaining portion of $h_{t}$ that has not been expressed. At a certain iteration $l$, current residue $r_{t}$ is used to search the nearest word embedding $e_{l}$ ($l$ represents the $l$-th iteration) from embedding matrix $E$ by comparing the inner product between $r_{t}$ and all word embeddings in embedding matrix:

where $\langle\cdot,\cdot\rangle$ is the inner product operation of two vectors. The concatenation of $e_{l}$ and previous selected embeddings forms the basis vector matrix $M\in\mathbb{R}^{k\times d}$, and the linear combination over the row vectors of $M$ is used to approximate $h_{t}$. The linear combination coefficient vector $c\in\mathbb{R}^{k}$ is determined by solving the least square problem:

where $M^{+}\in\mathbb{R}^{k\times d}$ is the pseudo-inverse of $M^{T},M^{+}=(MM^{T})^{-1}M$. After $c^{*}$ is calculated, the sparse representation $s_{t}$ of $h_{t}$ can be defined as:

where $s_{t}$ is the closest to $h_{t}$ until the current iteration. And $r_{t}$, the residual vector between $h_{t},s_{t}$ can be defined as:

The process described above will be repeated for $L$ times, where $L$ is a hyperparameter to control the degree of how well $h_{t}$ is represented approximately. After $L$ iterations, the final sparse representation $s_{t}\in\mathbb{R}^{d}$ is defined in Equation 12. For other hidden states $h_{1},h_{2},...,h_{T}\in H$, the same calculation process is performed to obtain their corresponding sparse representations $s_{1},s_{2},...,s_{T}\in\mathbb{R}^{b}$. These sparse representation are then concatenated together to form the final output $S\in\mathbb{R}^{k\times d}$ of the sparse encoder $S=[s_{1},s_{2},...,s_{T}]$, which is fed into the CNN-based discriminator to determine the score of the input sentence.

The sparse representation learning algorithm is differentiable. The gradient of $s_{t}$ can be passed to $c^{*}$ through Equation 12 and then be passed to $h_{t}$ through Equation 11. As a result, SparseGAN is trainable and differentiable via using sstandard back-propagation.

We conduct experiments on two different text generation datasets of COCO Image Caption Chen et al. (2015) and EMNLP2017 WMT News Guo et al. (2018) to demonstrate the effectiveness of SparseGAN. The COCO Image Caption dataset is preprocessed basically following Zhu et al Zhu et al. (2018), which contains $4,682$ distinct words, $10,000$ sentences as train set and other $10,000$ sentences as test set, where all sentences are $37$ or less in length. The EMNLP2017 WMT News dataset contains $5,712$ distinct words with maximum sentence length $51$. The training set and testing set consists of $278,586$ and $10,000$ sentences respectively.

The generator is a two layer LSTM with 300 hidden units and the discriminator is a multi-layer 1-D convolution neural network with 300 feature maps and filter size set to 5. The denoising auto-encoder (DAE) is a two layer LSTM with 300 hidden cells for both the encoder and the decoder. For training DAE, we preprocess the input data following Freitag and Roy Freitag and Roy (2018), where $50\%$ of words are randomly removed and all words are shuffled while keeping all word pairs together that occur in original sentence. A variational auto-encoer (VAE) Kingma and Welling (2013) is used to initialize the generator, which is trained with KL cost annealing and word dropout during decoding following Bowman et al Bowman et al. (2015). Inspired by WGAN-GP Gulrajani et al. (2017), the hyperparameter $\lambda$ of the gradient penalty term in Equation 6 is set to 10, and 5 gradient descent steps on the discriminator is performed for every step on the generator. All models are optimized by Adam with $\beta_{1}=0.9$, $\beta_{2}=0.999$ and $eps=10^{-8}$. Learning rate is set to $10^{-3}$ for pretraining and $10^{-4}$ for adversarial training. The 300-dimensional Glove word embeddings released by Pennington et al Pennington et al. (2014) are used to initialize word embedding matrix. The batch size is set to $64$, the maximum of sequence length to $40$, the maximum of iterations for adversarial training to $20,000$, and the number of iterations $L$ for sparse representation learning to $10$.

We use two metrics below to evaluate our models, comparing different models.

BLEU Papineni et al. (2002) This metric is used to measure quality of generated sentences. To calculate BLEU-N scores, we generate $10,000$ sentences as candidate texts and use the entire test set as reference texts. The higher the BLEU score is, the higher quality the generated sentences is.

Self-BLEU Zhu et al. (2018) This metric is used to measure diversity of generated sentences. Using one generated sentence as candidate text and others as reference texts, the BLEU is calculated for every generated sentence, and the average BLEU score of $10,000$ generated sentences is defined as the self-BLEU. The higher the self-BLEU score is, the less diversity the generated sentences is.

We compared the SparseGAN with several recent representative models. For RL-based text generative models, we choose to compare SeqGAN Yu et al. (2017), MaliGAN Che et al. (2017), RankGAN Lin et al. (2017) and LeakGAN Guo et al. (2018). We also compared TextGAN Zhang et al. (2017) and LATEXTGAN Haidar et al. (2019). TextGAN adopts the weighted sum over the embeddings matrix as the continuous approximation, while LATEXTGAN uses the multinomial distribution by the generator for adversarial training.

Top-$k$ method, which has not been applied to GAN-based text generation model, approximates the sampling action via the linear combination of word embeddings with $k$ highest probabilities and use the re-normalized probabilities as the linear combination coefficients. Here we denote this model as TopKGAN-S (static TopKGAN). TopKGAN-D (dynamic TopKGAN), a variant of TopKGAN-S, chooses words dynamically via comparing the logit of each word with a threshold $\delta$. The logit of each word is defined as the inner product between hidden state $h_{t}$ and word embedding $e_{k}$. For TopKGAN-S, the number of words to be chosen $K$ is set to 10, while for TopKGAN-D, the threshold $\delta$ is set to 0 here. Two variants of TopKGAN are implemented with the same setting as SparseGAN.

The BLEU scores and Self-BLEU scores on COCO Image Caption dataset and EMNLP2017 WMT News dataset are shown in Table 1 and Table 2, correspondingly. The proposed SparseGAN achieves the highest BLEU scores on both datasets, which means the generated sentences by SparseGAN is more natural and fluent. MLE-based model has the lowest Self-BLEU scores. TopKGAN-S and TopKGAN-D have similar performance on both COCO Image Caption dataset and EMNLP2017 WMT News dataset. These two models behave better than several competitive models in terms of both BLEU sores and Self-BLEU scores, such as RankGAN, LeakGAN, TextGAN and LATEXTGAN on COCO Image Caption dataset.

High BLEU scores of SparseGAN may benefits from the way to treat the embedding matrix. Since SparseGAN chooses word embedding via the residual vector $r_{t}$, which is initialized as $h_{t}$, the word with the highest probability will be chosen at the first iteration. This word is usually a common word in vocabulary. After several iterations, when $h_{t}$ has been well approximated by the sparse representation, uncommon words tend to be chosen. Both common and uncommon words are adjusted in SparseGAN, thus the embedding matrix obtains sufficient training. However, RL-based models only choose one word to adjust at each time stamp; TopKGAN only choose words with high probabilities, which is usually the common words, to adjust; continuous approximation methods choose all words to adjust but contain much noise in their approximation, resulting in imprecise gradient values.

Low Self-BELU scores of MLE-based model reflects that the generated sentences via MLE-based training are more diverse than all GAN-based models. It implies that GAN-based models tend to suffer from mode collapse and generate safe but similar sentences. However, the generated sentences of MLE-based model are less natural than GAN-based models, especially on EMNLP2017 WMT dataset which has longer sentences than the other dataset.

Table 3 shows the sentences generated by SpargeGAN that is trained with COCO Image Caption and EMNLP2017 WMT News datasets respectively. Those examples illustrate that SparseGAN is capable of generating meaningful and natural sentences with a coherent structure.