Neural-Driven Search-Based Paraphrase Generation (2021)

Abstract: We study a search-based paraphrase generation scheme where candidate paraphrases are generated by iterated transformations from the original sentence and evaluated in terms of syntax quality, semantic distance, and lexical distance. The semantic distance is derived from BERT, and the lexical quality is based on GPT2 perplexity. To solve this multi-objective search problem, we propose two algorithms: Monte-Carlo Tree Search For Paraphrase Generation (MCPG) and Pareto Tree Search (PTS). We provide an extensive set of experiments on 5 datasets with a rigorous reproduction and validation for several state-of-the-art paraphrase generation algorithms. These experiments show that, although being non explicitly supervised, our algorithms perform well against these baselines.

## introduction paraphrase generation, i.e. the transformation of a sentence into a well-formed but lexically different one while preserving its original meaning, is a fundamental task of nlp. its ability to provide diversity and coverage finds applications in several domains like question answering @xcite , machine-translation @xcite , dialog systems @xcite , privacy @xcite or adversarial learning @xcite . the formal definition of paraphrase may vary according to the targeted application and the tolerance we set along several axes, including the semantic distance from the source that we want to minimize, the quality of the syntax, and the lexical distance from the source that we want to maximize to ensure diversity. the available aligned paraphrase corpora are often biased toward specific problems like question answering or image captioning. for instance, a transformer or a seq2seq model trained on a question answering corpus will typically turn any input sentence into a question. with the lack of generic aligned datasets, it remains challenging to train generic paraphrase models in a supervised manner. on the other hand, with the availability of largescale non-supervised language models like bert and gpt2, the assessment of a given candidate paraphrase in terms of semantic distance from its source and lexical quality has become much more tractable. leveraging from these metrics, we propose to cast the paraphrase generation task as a multicriteria search problem. we use ppdb 2.0 @xcite , a large-scale database of rewriting rules derived from bilingual corpora, to potentially generate billions of 'naive' candidate paraphrases by edition from the source sentence. to sort the good candidates efficiently from the others, we experiment with two search algorithms. the first one, called monte-carlo paraphrase generation (mcpg), is a variant of the monte-carlo tree search algorithm (mcts) @xcite @xcite . the mcts algorithm is famous for its successes on mastering the -highly combinatorial -game of go @xcite . the second one is a novel search algorithm that we call pareto tree search (pts). in contrast to mcts which is a single-criterion search algorithm, we designed pts to retrieve an approximation of the whole pareto optimal set. this allows for more flexibility on paraphrase generation where the balance between semantic distance, syntax quality, and lexical distance is hard to tune a priori. another difference between mcpg and pts is that pts uses a randomized breadth-first exploration policy which proves to be more efficient on this problem. ## paraphrase generation scheme we model paraphrase generation as a sequence of editions and transformations from a source sentence into its paraphrase. in this work, we only consider local transformations, i.e. replacement of certain words or group of words by others that have the same or similar meanings, but the method we propose should work with more sophisticated transformations as well. the paraphrase database (ppdb) @xcite is a large collection of scored paraphrase rules that was automatically constructed from various bilingual corpora using a pivot alignment method @xcite . the database is divided into increasingly large and decreasingly accurate subsets foot_0 . we used the xl subset, and we removed the rules labeled as "independent". this left us with a set of 5.5 million rewriting rules. we give some examples of these rules in by iteratively applying the rules from a source sentence like the one in the number of rules that apply depends on the source sentence's size and the words it contains. for instance, on the msrparaphrase dataset (see section 6.2), sentences are quite long and the median number of ppdb-xl rules that apply is around 450. after two rewriting steps, the median number of candidates is around 10 5 , and by iterative rewriting, we quickly reach a number of paraphrase candidates that is greater than 10 8 . ## paraphrase selection criteria as it depends on the type of text we consider that may be spoken or written, casual or formal; it is not easy to define a universal semantic distance or a universal scale of well formed syntax. however, recent advances in nlp with neural networks like bert and gpt2 trained on huge corpora have led to the development of metrics that can act as good proxies for these ideal notions. for the semantic distance, a quick experiment confirms that the bert score @xcite performs well on difficult paraphrase identification tasks. the bert score is an f1-measure over an alignment of the bert contextual word embeddings of each of the sentences. to assess the sensitivity of this score, we computed the area under the roc curve (auc) on qqp and paws, two difficult paraphrase identification corpora @xcite . on qqp, we obtained 75.2% and on paws, we obtained 67.0%. the paws corpus being designed to trick paraphrase identification classifiers, 67.0% is a reasonable performance. we hence opted for the bert score between the source sentence and paraphrase candidate (denoted bert s ) as our semantic score. regarding the syntax quality, the perplexity of gpt2 @xcite is a good ranking criterion. although, as illustrated in the lexical distance is important to ensure the diversity of the produced paraphrases. it is however simple to handle. some authors use the bleu surface metric @xcite , we opted here for the normalized character-level levenshtein edition distance. the balance between these criteria is difficult to obtain. the candidate examples in this table underline the tough dilemma between maximizing the semantic similarity (safe and conservative policy) and maximizing the lexical distance (risk-prone). the third and fourth examples underline the utility of the spell-checker: some low-perplexity examples are ill-formed. on the second part of the table, we printed the sentences chosen by our two models: mcpg and pts. ## searching algorithms searching for good paraphrases in the large lattice of candidates generated by ppdb is a costly task. we propose two algorithms that share a similar structure: an outer loop explores the lattice at different depths, while an inner loop explores the candidates at each depth. both algorithms are anytime: they return the best solutions found so far when the time or space budget is depleted. ## experiments the evaluation metrics and datasets are described respectively in section 6.1 and 6.2. we paid attention to set up a rigorous validation protocol for our experiments. the reproducibility and methodology issues that we faced are discussed in section 6.3. we compare our model with state-of-theart supervised methods and with cgmh, another search-based algorithm. the technical details on these algorithms are developed in section 6.4. the results are detailed in section 6.5. ## conclusion we experimented with two search-based approaches for paraphrase generation. these approaches are pragmatic and flexible. being generic, our approaches did not overfit on small datasets. we performed extensive experiments with a rigorous evaluation methodology that we applied both on our algorithms and on the other related methods that we tried to reproduce faithfully. these experiments confirm that our two methods, namely mcpg and pts, are comparable to supervised stateof-the-art baselines despite being less tightly supervised. when compared with cgmh, another search-based and weakly-supervised method, our algorithms proved to be faster and more efficient. we plan to refine the scoring with deep reinforcement learning techniques and enrich the edition rules with more sophisticated patterns like phrase permutations. our search algorithms remain slow for a real-time deployment: the current versions are better suited as an offline model for data augmentation. the experiment of section 6.6 confirms that this application of search-based methods is a promising research avenue. a planning-thenrealization hybridization like the one proposed by @xcite and @xcite could also be considered for further works. the north american chapter of the association for computational linguistics: human language technologies, volume 1 (long and short papers), pages 1298-1308, minneapolis, minnesota. association for computational linguistics.