Unsupervised Paraphrasing by Simulated Annealing (2020)

Abstract: We propose UPSA, a novel approach that accomplishes Unsupervised Paraphrasing by Simulated Annealing. We model paraphrase generation as an optimization problem and propose a sophisticated objective function, involving semantic similarity, expression diversity, and language fluency of paraphrases. UPSA searches the sentence space towards this objective by performing a sequence of local editing. We evaluate our approach on various datasets, namely, Quora, Wikianswers, MSCOCO, and Twitter. Extensive results show that UPSA achieves the state-of-the-art performance compared with previous unsupervised methods in terms of both automatic and human evaluations. Further, our approach outperforms most existing domain-adapted supervised models, showing the generalizability of UPSA.

## introduction paraphrasing aims to restate one sentence as another with the same meaning, but different wordings. it constitutes a corner stone in many nlp tasks, such as question answering @xcite , information retrieval @xcite , and dialogue systems @xcite . however, automatically generating accurate and different-appearing paraphrases is a still challenging research problem, due to the complexity of natural language. conventional approaches @xcite model the paraphrase generation as a supervised encoding-decoding problem, inspired by machine translation systems. usually, such models require massive parallel samples for training. in machine translation, for example, the wmt 2014 english-german dataset contains 4.5m sentence pairs @xcite ). 1 code and data available at: https://github.com/ liuxg16/upsa replace what would you do when you have the power to be invisible ? what would you do when you have the power to become invisible ? what would you do if given the power to become invisible ? what would you do if given you have the power to become invisible ? sentence space score of the generated paraphrase insert delete what would you do if given you the power to become invisible ? 1 2 3 4 5 1 5 … editing steps what would you do if given you have the power to become invisible ? figure 1 : upsa generates a paraphrase by a series of editing operations (i.e., insertion, replacement, and deletion). at each step, upsa proposes a candidate modification of the sentence, which is accepted or rejected according to a certain acceptance rate (only accepted modifications are shown). although sentences are discrete, we make an analogue in the continuous real x-axis where the distance of two sentences is roughly given by the number of edits. however, the training corpora for paraphrasing are usually small. the widely-used quora dataset 2 only contains 140k pairs of paraphrases; constructing such human-written paraphrase pairs is expensive and labor-intensive. further, existing paraphrase datasets are domain-specific: the quora dataset only contains question sentences, and thus, supervised paraphrase models do not generalize well to new domains @xcite . on the other hand, researchers synthesize pseudo-paraphrase pairs by clustering news events @xcite , crawling tweets of the same topic @xcite , or translating bi-lingual datasets @xcite , but these methods typically yield noisy training sets, leading to low paraphrasing performance @xcite . as a result, unsupervised methods would largely benefit paraphrase generation as no parallel data are 2 https://www.kaggle.com/c/quora-question-pairs needed. with the help of deep learning, researchers are able to generate paraphrases by sampling from a neural network-defined probabilistic distribution, either in a continuous latent space @xcite or directly in the word space @xcite . however, the meaning preservation and expression diversity of those generated paraphrases are less "controllable" in such probabilistic sampling procedures. to this end, we propose a novel approach to unsupervised paraphrasing by simulated annealing (upsa). simulated annealing (sa) is a stochastic searching algorithm towards an objective function, which can be flexibly defined. in our work, we design a sophisticated objective function, considering semantic preservation, expression diversity, and language fluency of paraphrases. sa searches towards this objective by performing a sequence of local editing steps, namely, word replacement, insertion, deletion, and copy. for each step, upsa first proposes a potential editing, and then accepts or rejects the proposal based on sample quality. in general, a better sentence (higher scored in the objective) is always accepted, while a worse sentence is likely to be rejected, but could also be accepted (controlled by an annealing temperature) to explore the search space in a less greedy fashion. at the beginning, the temperature is usually high, and worse sentences are more likely to be accepted, pushing sa outside a local optimum. the temperature is cooled down as the optimization proceeds, making the model better settle down to some optimum. figure 1 illustrates how upsa searches an optimum in unsupervised paraphrase generation. we evaluate the effectiveness of our model on four paraphrasing datasets, namely, quora, wikianswers, mscoco, and twitter. experimental results show that upsa achieves a new state-of-theart unsupervised performance in terms of both automatic metrics and human evaluation. in summary, our contributions are as follows: ## related work in early years, paraphrasing was typically accomplished by exploiting linguistic knowledge @xcite @xcite and statistical machine translation methods @xcite . recently, deep neural networks have become a prevailing approach to text generation, where paraphrasing is often formulated as a supervised encodingdecoding problem, for example, using stacked residual lstm @xcite and the transformer model @xcite . unsupervised paraphrasing is an emerging research direction in the field of nlp. the variational autoencoder (vae) can be intuitively applied to paraphrase generation in an unsupervised fashion, as we can sample sentences from a learned latent space @xcite @xcite . but the generated sentences are less controllable and suffer from the error accumulation problem in vae's decoding phase @xcite . @xcite introduce an unsupervised model based on vector-quantized autoencoders @xcite . but their work mainly focuses on generating sentences for data augmentation instead of paraphrasing itself. @xcite use @xcite for constrained sentence generation, achieving the state-of-the-art unsupervised paraphrasing performance. the main difference between their work and ours is that upsa imposes the annealing temperature into the sampling process for better convergence to an optimum. in addition, we define our searching objective involving not only semantic similarity and language fluency, but also the expression diversity; we further propose a copy mechanism in our searching process. recently, a few studies have applied editingbased approaches to sentence generation. @xcite propose a heuristic delete-retrieve-generate component for a supervised sequence-to-sequence (seq2seq) model. @xcite learn the deletion and insertion operations for text simplification in a supervised way, where their groundtruth operations are obtained by some dynamic programming algorithm. our editing operations (insertion, deletion, and replacement) are the search actions of unsupervised simulated annealing. regarding discrete optimization/searching, a naïve approach is by hill climbing @xcite @xcite , which is in fact a greedy algorithm. in nlp, beam search (bs, @xcite ) is widely applied to sentence generation. bs maintains a k-best list in a partially greedy fashion during left-to-right (or right-to-left) decoding @xcite . by contrast, upsa is local search with distributed edits over the entire sentence. moreover, upsa is able to make use of the original sentence as an initial state of searching, whereas bs usually works in the decoder of a seq2seq model and is not applicable to unsupervised paraphrasing. ## approach in this section, we present our novel upsa framework that uses simulated annealing (sa) for unsupervised paraphrasing. in particular, we first present the general sa algorithm and then design our searching objective and searching actions (i.e., candidate sentence generator) for paraphrasing. ## conclusion and future work in this paper, we proposed a novel unsupervised approach upsa that generates paraphrases by simulated annealing. experiments on four datasets show that upsa outperforms previous state-of-theart unsupervised methods to a large extent. in the future, we plan to apply the sa framework on syntactic parse trees in hopes of generating more syntactically different sentences (motivated by our case study).